Ленстра и Хабер указали, что взломать некоторые модули намного легче, чем другие [950]. Если кто-нибудь заставит пользователей сети использовать один из таких слабых модулей, то их подписи будет легче подделать . Тем не менее это не представляет проблемы по двум причинам: такие модули легко обнаружить, и они так ре д-ки, что вероятность случайно использовать одного из них пренебрежимо мала, меньше, чем вероятность случайно получить составное число на выходе вероятностной процедуры генерации простых чисел .
В [1154] NIST рекомендовал конкретный метод генерации двух простых чисел ,р и д, где д является делителем р-1. Длина простого числа/; - между 512 и 1024 и кратна 64 -битам. Пусть L-l= I60n+b, где L - это длина/;, а п и Ъ - два числа, причем Ъ меньше 160.
(1) Выберем произвольную последовательность, по крайней мере, 160 битов и назовем ее S. Пусть g - это длина S в битах.
(2) Вычислим U = SHA(S) © SHA((S + 1) mod 2g), где SHA описан в разделе 18.7.
(3) Образуем д, установив наибольший и наименьший значащие биты U в 1.
(4) Проверим, является ли д простым.
(5) Если д не является простым, то вернемся на этап (1).
(6) Пусть 00 и N=2.
(7) Для к=0,1,-~,п, пусть Vk=SRA((S+N+k) mod 2g)
(8) Пусть Ж - целое число
W = V0 + 2lmVx +. . .+ 2160(-V Vn.x + 2160 (K„ mod 2b)
и пусть
X =ff+ 2"
Обратите внимание, что Х- это L-битовое число.
(9) Пустьр —Х- ((X mod 2q) - 1). Обратите внимание, что р конгруэнтно 1 mod 2q.
(10) Если р < 21Л, то перейдем на этап (13).
(11) Проверим, является ли р простым числом.
(12) Если р - простое, перейдем к этапу (15).
(13) Пусть ОС+1 и N=N+n+l.
(14) Если С — 4096, вернемся к этапу (1). В противном случае перейдем на этап (7).
(15) Сохраним значения S и С, использованные для генерации р и q.
В [1154] переменная S называется стартовой, переменная С - счетчиком, a N - смещением.
Смысл этого упражнения в том, что оно является опубликованным способом генерации р и q. Для всех практических применений этот метод позволяет избежать слабых значений р и q. Если кто-то вручит вам какие-то р и q, вас может заинтересовать, как получены эти числа. Однако, если вы получите значения S и С, использованные при генерации случайных р и q, вы сможете повторить всю процедуру самостоятельно. Использование однонаправленной хэш-функции (в стандарте используется SHA) не позволяет получить S и С по значениям р и q.
Эта безопасность лучше, чем обеспечиваемая RSA. В RSA простые числа хранятся в секрете. Любой может генерировать фальшивое простое число или число, форма которого упрощает разложение на множители . Не зная закрытого ключа, это никогда не проверишь. В DSA, даже если закрытый ключ неизвестен, можно убедиться, чтор и q генерировались случайным образом.
Шифрование ElGamal с DSA
Утверждалось, что DSA так нравится правительству, потому что его нельзя использовать в качестве алг о-ритма шифрования. Однако можно использовать вызов функции DSA для шифрования ElGamal. Пусть алгоритм реализован как вызов одной функции
DSAsign(p,q,g,k,x,h,r,s)
Задав входные значения р, q, g, k, xu h, можно получить параметры подписи: г и s.
Для шифрования сообщения m алгоритмом ElGamal с помощью открытого ключа у выберем случайное число А: и вызовем
DSAsign(p,p,g,k,0,0,r,s)
Возвращенное значение г и будет а из схемы ElGamal. Отбросим s. Затем вызовем, call
DSAsign(p,p,y,k,0,0,r,s)
Переименуем значение г в и, отбросим s. Вызовем
DSAsign(p,p,m,l,u,0,r,s)
Отбросим г. Возвращенное значение s и будет Ъ в схеме ElGamal. Теперь у вас есть шифротекст, а и Ъ. Дешифрирование также просто. Используя закрытый ключ х и шифротекст сообщений, аиЬ, вызовем
DSAsign(p,p,a,x,0,0,r,s)
Значение г - это if mod/;. Назовем его е. Затем вызовем
DSAsign(p,p,l,e,b,0,r,s)
Значение s и будет открытым текстом сообщения, от.
Этот способ работает не со всеми реализациями DSA - в некоторых из них могут быть зафиксированы значения/; и q или длины некоторых других параметров. Тем не менее, если реализация является достаточно общей, то можно шифровать сообщение, не используя ничего, кроме функции цифровой подписи .