Глава 12.

НЕКОТОРЫЕ СЛУЧАИ ОСЛАБЛЕНИЯ КРИПТОСИСТЕМЫ RSA

Основное в этой главе…

Атаки на RSA, не использующие факторизацию модуля.………….……....152

Атаки на RSA, использующие факторизацию модуля…………………..156

Алгоритм факторизации Диксона……..157

152 Глава12. НЕКОТОРЫЕСЛУЧАИОСЛАБЛЕНИЯКРИПТОСИСТЕМЫRSA

Криптосистема RSA основана на функции возведения в степень в кольце вычетов по двупростому модулю n = pq . Эта функция часто применяется в смешанных криптосистемах и широко используется в криптопротоколах, рекомендованных различными стандартами.

Зависимость сложности обращения степенной функции от ее параметров и наличие частных случаев снижения стойкости криптосистемы RSA приводит к выводу о необходимости разработки специальных алгоритмов для генерации простых чисел p и q .

12.1. Атаки на RSA, не использующие факторизацию модуля

Известным свойством криптосистемы RSA является зависимость ее стойкости от свойств сомножителей модуля n = pq . При необоснованном выборе этих сомножителей возможно полное дешифрование криптосистемы.

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

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

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

Подобные слабости не связаны с качеством криптосистемы RSA как таковой, но отражают то обстоятельство, что стойкость криптосистемы может изменяться, в зависимости от особенностей ее проектирования и эксплуатации.

Атаки на RSA, не использующие факторизацию модуля 153

Рассмотрим ряд примеров. Будем исходить из того, что некоторый абонент А использует криптосистему RSA с параметрами (e,d,n), n = pq .

Пример 1. Пусть в сети используется общее значение модуля для нескольких абонентов и перехвачены криптограммы вида c1 = me1 (n), c2 = me2 (n), где экспоненты взаимно просты.

Вычислив с помощью расширенного алгоритма Эвклида значения r, s : re1 + se2 =1, получаем возможность определить открытый текст: c1rc2s = m(n).

Заметим, что общее значение модуля для двух абонентов позволяет каждому из них читать сообщения, предназначенные для другого (см. ниже).

Пример 2. Очевидно, что если c - шифртекст, то расшифрованное

сообщение	имеет вид: m = cd (n).	Выберем псевдослучайно число x вида
x = re (n)	и вычислим произведение	y = xc(n), т.е. замаскируем шифртекст.
Если по просьбе абонента В абонент А подпишет сообщение y :			(y, yd ),	то
абонент В	получит значение yd = xd cd = rm(n), откуда можно		найти	m .

Очевидно, использование хэш-функции не позволит воспользоваться данной лазейкой.

Пример 3. Малое значение экспоненты, например, e = 3, не позволяет непосредственно зашифровать блок x, представляемый числом в три раза меньшей длины, чем модуль.

Действительно, тогда c = x3 < n , т.е. приведение по модулю не происходит. Откуда x = 3 c - обычное число.

Пример 4. (Атака Франклина). При зашифровании сообщений с известной по модулю n разностью на стойкость криптосистемы может повлиять величина открытого ключа [48].

154 Глава12. НЕКОТОРЫЕСЛУЧАИОСЛАБЛЕНИЯКРИПТОСИСТЕМЫRSA

Пусть e = 3, m1,m2 - сообщения, m2 = m1 + ∆(modn) и соответствующие

шифртексты равны	a = me (n),b = me (n). Пусть			также известно значение
	1	2
∆ ≠ 0(n).
То же, другими словами, означает,			что два многочлена g(x)= x3 − a		и
f (x)= (x + ∆)3 −b имеют общий корень			x = m1(n).	Отсюда следует, что	m1

является корнем наибольшего общего делителя указанных многочленов.

Можно показать, что условие взаимной однозначности шифра позволяет легко определить корень полинома НОД(f (x), g(x)) в случае, когда его

степень больше единицы.

С большой вероятностью выполняются также условия обратимости по модулю n некоторых элементов (они будут очевидны по ходу рассуждения), при которых искомый наибольший общий делитель имеет вид ux + v и его корень может быть вычислен.

Напомним,	что d(x)=НОД(f (x), g(x)),	где	степень f (x)	не	ниже
степени g(x),	можно найти с помощью		алгоритма	Эвклида:
r1(x)= f (x)mod g(x), r2 (x)= g(x)modr1(x)		r3 (x)= r1(x)modr2 (x)			и т.д.,

пока остаток от деления не станет равным нулю. В этом случае предыдущий остаток есть d(x).

Вычислим НОД(f (x), g(x)) по модулю n явно, с неопределенными

коэффициентами.

Имеем: g(x)= x3 − a ,			f (x)= (x + ∆)3 −b = x3 + 3x2∆ + 3x∆2 + ∆3 −b .
Деля f (x) на		g(x),	получим, что старший член частного равен 1.
Поэтому	остаток	от	деления равен r1(x)= f (x)−1 g(x), где
r (x)=3x2	∆ +3x∆2	+ ∆3 −b + a .
1

d = (eA ,k).

Атаки на RSA, не использующие факторизацию модуля 155

Ясно, что d(x)=НОД(r1(x), g(x)).

Делим g(x) на

r (x). Старший член частного равен

1

x .

1

3∆

В итоге,

g(x)=

1

xr

(x)+ s

(x)

, где

s

(x)= −x2∆ −

1

(∆3 + a −b)x − a

.

3∆

1

2

2

3∆

Следовательно,

d(x)=НОД(r1(x),s2 (x)). Поэтому далее делим r1(x) на

s2 (x)и получаем старший член частного равный (–3).

Вычисляем

остаток

от деления r1(x)

на

s2 (x),

который имеет вид

d(x)= 3∆2

−

1

(∆3 + a −b) x + ∆3

− 2a −b .

∆

Откуда получаем корень полинома

d

(x)

:

m = x = ∆(2a +b − ∆3 )

.

1

2∆3 − a +b

Условия

корректности

рассуждения

очевидны: НОД(∆,n)=1,

НОД(2∆3 − a +b,n)=1.

Пример 5. Необходимость выбора несовпадающих модулей при построении криптосистемы RSA для различных пользователей доверенным лицом. Уточним, что в этом случае числа p,q пользователям не известны.

Пусть пользователи А и В используют соответственно криптосистемы с параметрами (eA ,dA ,n) и (eB ,dB ,n). Очевидно, пользователь В, например, в

состоянии вычислить значение eBdB −1 = kϕ(n), хотя сомножители в правой части ему неизвестны.

По построению криптосистемы (eA,ϕ(n))=1, следовательно, наибольший общий делитель чисел eA и eBdB −1 совпадает с