v = ((gU1 * j;U2) mod,p) mod q Если v = r, то подпись правильна.

Ускоряющие предварительные вычисления

В 18-й приведены примеры скорости работы программных реализаций DSA [918].

Табл. 20-2.

Скорость DSA для различных длин модулей с 160-битовым показателем степени (на SPARC II)

Практические реализации DSA часто можно ускорить с помощью предварительных вычислений . Обратите внимание, что значение r не зависит от сообщения. Можно создать строку случайных значений k, и затем рассчитать значения r для каждого из них. Можно также вычислить k-1 для каждого из этих значений k. Затем, когда приходит сообщение, можно вычислить s для заданных r и k-1.

Эти предварительные вычисления заметно ускоряют DSA. В 17-й приведены сравнения времени вычисления DSA и RSA для конкретной реализации интеллектуальной карточки [1479].

Табл. 20-3.

Сравнение времени вычислений RSA и DSA

Вычисления вне карточки (off-card) выполнялись на персональном компьютере 180386/33 МГц. (P) указывает открытые параметры off-card, а (S) - на закрытые параметры off-card. В обоих алгоритмах используется 512-битовый модуль.

Генерация простых чисел 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 2g), где SHA описан в разделе 18.7.

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

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

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

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

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

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

W = V0 + 2160 V1 +. . .+ 2160(n-1) Vn-1 + 2160 (Vn mod 2b)

и пусть

X = W + 2L-1

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

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

(10) Если p < 2L-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 генерировались случайным образом.

Шифрование ElGamal с DSA

Утверждалось, что DSA так нравится правительству, потому что его нельзя использовать в качестве алг о-ритма шифрования. Однако можно использовать вызов функции DSA для шифрования EIGamal. Пусть алгоритм реализован как вызов одной функции

DSAsign(p,q,g,k,x,h,r,s)

Задав входные значения q, g, k, * и h, можно получить параметры подписи: r и s.

Для шифрования сообщения m алгоритмом EIGamal с помощью открытого ключа y выберем случайное число k и вызовем

DSAsign(p,p,g,k,0,0,r,s)

Возвращенное значение r и будет a из схемы EIGamal. Отбросим s. Затем вызовем, call

DSAsign(p,p,y,k,0,0,r,s)

Переименуем значение r в ", отбросим s. Вызовем

DSAsign(p,p,m,1,u,0,r,s)

Отбросим r. Возвращенное значение s и будет b в схеме EIGamal. Теперь у вас есть шифротекст, a и b. Дешифрирование также просто. Используя закрытый ключ * и шифротекст сообщений, a и b, вызовем

DSAsign(p,p,a,x,0,0,r,s)

Значение r - это a* mod p. Назовем его e. Затем вызовем

DSAsign(p,p,1,e,b,0,r,s)

Значение s и будет открытым текстом сообщения, m.

Этот способ работает не со всеми реализациями DSA - в некоторых из них могут быть зафиксированы зн а-чения p и q или длины некоторых других параметров . Тем не менее, если реализация является достаточно о б-щей, то можно шифровать сообщение, не используя ничего, кроме функции цифровой подписи .

Шифрование RSA с DSA

Шифрование RSA еще проще. Используя модуль n, сообщение т и открытый ключ e, вызовем

DSAsign(n,n,m,e,0,0,r,s)

Возвращенное значение r и есть шифротекст. Дешифрирование RSA является точно таким же. Если d - закрытый ключ, то

DSAsign(n,n,m,d,0,0,r,s)

возвращает открытый текст как значение r. Безопасность DSA

С 512 битами DSA недостаточно надежен для длительной безопасности, но он вполне надежен при 1024 б и-тах. В своем первом заявлении на эту тему NSA так комментировало утверждение Джо Эбернети (Joe Aber-nathy) из The Houston Chronic/e по поводу лазейки в DSS [363]:

Что касается предполагаемой лазейки в DSS. Мы считаем, что термин "лазейка" вводит в заблуждение, так он предпол а-гает, что через лазейку можно как-то расшифровать (прочитать) зашифрованные сообщения, подписываемые с помощью DSS, без разрешения отправителя.

DSS не шифрует никаких данных. По сути вопросом является, не может ли кто-то при помощи DSS подделать подпись, и, таким образом, дискредитировать всю систему. Мы категорически заявляем, что вероятность, что кто-нибудь - включая NSA -сможет подделать подпись DSS, при правильном использовании стандарта бесконечно мала.

Более того, предположение о чувствительности к лазейке справедливо для любой системы проверки подлинности с открытыми ключами, включая RSA. утверждение, что это влияет только на DSS (аргумент, популярный в прессе), полностью неверно. Вопрос в реализации и способе выбора простых чисел. Мы призываем вас уделить внимание недавней конференции EUROCRYPT, где "за круглым столом" обсуждался вопрос лазеек в DSS. Одним из участников обсуждения был один из исследователей из Bellcore, утверждавший о возможности лазейки, и по нашему пониманию участники дискуссии - включая этого исследователя из Bellcore - пришли к выводу, что вопрос о лазейке в DSS не представляет проблемы. Более того, всеми было признано, что вопрос о лазейке является тривиальным и был раздут прессой . Однако, пытаясь по просьбе NIST ответить на обвинение о лазейке, мы разработали процесс генерации простых чисел, позволяющий избежать выбора одного из относ и-тельно небольшого числа слабых простых чисел, использование которых ослабляет DSS. Кроме того, NIST настаивает на использовании модулей большей длины, вплоть до 1024, что позволяет не пользоваться разработанным процессом генерации простых чисел, избегая слабых простых чисел. Очень важным дополнительным моментом, на который часто не обращают внимание, является то, что при использовании DSS простые числа обедосшииы и, следовательно, могут быть предметом открытого изучения. Не все системы с открытыми ключами способны пройти подобную проверку .

Целостность любой системы защиты информации требует обратить внимание на реализацию. Учитывая уязвимость си с-тем с миллионами равноправных пользователей, NSA по традиции настаивает на использовании централизованных довере н-ных центров как на способе минимизировать риск в системе. Хотя мы по просьбе NIST и разработали ряд технических модификаций DSS, позволяющих реализовать менее централизованный подход, все же нужно выделить ту часть объявления о DSS в Federal Register, в которой говорится:

"Хотя этот стандарт должен обеспечить общие требования безопасности генерации цифровых подписей , соответствие стандарту не обеспечивает безопасность конкретной реализации. Ответственное лицо в каждом департаменте или управл е-нии должно гарантировать, что общая реализация гарантирует приемлемый уровень безопасности . NIST продолжит работу с правительственными пользователями, обеспечивая правильность реализ аций."

Наконец мы изучили все утверждения о небезопасности DSS, и они нас не убедили. DSS был тщательно изучен в NSA, что позволило нашему Директору по безопасности информационных систем разрешить использовать этот стандарт для по д-писи несекретных данных, обрабатываемых в определенных разведывательных системах, и даже для подписи секретных да н-ных в ряде систем. Мы считаем, что подобное признание свидетельствует о невозможности какого-либо вероятного вскрытия безопасности, обеспечиваемой DSS при его правильных реализации и использовании. Основываясь на требованиях правительства США к технике и безопасности цифровых подписей, мы считаем, что DSS является лучшим выбором. В действительности, DSS выступает в качестве пилотного проекта Системы защиты сообщений (Defense Message System), призванного гарантировать подлинность электронных сообщений для жизненно важных команд и контрольной информации . Эта начальная демонстрация включает участие Комитета начальников штабов , военных служб и оборонных ведомств и проводится в кооперации с NIST.

Я не собираюсь комментировать истинность заявления NSA. Принимать его на вру или нет - зависит от в а-шего к нему отношения.

Вскрытия к

Для каждой подписи нужно новое значение k, которое должно выбираться случайным образом . Если Ева узнает k, которое Алиса использовала для подписи сообщения, может быть воспользовавшись некоторыми сво й-ствами генератора случайных чисел, который выдает k, она сможет раскрыть закрытый ключ Алисы, x. Если Ева добудет два сообщения, подписанных с помощью одного и того же k, то, даже не зная значение k, она сможет раскрыть x. А с помощью x Ева сможет тайно подделывать подпись Алисы. В любой реализации DSA для безопасности системы очень важен хороший генератор случайных чисел [1468].

Опасности общего модуля

Хотя DSS не определяет применение пользователями общего модуля, различные реализации могут воспол ь-зоваться такой возможностью. Например, Налоговое управление рассматривает использование DSS для электронной налогов. Что если эта организация потребует, чтобы все налогоплательщики страны использовали о б-щие p и q? Общий модуль слишком легко становится мишенью для криптоанализа . Пока слишком рано обсуждать различные реализации DSS, но причины для беспокойства есть.