Скачать .docx  

Реферат: RSA алгоритмів кодування з відкритим ключем

Реферат на тему:

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 = me modn ;

г) надіслати шифротекст c до А .

2. Дешифрування. Для отримання повідомлення m із шифротксту c А робить наступні дії:

а) використовуючи секретний ключ d , обчислити m = cd modn .

Теорема. Шифр c декодується правильно.

Оскільки p та q – прості числа, то j (p * q ) = j (n ) = (p -1) * (q -1), де j – функція Ейлера. З умови вибору ключа d маємо: d * e modj(n ) = 1, або d * e = j (n ) * k + 1 для деякого натурального k.

cd modn = (m e )d modn = m ( e * d ) modn = m ^ ( j ( n ) * k + 1) modn = (m j ( n ) modn ) k * m = 1 k * m = m , оскільки за теоремою Ейлера m j (n ) mod n = 1.

Означення. RSA системою називають функцію RSAn , e (x ) = xe modn та обернену їй RSA-1 n , e (y ) = yd modn , де 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. Кодування: 47 mod 323 = 234.Декодування: 234247 mod 323 = 4.

2. m = 123. Кодування: 1237 mod 323 = 251.Декодування: 251247 mod 323 = 123.

Циклічна атака

За відомим шифром c (c = me modn ) злодій, маючи відкритий ключ e та n , бажає знайти повідомлення m .Він починає будувати послідовність чисел

c , ce , , , …

Оскільки обчислення відбуваються в групі Zn *, то елемпнти послідовності знаходяться в межах від 0 до n - 1. Отже існує таке натуральне k , що с = . Враховуючи що c = me modn , маємо: me = або m = .

Таким чином для знаходження повідомлення m за його шифром c необхідно побудувати послідовність c , ce , , , …, , = c , і взяти її передостаннє число.

Приклад

Розв’язати рівняння: m 7 mod 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 ’ = cd modn , злодій Z обчислює m = m ’ / b і отримує шукане m . Шифром m дійсно є c , оскільки me = me / be = cde / be = c ’ / be = c .

Така атака можлива, оскільки А не знає повної інформації про шифр c ’, який дає йому злодій Z .

Приклад. Нехай А має RSAсистему: p =17, q = 19, n = 323, e = 7, d = 247.

Злодій Z перехопив шифр c = 234 і хоче знайти таке m , що m 7 = 234 mod 323.

1. Z обирає b = 10 ÎZ323 * ,обчислює c ’ = 107 * 234 mod 323 = 14 і просить А дешифрувати його.

2. A обчислює m ’ = 14247 mod 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 = d mod (p - 1), dq = d mod (q - 1)

2. Обчислити mp = modp , mq = modq .

3. Розв’язати систему лінійних порівнянь

Розв’язком системи буде декодоване повідомлення: m = cd (modn ).

Приклад

Нехай RSA система має вигляд:p = 17, q = 19, n = 323, e = 7, d = 247.

Для розв’язку рівняння m 7 mod 323 = 251(c = 251) обчислимо 251247 mod 323:

1. dp = 247mod 16 = 7, dq = 247mod 18 = 13;

2., mp = 2517 mod 17 = 4, mq = 25113 mod 19 = 9;

3. Розв’яжемо систему лінійних порівнянь

Розв’язуючи її методом Гауса, отримаємо m = 123.

Отже 1237 mod 323 = 251.

Мала декодуюча експонента

Приклад . Виберемо аовідомлення m = 13 та зашифруємо його трьома різними RSAсистемами.

1. p = 5, q = 17, n = 85, e = 3, d = 57,

m 3 mod 85 = 72;

2. p = 11, q = 23, n = 253, e = 3, d = 169,

m 3 mod 253 = 173;

3. p = 17, q = 23, n = 391, e = 3, d = 261,

m 3 mod 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.