Вступ в криптоаналіз RSA криптосистем, страница 4

13. Визначте складність криптоаналізу RSA методом - Поларда, якщо довжина модуля дорівнює 1024 або 2048 бітів.

14. Визначте складність криптоаналізу дискретного логарифму методом - Поларда, якщо довжина модуля дорівнює 1024 або 2048 бітів.

15. Дайте характеристику алгоритму Евкліда знаходження НСД.

16. Порівняйте складність розв’язку задач факторизації та розв’язку дискретного логарифму.

Додаток Б   1.14 Криптоаналiз RSA методом квадратичного решета. Приклади розв’язку задач та задачі для самостійного розв’язання

1.14.1 Приклади розв'язку задач

Задача 1.

Факторизувати модуль N, використовуючи метод квадратичного решета, якщо N = 377.

Розв’язок задачі:

Знаходимо :

Таблиця 1.11 – Розрахунки

x	Z =  x+	Z 2  mod N	2	3	5	7	Залишок
1	20	23	-	-	-	-	23
2	21	64	6	-	-	-	+
3	22	107	-	-	-	-	107
4	23	152	3	-	-	-	19
5	24	199	-	-	-	-	199
6	25	248	3	-	-	-	31
7	26	299	-	-	-	-	299
8	27	352	5	-	-	-	11
9	28	30	1	1	1	-	+
10	29	87	-	1	-	-	29
11	30	146	1	-	-	-	73
12	31	207	-	2	-	-	23
13	32	270	1	3	1	-	+
14	33	335	-	-	1	-	67
15	34	25	-	-	2	-	+

У першому стовпчику задаємо значення x, у другому Z = х+19, у третьому - Z² modN. Далі значення Z² modN розкладається на співмножники бази Р¢, точніше робиться спроба, - це числа 2, 3, 5, 7, добуток цих чисел р¢ = 210. Із таблиці бачимо, що число 23 не розкладається на співмножники бази. Число 64 розкладається на співмножники – 2 (2⁶ = 64).

Якщо Z² modN повністю розкладається на співмножник або співмножники р¢, то таку спробу вважаємо позитивною та позначаємо рядок знаком “+”. Для успішної факторизації необхідно не менше k, де k – число співмножників бази розкладу, позитивних експериментів. Потім, перемножуючи значення
стовпців Z ²  modN та результати розкладу за базою, необхідно скласти рівняння вигляду

.

Наприклад, другий рядок (тільки одна) дає такий результат

або

.

Тоді x = 21, y = 8; x-y = 21-8 = 13.

Далі НCД (x-y, N) = НCД (13, 377) = 29.

Тому, наприклад, P = 13, Q = 29 і N = 13*29 = 377.

Аналогічно можна взяти 15 рядок. Тоді маємо

,

,

,

.

Задача 2.

Нехай відомо, що в RSA cистемі використовується відкритий ключ
D_k = 107, а модуль перетворення N = 209. Необхідно знайти особистий (секретний) ключ E_k та оцінити складність криптоаналізу.

Розв’язок задач здійснимо в декілька етапів. На першому факторизуємо модуль N, використовуючи метод квадратичного решета. Потім, розв’язавши ключове порівняння, знайдемо особистий ключ D_k. На завершення оцінимо складність криптоаналізу, основний етап якого складає факторизація.