RSA – алгоритмів кодування з відкритим ключем, Детальна інформація

\x0326\x3D6A

\x1619\xC568\xC44F\x4300\x1C4A\x6D00H\x6E04H\x7304\x2248\x7504\x0108\x0326\x5C6A

= c, і взяти її передостаннє число.

Приклад

Розв’язати рівняння: m7 mod 323 = 251.

e = 7, n = 323, c = 251.



0 251

1 310

2 47

3 4

4 234

5 123

6 251



= 123.

Атака методом осліплення

Припустимо, А має секретний ключ RSA системи, а Z – злодій, який перехопив шифр c і хоче декодувати його. При цьому А відмовляє видати Z вихідний текст m. Тоді Z обирає деяке значення b \xF0CE Zn*, обчислює c’ = be * c і просить А дешифрувати його. А погоджується дешифрувати c’ своїм секретним ключем d, оскільки зміст повідомлення c’ йому ні про що не говорить і виглядає невинним. Отримавши m’ = c’d mod n, злодій 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 \xF0CE Z323*, обчислює c’ = 107 * 234 mod 323 = 14 і просить А дешифрувати його.

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 (mod n).