Хотя DSS не определяет применение пользователями общего модуля, различные реализации могут воспол ь-зоваться такой возможностью. Например, Налоговое управление рассматривает использование DSS для электронной налогов. Что если эта организация потребует, чтобы все налогоплательщики страны использовали о б-щжр и ql Общий модуль слишком легко становится мишенью для криптоанализа . Пока слишком рано обсуждать различные реализации DSS, но причины для беспокойства есть.
Подсознательный канал в DSA
Гус Симмонс (Gus Simmons) открыл в DSA подсознательный канал [1468, 1469] (см. раздел 23.3). Этот подсознательный канал позволяет встраивать в подпись тайное сообщение, которое может быть прочитано только тем, у кого есть ключ. Согласно Симмонсу, это "замечательное совпадение", что "все очевидные недостатки подсознательных каналов, использующих схему ElGamal, могут быть устранены" в DSS, и что DSS "на сегодня обеспечивает наиболее подходящую среду для подсознательных коммуникаций ". NIST и NSA не комментировали этот подсознательный канал, никто даже не знает, догадывались ли они о такой возможности . Так как этот подсознательный канал позволяет при недобросовестной реализации DSS передавать с каждой подписью часть закрытого ключа. Никогда на пользуйтесь реализацией DSS, если вы не доверяете разработчику реализации.
Патенты
Дэвид Кравиц (David Kravitz), ранее работавший в NSA, владеет патентом DSA [897]. Согласно NIST [538]:
NIST в интересах общества стремится сделать технологию DSS доступной бесплатно по всему миру. Мы считаем, что эта технология может быть запатентована, и что никакие другие патенты не применимы к DSS, но мы не можем дать твердых гарантий этого до получения патента.
Несмотря на это, три владельца патентов утверждают, что DSA нарушает их патенты: Diffie-Hellman (см. раздел 2.2.1) [718], Merkle-Hellman (см. раздел 19.2.) [720] и Schnorr (см. раздел 21.3) [1398]. Патент Schnorr является источником наибольших сложностей. Срок действия двух других патентов истекает 1997 году, а патент Schnorr действителен до 2008 года. Алгоритм Schnorr был разработан не на правительственные деньги. В отличие от патентов РКР у правительства США нет прав на патент Schnorr, и Шнорр запатентовал свой алгоритм по всему миру. Даже если суды США вынесут решение в пользу DSA, неясно, какое решение примут суды в других странах. Сможет ли международная корпорация принять стандарт, который законен в одних странах и н а-рушает патентное законодательство в других? Нужно время, чтобы решить эту проблему, к моменту написания этой книги этот вопрос не решен даже в Соединенных Штатах .
В июне 1993 года NIST предложил выдать РКР исключительную патентную лицензию на DSA [541]. Соглашение провалилось после протестов общественности и стандарт вышел в свет без всяких соглашений . NIST заявил [542]:
• . . NIST рассмотрел заявления о возможном нарушении патентов и сделал вывод, что эти заявления несправедливы .
Итак стандарт официально принят, в воздухе пахнет судебными процессами , и никто не знает, что делать. NIST заявил, что он поможет защититься людям, обвиненным в нарушении патентного законодательства при использовании DSA в работе по правительственному контракту. Остальные, по видимому, должны заботиться о себе сами. Проект банковского стандарта, использующего DSA, выдвинут ANSI [60]. NIST работает над введением стандарта DSA в правительственном аппарате. Shell Oil сделала DSA своим международным стандартом. О других предложенных стандартах DSA мне неизвестно.
20.2 Варианты DSA
Этот вариант делает проще вычисления, необходимые для подписи, не заставляя вычислять к-1 [1135]. Все используемые параметры - такие же, как в DSA. Для подписи сообщения т Алиса генерирует два случайных числа, kud, меньшие q. Процедура подписи выглядит так
r = (gk mod p) mod q
s = (Щт) + xr) * d mod q
t = kd mod q
Боб проверяет подпись, вычисляя
w = t/s mod q
щ = (Щт) * w) mod q
u2 = (rw) mod q
Если r = ((g"> *y"2) mod/;) mod q, то подпись правильна.
Следующий вариант упрощает вычисления при проверке подписи [1040, 1629]. Все используемые параметры - такие же, как в DSA. Для подписи сообщения т Алиса генерирует случайное число к, меньшее q. Процедура подписи выглядит так
r = (gk mod p) mod q
s = k{H{m) + xrylmod q
Боб проверяет подпись, вычисляя
Mi = {Щт) *s) mod q
щ = (sr) mod 4
Если г = ((gu> *j/"2) mod/;) mod ?, то подпись правильна.
Еще один вариант DSA разрешает пакетную проверку, Боб может проверять подписи пакетами [1135]. Если все подписи правильны, то работа Боба закончена. Если одна из них неправильна, то ему еще нужно понять, какая. К несчастью, это небезопасно. Либо подписывающий, либо проверяющий может легко создать набор фальшивых подписей, который удовлетворяет критерию проверки пакета подписей [974].
Существует также вариант генерации простых чисел для DSA, который включает q и используемые для генерации простых чисел параметры внутрь р. Влияет ли эта схема на безопасность DSA, все еще неизвестно.
(1) Выберем произвольную последовательность, по крайней мере, 160 битов и назовем ее S. Пусть g - это длина S в битах.
(2) Вычислим U = SHA(S) © SHA((S + 1) mod 2s), где SHA описан в разделе 18.7.
(3) Образуем q, установив наибольший и наименьший значащие биты U в 1.
(4) Проверим, является ли q простым.
(5) Пустьр - это объединение q, S, С и SHA(S ). С представляет собой 32 нулевых бита.
(6) р=р-(р mod q)+l.
(7) p=p+q.
(8) Если С вр равно 0x7fffffff, вернемся на этап (1).
(9) Проверим, является ли р простым.
(10) Если р - составное, вернемся на этап (7).
Преимуществом этого варианта является то, что вам не нужно хранить значения С и S, использованные для генерации/; и q. Они включены в состав р. Для приложений, работающих в условиях нехватки памяти, напр и-мер, для интеллектуальных карточек, это может быть важно .
20.3 Алгоритм цифровой подписи ГОСТ
Это русский стандарт цифровой подписи, Официально называемый ГОСТ Р 34.10-94 [656]. Алгоритм очень похож на DSA, и использует следующие параметры
р = простое число, длина которого либо между 509 и 512 битами, либо между 1020 и 1024 битами.
q = простое число - множитель р-l, длиной от 254 до 256 битов.
а = любое число, меньшее р-, для которого а" тойр = 1.
х — число, меньшее q.
y^cfmod p.
Этот алгоритм также использует однонаправленную хэш-функцию : Щх). Стандарт определяет использование хэш-функции ГОСТ Р 34.1 1-94 (см. раздел 18.1 1), основанной на симметричном алгоритме ГОСТ (см. раздел 14.1) [657].
Первые три параметра,/;, qua, открыты и могут использоваться совместно пользователями сети . Закрытым ключом служит х, а открытым - у. Чтобы подписать сообщение т
(1) Алиса генерирует случайное число к, меньшее q
(2) Алиса генерирует / — (a* mod p) mod q s — (ct + k(H(m))) mod q r = (/mod/;) mod<7
s = (xr + k(H(m))) mod q
Если Щт) mod q =0, то значение хэш-функции устанавливается равным 1. Если г =0, то выберите другое значение к и начните снова. Подписью служат два числа: г mod 2256 и s mod 2256, Алиса посылает их Бобу.
(3) Боб проверяет подпись, вычисляя
v = tf(mr2 mod<7
zi = (sv) mod q
z2 = ((?-r)*v) mod 4
и = ((aZl *yZ2) mod/?) mod <?
Если и = г, то подпись правильна.
Различие между этой схемой и DSA в том, что в DSA s = {кл (Я(от) + xr)) mod q, что дает другое уравнение проверки. Любопытно, однако, что длина q равна 256 битам. Большинству западных криптографов кажется достаточным q примерно 160 битов длиной. Может быть это просто следствие русской привычки играть в сверхбезопасность.
Стандарт используется с начала 1995 года и не закрыт грифом "Для служебного пользования", что бы это не значило.
20.4 Схемы цифровой подписи с использованием дискретных логарифмов
Схемы подписи ElGamal, Schnorr (см. раздел 21.3) и DSA очень похожи. По сути, все они являются тремя примерами общей схемы цифровой подписи, использующей проблему дискретных логарифмов . Вместе с тысячами других схем подписей они являются частью одного и того же семейства [740, 741, 699, 1184].
Выберем р, большое простое число, и q, равное либо р-, либо большому простому множителю р-. Затем выберем g, число между 1 up, для которого gq = 1 (mod/;). Все эти числа открыты, и могут быть совместно использованы группой пользователей. Закрытым ключом является х, меньшее q. Открытым ключом служит y =gx mod q.
Чтобы подписать сообщение от, сначала выберем случайное значение к, меньшее q и взаимно простое с ним. Если q тоже простое число, то будет работать любое к, меньшее q. Сначала вычислим
r = gk mod p
Обобщенное уравнение подписипримет вид
ak = b + cx mod q
Коэффициенты а,Ьис могут принимать различные значения. Каждая строка 16th предоставляет шесть возможностей. Проверяя подпись, получатель должен убедиться, что
ra = g»yc mod p
Это уравнение называется уравнением проверки.