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

Ленстра и Хабер указали, что взломать некоторые модули намного легче, чем другие [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 2^g), где SHA описан в разделе 18.7.

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

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

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

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

(7) Для к=0,1,-~,п, пусть V_k=SRA((S+N+k) mod 2^g)

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

W = V₀ + 2^lmV_x +...+ 2¹⁶⁰⁽-V V_n._x + 2¹⁶⁰ (K„ mod 2^b)

и пусть

X =ff+ 2"

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

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

(10) Если р < 2^1Л, то перейдем на этап (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 или длины некоторых других параметров. Тем не менее, если реализация является достаточно об­щей, то можно шифровать сообщение, не используя ничего, кроме функции цифровой подписи.