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

Задача 1.

Факторизувати модуль N, використавши метод  - Поларда.

Дано, що N = 221, а = 11, = 127, C = 1.

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

,

x₁ = 118; НСД(127-118, 221) = (9, 221)=1, тобто спільних дільників немає.

,

x₂ = 19; НСД (118-19,221) = НСД (99,221) = 1.

Таким чином НСД (х₁ – х₂, N) знову не має сильного дільника.

.

Розрахуємо послідовно х_і поки, НСД (х₁ – х₂, N) різнитиметься від 1 або N.

x₃ = 210;  НСД (191,221) = 1,

,

x₄ = 7 ;  НСД (203 , 221) =1,

,

x₅ = 78 ;  НСД (71,221) = 1,

,

x₆ = 91. При х₆ маємо НСД (х₆ – х₅, N) = НСД (91 – 78, 221) = НСД (13, 221) = 13.

Таким чином один із співмножників модуля N є 13, наприклад, P=13. Тоді Q=N/P=221/13=17. Перевіряємо правильність розв’язку, знайшовши P*Q = 221.

Задача 2.

Факторизувати число N = 209, якщо x_i = x² + 1(mod N).

 прийнявши, що .

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

x₁ = (17² + 1)mod 209 = 81,

x₂ = (81² + 1)mod 209 = 83,

НОД (2, 209) = 1 розв’язку немає.

x₃ = (83² + 1)mod 209 = 202,

x₄ = (202² + 1)mod 209 = 50,

x₃ - x₄ = |202-50| = 152.

НОД (152, 209) = 19.

Таким чином один із співмножників, наприклад, P=19, тоді Q=209/19=11.

Задача 3.

Розв’язати порівняння 15^x º 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 отримуємо одне і теж значення x₆ = x₃ = 9.

Підставивши значення в (v = 2, w = 3, t = 4, u = 2) отримаємо

Задача 4.

Розв’язати рівняня методом -Поларда 20 º7^x (mod 23).

c = 10, r₀ = b = 20, a = 7.

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

Таким чином r₈ = r₀, причому r₈ можна подати як

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

1. Розв'яжіть рівняння 15^x º 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. Які обмеження притаманні методу - Поларда при факторизації та розв’язку дискретних логарифмічних рівнянь?