а, 6, c

значения функции /ab(x отрезке [-M, M] были равны по абсолютной величине и противоположны по знаку:

Поэтому полагаем:

62 = n (mod а), О < 6 <

62 - ае =

Заметим, что условие существования решения второго сравнения можно преобразовать следующим образом: для всех простых делителей q\a выполняется () = 1. Значение факторизации числа а необходимо также потому, что оно участвует в качестве сомножителя в

либо полный квадрат, либо число, факторизуемое в произведение простых чисел из факторной базы.

При данном выборе параметров значения многочлена /ab(x) на интервале [-M, M] удовлетворяют неравенству

\hb{x)\ < -Мл/Й,

что в 2\/2 раз лучше, чем у исходного алгоритма Померанца, в котором при М <С л/й

/„ь(ж) I < 2 + 2жл/й « 2жл/й < 2Мл/й.

Поэтому такие полиномы более предпочтительны для поиска

Метод Померанца называется методом квадратичного решета или qs-методом, а метод Дэвиса-Монтгомери - шpqs-мeтoдoм (multiply polinomial variation of quadratic sieve algorithm).

13.T. (p - 1)-метод факторизации Полларда

(p- 1)

параметром метода. Для успешной работы алгоритма нужно, чтобы выполнялось условие

(p - 1) M(k),

где M(k)0K(1, 2, , тесто M(k шользовать ki, либо произведение p1 p ртых k простых чисел в некоторых степенях ai ttk, которые выбираются из эвристических соображений). В силу малой теоремы Ферма выполняется сравнение

Если при этом

2м(k) = 1 (mod p) 2M(k) = 1 (mod n),

p (2м(k) - 1,n),

гдe1<p (2м(k) - 1, n)< образом, d=(2M(k) - 1, n) является

Ha этой идее основан следующий метод нахождения собственного nk последовательный перебор малых значений до некоторого фиксированного значения.

Пусть k - пшое чшсло, например k < 10 е - небольшое целое с условием (е, n) = щимер, е = 2.

Шаг 1. Для каждого т о стяется mi = ем(i) mod n и проверяется тест шага 2.

Шаг 2. Вычислить d = (mi - 1, &ли 1 < d < n, то найден нетри-

i=i+1

Можно модифицировать алгоритм, используя одновременно нес-

Так как (с, и) = (c,p) = как только (p - 1) М(i),

mi = 1 (mod p) p (mi - 1) и

mi = 1 (mod и)

При выполнении алгоритма возведение в степень cM 1i) надо осуществлять в кольце Zn методом повторного возведения в квадрат. Так как log М(i) € i log №1числения (mi - 1) mod и требуется 0(ilogi) х операций кольца Zn. Поэтому общая сложность алгоритма может быть грубо оценена величиной 0(k2 log k log3 и).

IV. Криптографическая система RSA

Криптографическая система RSA является классическим примером криптографической системы с открытыми ключами. Она была предложена в работе [50] и в настоящее время получила очень широкое распространение. Несмотря на многочисленные критические работы по изучению ее свойств, в которых указаны наборы параметров, приводящие к ослаблению схемы, при правильном использовании она считается безопасной.

Напомним общий алгоритм работы системы RSA. Каждый абонент вырабатывает свою пару открытых и секретных ключей. Для

и = pq e

взаимно простое с (и) = (p - 1)(q - 1) т число d из условия ed = 1 (mod (и) Шра (и,е) объявляется открытым ключом и помещается в открытый каталог. Остальные числа (p, q, (u),d) образуют секретный ключ. Заметим, что числа (p,q,(u)) в дальнейшем не нужны и могут быть уничтожены. Для расшифрования достаточно (и, d)

Если абонент еть сообщение отенту В, то он вы-

(и, e) В

шифрованное сообщение:

s = te (mod и).

t = sd (mod и)

§ 14. Выбор параметров системы RSA

При изучении криптографической системы RSA основным вопро-

p q e d

ния сравнения

te = s (mod и)

ключа (p,q,(u),d) является сложной.

-1 (mod n)

то тест прошел успешно. Если нет, то в результате будет

найдено такое s, что

6 = а2-1 r = ±1 (mod n), 62 = а2r = 1 (mod n)

6 (6 - 1, n)

(6 + 1, n) p q

Если для всех чисел ai, , ak тест на шаге 2 прошел успешно, то разложение не найдено.

Покажем что данный алгоритм с вероятностью успеха не менее 1 - факторизацию числа n.

Пусть zn = An и Bn,гдe

An = {а € zn: 3s < s,a2S-1r = ±1 (mod n),a2Sr = 1 (mod n)},

Bn = zn\An

Так как элементы a € та факторизацию n, то для доказательства теоремы надо доказать, что -В„ < " • Представим множество Bn в виде

Bn = В" и У] Bn,

s = 1

В" = {а € Zn : ar = 1 (mod n)},

В" = {a € Zn : r = -1 (mod n),a r = 1 (mod ,

Пусть p-1=2im q - 1=2jвде m, тетны и ij. Сначала заметим, что множество В" только при s i. Действительно,

(n) = 2im2j 1,

причем 2im2j 11 (ed - 1) = 2s тачит, m11 r. Поэтому условие

a2S 1r = -1 (mod n),

a, следовательно,и

a2 r = -1 (mod p)

может выполняться только, если s - 1 < е. s i. Итак,

Bn = вП

s = 1

14.1. Взаимосвязь между параметрами системы RSA

Покажем, что если имеется возможность найти любое из чисел (p, q, (n), d), то можно найти сам секретный ключ и осуществить рас-

и найти его делители и ы знаем (n) = (p - 1)(q - 1), а параметр тся из сравнения ed = 1 (mod (n)) с помощью расширенного алгоритма Евклида.

Если мы можем находить число (n числа и q легко находятся по формулам:

p + q = n - (n) + 1, p- q = + - in.

показывает следующая теорема, имеется эффективный вероятностный алгоритм факторизации.

Теорема. Пусть n = pde p и q - простые. Если существует

d (n, e)

Доказательство. Так как ed = 1 (mod (n)), то при некото-k

ed - 1 = k(n),

левая часть которого известна. Пусть ed -1 = 2s ще r - ететно, s1. По теореме Эйлера для каждого элемента Z" должно выполняться сравнение:

r = 1 (mod n)

Рассмотрим теперь вероятностный алгоритм, аналогичный тесту простоты Миллера-Рабина.

Шаг 1. Выбираем случайно теел ai, , ak € Z" и для каждого из них проверяем тест на шаге 2.

Шаг 2. Для данного теляем ar.

Если ar = 1 (mod n), то тест прошел успешно.

Если ar = 1 (mod n), то вычисляем последовательность