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

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

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

Знаходимо :

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

x	Z = x+	Z 2 mod N					Залишок
			-	-	-	-
				-	-	-	+
			-	-	-	-
				-	-	-
			-	-	-	-
				-	-	-
			-	-	-	-
				-	-	-
						-	+
			-		-	-
				-	-	-
			-		-	-
						-	+
			-	-		-
			-	-		-	+

У першому стовпчику задаємо значення 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					Залишок
					-	-	-	+
				-	-	-	-	-47
							-	+
				-	-		-	-23
					-	-	-	-19
				-	-	-	-	-
				-	-	-	-	-
						-	-	-11
				-		-	-	-37
					-	-	-	-79
				-		-	-	23-
				-	-			+
						-	-	17-
				-	-	-	-	-
				-	-		-	+
					-	-	-	+
				-	-		-	+
					-	-	-

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

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

x	Z =ë x+ û	Z 2 mod N					Залишок
				-	-	-	+
						-	+
			-	-			+
			-	-		-	+
				-	-	-	+
			-	-		-	+

Замінимо в таблиці всі парні числа 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 _k E _k = 1; 180(- k)+103 E _k = 1

180 x +103 y = 1 x =(-1)^m+1 b _m-1; y = (-1)^m a _m-1;

.

r ₀ = 1;

r ₁ = 1;

r ₂ = 2;

r ₃ = 1;

r₄ = 25;

m = 4;

a _m-1 = r _m-1 a _m-2+ a _m-3; b _m-1 = r _m-1 b _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	ln N	lnln N	(ln N)1/3	(lnln N)2/3	I1	I2
	179,2	5,29	5,64	2,99	1,7×1013	8,2×1013
	358,4	5,98	7,10	3,25	8,5×1019	1,2×1019
	537,6	6,29	8,13	3,41	1,7×1024	7,4×1022
	716,8	6,57	8,94	3,51	6,3×1029	7,8×1025
	1433,6	7,26	11,27	3,74	2,4×1044	6×1034
	2867,2	7,96	14,20	3,99	4,1×1065	5,6×1046
	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 перетворення методом двійкового решета, якщо

№
N

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. Порівняйте складність основних мотодів факторизації складених
чисел.