Россия, г. Елабуга эллиптические кривые в криптографии

Эллиптическая кривая определяется уравнением

E ( GF ( q )): y ² + a^xy + a₃y = x ³ + a_ox ² + a₂x + a ₄ (mod p )

^q = ^p - конечное поле с характеристикой p.

Математическое свойство, которое делает эллиптические кривые полезными для криптографии, состоит в том, что если взять две различных точки на кривой, то соединяющая их хорда пересечет кривую в третьей точке (так как мы имеем кубическую кривую). Зеркально отразив эту точку по оси Х, мы получим еще одну точку на кривой (так как кривая симметрична относительно оси X). Если мы обозначим две первоначальных точки как P и Q, то получим последнюю – отраженную – точку P+Q. Это «сложение» удовлетворяет всем известным алгебраическим правилам для целых чисел.

Рис.1. Геометрическая иллюстрация операции сложение точек на ЭК

Эту операцию можно выразить следующими формулами: суммой двух точек

P ( ^ 1 , ^ 1 ) и

Q ⁽ x 2 , У 2 )

является

точка

R ⁽ x 3 , У 3 )

с координатами,

определяемыми следующими соотношениями: x ₃ = 2 ² - x - x ₂ (mod p )

. У з = 2 ( X i — x з ) — У 1 (mod p )

2 = y ²—Л (mod p ) где      ^{x 2 -} x ¹

К точкам, лежащим на ЭК, добавляется еще одна специальная точка 0, которая называется бесконечно удаленной точкой.

Определим на точках ЭК операцию удвоения точки   ^{P (} x i , ^y i ) . Точкой

2P является по определению точка Q ^{( x} 2 , ^y 2 ) , удовлетворяющая уравнениям:

К

х₂ = 2 — 2 X j (mod p )

_ У 2 = 2 ( X i — х 2 ) — У i (mod p )

(**)

2 = 3 X L i a (mod p ) где       ^{2 У 1}

Из этих уравнений видно, что бесконечно удаленная точка 0 может быть получена, как результат удвоения точки Р с нулевой координатой y, либо при сложении двух различных точек с одинаковой координатой x.

Таким образом, мы можем определить конечную абелеву группу на точках кривой, где нулем будет являться бесконечно удаленная точка. В частности если точки P и Q совпадут, то можно вычислить P+P, т.е. 2P. Развивая эту идею, можно определить kP для любого целого числа k, и следовательно, определить значение P и значение наименьшего целого числа k, такого, что kP = F, где F – бесконечно удаленная точка. Теперь можно сформулировать «Проблему дискретного логарифма эллиптической кривой» (Elliptic Curve Discrete Logarithm Problem – ECDLP), на которой основана рассматриваемая система:

Даны базовая точка P и расположенная на эллиптической кривой точка Q=kP. Найти значение k.

Для эллиптических кривых и базовых точек решение таких уравнений представляет вычислительно сложную задачу. С точки же зрения криптографии мы имеем возможность определить новую криптографическую систему на основе эллиптических кривых.

Для каждой эллиптической кривой число точек в группе конечно, но достаточно велико. Оценка порядка (числа элементов) группы точек эллиптической кривой m такова:

p + 1 - 2 Jp <  m <  p + 1 + 2 -jp

, где р — характеристика поля, над которым определена кривая. Если в схеме Эль-Гамаля рекомендуется использовать число р порядка 2512, то в случае эллиптической кривой достаточно взять p > 2255.

Упражнение. Построить абелеву группу точек кривой y x ^{+ 1} (mod 5)

.

В данном примере, а=0 и b=1. Если взять исходную точку P(0; 1), то по формулам (**)

Л = 3 x -(mod5) = 0

^{2 y 1}           , откуда абсцисса т.2P будет

Возьмем поэтому, в качестве исходной точки, координатой x, например, P(2; 2). Имеем:

x i = 2,    X i² = 4,   y i = 2,  2 y i = 4,    ⁽² У 1 ) " ¹ = 4 ⁽mod5)

также точку

равна нулю. с ненулевой

.

По

формулам

(**)

Л = 3 x ² - ( 2 y )^{- 1} (mod5) = 4 • 4(mod5) = 1    x ₂ = Л ² - 2 x ₁ (mod 5) = 1 - 4 (mod 5) = 2

,                                                                                               , y2 = /(x1 — x2)—У1 (mod5) = (2 — 2)—2 (mod5) = 3. Значит,   T.2P=(2,   3).

Найдем теперь т. 3P:

^x 1 = 2, x 2 = ², ^y 1 = ², ^y 2 = ³ . По формулам (*)

Л =(y2 -yi)-(x2 -xi) (mod5) = x', откуда 3P = 0 - бесконечно удаленная точка.