Подсознательный канал в 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 был разработан не на правительственные деньги. В отличие от патентов PKP у правительства США нет прав на патент Schnorr, и Шнорр запатентовал свой алгоритм по всему миру. Даже если суды США вынесут решение в пользу DSA, неясно, какое решение примут суды в других странах. Сможет ли международная корпорация принять стандарт, который законен в одних странах и н а-рушает патентное законодательство в других ? Нужно время, чтобы решить эту проблему, к моменту написания этой книги этот вопрос не решен даже в Соединенных Штатах .

В июне 1993 года NIST предложил выдать PKP исключительную патентную лицензию на DSA [541]. Соглашение провалилось после протестов общественности и стандарт вышел в свет без всяких соглашений . NIST заявил [542]:

• . . NIST рассмотрел заявления о возможном нарушении патентов и сделал вывод, что эти заявления несправедливы .

Итак стандарт официально принят, в воздухе пахнет судебными процессами , и никто не знает, что делать. NIST заявил, что он поможет защититься людям, обвиненным в нарушении патентного законодательства при использовании DSA в работе по правительственному контракту. Остальные, по видимому, должны заботиться о себе сами. Проект банковского стандарта, использующего DSA, выдвинут ANSI [60]. NIST работает над введением стандарта DSA в правительственном аппарате. Shell Oil сделала DSA своим международным стандартом. О других предложенных стандартах DSA мне неизвестно.

20.2 Варианты DSA

Этот вариант делает проще вычисления, необходимые для подписи, не заставляя вычислять к-1 [1135]. Все используемые параметры - такие же, как в DSA. Для подписи сообщения m Алиса генерирует два случайных числа, k и d, меньшие q. Процедура подписи выглядит так

r = (gk mod p) mod q

s = (H(m) + xr) * d mod q

t = kd mod q

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

w = t/s mod q

"1 = (H(m) * w) mod q

"2 = (rw) mod q

Если r = ((g"1 * j"2) mod p) mod q, то подпись правильна.

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

r = (gk mod p) mod q

s = k (H(m) + xr)-1 mod q

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

u1 = (H(ot) *s) mod q

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

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

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

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

(2) Вычислим U = SHA(S) © SHA((S + 1) mod 2g), где SHA описан в разделе 18.7.

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

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

(5) Пусть p - это объединение q, S, C и SHA(S ). C представляет собой 32 нулевых бита.

(6) p=p-(p mod q)+l.

(7) /;=/;+q.

(8) Если C в p равно 0x7fffffff, вернемся на этап (1).

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

(10) Если p - составное, вернемся на этап (7).

Преимуществом этого варианта является то, что вам не нужно хранить значения C и S, использованные для генерации p и q. Они включены в состав p. Для приложений, работающих в условиях нехватки памяти, напр и-мер, для интеллектуальных карточек, это может быть важно .

20.3 Алгоритм цифровой подписи ГОСТ

Это русский стандарт цифровой подписи, Официально называемый ГОСТ Р 34.10-94 [656]. Алгоритм очень похож на DSA, и использует следующие параметры

p = простое число, длина которого либо между 509 и 512 битами, либо между 1020 и 1024 битами.

q = простое число - множитель p-1, длиной от 254 до 256 битов.

a = любое число, меньшее /7-1, для которого aq mod p = 1.

x = число, меньшее q.

y = ax mod p.

Этот алгоритм также использует однонаправленную хэш-функцию : H(x). Стандарт определяет использование хэш-функции ГОСТ Р 34.1 1-94 (см. раздел 18.1 1), основанной на симметричном алгоритме ГОСТ (см. раздел 14.1) [657].

Первые три параметра, p, q и a, открыты и могут использоваться совместно пользователями сети . Закрытым ключом служит x, а открытым - y. Чтобы подписать сообщение т

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

(2) Алиса генерирует I = (a* mod p) mod q s = (ct + k(H(OT))) mod q r = (ak mod p) mod q

s = (xr + k(H(OT))) mod q

Если H(ot) mod q =0, то значение хэш-функции устанавливается равным 1. Если r =0, то выберите другое значение k и начните снова. Подписью служат два числа: r mod 2256 и s mod 2256, Алиса пос1лает их Бобу.

(3) Боб проверяет подпись, вычисляя v = H(OT)q-2 mod q

z1 = (sv) mod q

z2 = ((q-r)*v) mod q

" = ((aZ1 * ) mod p) mod q

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

Различие между этой схемой и DSA в том, что в DSA s = (k-1 (H(m) + xr)) mod q, что дает другое уравнение проверки. Любопытно, однако, что длина q равна 256 битам. Большинству западных криптографов кажется достаточным q примерно 160 битов длиной. Может быть это просто следствие русской привычки играть в сверхбезопасность.

Стандарт используется с начала 1995 года и не закрыт грифом "Для служебного пользования", что бы это не значило.

20.4 Схемы цифровой подписи с использованием дискретных логарифмов

Схемы подписи ElGamal, Schnorr (см. раздел 21.3) и DSA очень похожи. По сути, все они являются тремя примерами общей схемы цифровой подписи, использующей проблему дискретных логарифмов . Вместе с тысячами других схем подписей они являются частью одного и того же семейства [740, 741, 699, 1184].

Выберем /7, большое простое число, и q, равное либо /7-1, либо большому простому множителю /7-1. Затем выберем g, число между 1 и p, для которого gq = 1 (mod p). Все эти числа открыты, и могут быть совместно использованы группой пользователей. Закрытым ключом является *, меньшее q. Открытым ключом служит y =gx mod q.

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

r = gk mod p

Обобщенное уравнение подписи примет вид ak = b + mod q

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

ra = gbyc mod p

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

Табл. 20-4. Возможные перестановки a, b и c

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

Табл. 20-5.

Схемы цифровой подписи с использованием дискретных логарифмов

Уравнение подписи Уравнение проверки

(1) rks+m* mod q rr =gsym mod p

(2) rkm+s* mod q rr =gmys mod p

(3) sk= r+m* mod q rs=grym mod p