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

Розрахунки зведемо в таблицю 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}