Другие алгоритмы, основанные на линейных кодах, исправляющих ошибки

Алгоритм Нидеррейтера (Niederreiter) [1167] очень близок к алгоритму МакЭлиса и считает, что открытый ключ - это случайная матрица проверки четности кода, исправляющего ошибки. Закрытым ключом служит эф­фективный алгоритм декодирования этой матрицы.

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

синдрома [1501], пояснения см. в [306]. Алгоритм [1621], использующий коды, исправляющие ошибки, небезо­пасен [698, 33, 31, 1560, 32].

19.8 Криптосистемы с эллиптическими кривыми

Эллиптические кривые изучались многие годы, и по этому вопросу существует огромное количество литер а-туры. В 1985 году Нил Коблиц (Neal Koblitz) и B.C. Миллер (V. S. Miller) независимо предложили использовать их для криптосистем с открытыми ключами [867, 1095]. Они не изобрели нового криптографического алгорит­ма, использующего эллиптические кривые над конечными полями, но реализовали существующие алгоритмы, подобные Diffie-Hellman, с помощью эллиптических кривых.

Эллиптические кривые вызывают интерес, потому что они обеспечивают способ конструирования "элементов" и "правил объединения", образующих группы. Свойства этих групп известны достаточно хорошо, чтобы использовать их для криптографических алгоритмов, но у них нет определенных свойств, облегчающих криптоанализ. Например, понятие "гладкости" неприменимо к эллиптическим кривым. То есть, не существует такого множества небольших элементов, используя которые с помощью простого алгоритма с высокой вероя т-ностью можно выразить случайный элемент. Следовательно, алгоритмы вычисления дискретного логарифма показателя степени не работают work. Подробности см. в [1095].

Особенно интересны эллиптические кривые над полем GF(2"). Для п в диапазоне от 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 Mtiller) и Вил-фрид Нобауер (Wilfried Nobauer) используют полиномы Диксона (Dickson) [1127, 1128, 965]. Рудольф Лидл (Rudolph Lidl) и Мюллер обобщили этот подход в [966, 1126] (этот вариант назван схемой Reidi), и Нобауер проанализировал его безопасность в [1172, 1173]. (Соображения по поводу генерации простых чисел с помо­щью функций Лукаса (Lucas) можно найти в [969, 967, 968, 598].) Несмотря на все предыдущие разработки группе исследователей из Новой Зеландии удалось запатентовать эту схему в 1993 году, назвав ее LUC [1486, 521, 1487].

и-ое число Лукаса, V„{P,\), определяется как

V_n(P,l) = PV„.₁(P,l)- V„.₂(P, 1)

Теория чисел Лукаса достаточно велика, и я ее пропущу. Теория последовательностей Лукаса хорошо изло­жена в [1307, 1308]. Особенно хорошо математика LUC описана в [1494, 708].

В любом случае для генерации пары открытый ключ/закрытый ключ сначала выбираются два больших чис­ла/; и q. Вычисляется и, произведение р и q. Ключ шифрования е - это случайное число, взаимно простое с р-\, q-\, p+\ и q+l. Существует четыре возможных ключа дешифрирования,

d = e^Amod (ROK(p+l), (q+l)))

d = e^Amod (ROK(p+l), (q-l))) d = e^Amod (ROK(p-l), (q+l)))

d = e^Amod (ROK(p-l), (q-l)))

где НОК означает наименьшее общее кратное.

Открытым ключом являются dun; закрытым ключом - eun. puq отбрасываются.

Для шифрования сообщения Р (Р должно быть меньше п) вычисляется

С = V_e(P,l) (mod п)

А для дешифрирования:

Р = VJP, 1) (mod я), с соответствующим d

В лучшем случае LUC не безопаснее RSA. А недавние, только что опубликованные результаты показывают, как взломать LUC по крайней мере в нескольких реализациях. Я не доверяю этому алгоритму.

19.10 Криптосистемы с открытым ключом на базе конечных автоматов

Китайский криптограф Тао Ренжи разработал алгоритм с открытым ключом, основанный на использовании конечных автоматов [1301, 1302, 1303, 1300, 1304, 666]. Такой же сложной задачей, как и разложение на мно­жители произведения двух больших простых чисел, является задача разложения на составляющие произведения двух конечных автоматов. Это тем более верно, если один из автоматов нелинеен.

Большая часть работы в этой области была выполнена в Китае в 80-х годах и опубликована на китайском языке. Ренжи начал писать по английски. Его главным результатом было то, что обратное значение некоторых нелинейных (квазилинейных) автоматов является слабым тогда и только тогда, когда эти автоматы обладают определенной ступенчатой матричной структурой. Это свойство исчезает, если они объединены с другим авто­матом (хотя бы линейным). В алгоритме с открытым ключом секретный ключ является инвертируемым квази­линейным автоматом, а соответствующий открытый ключ может быть получен с помощью их почленного пер е-множения. Данные шифруются, проходя через линейный автомат, а дешифрируются, проходя через обратные значения компонентов алгоритма (в некоторых случаях автоматы должны быть установлены в подходящее н а-чальное значение). Эта схема работает и для шифрования, и для цифровых подп исей.

О производительности таких систем вкратце можно сказать следующее: они, как и система МсЕНесе, намно­го быстрее RSA, но требуют использования более длинных ключей. Длина ключа, обеспечивающая, как дума­ют, безопасность, аналогичную 512-битовому RSA, равна 2792 битам, а 1024-битовому RSA - 4152 битам. В первом случае система шифрует данные со скоростью 20869 байт/с и дешифрирует данные со скоростью17117 байт/с, работая на 80486/33 МГц.

Ренжи опубликовал три алгоритма. Первым был FAPKC0. Эта слабая система использует линейные компо­ненты и, главным образом, является иллюстративной. Каждая из двух серьезных систем, FAPKC1 и FAPKC2, использует один линейный и один нелинейный компонент. Последняя сложнее, она была разработана для под­держки операции проверки подлинности.

Что касается их надежности, в Китае немало занимались этой проблемой (где сейчас свыше 30 институтов, публикующих работы по криптографии и безопасности). Из достаточного количества источников на китайском языке можно видеть, что проблема была изучена.

Привлекательной особенностью FAPKC1 и FAPKC2 является то, что они не ограждены никакими патентами США. Следовательно, так как срок действия патента на алгоритм Diffie-Hellman истекает в 1997 году, эти алго­ритмы несомненно являются очень интересными.