Генерация простых чисел DSA

Ленстра и Хабер указали, что взломать некоторые модули намного легче, чем другие [950]. Если кто-нибудь заставит пользователей сети использовать один из таких слабых модулей, то их подписи будет легче подделать. Тем не менее это не представляет проблемы по двум причинам: такие модули легко обнаружить, и они так редки, что вероятность случайно использовать одного из них пренебрежимо мала, меньше, чем вероятность случайно получить составное число на выходе вероятностной процедуры генерации простых чисел.

В [1154] NIST рекомендовал конкретный метод генерации двух простых чисел, p и q, где qявляется делителем p-1. Длина простого числа p- между 512 и 1024 и кратна 64 -битам. Пусть L-1= 160n+b, где L- это длина p, а n и b - два числа, причем b меньше 160.

(1) Выберем произвольную последовательность, по крайней мере, 160 битов и назовем ее S. Пусть g- это длина Sв битах.

(2) Вычислим U= SHA(S)Å SHA((S + 1) mod 2^g), где SHA описан в разделе 18.7.

(3) Образуем q, установив наибольший и наименьший значащие биты Uв 1.

(4) Проверим, является ли q простым.

(5) Если qне является простым, то вернемся на этап (1).

(6) Пусть C=0 и N=2.

(7) Для k=0,l,...,n, пусть V_k=SHA((S+N+k) mod 2^g)

(8) Пусть W - целое число

W= V₀+ 2¹⁶⁰V₁ +. . .+ 2^160(n-1) V_n-1 + 2¹⁶⁰ (V_nmod 2^b)

и пусть

X= W+ 2^L-1

Обратите внимание, что X - это L-битовое число.

(9) Пусть p = X- ((X mod 2q) - 1). Обратите внимание, что pконгруэнтно 1 mod 2q.

(10) Если p < 2^L-1, то перейдем на этап (13).

(11) Проверим, является ли p простым числом.

(12) Если p - простое, перейдем к этапу (15).

(13) Пусть C=C+1 и N=N+n+l.

(14) Если C= 4096, вернемся к этапу (1). В противном случае перейдем на этап (7).

(15) Сохраним значения Sи C, использованные для генерации pи q.

В [1154] переменная Sназывается стартовой, переменная C- счетчиком, а N- смещением.

Смысл этого упражнения в том, что оно является опубликованным способом генерации pи q. Для всех практических применений этот метод позволяет избежать слабых значений p и q. Если кто-то вручит вам какие-то pи q, вас может заинтересовать, как получены эти числа. Однако, если вы получите значения Sи C, использованные при генерации случайных pи q, вы сможете повторить всю процедуру самостоятельно. Использование однонаправленной хэш-функции (в стандарте используется SHA) не позволяет получить Sи C по значениям pи q.

Эта безопасность лучше, чем обеспечиваемая RSA. В RSA простые числа хранятся в секрете. Любой может генерировать фальшивое простое число или число, форма которого упрощает разложение на множители. Не зная закрытого ключа, это никогда не проверишь. В DSA, даже если закрытый ключ неизвестен, можно убедиться, что pи q генерировались случайным образом.