Алгоритм цифровой подписи (digital Signature Algorithm, DSA)

В августе 19991 года Национальный институт стандартов и техники (National Institute of Standards and Tech­nology, NIST) предложил для использования в своем Стандарте цифровой подписи (Digital Signature Standard, DSS) Алгоритм цифровой подписи (Digital Signature Algorithm, DSA). Согласно Federal Register [538]:

Предлагается Федеральный стандарт обработки информации (Federal Information Processing Standard, FIPS) для Стандарта цифровой подписи (Digital Signature Standard, DSS). В этом стандарте определяется алгоритм цифровой подписи с открытым ключом (DSA), пригодный для федеральных применений, требующих цифровой подписи. Предложенный DSS использует открытый ключ для проверки получателем целостности полученных данных и личности отправителя. DSS также может быть использован третьей стороной для проверки правил ьности подписи и связанных с ней данных.

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

И:

Предложенный стандарт представляет собой результат оценки различных методик цифровой подписи. Принимая реше­ние, NIST следовал положению раздела 2 Акта о компьютерной безопасности (Computer Security Act) 1987 года о том, что NIST разрабатывает стандарты,"... обеспечивающие рентабельные безопасность и секретность Федеральной информации, выбирая из технологий, предлагающих сравнимую степень защиты, ту, которая обладает наиболее подходящими рабочими и эксплуатационными характеристиками".

Среди факторов, рассмотренных в процессе принятия решения были уровень обеспечиваемой безопасности, простота а п-паратной и программной реализации, простота экспорта за пределы США, применимость патентов, влияние на национал ь-ную безопасность и обеспечение правопорядка, а также степень эффективностикак функции подписи, так и функции прове р-ки. Казалось, что обеспечить соответствующую защиту Федеральным системам можно многими способами. Выбранный удовлетворяет следующим требованиям:

NIST ожидает, что его можно будет использовать бесплатно. Широкое использование этой технологии, обусловленной его доступностью, послужит к экономической выгоде правительства и общества.

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

Прежде, чем все совсем запутается, позвольте мне разобраться с названиями: DSA - это алгоритм, a DSS стандарт. Стандарт использует алгоритм. Алгоритм является частью стандарта.

Реакция на заявление

Заявление NIST вызвало поток критических замечаний и обвинений. К сожалению, они были скорее полити­ческими, чем научными. RSA Data Security, Inc., продающая алгоритм RSA, возглавила критиков DSS. Они требовали, чтобы в стандарт использовался алгоритм RSA. RSADSI получило немало денег за лицензирование алгоритма RSA, и стандарт бесплатной цифровой подписи прямо повлиял бы на самую суть ее коммерческих успехов. (Примечание: DSA необязательно не нарушает патенты, мы рассмотрим эту тему позднее.)

До заявления о принятии алгоритма RSADSI вело компанию против "общего модуля," который, возможно, позволит правительству подделывать подписи. Когда было объявлено, что алгоритм не использует общий мо­дуль, критика была продолжена с других позиций [154], как с помощью писем в NIST, так и с помощью заявле­ний в прессе. (Четыре письма в NIST появилось в [1326]. Читая их, не забывайте, что по крайней мере два авто­ра, Ривест и Хеллман, были финансово заинтересованы в том, чтобы DSS не был принят.)

Многие большие компании, разрабатывающие программное обеспечение, которые уже лицензировали алг о-ритм RSA, также выступили против DSS. В 1982 году правительство попросило предоставить ему алгоритмы с открытым ключом для выбора одного из них в качестве стандарта [537]. После этого в течение девяти лет от NIST не было никаких известий. Такие компании, как IBM, Apple, Novell, Lotus, Northern Telecom, Microsoft, DEC и Sun потратили много денег, реализуя алгоритм RSA. Они не были заинтересованы в потере инвестиций.

Всего к концу первого периода обсуждения(28 февраля 1992 года) NIST получил 109 замечаний. Рассмотрим по порядку критические замечания в адрес DSA.

1. DSA нельзя использовать для шифрования или распределения ключей.

Правильно, но стандарт и не требует наличия этих возможностей. Это стандарт подписи. NIST подготовить стандарт шифрования с открытым ключом. NIST совершает большую ошибку, оставляя американский народ без стандарта шифрования с открытым ключом. По всей вероятности предложенный стандарт цифровой подп и-си будет невозможно использовать для шифрования. (Но оказывается, что возможно - см. раздел 23.3.) Это не означает, что стандарт подписи бесполезен.

2. DSA был разработан NSA, и в алгоритме могут быть специальные лазейки.

Большинство первоначальных комментариев были просто параноидальными: "Отрицание NIST существую­щих алгоритмов без видимых причин не внушает доверия к DSS, а усиливает подозрение, что существует тай­ная программа, стремящаяся позволить NIST и/или NSA вскрывать национальную криптосистему с открытым ключом" [154]. Серьезный вопрос относительно безопасности DSA был задан Аржаном Ленстрой (Arjen Lenstra) и Стюартом Хабером (Stuart Haber) из Bellcore. Он будет рассмотрен ниже.

3. DSA медленнее RSA [800].

Более или менее справедливо. Скорости генерации подписи примерно одинаковы, но проверка подписи с помощью DSA от 10 до 40 раз медленнее. Однако генерация ключей быстрее. Но эта операция неинтересна, пользователь редко применяет ее. С другой стороны проверка подписи - это наиболее частая опер ация.

Проблема критики в том, что существует много способов поиграть параметрами тестирования, добиваясь нужных результатов. Предварительные вычисления могут ускорить генерацию подписи DSA, но они не всегда возможны. Сторонники RSA подбираят числа так, чтобы выделить преимущества своего алгоритма, а сторо н-ники DSA используют свой способ оптимизации. В любом случае компьютеры становятся все быстрее и быст­рее. Хотя разница в скорости и существует, в большинстве прилож ений она не будет заметна.

4. RSA - это стандарт de facto.

Вот два примера подобных жалоб. Письмо Роберта Фоллета (Robert Follett), директора программы стандар­тизации компании IBM [570]:

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

Письмо Леса Шроера (Les Shroyer), вице-презитента и директора компании Motorola [1444]:

У нас должен быть единый, надежный, признанный всеми алгоритм цифровой подписи, который можно использовать по
всему миру как между американскими и неамериканскими объектами, так и между системами компании Motorola и система­
ми других производителей. Отсутствие других жизнеспособных технологий цифровой подписи за последние восемь лет сд е-
лало RSA фактическим стандартом_ Motorola и многие другие компании... вложили в RSA миллионы долларов. Мы со­
мневаемся во взаимодействии и возможности поддержки двух различных стандартов, такое положение приведет к росту рас­
ходов, задержек развертывания и усложнению систем....

Многим компаниям хотелось, чтобы NIST принял ISO 9796, международный стандарт цифровой подписи, использующий RSA [762.]. Хотя это и серьезный аргумент, он недостаточен, чтобы принять международный стандарт в качестве национального. Бесплатный стандарт лучше отвечал бы общественным интересам Соед и-ненных Штатов.

5. Выбор национального алгоритма не был открытым, не было дано достаточно времени для анализа.

Сначала NIST утверждал, что разработал DSA самостоятельно, затем признал помощь NSA. Наконец NIST подтвердил, что NSA является автором алгоритма. Это многих обеспокоило - NSA не внушает людям доверие. Даже так, алгоритм был опубликован и доступен для анализа, кроме того, NIST продлил время анализа и ком­ментирования алгоритма.

6. DSA может нарушать другие патенты. Это так. Этот вопрос будет рассмотрен в разделе, рассматриваю­щим патенты.

7. Размер ключа слишком мал.

Это единственно справедливая критика DSS. Первоначально предлагалось использовать модуль длиной 512 битов [1149]. Так как безопасность алгоритма определяется сложностью вычисления дискретных логарифмов по заданному модулю, этот вопрос волновал многих криптографов. С тех пор вычисление дискретных логариф­мов в конечном поле достигло определенных успехов, и 512 битов слишком мало для долговременной подписи (см. раздел 7.2). Согласно Браяну ЛаМаччиа (Brian LaMacchia) и Эндрю Одлыжко (Andrew Odlyzko), "... даже безопасность, обеспечиваемая 512-битовыми простыми числами, по видимому, находится на пределе... " [934]. В ответ на эти замечания NIST сделал длину ключа переменной, от 512 до 1024 битов. Немного, но все-таки получше.

19 мая 1994 года был издан окончательный вариант стандарта [1154]. При этом было сказано [542]:

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

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

Описание DSA

DSA, представляющий собой вариант алгоритмов подписи Schnorr и EIGamal, полностью описан в [1154].

Алгоритм использует следующие параметры:

р = простое число длиной L битов, где L принимает значение, кратное 64, в диапазоне от 512 до 1024. (В первоначальном стандарте размер р был фиксирован и равен 512 битам [1149]. Это вызвало множество крити­ческих замечаний, и NIST этот пункт алгоритма [1154].)

q = 160-битовой простое число - множитель р-\.

g = hW mod/;, где h - любое число, меньшее р-\, для которого h™ mod/; больше 1.

х — число, меньшее q.

y = g^x mod p.

В алгоритме также используется однонаправленная хэш-функция: Щт). Стандарт определяет использование SHA, рассмотренного в разделе 18.7.

Первые три параметра, р, q и g, открыты и могут быть общими для пользователей сети. Закрытым ключом является х, а открытым - у. Чтобы подписать сообщение, т:

(1) Алиса генерирует случайное число к, меньшее q

(2) Алиса генерирует

r = (g^k mod p) mod q

s = (к^л(Щт) +хг)) mod q

Ее подписью служат параметры г и s, она посылает их Бобу.

(3) Боб проверяет подпись, вычисляя
w = s^l mod q

Mi = (Щт) * w) mod q

u₂ = (rw) mod q

v = ((g^Ul*y^U2) mod p) mod q

Если v = г, то подпись правильна.

Доказательства математических соотношений можно найти в [1154]. 19th представляет собой краткое опи­сание алгоритма.

Табл. 20-1.
________________________________________ Подписи DSA ________________________________________

Открытый ключ:

р простое число длиной от 512 до 1024 битов (может использоваться группой пользователей)

q 160-битовый простой множитель р- 1 (может использоваться группой пользователей)

g = hW mod р, где h - любое число, меньшее р-\, для которого h™ mod p > 1 (может использоваться группой пользователей)

у = g^x mod p (р-битовое число)

Закрытый ключ:
х < q (160-битовое число)

Подпись:

к выбирается случайно, меньшее q

г (подпись) = (g* mod/;) mod q

s (подпись) = (к^Л (Щт) + xr)) mod _?

/7/>оверк«: w = s^Amod q Mi = (Я(от) * w) mod ^ м₂ = (rw) mod ^

v = ((g^u>*y^uz) mod p) mod q

Если v = г, то подпись правильна.