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

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

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

Особенно интересны эллиптические кривые над полем GF(2ⁿ). Для 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].

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 по крайней мере в нескольких реализациях. Я не доверяю этому алгоритму.