Математические основы защиты информации. Ишмухаметов Ш.Т - 60 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 61
где m ∈ [0, d − 1]–целое число. Если множитель d - мал, то решение будет
найдено подстановкой чисел (3.31) в уравнение g
X
≡ t mod t.
Так же, как в ρ–методе факторизации, в этом алгоритме можно
использовать модификацию Флойда, вычисляя на i-м шаге одновременно
тройку (a
i
, b
i
, x
i
) и тройку (a
2i
, b
2i
, x
2i
), пока не дойдем до шага i, на котором
x
i
= x
2i
. В этом варианте опять не надо хранить в памяти на шаге i все
тройки (a
j
, b
j
, x
j
) для j ≤ i, а достаточно сохранять две тройки (a
i
, b
i
, x
i
) и
(a
2i
, b
2i
, x
2i
).
Пример. Рассмотрим поле F
p
при p = 43. Элемент g = 2 не является
генератором по критерию Поклингтона, т.к.2
14
mod 43 = 1. Возьмем в
качестве генератора элемент g = 3 и решим уравнение
3
X
mod 43 = 15. (3.32)
Итак, p = 43, g = 3, t = 15. Определим (
0
, b
0
, x
0
) = (0, 0, 1), и будем строить
две последовательности (a
i
, b
i
, x
i
) и (a
2i
, b
2i
, x
2i
) по формулам (3.27) и (3.28):
i a
i
b
i
x
i
a
2i
b
2i
x
2i
1 2 0 10 6 0 11
2 3 0 21 7 1 22
3 6 0 11 15 2 36
4 7 0 36 30 6 11
5 7 1 22 31 7 22
На 5-м шаге значения x
i
и x
2i
совпали. Составим уравнение (3.30):
x(31−7)+y(43−1) ≡ 1−7 ( mod 42), или, 24x+42y ≡ 36 ( mod 42).
Вычислим Н.О.Д.(a
j
− a
i
, p − 1) =Н.О.Д.(24, 42) = 6 ̸= 1.
Поделим все коэффициенты уравнения на 6:
4x + 7y ≡ 6 ( mod 42).
С помощью расширенного алгоритма Евклида решим уравнение 4x +
7y = 1, подставляя вместо A и B коэффициенты этого уравнения (поменяв
их местами, чтобы A было больше B ):
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                                 61

где m ∈ [0, d − 1]–целое число. Если множитель d - мал, то решение будет
найдено подстановкой чисел (3.31) в уравнение g X ≡ t mod t.
          Так же, как в ρ–методе факторизации, в этом алгоритме можно
использовать модификацию Флойда, вычисляя на i-м шаге одновременно
тройку (ai , bi , xi ) и тройку (a2i , b2i , x2i ), пока не дойдем до шага i, на котором
xi = x2i . В этом варианте опять не надо хранить в памяти на шаге i все
тройки (aj , bj , xj ) для j ≤ i, а достаточно сохранять две тройки (ai , bi , xi ) и
(a2i , b2i , x2i ).

          Пример. Рассмотрим поле Fp при p = 43. Элемент g = 2 не является
генератором по критерию Поклингтона, т.к.214 mod 43 = 1. Возьмем в
качестве генератора элемент g = 3 и решим уравнение

       3X mod 43 = 15.                                                           (3.32)

Итак, p = 43, g = 3, t = 15. Определим (0 , b0 , x0 ) = (0, 0, 1), и будем строить
две последовательности (ai , bi , xi ) и (a2i , b2i , x2i ) по формулам (3.27) и (3.28):

            i     ai bi xi a2i b2i x2i
            1     2   0 10   6   0   11
            2     3   0 21   7   1   22
            3     6   0 11 15    2   36
            4     7   0 36 30    6   11
            5     7   1 22 31    7   22

          На 5-м шаге значения xi и x2i совпали. Составим уравнение (3.30):

x(31−7)+y(43−1) ≡ 1−7 ( mod 42),              или, 24x+42y ≡ 36 ( mod 42).

          Вычислим Н.О.Д.(aj − ai , p − 1) =Н.О.Д.(24, 42) = 6 ̸= 1.
          Поделим все коэффициенты уравнения на 6:

   4x + 7y ≡ 6 ( mod 42).

          С помощью расширенного алгоритма Евклида решим уравнение 4x +
7y = 1, подставляя вместо A и B коэффициенты этого уравнения (поменяв
их местами, чтобы A было больше B ):

Страницы