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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 53
Поскольку значение границы B
2
обычно выбирается так, чтобы
выполнялось B
2
≤ B
2
1
, последнее уравнение эквивалентно
√
B
1
< r < c
1
√
B
1
, где c
1
=
√
c. (3.25)
Общая доля чисел, удовлетворяющих (3.25), невелика и значительно
меньше числа простых чисел из интервала (B
1
, B
2
), поэтому ими можно
пренебречь. Однако, если не пренебрегать этими числами и добавить в
алгоритм дополнительный цикл по элементам r , удовлетворяющим условию
(3.25), общее время алгоритма увеличится незначительно. Поскольку
размер наибольшей степени q
t
сильно зависит от степени гладкости числа
p − 1, поэтому эффективность (p − 1)–метода Полларда сильно зависит
от исходного числа n, изменяясь в широких пределах при различных
n одинаковой длины. Поэтому одной из рекомендаций метода RSA
является выбор n так, чтобы p − 1 имел хотя-бы один большой делитель,
превышающий размер границы B
2
, до которой возможно выполнение
реальных вычислений по (p − 1)–методу Полларда.
Скажем несколько слов о выборе исходного значения параметра
a. Если p − 1 имеет большое число различных делителей, то
найдется много различных чисел a < n, для которых a
k
≡ 1 (modp)
выполнится для k < p − 1. Найдутся даже такие a < n, что
уже a
2
≡ 1 (modp). Для таких a скорость схождения метода будет
значительно выше. Поэтому, можно ускорить сходимости (p − 1)–
метода Полларда, запуская алгоритм с несколькими значениями
a. В статье «Pollard ρ on the Play Station 3», размещенной на сайте
http://www.hyperelliptic.org/tanja/SHARCS/slides09/03-bos.pdf, приводятся
примеры программирования алгоритмов факторизации, включая ρ и (p −1)
методы Полларда с возможностью распараллеливания на игровой консоли
Sony Play Station 3, имеющей 8 сопроцессоров.
Пример
Пусть p = 29–делитель n, тогда, p − 1 = 28 = 2
2
· 7. Для каждого
a ≤ 28 найдем наименьшее k такое, что a
k
≡ 1 ( mod p). Приведем фрагмент
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                             53

      Поскольку значение границы B2 обычно выбирается так, чтобы
выполнялось B2 ≤ B12 , последнее уравнение эквивалентно
              √                 √             √
                  B1 < r < c1    B1 , где c1 = c.                            (3.25)

      Общая доля чисел, удовлетворяющих (3.25), невелика и значительно
меньше числа простых чисел из интервала (B1 , B2 ), поэтому ими можно
пренебречь. Однако, если не пренебрегать этими числами и добавить в
алгоритм дополнительный цикл по элементам r , удовлетворяющим условию
(3.25), общее время алгоритма увеличится незначительно. Поскольку
размер наибольшей степени q t сильно зависит от степени гладкости числа
p − 1, поэтому эффективность (p − 1)–метода Полларда сильно зависит
от исходного числа n, изменяясь в широких пределах при различных
n одинаковой длины. Поэтому одной из рекомендаций метода RSA
является выбор n так, чтобы p − 1 имел хотя-бы один большой делитель,
превышающий размер границы B2 , до которой возможно выполнение
реальных вычислений по (p − 1)–методу Полларда.
      Скажем несколько слов о выборе исходного значения параметра
a.   Если    p − 1      имеет     большое   число       различных   делителей,   то
найдется много различных чисел a < n, для которых ak ≡ 1 (modp)
выполнится для k         <   p − 1. Найдутся даже такие a              <   n, что
уже a2 ≡ 1 (modp). Для таких a скорость схождения метода будет
значительно выше. Поэтому, можно ускорить сходимости (p − 1)–
метода      Полларда,   запуская      алгоритм      с    несколькими   значениями
a. В статье «Pollard ρ on the Play Station 3», размещенной на сайте
http://www.hyperelliptic.org/tanja/SHARCS/slides09/03-bos.pdf, приводятся
примеры программирования алгоритмов факторизации, включая ρ и (p − 1)
методы Полларда с возможностью распараллеливания на игровой консоли
Sony Play Station 3, имеющей 8 сопроцессоров.

Пример

      Пусть p = 29–делитель n, тогда, p − 1 = 28 = 22 · 7. Для каждого
a ≤ 28 найдем наименьшее k такое, что ak ≡ 1 ( mod p). Приведем фрагмент

Страницы