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

Хотя 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 = (g^k mod p) mod q

s = (Щт) + xr) * d mod q

t = kd mod q

Боб проверяет подпись, вычисляя

w = t/s mod q

щ = (Щт) * w) mod q

u₂ = (rw) mod q

Если r = ((g"> *y"²) mod/;) mod q, то подпись правильна.

Следующий вариант упрощает вычисления при проверке подписи [1040, 1629]. Все используемые парамет­ры - такие же, как в DSA. Для подписи сообщения т Алиса генерирует случайное число к, меньшее q. Процеду­ра подписи выглядит так

r = (g^k mod p) mod q

s = k{H{m) + xry^lmod q

Боб проверяет подпись, вычисляя

Mi = {Щт) *s) mod q

щ = (sr) mod 4

Если г = ((g^u> *j/"²) mod/;) mod?, то подпись правильна.

Еще один вариант DSA разрешает пакетную проверку, Боб может проверять подписи пакетами [1135]. Если все подписи правильны, то работа Боба закончена. Если одна из них неправильна, то ему еще нужно понять, какая. К несчастью, это небезопасно. Либо подписывающий, либо проверяющий может легко создать набор фальшивых подписей, который удовлетворяет критерию проверки пакета подписей [974].

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

(1) Выберем произвольную последовательность, по крайней мере, 160 битов и назовем ее S. Пусть g - это длина S в битах.

(2) Вычислим U = SHA(S) © SHA((S + 1) mod 2^s), где 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 2²⁵⁶ и s mod 2²⁵⁶, Алиса посылает их Бобу.

(3) Боб проверяет подпись, вычисляя
v = tf(mr² mod<7

zi = (sv) mod q

z₂ = ((?-r)*v) mod 4

и = ((a^Zl *y^Z2) 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, для которого g^q = 1 (mod/;). Все эти числа открыты, и могут быть совместно ис­пользованы группой пользователей. Закрытым ключом является х, меньшее q. Открытым ключом служит y =g^x mod q.

Чтобы подписать сообщение от, сначала выберем случайное значение к, меньшее q и взаимно простое с ним. Если q тоже простое число, то будет работать любое к, меньшее q. Сначала вычислим

r = g^k mod p

Обобщенное уравнение подписи примет вид

ak = b + cx mod q

Коэффициенты а,Ьис могут принимать различные значения. Каждая строка 16th предоставляет шесть воз­можностей. Проверяя подпись, получатель должен убедиться, что

r^a = g»y^c mod p

Это уравнение называется уравнением проверки.

Табл. 20-4.

Возможные перестановки», бис

(r'= r mod q)

± r' ± s от

± r' m ± s 1

+ г' от + ms 1

± m r' ± r' s 1

± ms ± r' s 1

В 15th перечислены возможные варианты подписи и проверки, полученные только из первой строки воз­можных значений а, Ъ и с без учета эффектов ±.

Табл. 20-5.