Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 79

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 73 74 75 76 77 78 < 79 > 80 81 82 83 84 85 .. 311 >> Следующая

5.5.1 Групповая операция
Множество Е, определенное соотношениями (5.5.2), представляет собой абе-леву группу с операцией "+", определенной следующим образом.
Определение 5.25 (Операция в группе, порожденной эллиптической кривой ("метод касательных и хорд")). Пусть P,QeE, ? — прямая, соединяющая точки Р и Q (если Р = Q, эта прямая является касательной к Е) и R — точка пересечения прямой ? и кривой Е. Пусть ?' — прямая, соединяющая точки Ru О. Тогда точка Р "+ " Q является такой точкой, что прямая ?' пересекает множество Е в точках R, О и Р "+ " Q.
Допустим на время, что пара {Е,"+") образует группу. Следует объяснить, почему необходимо, чтобы коэффициенты кубического полинома (5.5.1) удовлетворяли условию 4а3 + 27b2^0(modp). Заметим, что величина
4а3 + 27Ь2 4 х 27
является дискриминантом кубического полинома f(x) = х3 + ах + Ь. Если Д = 0, то уравнение f(x) =0 имеет по крайней мере двойной нуль X (корень, удовлетворяющий условию f(X) = 0). Очевидно, что точка (X, 0) лежит на кривой Е. Если F{x, у) = у2 — х3 — ах — Ь = 0 эта точка удовлетворяет условию
9F
OF
дх
= 0.
Иначе говоря, точка (X, 0) является сингулярной точкой, в которой касательная прямая не определена. Следовательно, поскольку операция "+" в точке (X, 0) не определена, множество Е не может быть группой.
Операция "касательная и хорда" продемонстрирована на рис. 5.1. Верхняя половина рисунка относится к ситуации, когда Д < 0 (кубический полином,
208
Часть II. Математические основы
У Г
1 1 —^
R
в - - ¦ ¦< , P"+"Q
Р "+'1Q"+"R = О
_____ 1
/
s ( p,,+„p
S"+"S= о
Рис. 5.1. Операция в группе, порожденной эллиптической кривой
имеющий только один действительный корень), а нижняя — когда Л > 0. Кривые преднамеренно изображены пунктиром, чтобы подчеркнуть, что множество Е(?р) является дискретным. Элементы этого дискретного множества называются Fp-рациональными точками. Их количество конечно (см. соотношение (5.5.6)).
Покажем, что пара (?,"+") образует группу относительно операции "касательная и хорда".
Глава 5. Алгебраические основы
209
Во-первых, применим к любой точке Р = (X, Y) е Е определение 5.25, когда Q = О (поскольку точка О включена в множество Е). Прямая ?, проходящая Через точки Р и О, имеет вид
? : ж = X.
Поскольку из условия Р е Е следует, что число f(X) = X3 + аХ + 6(modp) — квадратичный вычет в поле Fp, число —У является еще одним решением уравнения у2 = f(X) (т.е. другим квадратным корнем полинома f(X) по модулю р). Иначе говоря, прямая ? также проходит через точку R = (X, —Y)eE. Из условия ? = ?' следует, что прямая ?* проходит через те же три точки, что и прямая ?. По определению 5.25 получаем
Р = Р«+"0
для любой точки Р € Е. Более того, для всех точек (ж, у) ЕЕ
(х,уГ+"(х,-у) = 0.
Вводя обозначение (ж,—у) = "—"(ж, у), убеждаемся, что точка О является нулевым элементом относительно операции "+". Следовательно, в паре (Е,"+") выполняются аксиомы тождества и инверсии.
В частном случае у\ = —у2 = 0. В этом варианте Р = "—"Р (точка S на нижней кривой рис. 5.1). В этом весьма частном случае Р"+"Р = О. Иначе говоря, точка Р является элементом порядка 2. Этот вариант уже упоминался ранее: он соответствует решению уравнения у2 = /(ж) = 0(modp). Это решение существует, только если полином /(ж) имеет нули в поле Fp, т.е. является приводимым над полем Fp.
Рассмотрим теперь общий случай, когда прямая ? не является вертикальной. Она задается формулой
?:у-у\ = \{х- ж1), (5.5.3)
где
( У\ ~ У2
xi - ж2 3x1 +а
если х\ ф ж2,
если х\ = жг или yi = угф 0.
(5-5.4)
2yi
Поскольку прямая ? пересекает кривую в точке R = (жз, уз), чтобы ее найти, можно применить формулы (5.5.1) и (5.5.3). Координату ж точки R можно определить, решив уравнение
? П Е : [Л(ж - ж1) + yi]2 - (ж3 + ах + Ь) = 0.
Заметим, что пересечение ? П Е является кубическим полиномом, имеющим нули xi, ж2, жз. Это позволяет записать его уравнение.
?Г\Е : с(ж — ж!)(ж — ж2)(ж — жз) = 0,
210
Часть II. Математические основы
где с — константа. Сравнивая коэффициенты в двух формах записи полинома ?Г)Е (коэффициенты при степенях х3 и х2), получаем, что с = — 1 и
Хз = Л2 - х\ — х2-
В заключение, из определения 5.25 и того факта, что P"+"Q = "—получаем координаты точки P"+"Q:
хз = А2 - xi - х2, ^ 5 ^
Уз = 4^1 - хз) - уи
где число Л определяется формулами (5.5.4). Поскольку прямая ? проходит через точки P,QnR, точка R должна лежать на кривой. Следовательно, точка P"+"Q = = "—"R также должна лежать на кривой. Итак, в паре (Е,"+") выполняется аксиома замыкания.
Аксиому ассоциативности можно проверить, шаг за шагом применяя формулы (5.5.5). Это утомительное упражнение мы предлагаем проделать читателям.
Итак, мы доказали, что пара (Е,"+") является группой. Более того, она является абелевой группой.
Пример 5.20. Уравнение Е : у2 = х3 + 6х + 4 над полем F7 определяет группу, порожденную эллиптической кривой, поскольку 4 х б3 + 27 х 42 = 1 ф 0(mod 7). Группе Е^т) принадлежат следующие точки:
?(F7) = {О, (0,2), (0,5), (1,2), (1,5), (3,0), (4,1), (4,6), (6,2), (6,5)}.
Предыдущая << 1 .. 73 74 75 76 77 78 < 79 > 80 81 82 83 84 85 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed