Учитывая изоморфизм Zn = Zp + Zq, получаем

Bnn = BPo-Bqo = (r,p - 1)(r,q - 1)= ml,

так как порядок подгруппы

{a £ Zp: ar = 1 (mod p)}

группы аден {r,p - 1) = m.

Рассуждая аналогично, получаем

B:: = B;ЦВ = ((2sr,p - 1) - (2s-1 r,p - 1))((2sr,q - 1)- (2s-1r,q - 1)) = (2sm - 2s-1m)(2sl - 2s-1l) = 221s-1)ml.

Отсюда

Bn = ml Y 22kml = ml

= ml

4i - 1\

2i+j

< ml

Теорема доказана. □

В заключение заметим, что каждый пользователь должен неза-

ации простых чисел p ш q достаточно трудоемкий, нельзя делать число и = pq общим хотя бы для двух разных пользователей системы RSA.

Теорема. Если абонент те же числа и q, что и B

экспоненты друг друга с помощью детерминированного алгоритма.

dA Л eB

и таслить величину eBdB - 1 = k(u) k ш (и) -

неизвестные ему значения.

t eBdB - 1

(eBdB - 1)/t eA

Покажем что существует детерминированный алгоритм его вычисления.

Шаг 1. Полагаем qo = eB dB - 1, ho = (go,eA), t = ho. Шаг 2. Для всех nop, пока hi > 1, полагаем

gi = gi-i gi-i/hi-i, hi = (gi ,eA), t = thj.

будет искомым.

Легко видеть, что число t = hohi... hi, будет удовлетворять условию

eBdB - 1

-,еА

причем алгоритм выполнит не более 2 log № как если hi 2, то

i € log2(eBdB - 1) € 2log2 и.

Воспользуемся теперь расширенным алгоритм Евклида для нахождения чисел и Ъ из условия

ев(1в - 1

t

ЪeA = 1.

Далее, покажем, что Ъ = dA (mod и) - искомое число. Так как t = hoh1 X ... X вде hi (eA, (и)) = 1o (t, (и)) = 1. Отсюда

ев<1в - 1 t

□

В заключение сделаем еще одно замечание, относящееся к данному случаю. Предположим, что мы просмотрели список открытых ключей

(eA, eB) = 1

для чисел x, та, что xxeA + yeв = 1, будет верно простое соот-

зашифрованного на этих ключах. А именно, если s1 = teA (mod и), s2 = teB (mod u)o is2 = t (mod и).

14.2. Условия на выбор чисел рш q

воляет полностью дешифровать схему RSA и определить секретный

шифрования.

которых может приводить к снижению стойкости шифрования.

Во-первых, числа не должны содержаться в списках известных больших простых чисел. Поэтому они не должны являться числами специального вида (например, числами Мерсенна или Ферма) и не должны иметь закономерностей.

Во-вторых, они не должны быть близкими, так как иначе можно воспользоваться методом факторизации Ферма и решить уравнение

В-третьих, огромную роль играют разложения на простые множители чисел p - 1ш q - стлу изоморфизма Zn = Zp + Zg для порядков элементов а = ai + а2 этого кольца выполняется соотношение

ordn(a) TOK(ordp(ai),ordg(а2))

нение

ed = 1 (mod (p - 1,q - 1))

вместо сравнения

ed = 1 (mod (n)) p- 1 q - 1

Н0К(р-1,,-1).

Следовательно, в схеме RSA всегда есть эквивалентные по рас-

d d + (p - 1, q - 1) При этом эквивалентных решений будет тем больше, чем больше HOД(p - 1,q - 1).

(p-1, q-1)=2 p=2t+1 q=2s+1 s t (s, t) = 1

(p- 1) (p+ 1)

p- 1 p+ 1 q - 1 q + 1 дение маленьких простых сомножителей и содержали бы в качестве сомножителя хотя бы одно большое простое число. Наиболее сильное требование, сформулированное Ривестом в 1978 г., заключается в том, чтобы числа

p1 =

р-1 2

p2 =

Р+1 2

q1 =

2

q2 =

p1 - 1 q1 - 1

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

выполняются условия:

p = 1 (mod r), p = s - 1 (mod s), r = 1 (mod t),

p r s t

p q r t

при некоторых j k 1 выполнены равенства:

p =2jr + 1, p =2ks - 1, r = 21t + 1

Дж. Гордон предложил в 1984 г. алгоритм генерации таких чисел.

каждого из них используем следующий метод. Фиксиру-

и с помощью пробных делений оставляем в интервале [x,x + log x] только те числа, которые не имеют маленьких делителей. Проверяем оставшиеся числа на простоту одним из тестов простоты.

Шаг 2. Строим простое число гад а 21t+ м ч исел 1 в интервале [1, log t], используя аналогично шагу 1 просеивание с помощью пробных делений на маленькие простые числа и применяя затем к оставшимся числам тесты простоты.

Шаг 3. Вычисляем число м(г, s) = (sr-1 - rs-1) mod rs и полагаем

po =

м(г, s), м(г, s)=2g + 1,

м(г, s) + rs, м(г, s) = 2g, g €

po + 2krs простоты.

в основе данного алгоритма лежит следующая

r s p

удовлетворяет условиям

p = 1 (mod r) , p = s - 1 (mod s)

p= po + 2krs

Г u(r,s), u(r,s)=2g + 1,

]u(r,s)+ rs, u(r,s)=2g,g £ Z,

u(r,s) = (sr-1 + rs-1) mod rs.

Доказательство. В силу малой теоремы Ферма имеем

sr-1 = 1 (mod r), rs-1 = 1 (mod s).

Отсюда, учитывая, что sr-1 = 0 (mod rs-1 = 0 (mod r), получаем

{u(r, s) = 1 (mod r), u(r, s) = -1 (mod s).

p = po + 2 krs

Покажем, что других чисел, удовлетворяющих данному условию нет. Если p - число, то p - p = 0 (mod r) ш p - p = 0 (mod s). Отсюда p = p (mod rs тачит p = u(r, s) (mod rs тасло p имеет po + 2krs □

может быть наличие большого числа элементов ш £ Z*n, представляющих открытые сообщения и имеющих малый порядок ordn(u)). В этом случае для нахождения неизвестного сообщения ш можно изменить метод итерации процесса зашифрования

до тех пор, пока не выполнится условие

eu = 1 (mod OIdn(ш)),

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

{seU) 1 = ш" = ш (mod и)

Минимальное число шагов до получения шио oidordni)(e). Значит для безопасности шифрования необходимо потребовать, чтобы для почти всех x £ Z*n п e £ Zin отчина ordordn(ш) (e) была достаточно большой.

Приведем достаточное условие, доказанное в 1995 г. Мауэром, гарантирующее стойкость системы RSA относительно методов, использующих итерацию процесса зашифрования.

Лемма. Пусть h=p p-1=2RpF q - 1 = 2RqFq, где каноническое разложение чисел и Fq имеет вид

Тогда доля сообщений x £ тторых ordn(xx)

0K(Fp,Fq), удовлетворяет неравенству

Fq pi qi

Доказательство. Воспользуемся оценкой, доказанной в лемме 3 из 12.4:

{x £ Z; : Fp ordp(x)} (p - 1)

(Fq )

{x £ Z; : Fq ordq(x)} (q - 1)

Fp ordn(x) Fq ordn(x) (Fp, Fq) ordn(x)

{x £ zn : [Fp,Fq] ordn(x)} (p - 1)(q - 1)

(Fp) (Fq)

что и доказывает лемму.

и = pq

pi - 1 = 2aiЪi, i = 1,...,r, qj - 1 = 2aj Ъз , j = 1,...,s, где каноническое разложение чисел Ъi и Ъ.! имеет вид

=1 =1