Реферат на тему:
RSA – алгоритмів кодування з відкритим ключем
Перший алгоритм кодування з відкритим ключем (Public Key Encryption, далі PKE) було запропоновано Вітфілдом Діффі та Мартіном Хелманом у Стендфордському університеті. Вони, а також незалежно від них Ральф Меркл, розробили основні його поняття у 1976 році. Перевага PKE полягає у відсутності потреби секретної передачи ключа.
PKE базується на нерозв’язності проблеми розкладу натурального числа на прості множники.
RSA схему шифрування було запропоновано у 1978 році та названо іменами трьох його винахідників: Роном Рівестом (Ron Rivest), Аді Шаміром (Adi Shamir) та Леонардом Адлеманом (Leonard Adleman). RSAналежить до класу алгоритмів кодування з відкритим ключем.
У 80-х роках криптосистема переважно використовувалася для забезпечення секретності та достовірності цифрових даних. Усучасному світі RSAвикористовується в web – серверах та браузерах для зберігання таємності даних що передаються по мережі, .
Схема RSA базується на обчисленні виразів зі степенями. Відкритий текст шифрується блоками, довжина кожного із яких менша за деяке число n.
Алгоритм генерації ключа
A повинен згенерувати відкритий та секретний ключі:
1. Згенерувати два великих простих числа pта q приблизно однакової довжини;
2. Обчислити n = p * q, fi = (p – 1) * (q – 1);
3. Вибрати натуральнеe, 1 < e < fi, взаємно просте з fi;
4. Використовуючи розширений алгоритм Евкліда, розв’язати рівняння
d * eº 1 (mod fi).
Відкритий ключ: (n, e). Секретний ключ: d.
Схема шифрування RSA
B шифрує повідомлення m та надсилає A.
1. Шифрування. В робить наступні дії:
а) отримати відкритий ключ (n, e)від А;
б) представити повідомлення у вигляді натурального числа m з проміжку [1..n];
в) обчислити c = memodn;
г) надіслати шифротекст cдо А.
2. Дешифрування. Для отримання повідомлення m із шифротксту cА робить наступні дії:
а) використовуючи секретний ключ d, обчислити m = cdmodn.
Теорема. Шифр c декодується правильно.
Оскільки pта q – прості числа, то j (p * q) = j (n) = (p-1) * (q-1), де j – функція Ейлера. З умови вибору ключа dмаємо: d * emodj(n) = 1, або d * e = j (n) * k + 1 для деякого натурального k.
cdmodn = (me)dmodn = m(e*d)modn = m ^ (j (n) * k + 1)modn = (mj (n) modn) k * m= 1 k * m = m, оскільки за теоремою Ейлера mj (n) mod n = 1.
Означення.RSAсистемою називають функцію RSAn,e(x) = xemodnта обернену їй RSA-1n,e(y) = ydmodn, де e– кодуюча, а d– декодуюча експонента, x, yÎ Zn*.
Приклад
1. Оберемо два простих числа: p = 17, q = 19;
2. Обчислимо n = 17 * 19 = 323, fi = (p - 1) * (q - 1) = 16 * 18 = 288;
3. Оберемоe = 7 (НСД(e, fi) = 1) та розв’яжемо рівняння 7 * dº1 (mod 288), звідки d = 247.
Побудовано RSAсистему: p = 17, q = 19, n = 323, e = 7, d = 247.
Відкритий ключ: n = 323, e = 7, секретний ключ: d = 247.
1. m = 4. Кодування: 47mod 323 = 234.Декодування: 234247mod 323 = 4.
2. m = 123. Кодування: 1237mod 323 = 251.Декодування: 251247mod 323 = 123.
За відомим шифром c (c = memodn) злодій, маючи відкритий ключ eта n, бажає знайти повідомлення m.Він починає будувати послідовність чисел
c, ce, , , …
Оскільки обчислення відбуваються в групі Zn*, то елемпнти послідовності знаходяться в межах від 0 до n - 1. Отже існує таке натуральне k, що с = . Враховуючи що c = memodn, маємо: me = або m = .
Таким чином для знаходження повідомлення m за його шифром c необхідно побудувати послідовність c, ce, , , …, , = c, і взяти її передостаннє число.
Розв’язати рівняння: m7mod 323 = 251.
e = 7, n = 323, c = 251.
| k | |
| 0 | 251 |
| 1 | 310 |
| 2 | 47 |
| 3 | 4 |
| 4 | 234 |
| 5 | 123 |
| 6 | 251 |
З таблиці маємо:c = = 251. Оскількиme = , то m = = 123.
Припустимо, А має секретний ключ RSA системи, а Z – злодій, який перехопив шифр c і хоче декодувати його. При цьому А відмовляє видати Z вихідний текст m. Тоді Z обирає деяке значення bÎZn*, обчислює c’ = be * c і просить А дешифрувати його. А погоджується дешифрувати c’ своїм секретним ключем d, оскільки зміст повідомлення c’ йому ні про що не говорить і виглядає невинним. Отримавши m’ = c’dmodn, злодій Zобчислює m = m’ / b і отримує шукане m. Шифром m дійсно є c, оскільки me = m’e/ be = c’de / be = c’ / be = c.
Така атака можлива, оскільки А не знає повної інформації про шифр c’, який дає йому злодій Z.
Приклад. Нехай А має RSAсистему: p =17, q = 19, n = 323, e = 7, d = 247.
Злодій Z перехопив шифр c = 234 і хоче знайти таке m, що m7 = 234 mod 323.
1. Z обирає b = 10 ÎZ323*,обчислює c’ = 107 * 234 mod 323 = 14 і просить А дешифрувати його.
2. A обчислює m’ = 14247mod 323 = 40 і передає його Z.
3. Z знаходить шукане повідомлення обчислюючи
m = 40 / 10 = 40 * 10-1 = 40 * 97 = 4 mod 323.
Таким чином 47 = 234 mod 323.
Прискорення дешифрування
За допомогою китайської теореми про лишки можна прискорити процес дешифрування, знаючи секретні прості числа pта q.
Алгоритм
Дешифрування. А має декодуючу експоненту d, а також pта q (n = p * q).А отримує від В шифр с та повинен виконати операцію cd (modn).
1. Обчислити dp = dmod (p - 1), dq = dmod (q - 1)
2. Обчислити mp = modp, mq = modq.
3. Розв’язати систему лінійних порівнянь
Розв’язком системи буде декодоване повідомлення: m = cd (modn).
Нехай RSA система має вигляд:p = 17, q = 19, n = 323, e = 7, d = 247.
Для розв’язку рівняння m7mod 323 = 251(c = 251) обчислимо 251247mod 323:
1. dp = 247mod 16 = 7, dq = 247mod 18 = 13;
2., mp = 2517 mod 17 = 4, mq = 25113 mod 19 = 9;
3. Розв’яжемо систему лінійних порівнянь
Розв’язуючи її методом Гауса, отримаємо m = 123.
Отже 1237mod 323 = 251.
Приклад. Виберемо аовідомлення m = 13 та зашифруємо його трьома різними RSAсистемами.
1. p = 5, q = 17, n = 85, e = 3, d = 57,
m3 mod 85 = 72;
2. p = 11, q = 23, n = 253, e = 3, d = 169,
m3 mod 253 = 173;
3. p = 17, q = 23, n = 391, e = 3, d = 261,
m3mod 391 = 242;
Для знаходження повідомлення m за відкритими ключами (ni, ei ) та перехопленими шифрамиci складемо систему порівнянь
Одним із її розв’язків буде x = 2197 = 133. Тобто шуканим повідомленням буде m = 13.
Означення. Повідомлення m називається неприхованим, якщо його шифр дорівнює самому повідомленню, тобто me = m (modn).
Наприклад, повідомлення m = 0 та m = 1 завжди є неприхованимидля довільних значень eта m.
Твердження. Кількість неприхованих повідомлень в RSAсистемі дорівнює
(1 + НСД(e - 1, p - 1)) * (1 + НСД(e - 1,q - 1))
Оскільки значення e- 1, p- 1 та q- 1 – парні, то НСД(e- 1, p- 1) ³2, НСД(e- 1,q- 1)³2, а отже кількість неприхованих повідомлень завжди не менша за 9.