Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
подобные Diffie-Hellman, с помощью эллиптических кривых. Эллиптические кривые вызывают интерес, потому что они обеспечивают способ конструирования "элементов" и "правил объединения", образующих группы . Свойства этих групп известны достаточно хорошо, чтобы использовать их для криптографических алгоритмов , но у них нет определенных свойств, облегчающих криптоанализ. Например, понятие "гладкости" неприменимо к эллиптическим кривым . То есть, не существует такого множества небольших элементов, используя которые с помощью простого алгоритма с высокой вероя т- ностью можно выразить случайный элемент . Следовательно, алгоритмы вычисления дискретного логарифма показателя степени не работают work. Подробности см. в [1095]. Особенно интересны эллиптические кривые над полем GF(2 n ). Для n в диапазоне от 130 до 200 несложно разработать схему и относительно просто реализовать арифметический процессор для используемого поля . Та- кие алгоритмы потенциально могут послужить основой для более быстрых криптосистем с открытыми ключами и меньшими размерами ключей. С помощью эллиптических кривых над конечными полями могут быть реал и- зованы многие алгоритмы с открытыми ключами , такие как Diffie-Hellman, EIGamal и Schnorr. Соответствующая математика сложна и выходит за рамки этой книги . Интересующимся этой темой я пред- лагаю прочитать две вышеупомянутые работы и отличную книгу Альфреда Менезеса ( Alfred Menezes) [1059]. Эллиптические кривые используются двумя аналогами RSA [890, 454]. Другими работами являются [23, 119, 1062, 869, 152, 871, 892, 25, 895, 353, 1061, 26, 913, 914, 915]. Криптосистемы с ключами небольшой длины на базе эллиптических кривых рассматриваются в [701]. Алгоритм Fast Elliptic Encryption (FEE, быстрое эллипти- ческое шифрование) компании Next Computer Inc. также использует эллиптические кривые [388]. Приятной особенностью FEE является то, что закрытый ключ может быть любой легко запоминающейся строкой . Предла- гаются и криптосистемы, использующие гиперэллиптические кривые [868, 870, 1441, 1214]. 19.9 LUC Некоторые криптографы разработали обобщенные модификации RSA, которые используют различные пере- становочные многочлены вместо возведения в степень . Вариант, называющийся Kravitz-Reed и использующий неприводимые двоичные многочлены [898], небезопасен [451, 589]. Винфрид Мюллер (Winfried Mьller) и Вил- фрид Нобауер (Wilfried Nцbauer) используют полиномы Диксона (Dickson) [1127, 1128, 965]. Рудольф Лидл (Rudolph Lidl) и Мюллер обобщили этот подход в [966, 1126] (этот вариант назван схемой Rйidi), и Нобауер проанализировал его безопасность в [1172, 1173]. (Соображения по поводу генерации простых чисел с пом о- щью функций Лукаса (Lucas) можно найти в [969, 967, 968, 598].) Несмотря на все предыдущие разработки группе исследователей из Новой Зеландии удалось запатентовать эту схему в 1993 году, назвав ее LUC [1486, 521, 1487]. n-ое число Лукаса, V n (P,1), определяется как V n (P,1) = PV n-1 (P,1)- V n-2 (P,1) Теория чисел Лукаса достаточно велика, и я ее пропущу. Теория последовательностей Лукаса хорошо изл о- жена в [1307, 1308]. Особенно хорошо математика LUC описана в [1494, 708]. В любом случае для генерации пары открытый ключ/закрытый ключ сначала выбираются два больших чис- ла p и q. Вычисляется n, произведение p и q. Ключ шифрования e - это случайное число, взаимно простое с p-1, q-1, p+1 и q+1. Существует четыре возможных ключа дешифрирования , d = e -1 mod (НОК(p+1), (q+1))) d = e -1 mod (НОК(p+1), (q-1))) d = e -1 mod (НОК(p-1), (q+1))) d = e -1 mod (НОК(p-1), (q-1))) где НОК означает наименьшее общее кратное . Открытым ключом являются d и n; закрытым ключом - e и n. p и q отбрасываются. Для шифрования сообщения P (P должно быть меньше n) вычисляется C = V e (P,1) (mod n) А для дешифрирования: P = V d (P, 1) (mod n), с соответствующим d В лучшем случае LUC не безопаснее RSA. А недавние, только что опубликованные результаты показывают, как взломать LUC по крайней мере в нескольких реализациях . Я не доверяю этому алгоритму. 19.10 Криптосистемы с открытым ключом на базе конечных автоматов Китайский криптограф Тао Ренжи разработал алгоритм с открытым ключом, основанный на использовании конечных автоматов [1301, 1302, 1303, 1300, 1304, 666]. Такой же сложной задачей, как и разложение на мн о- жители произведения двух больших простых чисел, является задача разложения на составляющие произведения двух конечных автоматов. Это тем более верно, если один из автоматов нелинеен . Большая часть работы в этой области была выполнена в Китае в 80-х годах и опубликована на китайском языке. Ренжи начал писать по английски. Его главным результатом было то, что обратное значение некоторых нелинейных (квазилинейных) автоматов является слабым тогда и только тогда, когда эти автоматы обладают определенной ступенчатой матричной структурой . Это свойство исчезает, если они объединены с другим авт о- матом (хотя бы линейным). В алгоритме с открытым ключом секретный ключ является инвертируемым квази- линейным автоматом, а соответствующий открытый ключ может быть получен с помощью их почленного пер е- множения. Данные шифруются, проходя через линейный автомат, а дешифрируются, проходя через обратные значения компонентов алгоритма (в некоторых случаях автоматы должны быть установлены в подходящее н а- чальное значение). Эта схема работает и для шифрования, и для цифровых подп исей. О производительности таких систем вкратце можно сказать следующее: они, как и система McEliece, намно- го быстрее RSA, но требуют использования более длинных ключей . Длина ключа, обеспечивающая, как дум а- ют, безопасность, аналогичную 512-битовому RSA, равна 2792 битам, а 1024-битовому RSA - 4152 битам. В первом случае система шифрует данные со скоростью 20869 байт/с и дешифрирует данные со скоростью17117 байт/с, работая на 80486/33 МГц. Ренжи опубликовал три алгоритма. Первым был FAPKC0. Эта слабая система использует линейные комп о- ненты и, главным образом, является иллюстративной . Каждая из двух серьезных систем, FAPKC1 и FAPKC2, использует один линейный и один нелинейный компонент . Последняя сложнее, она была разработана для по д- держки операции проверки подлинности. Что касается их надежности, в Китае немало занимались этой проблемой (где сейчас свыше 30 институтов, публикующих работы по криптографии и безопасности ). Из достаточного количества источников на китайском языке можно видеть, что проблема была изучена . Привлекательной особенностью FAPKC1 и FAPKC2 является то, что они не ограждены никакими патентами США. Следовательно, так как срок действия патента на алгоритм Diffie-Hellman истекает в 1997 году, эти алго- ритмы несомненно являются очень интересными . Глава 20 Алгоритмы цифровой подписи с открытым ключом 20.1 Алгоритм цифровой подписи (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 - это алгоритм, а 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]. Алгоритм использует следующие параметры : p = простое число длиной L битов, где L принимает значение, кратное 64, в диапазоне от 512 до 1024. (В первоначальном стандарте размер p был фиксирован и равен 512 битам [1149]. Это вызвало множество крити- ческих замечаний, и NIST этот пункт алгоритма [1154].) q = 160-битовой простое число - множитель p-1. g = h (p-1)/q mod p, где h - любое число, меньшее p-1, для которого h (p-1)/q mod p больше 1. x = число, меньшее q. y = g N mod p. В алгоритме также используется однонаправленная хэш-функция : H(m). Стандарт определяет использование SHA, рассмотренного в разделе 18.7. Первые три параметра, p, q и g, открыты и могут быть общими для пользователей сети . Закрытым ключом является x, а открытым - y. Чтобы подписать сообщение, m: (1) Алиса генерирует случайное число k, меньшее q (2) Алиса генерирует r = (g k mod p) mod q s = (k -1 (H(m) + xr)) mod q Ее подписью служат параметры r и s, она посылает их Бобу. (3) Боб проверяет подпись, вычисляя 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, то подпись правильна. Доказательства математических соотношений можно найти в [1154]. 19th представляет собой краткое опи- сание алгоритма. |