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

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

ОГЛАВЛЕНИЕ

Следующая >>

Парадокс дней рождения позволяет нам оценить, насколько
быстро появится повторение, если производить выборку из ко­
нечного множества.


Дополнительная литература
Бэч и Шаллит — наилучшее известное мне введение в конечные по­
ля и алгоритм Евклида. Эта книга содержит довольно много исто­
рической информации и превосходный указатель важной исследова­
тельской литературы. Предназначенная для специалистов в области
информатики, некоторым она может показаться слишком матема-
тезированной. Более традиционное введение в основы дискретной
математики, сложность которого можно оценить первым курсом
информатики — это учебники Биггса и Розена.
Е. Bach and J. Shallit. Algorithmic Number Theory. Volume 1: Efficient
Algorithms. MIT Press, 1996.
N. L. Biggs. Discrete Mathematics. Oxford University Press, 1989.
K. H. Rosen. Discrete Mathematics and its Applications. McGraw-Hill,
1999.
1.4' Вероятность 51

Контрольные вопросы
1.1.1. Сформулируйте определения группы, кольца и поля.

1.1.2. Почему ненулевые целые числа не образуют группу по умно­
жению?

1.1.3. Почему мы учитываем только ненулевые числа, говоря о ве­
щественных или рациональных числах как о группе по умно­
жению?

1.1.4. Почему множество целых чисел не является полем?

1.1.5. Почему ?p[x]/{f{x)) всегда кольцо?

1.1.6. Чему равно значение функции Эйлера (p{N) при N = р VL
N — р ' q^ где р и g — простые числа?

1.1.7. Дайте определение символа Лежандра и объясните, как его
использовать р^ля выяснения того, является ли данное число
полным квадратом по модулю простого числа р.

1.1.8. Верно ли, что число а по модулю составного п является пол­
ным квадратом, если его символ Якоби относительно п ра­
вен 1?

1.1.9. Сколько раз нужно вытаскивать шарик из ящика с шестьюде­
сятью шариками разного увета (и возвращать его обратно),
пока не попадется цвет, который уже вытаскивали?

Лабораторные работы
1.2.1. Напишите программу (на знакомом Вам языке) для стан­
дартного и двоичного алгоритмов Евклида вычисления ПОД.
Сравните продолжительность их работы, постепенно увели­
чивая их входные данные.

1.2.2. Разработайте программу, реализующую расширенный алго­
ритм Евклида. Сначала используйте стандартное отображе­
ние, сохраняющее ПОД, а затем двоичное.

1.2.3. Реализуйте на компьютере алгоритм вычисления символа Ле­
жандра на основе квадратичного закона взаимности.
Глава 1. Сравнения, группы, конечные поля и вероятность

Упражнения
1.3.1. Покажите, что стандартный и расширенный алгоритмы Ев­
клида могут быть приспособлены р^ля работы с многочлена­
ми.

1.3.2. Напишите аналог двоичного расширенного алгоритма Ев­
клида р^ля многочленов с двоичными коэффициентами. Ис­
пользуя его, вычислите обратный элемент к многочлену
ж^ + ж + 1 в конечном поле F28 = ?2[х]/{х^ + х^ + х^ -\-х+ 1).

1.3.3. Числа Фибоначчи определяются по рекуррентному правилу:
Fo = 0, Fi = 1, Fn+i = F^ + F ^ - i .
Покажите, что если все неполные частные qi^ которые по­
являются в алгоритме Евклида, вычисляющем НОД (а, 6), рав­
ны 1, то а и 6 — соседние числа Фибоначчи.

1.3.4. Пусть п — нечетное число, обладаюш;ее к разными простыми
делителями. Покажите, что число решений уравнения
х^ = \ (modn)
равно 2^.

1.3.5. Докажите, что элемент д ??р является образующей цикличе­
ской группы F* тогда и только тогда, когда р^˜^ = 1 (modp)
=
и д^ ^ 1 (modp) для всех простых делителей q числа р — 1.

1.3.6. Дано составное число N и числа а, Ь, а
1/3^1/5 (modiV). Вы­
числите о
1/3 (modTV) HbV5 (modTV).
1.3.7. Найдите примитивный элемент в каждом из конечных полей
?2п при 1 ^ п ^ 8.
1.3.8. Вычислите символы Якоби ( | ^ ) и (fff), используя лишь кар­
манный калькулятор.
ГЛАВА 2
ЭЛЛИПТИЧЕСКИЕ
КРИВЫЕ


Ц е л и главы
• Рассказать, что такое эллиптическая кривая.
• Выяснить, почему эллиптическая кривая представляет инте­
рес для криптографии.
• Показать, как использование проективных координат повы­
шает скорость вычислений.
• Объяснить, как сжатие точек используется д^ля повышения эф­
фективности вычислений.



2.1. Введение

Эта глава посвяш;ена введению в теорию эллиптических кривых над
конечными полями. Некоторые из наиболее современных криптогра­
фических систем с открытым ключом основаны на использовании
эллиптической кривой, в результате чего они обеспечивают высо­
кую эффективность и большую пропускную способность. Настоя­
щую главу можно пропустить при первом чтении, поскольку мно­
гое из этой книги можно читать, понимая лишь, что эллиптическая
кривая над конечным полем — конечная абелева группа, в которой
можно ставить задачу о вычислении дискретных логарифмов.
Проективная плоскость ?'^{К) над полем К определяется как
множество троек (X, У, Z) не равных одновременно нулю элементов
X^Y^Ze К, на котором введено отношение эквивалентности:
(X, У, Z) - (АХ, АУ, XZ) для любых X е К\
Так, например, две точки (4,1,1) и (5,3,3) эквивалентны в P^(F7).
Класс эквивалентности троек называется проективной точкой.
Эллиптической кривой Е называется множество точек проек­
тивной плоскости, удовлетворяюш;их однородному уравнению Вей-
Глава 2. Эллиптические кривые

ерштрасса
Е : F{X, F, Z) =
= -Х^ + Y^Z + aiXYZ - a2X^Z + asYZ^ - a^XZ^ - a^Z^ = 0,
где ai, a2, «3, a4, ae G A'. Это уравнение также называют длинной
формой Вейерштрасса. Кривая должна быть неособой в том смысле,
что частные производные
дР дР дР
Ъх' W' dz
не должны обращаться в нуль одновременно ни в одной ее точке.
Множество Х-рациональных точек кривой Е^ т. е. точек из Р^(/С),
удовлетворяющих уравнению кривой, обозначается через Е{К). От­
метим, что кривая имеет ровно одну точку, чья координата Z равна
нулю, а именно (0,1,0). Ее принято называть бесконечно удаленной
точкой (или просто точкой на бесконечности) и обозначать сим­
волом О.
Для удобства мы будем часто пользоваться аффинной версией
уравнения Вейерштрасса:
Е: у2 + aiXY -\- asY = Х^ + азХ^ + ОАХ + ае, (2.1)
с Oi Е К.
/С-рациональные точки в аффинном случае — это решения урав­
нения в К^ и бесконечно удаленная точка О. Хотя большинство
протоколов в криптографии используют эллиптическую кривую в
аффинном виде, с точки зрения вычислений бывает удобно перей­
ти к проективным координатам. К счастью, такой переход легко
осуществить:
- точка на бесконечности всегда переходит в бесконечно уда­
ленную точку, как при переходе от аффинных координат к
проективным, так и наоборот;
- проективная точка (X, F, Z) кривой, отличная от бесконечно
удаленной (Z т^ 0), переходит в аффинную точку с координа­
тами ( f , | ) ;
- чтобы найти проективные координаты аффинной точки (X, У),
не лежащей на бесконечности, достаточно выбрать произволь­
ное значение Z G К* и вычислить (X • Z, F • Z, Z).
Как мы увидим, иногда будет удобнее пользоваться слегка моди­
фицированной формой проективной плоскости, когда проективные
координаты (X, F, Z) представляют аффинную точку (X/Z^, Y/Z^),
2.1. Введение

J\RK эллиптической кривой, заданной уравнением (2.1), вводятся
следующие константы, которые будут использованы в дальнейших
формулах:
62 = а\ + 4а2,
^4 = CLicts + 2а4,
Ьв = «3 + 4аб,
bs = ofaG + 4а2аб - aiasa4 + а2а\ - а\,
С4 = Щ- 24^4,
Сб = - Ь | +866264-216Ьб.
Дискриминант кривой J5 определяется по формуле
Д = -Ь^бз - 8Ь1 - 2П1 + 9626465.
Если char К ф2^ 3, то дискриминант можно вычислить и так:


1728
Заметим, что 1728 = 2^3^, так что деление на это число имеет смысл
только в тех полях, чья характеристика отлична от 2 и от 3. Извест­
но, что кривая Е неособа тогда и только тогда, когда Д т^ 0. С этого
момента будем предполагать, что Д ^^ 0.
Для неособых кривых вводится j-инвариант



Рассмотрим пример эллиптической кривой, определенной над полем
Fy, к которому мы часто будем возвращаться:
Е: у2 = Х^ + X + 3. (2.2)
Вычисляя выписанные ранее константы, найдем Д = 3 и j{E) = 5.
Инвариант j тесно связан с понятием изоморфизма эллиптических
кривых. Говорят, что кривая Е с координатами X и Y изоморфна
над полем К кривой Е^ с координатами Х^ и Y^ (обе заданы урав­
нением Вейерштрасса), если найдутся такие константы г^ s, t G К
и и Е К*^ что при замене переменных
X - и'^Х' + г, У = u^Y' + su^X' + t
кривая Е перейдет в кривую Е\ Отметим, что изоморфизм кривых
определен относительно поля К.
Вернемся к нашему примеру, т.е. кривой Е из (2.2) над по­
лем ?j. Сделаем замену переменных с набором констант [и^ г, 5, t] =
Глава 2. Эллиптические кривые

= [2,3,4,5], т.е. положим
Х = 4ХЧЗ и У = У Ч 2 Х ' + 5.

Получим изоморфную кривую, задаваемую уравнением
Е' : У'2 + 4XV + ЗУ' = Х'^ + X ' + 1.
Легко убедиться, что j{E) = j{E') = 5.
Изоморфизм эллиптических кривых является отношением экви­
валентности. Следуюш;ая лемма показывает, что ^-инвариант разде­
ляет классы эквивалентности этого отношения над алгебраическим
замыканием К поля К,

Лемма 2.1. Изоморфные над полем К кривые имеют один и тот
же j-инвариант. С другой стороны, любые кривые с совпадаюш;ими
^-инвариантами изоморфны над алгебраическим замыканием К.
Однако кривые с одним и тем же ^-инвариантом не обязательно
изоморфны над основным полем. Например, jf-инвариант кривой над
полем F j , заданной уравнением
Е" : Y"^ = Х''^ + 4Х" + 4,
равен 5, как и у нашей кривой Е (см. (2.2)). Но эти кривые не изо­
морфны над Fy, поскольку замена переменных, задаюш;ая изомор­
физм, выглядит как
X = ЗХ'' и Y= V6Y'\
Но л/б ^ ?j. Итак, Е и Е^^ определены над полем Fy, но не изоморф­
ны над ним. Эти кривые будут изоморфны над любым алгебраиче­
ским расширением поля Fy, содержаш;им элемент л/б, например, над
полем F72 = F7[A/6].


2.2. Групповой закон

Допустим, что сЪ.а.тК т^ 2, 3 и рассмотрим замену переменных



переводящую кривую, заданную длинной формой Вейерштрасса (2.1),
в изоморфную ей кривую, определяемую короткой формой Вейер­
штрасса
Е: Y^ = Х^ + аХ + Ь
2.2. Групповой закон

при некоторых а., b Е К, На таких представителях классов изоморф­
ных эллиптических кривых можно наглядно ввести групповой закон
методом хорд и касательных.
Сложение точек определяется с помощью хорд (рис. 2.1). Пусть
Р и Q — две точки кривой. Соединим их прямой линией. Она обя­
зательно пересечет кривую в какой-то третьей точке i?, поскольку
мы пересекаем кубическую кривую прямой. Точка R будет опреде­
лена над тем же полем, что сама кривая и исходные точки Р и Q.
Отразим затем точку R относительно горизонтальной оси коорди­
нат и получим точку, определенную над основным полем. Последняя
точка и будет суммой Р + Q.




Рис. 2.1. Сложение точек на эллиптической кривой

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

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

ОГЛАВЛЕНИЕ

Следующая >>