Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Табл. 20-1. Подписи DSA Открытый ключ: p простое число длиной от 512 до 1024 битов (может использоваться группой пользователей) q 160-битовый простой множитель p-1 (может использоваться группой пользователей) g = h (p-1)/q mod p, где h - любое число, меньшее p-1, для которого h (p-1)/q mod p > 1 (может использоваться группой пользователей) y = g N mod p (p-битовое число) Закрытый ключ: x < q (160-битовое число) Подпись: k выбирается случайно, меньшее q r (подпись) = (g k mod p) mod q s (подпись) = (k -1 (H(m) + xr)) mod q Проверка: w = s -1 mod q u 1 = (H(m) * w) mod q u 2 = (rw) mod q v = (( g y u u 1 2 * ) mod p) mod q Если v = r, то подпись правильна. Ускоряющие предварительные вычисления В 18-й приведены примеры скорости работы программных реализаций DSA [918]. Табл. 20-2. Скорость DSA для различных длин модулей с 160-битовым показателем степени (на SPARC II) 512 битов 768 битов 1024 бита Подпись 0.20 с 0.43 с 0.57 с Проверка 0.35 с 0.80 с 1.27 с Практические реализации DSA часто можно ускорить с помощью предварительных вычислений . Обратите внимание, что значение r не зависит от сообщения. Можно создать строку случайных значений k, и затем рас- считать значения r для каждого из них. Можно также вычислить k -1 для каждого из этих значений k. Затем, ко- гда приходит сообщение, можно вычислить s для заданных r и k -1 Эти предварительные вычисления заметно ускоряют DSA. В 17-й приведены сравнения времени вычисления DSA и RSA для конкретной реализации интеллектуальной карточки [1479]. Табл. 20-3. Сравнение времени вычислений RSA и DSA DSA RSA DSA с общими p, q, g Глобальные вычисления Off-card (P) N/A Off-card (P) Генерация ключа 14 с Off-card (S) 4с Предварительные вычисления 14 с N/A 4 с Подпись 0.03 с 15 с 0.03 с Проверка 16 с l.5 с 10 с 1-5 с off-card (P) 1-3 с off-card (P) Вычисления вне карточки (off-card) выполнялись на персональном компьютере i80386/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 2 g ), где SHA описан в разделе 18.7. (3) Образуем q, установив наибольший и наименьший значащие биты U в 1. (4) Проверим, является ли q простым. (5) Если q не является простым, то вернемся на этап (1) . (6) Пусть C=0 и N=2. (7) Для k=0,l,...,n, пусть V k =SHA((S+N+k) mod 2 g ) (8) Пусть W - целое число W = V 0 + 2 160 V 1 +. . .+ 2 160(n-1) V n-1 + 2 160 (V n mod 2 b ) и пусть X = W + 2 L-1 Обратите внимание, что X - это L-битовое число. (9) Пусть p = X - ((X mod 2q) - 1). Обратите внимание, что p конгруэнтно 1 mod 2q. (10) Если p < 2 L-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) Задав входные значения p, q, g, k, x и 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 в u, отбросим s. Вызовем DSAsign(p,p,m,1,u,0,r,s) Отбросим r. Возвращенное значение s и будет b в схеме EIGamal. Теперь у вас есть шифротекст, a и b. Де- шифрирование также просто. Используя закрытый ключ x и шифротекст сообщений, a и b, вызовем DSAsign(p,p,a,x,0,0,r,s) Значение r - это a x mod p. Назовем его e. Затем вызовем DSAsign(p,p,1,e,b,0,r,s) Значение s и будет открытым текстом сообщения, m. Этот способ работает не со всеми реализациями DSA - в некоторых из них могут быть зафиксированы зн а- чения p и q или длины некоторых других параметров . Тем не менее, если реализация является достаточно о б- щей, то можно шифровать сообщение, не используя ничего, кроме функции цифровой подписи . Шифрование RSA с DSA Шифрование RSA еще проще. Используя модуль n, сообщение m и открытый ключ 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 Chronicle по поводу лазейки в 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, которое Алиса использовала для подписи сообщения, может быть воспользовавшись некоторыми сво й- ствами генератора случайных чисел, который выдает k, она сможет раскрыть закрытый ключ Алисы, x. Если Ева добудет два сообщения, подписанных с помощью одного и того же k, то, даже не зная значение k, она смо- жет раскрыть x. А с помощью x Ева сможет тайно подделывать подпись Алисы. В любой реализации DSA для безопасности системы очень важен хороший генератор случайных чисел [1468]. Опасности общего модуля Хотя DSS не определяет применение пользователями общего модуля, различные реализации могут воспол ь- зоваться такой возможностью. Например, Налоговое управление рассматривает использование DSS для элек- тронной налогов. Что если эта организация потребует, чтобы все налогоплательщики страны использовали о б- щие p и q? Общий модуль слишком легко становится мишенью для криптоанализа . Пока слишком рано обсуж- дать различные реализации 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 был разработан не на правительственные деньги. В отл и- чие от патентов 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 Этот вариант делает проще вычисления, необходимые для подписи, не заставляя вычислять k -1 [1135]. Все используемые параметры - такие же, как в DSA. Для подписи сообщения m Алиса генерирует два случайных числа, k и d, меньшие q. Процедура подписи выглядит так r = (g k mod p) mod q s = (H(m) + xr) * d mod q t = kd mod q Боб проверяет подпись, вычисляя w = t/s mod q u 1 = (H(m) * w) mod q u 2 = (rw) mod q Если r = (( g y u u 1 2 * ) mod p) mod q, то подпись правильна. Следующий вариант упрощает вычисления при проверке подписи [1040, 1629]. Все используемые парамет- ры - такие же, как в DSA. Для подписи сообщения m Алиса генерирует случайное число k, меньшее q. Процеду- ра подписи выглядит так r = (g k mod p) mod q s = k (H(m) + xr) -1 mod q Боб проверяет подпись, вычисляя u 1 = (H(m) *s) mod q u 2 = (sr) mod q Если r = (( g y u u 1 2 * ) mod p) mod q, то подпись правильна. Еще один вариант DSA разрешает пакетную проверку, Боб может проверять подписи пакетами [1135]. Если все подписи правильны, то работа Боба закончена. Если одна из них неправильна, то ему еще нужно понять, какая. К несчастью, это небезопасно. Либо подписывающий, либо проверяющий может легко создать набор фальшивых подписей, который удовлетворяет критерию проверки пакета подписей [974]. Существует также вариант генерации простых чисел для DSA, который включает q и используемые для ге- нерации простых чисел параметры внутрь p. Влияет ли эта схема на безопасность DSA, все еще неизвестно. (1) Выберем произвольную последовательность, по крайней мере, 160 битов и назовем ее S. Пусть g - это длина S в битах. (2) Вычислим U = SHA(S) ? SHA((S + 1) mod 2 g ), где 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) p=p+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 битами. |