Применение эллиптических кривых в криптографии. Жданов О.Н - 5 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

Составители: 

Рубрика: 

Рис. 1. Примеры геометрического построения суммы точек эллиптической кривой
Теперь мы покажем, почему существует в точности еще одна точка, в которой пря-
мая
l, проходящая через Р и Q, пересекает кривую; заодно мы выведем формулу для коор-
динат этой третьей точки и тем самым – для координат
Р+Q.
Обозначим
(
)
11
, yx
,
()
22
, yx
и
(
)
33
, yx – координаты точек P, Q и P+Q соответст-
венно. Мы хотим выразить
3
x и
3
y через
211
,, xyx
и
2
y
.
Предположим, что мы находимся в ситуации п. 3 определения операции сложения
точек, и пусть
β
α
+= xy
есть уравнение прямой, проходящей через Р и Q (в этой ситуа-
ции она не вертикальна). Тогда
(
)
(
)
1212
xxyy
−
−
=
α
и
11
xy
α
β
−
=
. Точка на l, т. е. точка
()
β
α
+xx, , лежит на эллиптической кривой тогда и только тогда, когда
(
)
baxxx ++=+
3
2
βα
.
Таким образом, каждому корню кубического многочлена
()
baxxx +++−
2
3
βα
со-
ответствует точка пересечения. Мы уже знаем, что имеется два корня
1
x
и
2
x
, так как
()
β
α
+
11
, xx и
()
β
α
+
22
, xx – точки Р и Q на кривой. Так как сумма корней нормированно-
го многочлена (т.е. многочлена, старший коэффициент которого равен 1) равна взятому с
обратным знаком коэффициенту при второй по старшинству степени многочлена, то в
нашем случае третий корень – это
21
2
3
xxx −−=
α
. Тем самым получаем выражение для
3
x , и, следовательно, Р + Q =
(
)()
β
+
33
, axx , или, в терминах
11
, yx ,
22
, yx :
,
21
2
12
12
3
xx
xx
yy
x −−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
−
= (4)
()
.
31
12
12
13
xx
xx
yy
yy −
−
−
+−=
Ситуация в п. 5 аналогична рассмотренной, только теперь
α
– производная dxdy
в точке Р. Дифференцирование неявной функции, заданной уравнением (1), приводит к
формуле
(
)
1
2
1
2/3 yax +=
α
, и мы получаем следующие формулы для координат удвоенной
точки:
1
2
1
2
1
3
2
2
3
x
y
ax
x −
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
+
= , (5)
()
31
1
2
1
13
2
3
xx
y
ax
yy −
+
+−= .
Пример 2
. Пусть Р = (-3, 9) и Q = (-2, 8) – точки на эллиптической кривой
xxy 36
32
−= . Найти Р + Q и 2Р.

Страницы