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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 60
называется генератором поля, если любой элемент t ∈ F
∗
p
равен некоторой
степени элемента g : t = g
k
. Пусть g – (какой-нибудь) генератор этой группы,
и пусть t - произвольный элемент F
∗
p
.
Для нахождения неизвестного показателя k такого, что g
k
= t,
будем строить последовательность пар (a
i
, b
i
) чисел по модулю p − 1 и
последовательность x
i
чисел по модулю p такую что x
i
= t
a
i
g
b
i
. Определим
начальные значения a
0
= b
0
= 0, x
0
= 1. Вычисление последующих членов
последовательностей будем выполнять по формулам:
(a
i+1
, b
i+1
) =
(a
i
+ 1, b
i
) mod (p − 1), если 0 < x
i
< p/3,
(2a
i
, 2b
i
) mod (p − 1), если p/3 < x
i
< 2p/3,
(a
i
, b
i
+ 1) mod (p − 1) если 2p/3 < x
i
< p,
(3.27)
и, соответственно,
x
i+1
=
tx
i
mod p, если 0 < x
i
< p/3,
x
2
i
mod p, если p/3 < x
i
< 2p/3,
gx
i
mod p если 2p/3 < x
i
< p,
(3.28)
Эта последовательность вычисляется до тех пор, пока не появятся номера
i, j такие, что x
i
= x
j
. Тогда, t
a
i
g
b
i
= t
a
j
g
b
j
, откуда,
(a
j
− a
i
)k ≡ b
i
− b
j
(mod(p − 1)) (3.29)
Если Н.О.Д.(a
j
−a
i
, p−1) = 1, тогда множитель k в уравнении (3.29) может
быть найден с использованием обобщенного алгоритма Евклида, решив в
целых числах уравнение
x(a
j
− a
i
) + y(p − 1) = b
i
− b
j
(3.30)
относительно x, y и определяя k = x mod (p − 1).
Если же Н.О.Д.(a
j
− a
i
, p − 1) = d > 1, тогда, уравнение (3.30) по-
прежнему, разрешимо, но дает решение нашего уравнения с точностью до
слагаемого кратного (p − 1)/d, т.е. решение имеет вид
x = x
0
+ m(p − 1)/d (3.31)
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                        60

называется генератором поля, если любой элемент t ∈ Fp∗ равен некоторой
степени элемента g : t = g k . Пусть g – (какой-нибудь) генератор этой группы,
и пусть t - произвольный элемент Fp∗ .
       Для нахождения неизвестного показателя k такого, что g k = t,
будем строить последовательность пар (ai , bi ) чисел по модулю p − 1 и
последовательность xi чисел по модулю p такую что xi = tai g bi . Определим
начальные значения a0 = b0 = 0, x0 = 1. Вычисление последующих членов
последовательностей будем выполнять по формулам:
                    
                    
                     (ai + 1, bi ) mod (p − 1),
                                                если 0 < xi < p/3,
   (ai+1 , bi+1 ) =   (2ai , 2bi ) mod (p − 1),  если p/3 < xi < 2p/3,   (3.27)
                    
                    
                     (ai , bi + 1) mod (p − 1)  если 2p/3 < xi < p,

и, соответственно,
                           
                           
                                            если 0 < xi < p/3,
                            txi mod p,
                  xi+1 =     x2i mod p,      если p/3 < xi < 2p/3,       (3.28)
                           
                           
                            gxi mod p       если 2p/3 < xi < p,

Эта последовательность вычисляется до тех пор, пока не появятся номера
i, j такие, что xi = xj . Тогда, tai g bi = taj g bj , откуда,

                 (aj − ai )k ≡ bi − bj (mod(p − 1))                      (3.29)

Если Н.О.Д.(aj − ai , p − 1) = 1, тогда множитель k в уравнении (3.29) может
быть найден с использованием обобщенного алгоритма Евклида, решив в
целых числах уравнение

                   x(aj − ai ) + y(p − 1) = bi − bj                      (3.30)

относительно x, y и определяя k = x mod (p − 1).
       Если же Н.О.Д.(aj − ai , p − 1) = d > 1, тогда, уравнение (3.30) по-
прежнему, разрешимо, но дает решение нашего уравнения с точностью до
слагаемого кратного (p − 1)/d, т.е. решение имеет вид

                                 x = x0 + m(p − 1)/d                     (3.31)

Страницы