Методичні вказівки до практичних занять з дисципліни “Оcнови теорїї захисту інформації”, страница 22

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

При цьому

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

Значить N»P

Таблица 2

N/n

x

=ë  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

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

Таблица 3

x

=ë 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.  152 º 24(mod 209); 152 º 42(mod 209)

x=15, y=4.

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

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

2.{3,15}

172 292 º 5 242(mod 209); (17*29)2 º (20)2(mod 209)

x=75, y=20.

НСД(75-20, 209)

{15, 17}

292 º 51(mod 209)

312 º 53(mod 209)

(3129)2 º 5 4(mod 209); (2931)2 º 25 2(mod 209);

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

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

a1 = 209; a2 = 38

P=209:19=11;Q=19

209:38=5; r=19

a1 = 38; a2 = 19

39:19=2; r=0;

НСД (a1, a2)=a2 = 19

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

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

j(N) (-k)+DkEk = 1;     180(-k)+103Ek = 1

180x+103y = 1  x=(-1)m+1bm-1;  y = (-1)mam-1;

r0 = 1;

r1 = 1;

r2 = 2;

r3 = 1;

r4 = 25;

m = 4;

am-1 = rm-1am-2+am-3;             bm-1 = rm-1bm-2+bm-3;

a3 = r3a2 + a1;                b3 = r3b2 + b1

;

a2 = 1(1*2+1)+2 = 5; b2 = 3

a3 = 7

y = (-1)47 = 7

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

В таблиці 5 наведені значення складності криптаналізу, I1 – методом Ленстри, І2 – з використанням двійкового решета.

Таблиця 4