Алгоритм Нидеррейтера (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,), определяется как
Vn(P,l) = PV„.1(P,l)- V„.2(P,1)
Теория чисел Лукаса достаточно велика, и я ее пропущу. Теория последовательностей Лукаса хорошо изложена в [1307, 1308]. Особенно хорошо математика LUC описана в [1494, 708].
В любом случае для генерации пары открытый ключ/закрытый ключ сначала выбираются два больших числа/; и q. Вычисляется и, произведение р и q. Ключ шифрования е - это случайное число, взаимно простое с р-, q-, p+ и q+l. Существует четыре возможных ключа дешифрирования,
d = eAmod (ROK(p+l), (q+l)))
d = eAmod (ROK(p+l), (q-l))) d = eAmod (ROK(p-l), (q+l)))
d = eAmod (ROK(p-l), (q-l)))
где НОК означает наименьшее общее кратное.
Открытым ключом являются dun; закрытым ключом - eun. puq отбрасываются.
Для шифрования сообщения Р (Р должно быть меньше п) вычисляется
С = Ve(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 году, эти алгоритмы несомненно являются очень интересными.