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² mod N. Далі значення Z² mod N розкладається на співмножники бази Р¢, точніше робиться спроба, - це числа 2, 3, 5, 7, добуток цих чисел р¢ = 210. Із таблиці бачимо, що число 23 не розкладається на співмножники бази. Число 64 розкладається на співмножники – 2 (2⁶ = 64).

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

.

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

або

.

Тоді 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. На завершення оцінимо складність криптоаналізу, основний етап якого складає факторизація.

Розрахунки зведемо в таблицю 1.12, при цьому знаходитимемо НСД, використовуючи алгоритм Евкліда. Сутність алгоритму Евкліда:

Нехай

a₁ = x-y; a₂ = N.

1. if a₁ =a₂ then НСД:= a₂;

2. a₁ := max(a₁, a₂),

a₂ := min(a₁, a₂).

3) a₁/a₂ ®a₃ =r;

4) if a₃ = 0 then НСД :=a₂, END;

5) a₁:= a₂; a₁:= a₃; goto 3).

Аналогічно, як і в задачі 1, для факторизації використовується квадратичне решето.

При цьому

.

p = 2*3*5*7* = 210.

Значить N»P.

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

N/n	x	Z =ë  x+ û	Z 2  mod N	2	3	5	7	Залишок
1	1	15	16	4	-	-	-	+
2	2	16	47	-	-	-	-	-47
3	3	17	80	4		1	-	+
4	4	18	115	-	-	1	-	-23
5	5	19	152	3	-	-	-	-19
6	6	20	191	-	-	-	-	-
7	7	21	23	-	-	-	-	-
8	8	22	66	1	1	-	-	-11
9	9	23	111	-	1	-	-	-37
10	10	24	158	1	-	-	-	-79
11	11	25	207	-	2	-	-	23-
12	12	26	47	-	-		2	+
13	13	27	102	1	1	-	-	17-
14	14	28	157	-	-	-	-	-
15	15	29	5	-	-	1	-	+
16	16	30	64	6	-	-	-	+
17	17	31	125	-	-	3	-	+
18	18	32	188	2	-	-	-	47

У таблиці 1.13 наведені позитивні рядки

Таблиця 1.13 – Позитивні рядки

x	Z =ë  x+ û	Z 2  mod N	2	3	5	7	Залишок
1	15	16	4	-	-	-	+
3	17	80	4		1	-	+
12	26	47	-	-		2	+
15	29	5	-	-	1	-	+
16	30	64	6	-	-	-	+
17	31	125	-	-	3	-	+

Замінимо в таблиці всі парні числа 0, а непарні 1. У матриці розміром n x(n+1) із нулів та одиниць завжди можна обрати множину рядків, таку, що у всіх стовпцях буде парне число одиниць, а отже є сукупність рядків у яких

.

Наприклад, розв’язок дають рядки {3,15}, {3, 17}, {15, 17}, {1}, {12}, {16}.

1. 15² º 2⁴(mod 209); 15² º 4²(mod 209)

x=15, y=4.

НСД(15-4, 209) = 11,

P=11; Q=N:P=209:11=19.

2. {3,15}

17² 29² º 5 ²4²(mod 209); (17*29)² º (20)²(mod 209).

x=75, y=20.

НСД(75-20, 209).

3. {15, 17}

29² º 5¹(mod 209)

31² º 5³(mod 209)

(3129)² º 5 ⁴(mod 209); (2931)² º 25 ²(mod 209);

x=63; y=25; (x-y, 209) НСД=(38, 209)=(219, 209) = 19

Використовуючи алгоритм Евкліда маємо:

a₁ = 209; a₂ = 38

P=209:19=11;Q=19

209:38=5; r=19

a₁ = 38; a₂ = 19

39:19=2; r=0;

НСД (a₁, a₂)=a₂ = 19

Тепер розв’яжемо ключове порівняння

D_k = 103; N=209; j(N)= 10*18 = 180

j(N) (-k)+D_kE_k = 1; 180(-k)+103E_k = 1

180x+103y = 1 x=(-1)^m+1b_m-1; y = (-1)^ma_m-1;

.

r₀ = 1;

r₁ = 1;

r₂ = 2;

r₃ = 1;

r₄ = 25;

m = 4;

a_m-1 = r_m-1a_m-2+a_m-3; b_m-1 = r_m-1b_m-2+b_m-3;

a₃ = r₃a₂ + a₁; b₃ = r₃b₂ + b₁;

;

a₂ = 1(1*2+1)+2 = 5; b₂ = 3;

a₃ = 7;

y = (-1)⁴7 = 7.

Таким чином E_k = 7.

В таблиці 1.14 наведені значення складності криптоаналізу, I₁ – методом Ленстри, І₂ – з використанням квадратичного решета.

.

.

Таблиця 1.14 – Значення складності криптоаналізу

N	lnN	lnlnN	(lnN)1/3	(lnlnN)2/3	I1	I2
256	179,2	5,29	5,64	2,99	1,7×1013	8,2×1013
512	358,4	5,98	7,10	3,25	8,5×1019	1,2×1019
768	537,6	6,29	8,13	3,41	1,7×1024	7,4×1022
1024	716,8	6,57	8,94	3,51	6,3×1029	7,8×1025
2048	1433,6	7,26	11,27	3,74	2,4×1044	6×1034
4096	2867,2	7,96	14,20	3,99	4,1×1065	5,6×1046
8192	5734,4	8,65	17,89	4,21	5,3×1096	1,4×1062

Перевірка E_k*D_k = 103*7 = 721(mod 180)º1 (mod 180). Тоді розв’язок зроблено правильно.

1.14.2 Задачi для самостiйного розв'язання

1. Факторизуйте модуль RSA перетворення методом двійкового решета, якщо

№	1	2	3	4	5	6	7	8	9	10	11
N	391	221	299	209	247	133	217	253	161	91	437

2. Порівняйте складність криптоаналізу RSA, якщо використовуються метод –Полларда, метод Ленстри, квадратичне решето та загальне решето числового поля.

Визначте складність криптоаналізу, якщо довжини модулів бітів.

1.14.3 Контрольнi запитання та завдання

1. Сутність методу квадратичного решета?

2. Як розраховується база квадратичного решета?

3. Як рекомендується обирати значення числа Z?

4. Викладіть сутність двійкового решета?

5. В чому сутність алгоритму Евкліда та які умови його застосування?

6. Скільки розкладів таблиці квадратичного решета мають бути позитивними?

7. Як оцінити стійкість RSA криптоперетворень?

8. Яким чином стійкість криптоперетворень залежить від методу криптоаналізу?

9. В чому суть методики RSA криптоаналізу?

10. Дайте оцінку складності криптоаналізу різних етапів його виконання.

11. Які вимоги ставляться до простих чисел, щоб складність крипто-аналізу була найбільшою?

12. Як RSA перетворення може бути використане для здійснення цифрового підпису?

13. Як RSA перетворення може бути використане для здійснення направленого шифрування?

14. Які вимоги висуваються до пари ключів RSA-перетворення?

15. Які канали вразливості властиві RSA-перетворенням?

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