Реферат на тему:
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
’ = c
’d
modn
, злодій 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
, що 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.
|
