4.3 Криптографические системы на основе эллиптических алгоритмов
Эллиптические кривые изучались многие годы, и по этому вопросу существует огромное количество литературы. В 1985 году Нил Коблиц (Neal Koblitz) и В. Миллер (V. S. Miller) независимо предложили использовать их для криптосистем с открытыми ключами. Они не изобрели нового криптографического алгоритма, использующего эллиптические кривые над конечными полями, но реализовали существующие алгоритмы, подобные Diffie-Hellman, с помощью эллиптических кривых.
Эллиптические кривые вызывают интерес, потому что они обеспечивают способ конструирования "элементов" и "правил объединения", образующих группы. Свойства этих групп известны достаточно хорошо, чтобы использовать их для криптографических алгоритмов, но у них нет определенных свойств, облегчающих криптоанализ. Например, понятие "гладкости" неприменимо к эллиптическим кривым, то есть, не существует такого множества небольших элементов, используя которые с помощью простого алгоритма с высокой вероятностью можно выразить случайный элемент. Следовательно, алгоритмы вычисления дискретного логарифма показателя степени не работают. Особенно интересны эллиптические кривые над полем GF(2). Для n в диапазоне от 130 до 200 несложно разработать схему и относительно просто реализовать арифметический процессор для используемого поля. Эллиптические алгоритмы потенциально могут послужить основой для более быстрых криптосистем с открытыми ключами и меньшими размерами ключей. С помощью эллиптических кривых над конечными полями могут быть реализованы многие алгоритмы с открытыми ключами, такие как Diffie-Hellman, EIGamal и Schnorr. Соответствующая математика сложна и не будет здесь приводится.
Алгоритм Fast Elliptic Encryption (FEE, быстрое эллиптическое шифрование) компании Next Computer Inc. также использует эллиптические кривые. Приятной особенностью FEE является то, что закрытый ключ может быть любой легко запоминающейся строкой. Используются также и криптосистемы, использующие гиперэллиптические кривые.
Эллиптические кривые - математический объект, который может определен над любым полем (конечным, действительным, рациональным или комплексным). В криптографии обычно используются конечные поля. Эллиптическая кривая есть множество точек (x,y), удовлетворяющее следующему уравнению:
y2 = x3 + ax + b,
а также бесконечно удаленная точка. Для точек на кривой довольно легко вводится операция сложения, которая играет ту же роль, что и операция умножения в криптосистемах RSA и Эль-Гамаля.
В реальных криптосистемах на базе эллиптических уравнений используется уравнение
y2 = x3 + ax + b mod p,
где р - простое.
Проблема дискретного логарифма на эллиптической кривой состоит в следующем: дана точка G на эллиптической кривой порядка r (количество точек на кривой) и другая точка Y на этой же кривой. Нужно найти единственную точку x такую, что Y = xG, то есть Y есть х-я степень G.
Используемый в ECC алгоритм является конкурентом по отношению к другим асимметричным алгоритмам шифрования, так как при эквивалентной стойкости он использует ключи меньшей длины и имеет большую производительность.
Криптосистема ECC гораздо более эффективна, чем другие системы с открытыми ключами. Ее производительность приблизительно на порядок выше, чем производительность RSA, Диффи-Хеллмана и DSA.