Глава 16.

ВЫБОР ПАРАМЕТРОВ КРИПТОСИСТЕМЫ RSA

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

Общие требования к выбору параметров…………………………....190

Метод Гордона построения сильно простых чисел………….……….……192

190 Глава 16. ВЫБОР ПАРАМЕТРОВ КРИПТОСИСТЕМЫ RSA

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

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

16.1. Общие требования к выбору параметров

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

Исходя из этого соображения, рассмотрим наиболее общие требования к выбору чисел p, q, e, d [16].

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

Очевидно, число n=pq должно быть большим. Числа p, q не должны содержаться в списках известных больших простых чисел, не должны быть слишком близки друг к другу, либо существенно различаться по величине. Они не должны быть построенными по детерминированным алгоритмам с небольшим числом известных вариантов начальных параметров или содержать закономерности в двоичной записи. В общем, p и q не должны отличаться от типичных представителей случайных простых чисел.

Аналогичными свойствами должны обладать параметры e и d.

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

Можно доказать, что при известном d существует возможность факторизации модуля.

ed =1(ϕ(n)), можно

ordna

Общие требования к выбору параметров 191

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

Заметим также, что при наличии легко получить a из сравнения ae = c(n). Достаточно возвести c в степень h, удовлетворяющую соотношению

eh =1(ordna)

Далее. Для любого a, взаимно простого с n, ordp a делит p-1, а ordq a делит q-1. Поэтому ordn a делит G=НОК(p −1,q −1). Следовательно, для построения криптосистемы, вместо определения d из сравнения

воспользоваться решением сравнения ed1 =1(G).

Пусть g=НОД(p −1,q −1). Тогда Gg =ϕ(n). Очевидно, из соотношения ed =1(ϕ(n)) следует ed =1(G), поэтому d = d1(G) и d ≠ d1(ϕ(n)). Этим условиям удовлетворяют ключи d1, d1+G, d1+2G, …, d1+ (g −1)G,

криптоэквивалентные, таким образом, ключу d. Следовательно, чем больше НОД(p −1,q −1), тем больше криптоэквивалентных ключей, тем хуже для системы.

Очевидно,	в наилучшем		случае НОД(p −1,q −1)= 2, при этом
p = 2s +1, q = 2t +1, где (s,t)=1.
Чтобы	исключить	возможность		применения	(p ±1)-методов
факторизации,	необходимо	потребовать,		чтобы числа	p1 = (p −1) 2 ,
p2 = (p +1) 2	, q1 = (q −1)	2,	q2 = (q +1)	2 не разлагались в произведение

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

192 Глава 16. ВЫБОР ПАРАМЕТРОВ КРИПТОСИСТЕМЫ RSA

Требования, сформулированые Р. Ривестом в наиболее сильной форме, заключаются в том, чтобы числа p1, p2, q1, q2 были простыми, причем в разложении как p1 −1, так и q1 −1 содержалось большое простое число.

Заметим, кстати, что неизвестно, является ли множество простых чисел вида p1 =(p −1)2 бесконечным.

Для практики достаточно, чтобы существовал достаточно большой

простой делитель числа p −1. Очевидно, такой делитель имеет вид

r = (p −1)(2 j).

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

16.2. Метод Гордона построения сильно простых чисел

Определение. Простое число p называется сильно простым, если выполняются условия:

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

где r, s, t - большие простые числа.
Поскольку числа p, r,		s, t - нечетные, то они	представляются в	виде
p =1 + 2 jr ,	p = −1+ 2ks ,	r =1+ 2lt . Кроме того,	для наших целей,	чем
меньше числа	j,k,l , тем лучше.

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

Данные процедуры работают тем лучше, чем больше разрядность чисел, используемых в вычислениях.

Метод Гордона построения сильно простых чисел 193

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

Суть метода Гордона построения сильно простого числа p заключается в следующем [16,53].

1. Строим случайное простое число s, исходя из заранее выбранной для него разрядности. Для этого выбираем псевдослучайно число x разрядности s и

с помощью метода пробных делений оставляем в промежутке [x, x +log2 x]

числа, не имеющие малых делителей. Среди оставшихся чисел с помощью тестов на простоту определяем простое число s.

2.Строим случайное простое число t аналогично построению числа s.

3.С помощью метода пробных делений и тестов на простоту, аналогично

пункту 1, строим простое число r =1+ 2lt , перебирая l в промежутке

[1,log2 t].

4. Вычисляем u = u(r,s)= (sr−1 − rs−1 )mod rs .	Это удобно	сделать с
помощью китайской теоремы об остатках, т.к. u =1(r) и u = −1(s).
Для дальнейшего заметим, что искомое число p должно удовлетворять тем
же условиям: u = p =1(mod r), u = p = −1(mod s).
5. Если число u - нечетное, то присваиваем	p0 =u , иначе,	полагаем
p0 = u + rs .