<< Предыдущая

стр. 9
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Касательные служат для удвоения точек (используя хорду, не­
льзя сложить точку с собой). Пусть Р — произвольная точка эл­
липтической кривой (рис. 2.2). Проведем касательную к кривой в
точке Р. Она пересечет кривую еще в какой-то одной точке R (ку­
бическая кривая пересекается с прямой по трем точкам с учетом
кратности пересечения). Отразив R относительно горизонтальной
оси, мы получим точку [2]Р = Р + Р. Вертикальная касательная в
точке Р «пересекает» кривую в бесконечно удаленной точке. В этой
ситуации Р + Р = О и говорят, что Р — точка порядка 2.
Глава 2. Эллиптические кривые

Можно показать, что метод хорд и касательных наделяет элли­
птическую кривую структурой абелевой группы с бесконечно уда­
ленной точкой в качестве единичного элемента, т. е. нуля. Опреде­
ление операций можно легко перенести на случай общей эллипти­
ческой кривой, заданной длинной формой Вейерштрасса (в частно­
сти, характеристика поля может быть любой). Необходимо только
заменить отражение относительно оси абсцисс на симметрию отно­
сительно прямой
Y = aiX -f аз.




Рис. 2.2. Удвоение точек на эллиптической кривой

В дополнение к сказанному приведем алгебраические формулы,
реализующие сложение точек по методу хорд и касательных. Это
необходимо сделать, поскольку вычерчивание диаграмм в поле ко­
нечной характеристики — дело безнадежное.

Лемма 2.2. Пусть Е — эллиптическая кривая, определяемая урав­
нением
Е: Y^ + aiXY + a^Y = Х^ + а з ^ з + а^Х + ае,
на которой выбраны точки Pi{xi^yi) и Р2{х2',У2)- Точка —Pi имеет
2.2, Групповой закон

координаты
-Pi{xi -у1 -aixi -аз).
Введем коэффициенты
л_ У2 -У1 _ У1Х2 - У2Х1
л— , fi —
Х2 —XI Х2 - XI
при Ж1 7^ а;2 И
_ 3xi + 2a2Xi + а4 — aij/i _ —xf + a4^i + 2ae — a^yi
2yi + aixi + аз ' 2j/i + aixi + аз
если xi = X2-, HO P2 7^ —^1- Если


то ггз и Уз вычисляются по формулам:
жз = А^ + aiA - а2 - Ж1 - Ж2, Уз = -(А + ai)a:3 - /i - аз.

Описанный ранее изоморфизм эллиптических кривых сохраня­
ет структуру группы. Так что на изоморфных кривых указанные
формулы определяют структуры изоморфных абелевых групп.
Фиксируем натуральное число т и обозначим через [т] отобра­
жение кривой на себя, сопоставляющее каждой точке Р ее кратное
[т]Р,, т. е.

т
Это отображение — основа криптографических систем, опираю­
щихся на эллиптическую кривую, поскольку его можно легко вы­
числить, но крайне сложно обратить, т. е. по данным координатам
Р{х^ у) и [т]Р{х\ у') найти т очень трудно. Конечно, наше выска­
зывание о сложности обращения предполагает специальный выбор
эллиптической кривой и соблюдение нескольких других условий, к
чему мы еще вернемся.
Закончим этот параграф иллюстрацией группового закона на
эллиптической кривой. Вновь рассмотрим кривую Е над полем F7,
заданную уравнением (2.2). Оказывается, на этой кривой всего лишь
шесть точек, одна из которых — О, а координаты других предста­
влены списком:
(4,1), (6,6), (5,0), (6,1), (4,6).
Результаты сложения несложно получить по формулам леммы 2.2.
Сведем их в таблицу 2.1. Найдем координаты образов точки Р(4,1)
Глава 2. Эллиптические кривые

при отображении [т] для различных т .
[2]Р(б,б), [5]Р(4,6),
[3]Р(5,0), ЩР = 0.
[4]Р(6,1),
Из вычислений видно, что в нашем примере E{?i) — конечная ци­
клическая группа порядка 6, а точка Р(4,1) — ее образующая. Элли­
птическая кривая над любым конечным полем будет конечной абе-
левой группой, и, что очень удачно, циклической (или близкой к
циклической).

Таблица 2.1. Сложение точек на кривой (2.4) над полем F?
1+ О (4,1) (6,6) (5,0) (6,1) (4,6)
о О (4,1) (6,6) (5,0) (6,1) (4,6)
(4,1) (4,1) (6,6) (5,0) (6,1) (4,6) О
(6,6) (6,6) (5,0) (6,1) (4,6) О (4,1)
(5,0) (5,0) (6,1) (4,6) О (4,1) (6,6)
(6,1) (6,1) (4,6) О (4,1) (6,6) (5,0)
(4,6) (4,6) О (4,1) (6,6) (5,0) (6,1)



2.3. Эллиптические кривые над конечными полями
Как мы уже отмечали, количество F^-рациональных точек эллипти­
ческой кривой конечно. Обозначим его символом #Е{?д). Ожидае­
мое число точек кривой близко к ^ + 1 и можно положить
#EiFg) = q + l - t ,
где «дефект» t называется следом отображения Фробениуса в q,
В хорошо известной теореме Хассе дана оценка порядка группы -B(F^).

Теорема 2.3. (Хассе, 1933.) След отображения Фробениуса удо­
влетворяет неравенству


в примере (2.2) кривая над полем F7 имеет 6 точек. Так что
след отображения Фробениуса здесь равен 2, что, конечно, меньше
2 у ^ = 2 v ^ « 5,29.
На эллиптической кривой Е над полем F^ определено отображе­
ние Фробениуса:
^ : E(F,) - ^ ?;(f,), <^(а;, у) = (^г", у"), <^(С?) = О.
2.3. Эллиптические кривые над конечными полями

Оно сопоставляет точке кривой Е точку на той же кривой, вне за­
висимости от поля, над которым эта точка определена. Кроме того,
отображение Фробениуса сохраняет групповую операцию, т. е.
<p{P + Q) = ip{P)+<piQ).
Другими словами, ср — эндоморфизм группы Е над алгебраическим
замыканием F^, который обычно называют эндоморфизмом Фробе-
ниуса.
Сед отображения Фробениуса и эндоморфизм Фробениуса свя­
заны уравнением:
? ' ' - [ % + Ы = [о],
Т. е. для произвольной точки Р(ж, у) кривой выполнено соотношение
( a ^ ' ' ^ / ) - M ( a : ^ y ' ^ ) + [g](a:,y) = 0 ,
В котором сложение и вычитание — суть групповые операции на
эллиптической кривой. Есть два частных случая криптографически
непригодных эллиптических кривых:
- Кривая E{?q) называется аномальной^ если ее след Фробени­
уса равен 1, т.е. ij^E{Fq) = q. Эта кривая особенно неудобна,
когда q — простое число.
- Кривая E{?q) называется суперсингулярной^ если характери­
стика р поля F^ делит след отображения Фробениуса t. Таких
кривых также стараются избегать в криптографии. При q = р
суперсингулярная кривая насчитывает р + 1 точку, поскольку
t = О в этом случае. Если же q = р^ ^ то t у суперсингулярных
кривых может принимать значения
при нечетном / : t = О, t^ = 2д и t^ = 3^';
при четном / : t^ = 4^, t^ = q^ если р = 1 (mod3); и ^ = О,
если р ^ 1 (mod 4).
Выбирая кривую А^ЛЯ шифрования, нужно стремиться к тому,
чтобы число ее точек делилось на достаточно большое простое чи­
сло. В связи с этим необходимо научиться вычислять порядок груп­
пы Е{?д),
Известно, что порядок произвольной группы E{?q) над любым
полем вычисляется за полиномиальное время. Это делается с помо-
ш;ью сложного алгоритма, который мы не можем объяснить в этой
книге. Достаточно запомнить, что вычисление порядка группы воз­
можно как в теоретическом, так и в практических планах. В следу­
ющих главах, рассматривая алгоритмы решения задачи о дискрет-
Глава 2. Эллиптические кривые

ных логарифмах, мы увидим, что информация о порядке группы
очень суш;ественна для оценки стойкости протокола, основанного
на соответствуюш;ей кривой.
Одним из достоинств эллиптических кривых является то, что
они доставляют большое число возможных групп. Можно менять
как основное поле, так и коэффициенты уравнения кривой. Наконец,
отыскать эллиптическую кривую с хорошими криптографическими
свойствами ^ля создания безопасного протокола, относительно легко.
Как было отмечено ранее, случаи char iC = 2, 3 требуют дополни­
тельных усилий. Реализация криптографических систем, основан­
ных на эллиптической кривой, базируется на поле ?2^^, чья характе­
ристика равна 2, или на поле Fp с большим простым числом р. Поэто­
му в конце текущей главы мы сконцентрируем внимание на полях
характеристики 2 и р > 3, опустив случай chbxK = 3. Большин­
ство обш;их рассуждений с некоторой модификацией переносится
на случай характеристики три, что хорошо освеш;ено в специальной
литературе.

2.3.1. Кривые над полем характеристики р > 3
Пусть основное поле JFC = F^ с g = р^, где р > 3 — простое число
и п ^ 1. Как уже отмечалось, уравнение кривой над таким полем
можно представить в виде короткой формы Вейерштрасса
Е: Г^ = Х^ -f аХ + й. (2.3)
Ее дискриминант равен А = — 16(4а^ + 27Ь'^)^ а j-инвариант —
j{E) = —1728(4а)^/Д. Формулы из леммы 2.2, описываюп1;ие груп­
повой закон, также упрош;аются: —Pi = (^i, —yi) и, если Рз(^з? Уз) =
= Pi + Р2 ^ О^ то координаты жз? Уз вычисляются так:
Хз = Х^ - XI - Х2, Уз = {Xl - Хз)Х - УЪ

где при х\ф Х2
У2 - У 1
Х=

а при х\ — Х2, У\ф^
3x1 + а
Х=
2У1


2.3.2. Кривые над полем характеристики 2
Здесь мы ограничимся конечными полями F^ с ^ = 2^ при п ^ 1.
В этом случае ^'-инвариант кривой Е вычисляется по формуле
2.4' Проективные координаты

j{E) = а Р / А . Условие j{E) = О, т.е. ai = О, в характеристике 2
равносильно суперсингулярности кривой Е. Мы уже отмечали, что
суперсингулярные кривые — очень специфический случай, который
не используется в криптографии. Поэтому будем предполагать, что
КЕ) ф 0.
В этих предположениях представитель любого класса изомор­
физма эллиптических кривых над F^ записывается уравнением
^: Г^ + Х Г = Х^ + а^Х^ + ае, (2.4)
где «б G F* и а2 G {0,7}- Здесь 7 — фиксированный элемент поля
F^, удовлетворяющий соотношению: Тг^|2(7) = 1? где Тг^|2 — абсо­
лютный след, вычисляющийся по формуле

п-\


г=0
Когда характеристика поля равна 2, формула ]\319L противополож­
ного элемента эллиптической кривой из леммы 2.2 преобразуется к
виду - P i = (Ж1,у1 + хх) и, если Рз = (^з,Уз) = Pi + Р2 7^ О, то
жз = А^ + Л -h а2 + ^1 + Х2,
Уз = (А + \)хг + /i = (ж1 + ггз)А + жз + Уъ
где при х\ф Х2
л _ У2 + У1 _ У1Х2 + У2Х1
л— , /i — 5
Х2 -\- XI Ж2 + Xi
а если х\— Х2ф О, то

Хх



2.4. Проективные координаты
Одна из проблем, возникающих при использовании формул груп­
пового закона как при большой, так и при четной характеристике
поля, связана с необходимостью деления. Деление в конечном поле
считается дорогой операцией, т. к. включает в себя некий вариант
расширенного алгоритма Евклида, который хотя и имеет приблизи­
тельно ту же сложность, что и умножение, однако обычно не может
быть реализован достаточно эффективно.
Во избежание операции деления применяют проективные коор­
динаты. При этом уравнение эллиптической кривой записывается
Глава 2, Эллиптические кривые

через три координаты (X, У, Z) вместо двух (X, У). Однако вместо
стандартного варианта уравнения кривой, который был приведен в
начале главы, используется уравнение вида
Е: у2 + aiXYZ + агУ^^ = Х^ + a2X'^Z'^ + a^XZ^ + a^Z^,
Точка на бесконечности здесь также имеет координаты (0,1,0), но
переход от проективных координат к аффинным осуществляется по
правилу
(X,y,Z)H^(X/Z2,y/Z3).
Выбор таких проективных координат обусловлен стремлением сде­
лать арифметические операции более эффективными.

2.4.1. Болыпая характеристика
Формулы сложения точек эллиптической кривой, заданной уравне­
нием
у2 = Х^ + aXZ'^ + ЬZ^
над полем большой характеристики выглядят теперь как


где тройка координат (Хз,Уз,^з) вычисляется последовательно по
правилу:
Ai = X\Z\, А2 = X2Z1,
A3 = Ai - А2, А4 = YiZ^,
A5 = Y2Zf, Аб = A4 - Аз,
A? = Ai + A2, Ag = A4 + A5,
Zs = Z1Z2A3, Xs = XQ — A7A3,
A9 = ArAi - 2X3, Уз = (АдАб - A8Ai)/2.

<< Предыдущая

стр. 9
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>