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

  • 06 апр. 2012 г.
  • 3146 Слова
КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ



6.1. Введение
В этой главе мы рассмотрим одно из новых направлений криптогра¬фии с открытыми ключами — системы на эллиптических кривых. Эллиптические кривые давно изучались в математике, но их исполь¬зование в криптографических целях было впервые предложено Коб-лицом (Neal Koblitz) и Миллером (Victor Miller) в 1985 году. Пят¬надцать лет интенсивныхисследований этих систем подтвердили их полезные свойства и привели к открытию множества эффективных методов их реализации. С 1998 года использование эллиптических кривых для решения криптографических задач, таких, как цифро¬вая подпись, было закреплено в стандартах США ANSI Х9.62 и FIPS 186-2, а в 2001 году аналогичный стандарт, ГОСТ Р34.10-2001, был принят и в России.
Основное достоинствокриптосистем на эллиптических кривых состоит в том, что по сравнению с «обычными» криптосистемами, которые мы рассматривали в предыдущих главах, они обеспечива¬ют существенно более высокую стойкость при равной трудоемкости или, наоборот, существенно меньшую трудоемкость при равной стой¬кости. Это объясняется тем, что для вычисления обратных функ¬ций на эллиптических кривых известны только алгоритмы сэкспо¬ненциальным ростом трудоемкости, тогда как для обычных систем предложены субэкспоненциальные методы. В результате тот уровень стойкости, который достигается, скажем, в RSA при использовании 1024-битовых модулей, в системах на эллиптических кривых реали¬зуется при размере модуля 160 бит, что обеспечивает более простую как программную, так и аппаратную реализацию.
Детальное изучение эллиптических кривыхтребует знаний выс¬шей алгебры, в особенности алгебраической геометрии. Мы, однако, постараемся изложить материал без привлечения сложных алгебра¬ических конструкций и в объеме, достаточном для понимания принципов построения и работы соответствующих криптосистем. Более подробное изложение теории эллиптических кривых и их использо¬вания в криптографии может быть найдено, например, в [20, 27, 36].6.2. Математические основы
Кривая третьего порядка Е, задаваемая уравнением вида
Е: Y2 = X3 + aX + b, (6.1)
называется эллиптической кривой (на самом деле уравнение (6.1) получено путем замены переменных из более общего уравнения, ко¬торое нас не будет интересовать).
Поскольку Y = ± , график кривой симметричен относительно оси абсцисс. Чтобы найти точки его пересечения с осью абсцисс,необходимо решить кубическое уравнение
Х3 + аХ + b = 0. (6.2)
Это можно сделать с помощью известных формул Кардано. Дискри¬минант этого уравнения


(6.3)

Если D < 0, то (6.2) имеет три различных действительных корня α,β,γ; если D = 0, то (6.2) имеет три действительных корня, скажем, α,β, β, по крайней мере два из которых равны; наконец, если D > 0, уравнение (6.2) имеет одиндействительный корень α и два комплексно сопряженных. Вид кривой во всех трех случаях представлен на рисунках 6.1—6.3.
Кривая, представленная на рис. 6.2, называется сингулярной. В ее точке сингулярности (/3,0) имеются две касательные. Сингу¬лярные кривые мы будем исключать из нашего рассмотрения. По¬этому при задании кривой с помощью параметров а и b потребуем выполнения условия D≠0, что эквивалентно условию
4а3+ 27b2 ≠ 0. (6.4)
Итак, пусть эллиптическая кривая Е задана уравнением (6.1) с ограничением на коэффициенты (6.4). Определим операцию компо¬зиции точек на кривой. Возьмем какие-либо две точки Р = (x1,y1),





Q = (x2,y2) € Е и проведем через них прямую (рис. 6.4). Эта прямая обязательно пересечет кривую в третьей точке, которую обозначим через R'. (Третья точка обязательно существует.Дело в том, что ку¬бическое уравнение, получаемое после подстановки уравнения пря¬мой в (6.1), имеет два действительных корня, соответствующих точ¬кам Р и Q, следовательно, его третий корень, соответствующий R', также действителен.) Точку R = (x3,y3) получим путем изменения знака ординаты точки R'. Будем обозначать описанную операцию композиции точек следующим образом: R = Р...
tracking img