Математические основы защиты информации. Ишмухаметов Ш.Т - 99 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 100
5.7. ”Скрученные” кривые и метод Монтгомери
Одним из чрезвычайно полезных понятий в эллиптической факторизации
является понятие скрученной кривой (см.[14], p.329).
Определение. Пусть E(F )– эллиптическая кривая над полем F ,
заданная уравнением Вейерштрассе
y
2
= x
3
+ Cx
2
+ Ax + B,
и g – ненулевой элемент F , тогда квадратичным кручением кривой E
относительно элемента g называется эллиптическая кривая над полем F ,
заданная уравнением
gy
2
= x
3
+ Cx
2
+ Ax + B (5.59)
Заменой переменных X = gx, Y = g
2
y , эта кривая преобразуется к
кривой обычного вида
Y
2
= X
3
+ gCX
2
+ g
2
AX + g
3
B (5.60)
Будем изучать скрученную кривую, заданную уравнением (5.59).
Питер Монгтомери предложил рассматривать точки на скрученных кривых
с пропущенной координатой Y . Рассмотрим его идею первоначально для
афинных координат. Пусть P
1
(x
1
, y
1
) и P
2
(x
2
, y
2
)– точки кривой (5.59) такие,
что P
1
̸= ±P
2
. Обозначим через x
+
, x
−
x–координаты точек P
1
+P
2
и P
1
−P
2
соответственно. Следующая теорема была доказана П. Монтгомери в ([30])
и переформулирована для скрученных координат Кренделом и Померансом
([14], c.329).
Теорема. (Монтгомери [30], p.260). Пусть эллиптическая кривая EC
задана уравнением
gy
2
= x
3
+ Cx
2
+ Ax + B, (5.61)
точки P
1
(x
1
, y
1
), P
2
(x
2
, y
2
) принадлежат EC , а координаты x
+
, x
−
определены как раньше. Тогда при x
1
̸= x
2
выполняется следующая формула
x
+
· x
−
=
(x
1
x
2
− A)
2
− 4B(x
1
+ x
2
+ C)
(x
2
− x
1
)
2
(5.62)
Глава 3. Эллиптические кривые                                                 100

5.7. ”Скрученные” кривые и метод Монтгомери
Одним из чрезвычайно полезных понятий в эллиптической факторизации
является понятие скрученной кривой (см.[14], p.329).
       Определение. Пусть E(F )– эллиптическая кривая над полем F ,
заданная уравнением Вейерштрассе

                           y 2 = x3 + Cx2 + Ax + B,

и g – ненулевой элемент F , тогда квадратичным кручением кривой E
относительно элемента g называется эллиптическая кривая над полем F ,
заданная уравнением
                           gy 2 = x3 + Cx2 + Ax + B                         (5.59)
       Заменой переменных X = gx, Y = g 2 y , эта кривая преобразуется к
кривой обычного вида

                       Y 2 = X 3 + gCX 2 + g 2 AX + g 3 B                   (5.60)

       Будем изучать скрученную кривую, заданную уравнением (5.59).
Питер Монгтомери предложил рассматривать точки на скрученных кривых
с пропущенной координатой Y . Рассмотрим его идею первоначально для
афинных координат. Пусть P1 (x1 , y1 ) и P2 (x2 , y2 )– точки кривой (5.59) такие,
что P1 ̸= ±P2 . Обозначим через x+ , x− x–координаты точек P1 +P2 и P1 −P2
соответственно. Следующая теорема была доказана П. Монтгомери в ([30])
и переформулирована для скрученных координат Кренделом и Померансом
([14], c.329).
       Теорема. (Монтгомери [30], p.260). Пусть эллиптическая кривая EC
задана уравнением

                   gy 2 = x3 + Cx2 + Ax + B,                                (5.61)

точки P1 (x1 , y1 ), P2 (x2 , y2 ) принадлежат EC , а координаты x+ , x−
определены как раньше. Тогда при x1 ̸= x2 выполняется следующая формула
                             (x1 x2 − A)2 − 4B(x1 + x2 + C)
                   x+ · x− =                                                (5.62)
                                        (x2 − x1 )2

Страницы