Анимация
JavaScript
|
Главная Библионтека Скорости EIGamal для различных длин модулей при 160-битовом показателе степени (на SPARC II)
Патенты ElGamal незапатентован. Но, прежде чем двигаться вперед и реализовывать алгоритм, нужно знать, что PKP считает, что этот алгоритм попадает под действие патента Диффи-Хеллмана [718]. Однако срок действия патента Диффи-Хеллмана заканчивается 29 апреля 1997 года, что делает ElGamal первым криптографическим плго-ритмом с открытыми ключами, пригодным для шифрования и цифровых подписей и несвязанным в Соедине н-ных Штатах патентами. Я не могу дождаться этого момента. 19.7 McEliece В 1978 году Роберт МакЭлис (Robert McEliece) разработал криптосистему с открытыми ключами на основе теории алгебраического кодирования [1041]. Этот алгоритм использует существование определенного класса исправляющих ошибки кодов, называемых кодами Гоппа (Goppa). Он предлагал создать код Гоппа и замаскировать его как обычный линейный код. Существует быстрый алгоритм декодирования кодов Гоппа, но общая проблема найти слово кода по данному весу в линейном двоичном коде является NP-полной. Хорошее описание этого алгоритма можно найти в [1233], см. также [1562]. Ниже приведен только краткий обзор. Пусть dH(x,y) обозначает расстояние Хэмминга между x и y. Числа n, k и t служат параметрами системы. Закрытый ключ состоит из трех частей: G - это матрица генерации года Гоппа, исправляющего t ошибок. P -это матрица перестановок размером n*n. S - это nonsingular матрица размером k*k. Открытым ключом служит матрица G размером k*n: G = SGP. Открытый текст сообщений представляет собой строку k битов в виде k-элементного вектора над полем GF(2). Для шифрования сообщения случайным образом выбирается n-элементный вектор z над полем GF(2), для которого расстояние Хэмминга меньше или равно t. c = otG + z Для дешифрирования сообщения сначала вычисляется c = cP-1. Затем с помощью декодирующего алгоритма для кодов Гоппа находится от , для которого dH(OTG,c) меньше или равно t. Наконец вычисляется от = otS1. В своей оригинальной работе МакЭлис предложил значения n = 1024, t = 50 и k = 524. Это минимальные значения, требуемые для безопасности. Хотя этот алгоритм был одним из первых алгоритмов с открытыми ключами, и вне появлялось публикаций о его успешном криптоаналитическом вскрытии, он не получил широкого признания в криптографическом с о-обществе. Схема на два-три порядка быстрее, чем RSA, но у нее есть ряд недостатков. Открытый ключ огромен: 219 битов. Сильно увеличивается объем данных - шифротекст в два раза длиннее открытого текста . Ряд попыток криптоанализа этой системы можно найти в [8, 943, 1559, 306]. Ни одна из них не достигла успеха для общего случая, хотя сходство между алгоритмом МакЭлиса и алгоритмом рюкзака немного волнует. В 1991 два русских криптографа заявили, что взломали систему МакЭлиса с некоторыми параметрами [882]. В их статье это утверждение не было обосновано , и большинство криптографов не приняли во внимание этот результат. Еще одно выполненное русскими вскрытие, которое нельзя непосредственно использовать против системы МакЭлиса, описано в [1447, 1448]. Расширения McEliece можно найти в [424, 1227, 976]. Другие алгоритмы, основанные на линейных кодах, исправляющих ошибки Алгоритм Нидеррейтера (Niederreiter) [1167] очень близок к алгоритму МакЭлиса и считает, что открытый ключ - это случайная матрица проверки четности кода, исправляющего ошибки . Закрытым ключом служит эффективный алгоритм декодирования этой матрицы . Другой алгоритм, используемый для идентификации и цифровых подписей, основан на декодировании синдрома [1501], пояснения см. в [306]. Алгоритм [1621], использующий коды, исправляющие ошибки, небезопасен [698, 33, 31, 1560, 32]. 19.8 Криптосистемы с эллиптическими кривыми Эллиптические кривые изучались многие годы, и по этому вопросу существует огромное количество литер а-туры. В 1985 году Нил Коблиц (Neal Koblitz) и В.С. Миллер (V. S. Miller) независимо предложили использовать их для криптосистем с открытыми ключами [867, 1095]. Они не изобрели нового криптографического алгоритма, использующего эллиптические кривые над конечными полями, но реализовали существующие алгоритмы, подобные Diffie-Hellman, с помощью эллиптических кривых. Эллиптические кривые вызывают интерес, потому что они обеспечивают способ конструирования "элементов" и "правил объединения", образующих группы. Свойства этих групп известны достаточно хорошо, чтобы использовать их для криптографических алгоритмов , но у них нет определенных свойств, облегчающих криптоанализ. Например, понятие "гладкости" неприменимо к эллиптическим кривым. То есть, не существует такого множества небольших элементов, используя которые с помощью простого алгоритма с высокой вероя т-ностью можно выразить случайный элемент. Следовательно, алгоритмы вычисления дискретного логарифма показателя степени не работают work. Подробности см. в [1095]. Особенно интересны эллиптические кривые над полем GF(2n). Для 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 Muller) и Вил-фрид Нобауер (Wilfried Nobauer) используют полиномы Диксона (Dickson) [1127, 1128, 965]. Рудольф Лидл (Rudolph Lidl) и Мюллер обобщили этот подход в [966, 1126] (этот вариант назван схемой Reidi), и Нобауер проанализировал его безопасность в [1172, 1173]. (Соображения по поводу генерации простых чисел с помощью функций Лукаса (Lucas) можно найти в [969, 967, 968, 598].) Несмотря на все предыдущие разработки группе исследователей из Новой Зеландии удалось запатентовать эту схему в 1993 году, назвав ее LUC [1486, 521, 1487]. n-ое число Лукаса, Кп(Р,1), определяется как Vn(P,1) = PVn-1(P,1)- Vn-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 = Ve(P,1) (mod n) А для дешифрирования: P = Vd(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 году, эти алгоритмы несомненно являются очень интересными . 0 1 2 3 4 5 6 7 8 9 10 11 [ 12 ] 13 14 15 16 17 |