1.13 Криптоаналіз rsa та дискретних логарифмiв методом -Поларда. Приклади розв’язку задач та задачі для самостійного розв’язання
1.13.1 Приклади розв'язку задач
Задача 1.
Факторизувати модуль N, використавши метод - Поларда.
Дано,
що N
= 221, а
= 11,
=
127, C
= 1.
Розв’язок задачі:
,
x1 = 118; НСД(127-118, 221) = (9, 221)=1, тобто спільних дільників немає.
,
x2 = 19; НСД (118-19,221) = НСД (99,221) = 1.
Таким чином НСД (х1 – х2, N) знову не має сильного дільника.
.
Розрахуємо послідовно хі поки, НСД (х1 – х2, N) різнитиметься від 1 або N.
x3 = 210; НСД (191,221) = 1,
,
x4 = 7 ; НСД (203 , 221) =1,
,
x5 = 78 ; НСД (71,221) = 1,
,
x6 = 91. При х6 маємо НСД (х6 – х5, N) = НСД (91 – 78, 221) = НСД (13, 221) = 13.
Таким чином один із співмножників модуля N є 13, наприклад, P=13. Тоді Q=N/P=221/13=17. Перевіряємо правильність розв’язку, знайшовши P*Q = 221.
Задача 2.
Факторизувати число N = 209, якщо xi = x2 + 1(mod N).
прийнявши,
що
.
Розв’язок задачі:
x1 = (172 + 1)mod 209 = 81,
x2 = (812 + 1)mod 209 = 83,
НОД (2, 209) = 1 розв’язку немає.
x3 = (832 + 1)mod 209 = 202,
x4 = (2022 + 1)mod 209 = 50,
x3 - x4 = |202-50| = 152.
НОД (152, 209) = 19.
Таким чином один із співмножників, наприклад, P=19, тоді Q=209/19=11.
Задача 3.
Розв’язати порівняння 15x º 9(mod 23) методом -Поларда. Нехай с = 6.
Розв’язок задачі:
Використовуючи (1.171) розрахунки зведемо в таблицю. Знайдемо
Розрахунки зведемо в табл. 1.10.
Таблиця 1.10 – Розрахунки
Цикл |
Довжина |
xi |
u |
V |
xi |
t |
v |
1 |
2 |
Х0 = 9 |
0 |
1 |
X1 = 20 |
1 |
1 |
|
|
X1 = 20 |
1 |
1 |
X2 = 1 |
2 |
1 |
|
|
X2 = 1 |
2 |
1 |
X3 = 9 |
2 |
2 |
|
|
X3 = 9 |
2 |
2 |
X4 = 20 |
3 |
2 |
|
|
|
|
|
X5 = 1 |
4 |
2 |
|
|
|
|
|
X6 = 9 |
4 |
3 |
Таким чином при u=2,v=2, і u=4,v=3 отримуємо одне і теж значення x6 = x3 = 9.
Підставивши значення в (v = 2, w = 3, t = 4, u = 2) отримаємо
Задача 4.
Розв’язати рівняня методом -Поларда 20 º7x (mod 23).
c = 10, r0 = b = 20, a = 7.
Розв’язок задачі:
Таким чином r8 = r0, причому r8 можна подати як
1.13.2 Задачi для самостiйного розв'язання
1. Розв'яжіть рівняння 15x º n (mod 23) методом - Поларда. Перевірте правильність розв'язку порівняння.
n = (k+2)mod 23, де k-номер по журналу, якщо n=0, то n:=21.
2.
Факторизуйте модуль
RSA
перетворення методом
- Поларда, якщо
-
k
1
2
3
4
5
6
7
8
9
10
11
N
391
221
299
209
247
133
217
253
161
91
437
i = k (mod 12), k - номер по журналу.
1.13.3 Контрольнi запитання та завдання
1. Сутність -метода Поларда?
2. Чому метод Поларда називають -методом?
3. Яка ознака того, що розв’язок знайдено?
4. Що таке "факторизацiя модуля"?
5. Які вимоги до модуля N?
6. Як розраховується значення функції Ойлера для RSA перетворення?
7. Дайте оцінку складності RSA криптоаналізу методом - Поларда?
8. Які прості числа називаються “сильними”?
9. В чому полягає криптоаналіз дискретних логарифмів методом -Поларда?
10. Як обирають коефіцієнти с при розв’язку дискретного логарифмічного порівняння?
11. Як знайти НСД заданих двох чисел?
12. Які обмеження притаманні методу - Поларда при факторизації та розв’язку дискретних логарифмічних рівнянь?
13. Визначте складність криптоаналізу RSA методом - Поларда, якщо довжина модуля дорівнює 1024 або 2048 бітів.
14. Визначте складність криптоаналізу дискретного логарифму методом - Поларда, якщо довжина модуля дорівнює 1024 або 2048 бітів.
15. Дайте характеристику алгоритму Евкліда знаходження НСД.
16. Порівняйте складність розв’язку задач факторизації та розв’язку дискретного логарифму.