Эллиптические кривые. Особенности реализации. Разработка лабораторного практикума
Автор работы: Пользователь скрыл имя, 14 Марта 2013 в 19:10, курсовая работа
Краткое описание
Данная курсовая работа призвана помочь студентам в практическом
изучении эллиптических кривых, и особенностей работы с ними.
В первой главе приводятся теоретические сведения об эллиптических
кривых, и алгоритмы работы с ними.
Во второй главе рассматривается описание методов работы с
эллиптическими кривыми в пакете LiDIA, и основное устройство данного
пакета.
В третьей главе содержится собственно лабораторный практикум по
эллиптическим кривым, разработанный при помощи данного пакета.
Содержание
Введение........................................................................................................................3
Глава 1 Общие теоретические сведения об эллиптических кривых
1.1. Сингулярные и несингулярные эллиптические
кривые.....................................................................................................6
1.2. Закон сложения точек эллиптической кривой. Построение
абелевой группы точек эллиптической
кривой......................................................................................................9
1.3. Порядок группы E. Порядок точки. Подгруппы
кручения................................................................................................12
1.4. Проективные координаты.............................................................14
1.5. Эллиптические кривые над простыми полями. Редукция кривой
по простому модулю. Граница Хассе для порядка кривой. Расчет
порядка...................................................................................................16
1.6. Структура группы Ep и тип группы.............................................18
Глава 2 Принципы реализации эллиптических кривых в пакете LiDIA и
работа с ним.
2.1. Общие принципы организации библиотеки. Работа с большими
числами..................................................................................................19
2.2. Работа с эллиптическими кривыми. Класс, реализующий
эллиптическую кривую, класс, реализующий точку на
эллиптической
кривой.....................................................................................................21
Глава 3 Разработка лабораторного практикума.
2.1. Лабораторная работа №1. Реализация протокола Диффи-
Хеллмана на эллиптических
кривых...................................................................................................24
2.2. Лабораторная работа №2 Реализация дискретного
логарифмирования на эллиптических
кривых....................................................................................................29
Заключение....................................................................................................………..34
Список использованной литературы....................................................................…
Прикрепленные файлы: 1 файл
3
ДАЛЬНЕВОСТОЧНЫЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
ИНСТИТУТ ФИЗИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
Кафедра информационной безопасности
Эллиптические кривые. Особенности реализации. Разработка
лабораторного практикума.
Курсовая работа
студента 147 группы
Клочкова М. А.
Научный руководитель:
доцент
ГОНЧАРОВ С. М.
Срок сдачи работы:
Подпись научного руководителя:
Владивосток 2006
4
ОГЛАВЛЕНИЕ
Введение........................................................................................................................3
Глава 1
Общие теоретические сведения об эллиптических кривых
1.1. Сингулярные и несингулярные эллиптические
кривые.....................................................................................................6
1.2. Закон сложения точек эллиптической кривой. Построение
абелевой группы точек эллиптической
кривой......................................................................................................9
1.3. Порядок группы E. Порядок точки. Подгруппы
кручения................................................................................................12
1.4. Проективные координаты.............................................................14
1.5. Эллиптические кривые над простыми полями. Редукция кривой
по простому модулю. Граница Хассе для порядка кривой. Расчет
порядка...................................................................................................16
1.6. Структура группы Ep и тип группы.............................................18
Глава 2
Принципы реализации эллиптических кривых в пакете LiDIA и
работа с ним.
2.1. Общие принципы организации библиотеки. Работа с большими
числами..................................................................................................19
2.2. Работа с эллиптическими кривыми. Класс, реализующий
эллиптическую кривую, класс, реализующий точку на
эллиптической
кривой.....................................................................................................21
Глава 3
Разработка лабораторного практикума.
2.1. Лабораторная работа №1. Реализация протокола Диффи-
Хеллмана на эллиптических
кривых...................................................................................................24
2.2. Лабораторная работа №2 Реализация дискретного
логарифмирования на эллиптических
кривых....................................................................................................29
Заключение....................................................................................................………..34
Список использованной литературы....................................................................…35
5
Введение
В современном мире информация стала, наряду с природными ископаемыми
важнейшим ресурсом для человека. Поэтому проблема безопасности информации,
и предотвращения неправомарного доступа к ней сегодня стоит особенно остро.
Обеспечение безопасности информации – основная задача такой науки, как
криптография. Она развивается уже не одно столетие, но наиболее активно стала
развиваться в последние двадцать лет.
Современная криптография решает такие проблемы безопасности
информации, как конифиденциальность, целостность, аутентификация и
невозможность отказа сторон от авторства.
Обеспечение
конфиденциальности
– решение
проблемы
защиты
информации от ознакомления с ее содержанием со стороны лиц, не имеющих права
доступа к ней.
Обеспечение
целостности
–
гарантирование
невозможности
несанкционированного изменения информации.
Обеспечение аутентификации – разработка методов подтверждения
подлинности сторон(идентификация) и самой информации в процессе
информационного взаимодействия. Иноформация, передаваемая по каналу связи,
должна быть аутентифицирована по источнику, времени создания, содержанию,
времени пересылки, и т. п.
Обеспечение невозможности отказа от авторства – предотвращение
возможности
отказа
субъектов
от
некоторых
из
совершенных
ими
действий(например отказа от подписи контракта).
Криптографические протоколы можно разделить на два класса:
симметричные и асимметричные. В симметричных криптосистемах ключи
зашифрования и расшифрования совпадают, либо один из них можно определить,
зная другой. Использование этих алгоритмов связано с необходимостью для обоих
пользователей хранить и передавать общую информацию(например секретный
ключ), что предполагает наличие защищенного канала связи, что не всегда
возможно.
6
В асимметричных криптосистемах эта проблема отсутсвует, так определение
секретного ключа связано с решением трудных вычислительных задач.
В настоящее время время для построения обобщенных криптосистем с
открытым ключом используются следующие классы задач:
1. Задача определения порядка и структуры конечной абелевой группы
(эквивалентна задаче факторизации числа в Z);
2. Задача определения индекса элемента конечной абелевой группы
(эквивалентна задаче дискретного логарифмирования в циклической
группе);
3. Задача об укладке рюкзака.
Примерами использования этих задач служат такие протоколы, как RSA (1
класс), шифрсистема Эль-Гамаля, протокол Диффи-Хеллмана (2 класс), и другие.
Некоторые протоколы строятся на основе комбинаций нескольких классов задач.
Но у криптографии с открытым ключом есть несколько существенных
недостатков:
1.
Алгоритмы с открытыми ключами работают медленно.
Симметричные алгоритмы, по крайней мере, в 1000 раз быстрее,
чем алгоритмы с открытыми ключами. Да, компьютеры
становятся все быстрее и быстрее, и лет через 15 криптография с
открытыми ключами достигнет скоростей, сравнимых с
сегодняшней скоростью симметричной криптографии. Но
требования к объему передаваемой информации также
возрастают, и всегда будет требоваться шифровать данные
быстрее, чем это сможет сделать криптография с открытыми
ключами.
2.
Криптосистемы с открытыми ключами уязвимы по отношению
к вскрытию с выбранным открытым текстом. Если C = E(P), где
P - открытый текст из n возможных открытых текстов, то
криптоаналитику нужно только зашифровать все n возможных
открытых текстов и сравнить результаты с C (помните, ключ
шифрования общедоступен). Он не сможет раскрыть ключ
дешифрирования, но он сможет определить P.
7
3.
Большой размер ключей. При одинаковой стойкости, длина
ключа в симметричных алгоритмах составляет 256-512 бит,
тогда как в асимметричных – 2048-4096 бит.
Применение эллиптических кривых в асимметричнх алгоритмах, позволяет
снизить объем ключевой информации. Сравнимой с симметричными
системами стойкости возможно достичь уже при длине ключа в 160 бит. А
уменьшение длины ключа ведет к повышению скорости работы алгоритмов.
Большинство
алгоритмов, основанных
на
проблеме
дискретного
логарифмирования, легко переносятся на эллиптические кривые.
Эллиптические кривые также все активней начинают применяться в
криптоанализе. Это связано с тем, что некоторые классы задач(дискретное
логарифмирование) на сингулярных кривых возможно решить за
полиномиальное время.
Но изучение и реализация эллиптических кривых в практическом плане
вызывает определенные трудности.
Существующие библиотеки либо узкоспециализированные (реализуют один
или несколько криптопротоколов на эллиптических кривых), либо стоят
больших денежных вложений.
Данная курсовая работа призвана помочь студентам в практическом
изучении эллиптических кривых, и особенностей работы с ними.
В первой главе приводятся теоретические сведения об эллиптических
кривых, и алгоритмы работы с ними.
Во второй главе рассматривается описание методов работы с
эллиптическими кривыми в пакете LiDIA, и основное устройство данного
пакета.
В третьей главе содержится собственно лабораторный практикум по
эллиптическим кривым, разработанный при помощи данного пакета.
8
Глава 1 Общие теоретические сведения об
эллиптических кривых
§1.1 Сингулярные и несингулярные эллиптические кривые
Пусть К – поле. Тогда:
Определение. Эллиптической кривой Е над полем К называется множество точек
К
К
y
x
×
∈
)
,
(
, удовлетворяющих уравнению (в афинных координатах)
K
a
a
x
a
x
a
x
y
a
xy
a
y
E
i
∈
+
+
+
=
+
+
,
:
6
4
2
2
3
3
1
2
(1.1)
вместе с точкой O, которую называют «точкой в бесконечности» Иногда более
удобно бывает пользоваться алгебраическим уравнением для функции двух
переменных:
0
)
,
(
6
4
4
2
2
3
3
1
2
=
+
+
−
−
+
+
=
a
x
a
x
a
x
y
a
xy
a
y
y
x
F
Введение операции сложения над парами точек позволяет построить структуру
абелевой группы точек, если все точки кривой неособые, то есть имеют
однозначные производные. Такую кривую еще называют гладкой, или
несингулярной кривой.
Определение. Кривая называется сингулярной (особой), если существует хотя бы
одна точка (x,y) в которой частные производные функции (1.2) обращаются в 0.
Т.е., имеем следующее:
0
=
∂
∂
=
∂
∂
y
F
x
F
(1.2)
Часто, вместо (1.1) рассматривают канонические уравнения трех типов кривых:
3,
2
,
:
3
2
≠
+
+
=
p
b
ax
x
y
E
(1.3)
2
,0
,
:
2
3
2
=
≠
+
+
=
+
p
b
b
ax
x
xy
y
E
N
(1.4)
2
,
:
3
2
=
+
+
=
+
p
b
ax
x
y
y
E
s
(1.5)
первая из них описывает все кривые над полями характеристики, не равной 2 и 3,
вторая и третья – кривые над полями характеристики 2. К канонической форме
несингулярной кривой с определенными свойствами можно придти заменой
переменных в (1.1).
9
Рассмотрим эллиптическую кривую вида (1.4) над полем Q Для этой кривой
условие сингулярности (1.3) равносильно существованию кратных корней у
кубического уравнения в правой части. Действительно, распишем кубическое
уравнение в виде:
)
)(
)(
(
)
(
3
2
1
3
α
α
α
−
−
−
=
+
+
=
x
x
x
b
ax
x
x
f
(1.6)
Согласно (1.3) в особой точке:
0
)
)(
(
)
)(
(
)
)(
(
,0
)
)(
)(
(,
0
2
3
1
3
2
2
1
3
2
1
=
−
−
+
−
−
+
−
−
=
∂
∂
−
=
−
−
−
=
=
∂
∂
α
α
α
α
α
α
α
α
α
x
x
x
x
x
x
x
F
x
x
x
y
y
F
В таком случае, если хотя бы два корня совпадают, то особая точка будет
существовать. С другой стороны:
.
0
27
4
,0
3
2
,
2
,0
3
2
3
3
2
=
+
⇒
=
+
=
=
+
=
∂
∂
b
a
b
ax
b
x
отсюда
a
x
x
F
Для несингулярной кривой вида (1.4), следовательно, должно выполняться
условие:
0
)
27
4(
2
3
≠
+
−
=
∆
b
a
(1.7)
Величину ∆ называют дискриминантом.
Примеры несингулярных и сингулярных кривых показаны, соответсвенно, на
рисунках 1.1 и 1.2.
10
Рис 1.1 Примеры графиков несингулярных эллиптических кривых над полем Q. а-3
вещественных корня; б- один вещественный корень кубического уравнения (1.4)
Рис 1.2 Примеры графиков сингулярных эллиптических кривых над полем Q(вид
1.4); a - для двух кратных вещественных корней кубического уравнения
(особенность типа «узел»); б – для трех кратных вещественных
корней(особенность типа «пик»)
11
§1.2 Закон сложения точек эллиптической кривой. Построение
абелевой группы точек эллиптической кривой.
Важным свойством несингулярных кривых, является то, что любая прямая,
проходящая через две точки кривой E, пересекает эту кривую в единственной
третьей точке. Кроме того, касательная к любой точке кривой (кроме точки
перегиба) пересекает ее еще в одной точке. Симметрия кривой относительно оси x
позволяет дать наглядное определение обратной к точке
)
,
(
1
1
y
x
P =
точки:
)
,
(
1
1
y
x
P
−
=
−
(1.8)
Используя эти свойства, можно дать определение групповой операции сложения
точек эллиптической кривой.
Определение Суммой двух точек
)
,
(
1
1
y
x
P =
и
)
,
(
2
2
y
x
Q =
называется точка
)
,
(
3
3
y
x
Q
P
R
=
+
=
, обратная третьей точке пересечения эллиптической кривой
прямой линией, проходящей через точки P и Q. Найдем координаты точки R,
выразив их через координаты точек P и Q. При этом точки P и Q могут быть
различными, или совпадающими. Рисунок (1.3) иллюстрирует это.
Рис. 1.3. Геометрическая интерпретация сложения двух различных точек P и Q
(а) и удвоения точки P(б)
Возможны два случая:
1.
Q
P
±
≠
. Тогда уравнение прямой линии (Рисунок 1.3а),проходящей через точки
P и Q имеет вид:
12
1
1
1
2
1
2
;
x
y
x
x
y
y
x
y
λ
β
λ
β
λ
−
=
−
−
=
+
=
(1.9)
Перепишем уравнение (1.2) в каноническом виде (2.4) (см предыдущий параграф):
0
)
,
(
3
2
=
−
−
−
=
b
ax
x
y
y
x
F
(1.10)
Точки пересечиния кривой (1.10) и(1.9) имеют по оси x координаты
3
2
1
,
,
x
x
x
точек P,Q,R соответственно. Поскольку они являются общими для функций (1.9) и
(1.10), то получим:
.
0
)
)(
)(
(
,0
3
2
1
3
2
)
(
=
−
−
−
−
=
−
−
−
+
x
x
x
x
x
x
или
b
ax
x
x
β
λ
Приравняем в этих кубических уравнениях коэффициенты при
2
x
получим:
3
2
1
2
x
x
x
+
+
=
λ
1
2
1
2
x
x
y
y
−
−
−
=
λ
(1.11)
Из (1.11) получаем, что координаты точки R равны:
1
2
1
2
1
3
1
3
2
1
2
3
),
(
;
,
x
x
y
y
x
x
y
y
Q
P
x
x
x
−
−
−
=
−
−
−
=
≠
−
−
=
λ
λ
λ
(1.12)
2. P=Q, R=2P. В этом случае
2
1
x
x =
и параметр λ в (1.12) не определен.
Дифференциал функции (1.4)
,
3
2
2
adx
dx
x
ydy
+
=
Тогда, при
1
x
x =
, производная равна параметру ν касательной
β
ν
+
= x
y
к
кривой в точке P.
.
3
2
1
1
a
x
dx
dy
x
x
+
=
=
=
ν
Вместо (1.12) теперь можно записать координаты точки R=2P:
13
1
2
1
3
1
3
1
2
3
2
3
),
(
;
,
2
y
a
x
x
x
y
y
Q
P
x
x
+
=
−
−
−
=
=
−
=
ν
ν
ν
(1.13)
Отметим, что формулы сложения (1.12) и удвоения (1.13) справедливы для
эллиптических кривых над всеми полями, в том числе и конечными, кроме полей
характеристик 2 и 3. Очевидно, что в последнем случае редукция по модулю 2 или
3 приведет к некорректности формул удвоения и следует использовать другие
канонические уравнения кривых (например (1.5) или (1.6)).
Для построения абелевой группы точек эллиптической кривой после введения
операции сложения и обратного элемента, осталось определить O группы, как
,
,
)
(
E
P
O
P
P
∈
∀
=
−
+
где E – эллиптическая кривая. Если провести прямую через точки P и –P, то третья
точка пересечения прямой и эллиптической кривой уходит в бесконечную точку
вдоль оси y(рис 1.3 а, где в качестве P и -P можно взять R и -R). Поэтому точку O
группы E еще называют «точкой на бесконечности»
Смысл перехода к обратной к точке пересечения прямой и кривой при определении
суммы R=P+Q становится понятен, если выразить, например точку P=R-Q. В этом
случае прямая проходит через точки R, -Q, и –P, а обратной к этой точке является
P. Очевидна и ассоциативность сложения P+(Q+S)=(P+Q)+S, и коммутативность
P+Q=Q+P.
Таким образом, множество точек эллиптической кривой E замкнуто, относительно
сложения, удовлетворяет условиям коммутативности и ассоциативности, откуда
можно сделать вывод, что оно является абелевой группой.
14
§1.3 Порядок группы E. Порядок точки. Подгруппы кручения.
Аналогией с экспоненциированием в мултьтипликативной группе, в аддитивной
группе точек является k-кратное сложение элементов (в нашем случае – точек
эллиптической кривой), которые обозначается, как:
.
kP
P
P
P
P
k
=
+
+
+
+
4
4
4
4
3
4
4
4
4
2
1
K
Точку kP называют скалярным произведением, а процесс ее вычисления –
экспоненциированием (возведением в степень).
Определение. Порядком эллиптической кривой
E
N
называется число всех ее точек
(x,y) вместе с точкой на бесконечности (точкой O).
Определение. Порядком точки P эллиптической кривой называется наименьшее
натуральное число
,0
≠
m
для которого mP=O.
Порядки
E
N
и m могут быть конечными и бесконечными. В группе бесконечного
порядка (например в группе кривой над R) могут быть точки конечного порядка. В
частности, в группе кривой над R всегда есть точки 2-го и 3-го порядков.
Координаты
i
x
точек 2-го порядка – это корни кубического трехчлена из правой
части (1.4). Для трехчлена с тремя действительными корнями,
3
2
1
,
,
α
α
α
имеем
три точки второго порядка
)0
,
(
),
0,
(
),
0,
(
3
2
1
α
α
α
. В этих точках
.
)0
,
(2
)0
,
(
)0
,
(
O
i
i
i
=
⇒
−
=
α
α
α
Вместе с точкой O эти точки образуют подгруппу 4-го порядка группы E
бесконечного порядка. Если вещественный корень единственный, то он порождает
подгруппу 2-го порядка точек 2-го порядка.
Точки 3-го порядка в группе E над R найдем из соотношений:
1
3
3
2
x
x
O
P
P
P
=
⇒
=
⇒
−
=
Согласно (1.13)
.
0
2
1
1
1
1
1
2
2
3
≥
⇒
=
−
+
x
x
x
y
a
x
Отсюда, с учетом (1.4):
15
0
,0
12
6
3
1
2
1
1
4
1
≥
=
−
+
+
x
a
bx
ax
x
(1.14)
В общем случае, x-координата точки третьего порядка совпадает с x-координатой
точки перегиба эллиптической кривой E.
Точки конечного порядка кривой образуют так называемые подгруппы кручения.
(В литературе можно также встретить термин – торсионные подгруппы)
Рис. 1.5 Точки конечного порядка над кривой
x
x
y
−
=
3
2
16
§1.4 Проективные координаты.
При изучении свойств эллиптических кривых и в ряде практических приложений
полезным оказывается переход от аффинных координат (x,y) к проективным
(X,Y,Z), связывая точки кривой в этих координатах отношением эквивалентности.
Привлечение новой переменной Z позволяет задать координаты нуля группы E
(точки на бесконечности). В операциях над конечными полями этот
инструментарий позволяет избежать трудоемких вычислений обратного элемента
поля при сложении точек.
Определение Проективной плоскостью над полем K называется множество
классов эквивалентности троек (X,Y,Z), в которых хотя бы один элемент
ненулевой. Эквивалентными считаются тройки, если элементы одной из них
получаются из другой умножением на скаляр:
)
,
,
(
)
,
,
(
Z
Y
X
Z
Y
X
′
′
′
, если для
некоторого элемента
)
,
,
(
)
,
,
(
:
Z
Y
X
Z
Y
X
K
=
′
′
′
∈
λ
λ
λ
λ
Такие классы эквивалентности называются проективными точками. Проективные
точки с ненулевым элементом Z принадлежат классу эквивалентности,
содержащему единственную точку, вида(x,y,1): она просто вычисляется
x=X/Z,y=Y/Z. Таким образом, проективная плоскость может быть определена, как
множество всех точек(x,y) обычной (аффинной) плоскости с дополнением точек,
для которых Z=0. Эти точки можно интерпретировать как линию в бесконечности
и рассматривать ее как «горизонт» плоскости. Всякое уравнение F(X,Y)=0 кривой в
аффинной плоскости соответствует однородному уравнению
0
)
,
,
(
=
Z
Y
X
F
,
выполняемое для соответствующих проективных точек: просто заменим x на X/Z, y
на Y/Z и умножим на степень Z, чтобы избавиться от знаменателей. Применим эту
тактику к уравнению кривой (1.4). Уравнение (1.4) запишем в виде:
K
b
a
b
ax
x
y
y
x
F
∈
−
−
−
=
,
;
)
,
(
3
2
Используем нашу подстановку. Тогда при
0
≠
Z
, получим:
0
)
,
(
3
2
=
−
−
−
=
b
a
y
x
F
Z
X
Z
X
Z
Y
Умножим это уравнение на
3
Z
17
0
)
,
(
)
,
,
(
3
2
3
2
3
=
−
−
−
=
=
bZ
aXZ
X
Z
Y
y
x
F
Z
Z
Y
X
F
(1.15)
Кроме точек с
0
≠
Z
уравнению 1.15 удовлетворяет еще одна точка. Подставим
Z=0 в уравнение, получим
0
3
=
X
, это означает, что X=0. Но имеется только один
класс эквивалентности, где оба элемента X и Z нулевые – класс, содержащий
(0,1,0). Это и есть точка, которую мы обозначаем O. Точка прересечения оси y с
линией бесконечности.
18
§1.5 Эллиптические кривые над простыми полями. Редукция кривой
по простому модулю. Граница Хассе для порядка кривой. Расчет
порядка.
Пусть кривая (1.4) с целыми коэффициентами a и b определена над полем
рациональных чисел и p>3 – простое. Тогда сравнение:
)
(mod
3
2
p
b
ax
x
y
+
+
≡
(1.16)
называется редукцией кривой по модулю p. При этом и коэффициенты кривой, и
координаты (x,y) точек являются целыми сравнимыми по модулю p числами.
Редукция называется хорошей, если p не делит дискриминант, или:
0
mod
)
27
4(
2
3
≠
+
−
=
∆
p
b
a
(1.17)
В этом случае все корни кубического уравнения в правой части различны, и кривая
является несингулярной. Абелеву группу точек (x,y) вместе с точкой на
бесконечности O обозначим
p
E
. Отметим, что в отличие от коэффициентов a и b
кривой, координаты (x,y) точек могут рассматриваться как элементы любого
расширения
p
m
p
F
поля
m
F
)
,3
,2
,1
(
K
=
вплоть до алгебраического замыкания.
Законы сложения точек (1.12), (1.13) справедливы для группы
)3
,2
(, ≠
p
E
p
после
введения редукции по модулю p, а операция деления равнозначна умножению на
обратный элемент поля
p
F
. Из конечности поля следует конечность числа точек
кривой, то есть ее порядка.
Так как кривая всегда содержит точку на бесконечности O, а для каждого решения
x уравнения (1.4) имеются по два решения y, то можно получить грубую оценку
порядка кривой
E
N
:
.
1
,1
2
1
p
N
p
или
p
N
E
E
<
−
+
+
<
<
Но все же более точную оценку дает теорема Хассе:
Теорема(Хассе): Для эллиптической кривой E над конечным полем
q
F
,
справедлива следующая оценка порядка кривой
E
N
19
K
,3
,2
,1
,
,
2
1
2
1
=
=
+
+
≤
≤
−
+
m
p
q
q
q
N
q
q
m
E
(1.18)
Для простого поля (q=p) оценка модет быть записана, как
.
2
1
p
N
p
E
<
−
+
(1.19)
Доказательатво можно найти в [3].
Пусть χ(z) – квадратичный характер элемента z поля K=F
q
, определяемый, как:
0
z
0,
,
1,
-
)
(
,
,
1,
2
2
=
≠
=
∈
=
a
z
z
K
a
a
z
χ
(1.20)
Иными словами, если z имеет корень квадратный в поле K, то χ(z)=1, а
противном случае χ(z)=-1. В первом случае говорят, что z является квадратичным
вычетом, во втором – квадратичным невычетом. Тогда, порядок кривой можно
рассчитать перебором всех элементов поля K, как сумму:
{
}
∑
∑
∑
∈
∈
∈
+
+
−
=
−
+
=
=
+
+
+
+
=
+
+
+
+
=
K
x
K
x
K
x
E
b
ax
x
t
где
t
q
b
ax
x
q
b
ax
x
N
).
(
1
)
(
1
1
)
(
1
3
3
3
χ
χ
χ
(1.21)
Первая единица в(1.21) учитывает точку на бесконечности O, а под знаком
суммы каждое решение x уравнения (1.4) даст по две точки Е. Исключением
являются точки второго порядка с координатой y=0, которые учитываются по
одному разу.Значение t,
q
t
2
<
, может быть как положительным, так и
отрицательным.
20
§1.6 Структура группы E
p
и тип группы
Порядок N
E
группы E
p,
как правило является составным числом и,
следовательно, группв E
p
содержит подгруппы порядков, делящих порядок группы.
Если порядок подгруппы(группы E
p
) – простое число, то такая подгруппа (группа)
– циклическая. В целом группа E
p
составного порядка может оказаться
нециклической, причем встречаются случаи, когда различные группы с
одинаковым порядком имеют циклические и нециклические структуры.
Теорема (Кассельса) Группа E
p
порядка N
E
является либо представляется
прямой суммой двух циклических групп порядков n
1
и n
2
таких, что
)1
,
(
|
n
n
|
n
1
2
1
−
p
N
НОД
и
E
(1.22)
Так как
2
1
n
n
N
E
=
и из (1.22)
.
,
1
1
2
m
n
N
то
m
n
n
E
=
=
Следовательно,
группа E
p
может быть нециклической только тогда, когда делители порядка кривой
содержат квадраты. Это условие является необходимым, но не достаточным, для
образования нециклической группы. Кроме этого, должно выполняться второе
условие в (1.22). С другой стороны группа E
p
является циклической тогда, когда
порядок кривой N
E
свободен от квадратов. Это условие достаточно для того, чтобы
группа E
p
была циклической. Вместе с тем, есть примеры циклических групп E
p,
порядок которых содержит квадраты. Более жестким достаточным условием
цикличности E
p
является взаимная простота порядка N
E
и p-1.
Теорема (о порядке групп кручения) Пусть E – эллиптическая кривая над
полем K, характеристики не равной 2. Тогда существует не более n
2
точек порядка
n, над любым расширением поля K.
Если в группе E имеется не более n точек порядка n, то любая из них
генерирует циклическую подгруппу порядка n. При простом n таких точек ровно n.
В циклической подгруппе составного порядка n число генераторов подгруппы
определяется функцией Эйлера ϕ(n). Нециклические подгруппы порядка n
2
являются множествами точек порядка n и делителей n.
Определение. Типом конечной абелевой группы, представленной в виде
прямой суммы циклических подгрупп, называется запись порядков циклических
подгрупп, равных степеням нарастающих простых чисел.
21
Глава 2 Принципы реализации эллиптических кривых в
пакете LiDIA и работа с ним.
§2.1 Общие принципы организации библиотеки. Работа с большими
числами.
Данная библиотека, написана на языке C++, и организована в виде шаблонов
(templates). Данная технология предоставляет более удобный интерфейс для
программиста и пользователя классов, а также позволяет легко расширять
возможности данного пакета.
Вот общая структура пакета LiDIA:
Первый уровень (kernel) – уровень ядра. На этом уровне работает библиотека,
реализующая большие числа (multiprecision arithmetic). В моей версии
используется GNU MP library 4.1
Второй уровень(interfaces) – связующее звено, между пакетом и библиотекой,
реализующей большие числа, а также операционной системой.
Третий уровень(simple classes) – содержит классы, реализующие
вещественные, целые, рациональные и комплексные числа.
Четвертый уровень(parametrized classes) – содержит классы для работы с
полиномами, матрицами, эллиптическими кривыми… и т.п.
22
Большие числа в пакете представлены классами bigint, bigrational, bigcomplex
и bigfloat. Все эти классы поддерживают конверсию чисел из строки, и
стандартных типов C++(int, float, double, long double, long, и т.п)
Так как в криптографии в основном используется целочисленная арифметика,
то не будем подробно рассматривать классы bigfloat и bigrational.
Остановимся на классе bigint:
Класс bigint реализует, в общем случае, арифметику над Z,
а также следующие теоретико-числовые методы:
1. bigint dl(const bigint & a, const bigint & b, const bigint &p)
Решает сравнение
p
b
a
mod
≡
.
2. bool fermat (const bigint & a)
Проверяет число на простоту, используя малую теорему Ферма.
3. bool a.is_prime (int n = 10) const
bool is_prime (const bigint & a, int n = 10)
Проверяет число на простоту, используя метод Рабина-Миллера.
4. bigint gcd (const bigint & a, const bigint & b)
Считает НОД(a,b)
5. bigint bgcd (const bigint & a, const bigint & b)
Считает НОД, используя двоичный метод.
6. bigint dgcd (const bigint & a, const bigint & b)
Считает НОД по алгоритму Евклида.
7. bigint xgcd (bigint & u, bigint & v, const bigint & a, const bigint & b)
Считает НОД и коэффициенты u и v такие, что
НОД(a,b) = u·a+v ·b,
Кроме арифметики над Z, пакет LiDIA также поддерживает арифметику над
конечными полями, в том числе полями Галуа по простому модулю, по модулю 2
m
,
и p
m
, для простых p. Это реализуется в классе gf_element (элементы полей Галуа) и
bigmod(модулярная арифметика).
23
§2.2 Работа с эллиптическими кривыми. Класс, реализующий
эллиптическую кривую, класс, реализующий точку на эллиптической
кривой.
Собственно реализация эллиптических кривых в пакете LiDIA разбита на
несколько базовых классов.
Эллиптические кривые представлены в пакете шаблоном класса
elliptic_curve< T > , где Т – определяет поле, над которым задается кривая.
Кривая рассматривается в виде (1.1)
Т может принимать значение - bigint, bigrational, bigcomplex и gf_element.
Данный класс реализует методы работы с кривой в целом.
Перечислим основные методы этого класса.
1. T C.discriminant () const
Считает дискриминант кривой C
2. T C.get_a1 () const
T C.get_a2 () const
T C.get_a3 () const
T C.get_a4 () const
T C.get_a6 () const
Возвращает соответствующие коэффициенты уравнения (1.1).
3. T C.j_invariant () const
Считает j-инвариант кривой C.
4. int C.is_singular () const
Проверяет кривую на сингулярность.
5. bool C.is_supersingular ()
Проверяет кривую на суперсингулярность
6. unsigned int C.degree_of_definition () const
Возвращает степень расширения, над простым полем.
7. point< T > random_point (const elliptic_curve< T > & C)
Генерирует случайную точку кривой
8. bigint C.group_order ()
Определяет порядок группы кривой (использует теорему Хассе и алгоритм
Шуфа)
24
9. void C.isomorphism_type (bigint & m, bigint & n)
void C.isomorphism_type(bigint &m, bigint &n, point<T> &P,point<T> &Q)
Возвращает тип группы точек эллиптической кривой
10. bool C.is_cyclic ()
Проверяет, циклическая ли группа точек эллиптической кривой.
11. bool C.probabilistic_is_order (const bigint & r, unsigned int t = 5)
Проверяет, является ли r порядком группы точек.
Точка на эллиптической кривой представляется отдельным классом point<T>,
который представляет точки эллиптической кривой P(x,y) илм P(x,y,z) – для
проективных координат, над полем T.
Класс поддерживает основные операторы C++(+,-,+=,-=,*…)
Для сложения и скалярного умножения класс использует методы, подробно
описанные в Главе 1. Единственное ограничение – характеристика поля не
должна быть равна 2 или 3.
Рассмотрим более подробно методы класса point:
1. bool P.on_curve () const
Проверяет, на кривой ли точка P.
2. bool P.is_zero () const
Проверяет, является ли точка P точкой на бесконечности(O).
3. bool P.is_negative_of (const point< T > & Q) const
Проверяет, является ли P обратной к Q
4. bool P.is_affine_point () const
bool P.is_projective_point () const
Проверяют, в каком представлении находится точка P
5. T P.get_x () const
T P.get_y () const
T P.get_z () const
Возвращает соответствующую координату точки P
6. elliptic_curve< T > P.get_curve () const
25
Возвращает класс, представляющий кривую, на которой находится точка P
7. bigint order_point (const point< T > & P)
bigint order_point (const point< T > & P, rational_factorization & f)
Возвращает порядок точки P
8. bigint bg_algorithm (const point< T > & P, const point< T > & Q,
const bigint & l, const bigint & u)
Пытается решить проблему дискретного логарифмирования x·P = Q
Использует метод Babystep-Giantstep
9. bigint discrete_logarithm (const point< T > & P, const point< T > & Q,
bool info = false)
Использует метод Полига Хеллмана, для решения проблемы дискретного
логарифмирования.
Также, пакет обладает таким полезным классом, как gec. Данный класс генерирует
эллиптические кривые с заданными свойствами.
26
Глава 3 Разработка лабораторного практикума.
§3.1 Лабораторная работа №1.
Реализация протокола Диффи-Хеллмана на эллиптических кривых.
ЦЕЛЬ РАБОТЫ: приобретение практических навыков реализации
протоколов на эллиптических кривых, широко используемых в системах защиты
информации.
Краткая теория
Протокол передачи ключей Диффи-Хеллмана на эллиптических кривых.
Предлягаемая к реализации модель протокола Д-Х. следующая:
Сторонам известны параметры кривой, а также генератор группы(подгруппы)
точек этой кривой. Также у каждого из абонентов есть свой секретный ключ(для –
А, это некоторое число a, для B – некоторое число b. Сторонам необходимо
выработать общий ключ на основании этих данных. Итак схема:
1) А вычисляет точку P=aG и передает ее B.
2) B вычисляет точку Q=bG и передает ее A.
3) Стороны вырабатывают общий ключ, являющейся координатой x следующих
точек:
А:K=aQ=abG
B:K=bP=abG.
Используемые классы и структуры.
Реализуемая кривая имеет следующий вид:
K
a
a
x
a
x
a
x
y
E
i
∈
+
+
+
=
,
:
6
4
2
2
3
2
Эллиптические кривые представлены в пакете шаблоном класса
elliptic_curve< T > , где Т – определяет поле, над которым задается кривая.
Кривая рассматривается в виде (1.1)
Т может принимать значение - bigint, bigrational, bigcomplex и gf_element.
Данный класс реализует методы работы с кривой в целом.
Перечислим основные методы этого класса.
1. T C.discriminant () const
27
Считает дискриминант кривой C
2. T C.get_a1 () const
T C.get_a2 () const
T C.get_a3 () const
T C.get_a4 () const
T C.get_a6 () const
Возвращает соответствующие коэффициенты уравнения (1.1).
3. T C.j_invariant () const
Считает j-инвариант кривой C.
4. int C.is_singular () const
Проверяет кривую на сингулярность.
5. bool C.is_supersingular ()
Проверяет кривую на суперсингулярность
6. unsigned int C.degree_of_definition () const
Возвращает степень расширения, над простым полем.
7. point< T > random_point (const elliptic_curve< T > & C)
Генерирует случайную точку кривой
8. bigint C.group_order ()
Определяет порядок группы кривой (использует теорему Хассе и алгоритм
Шуфа)
9. void C.isomorphism_type (bigint & m, bigint & n)
void C.isomorphism_type(bigint &m, bigint &n, point<T> &P,point<T> &Q)
Возвращает тип группы точек эллиптической кривой
10. bool C.is_cyclic ()
Проверяет, циклическая ли группа точек эллиптической кривой.
11. bool C.probabilistic_is_order (const bigint & r, unsigned int t = 5)
Проверяет, является ли r порядком группы точек.
Точка на эллиптической кривой представляется отдельным классом point<T>,
который представляет точки эллиптической кривой P(x,y) илм P(x,y,z) – для
проективных координат, над полем T.
Класс поддерживает основные операторы C++(+,-,+=,-=,*…)
28
Единственное ограничение – характеристика поля не должна быть равна 2 или
3.
Рассмотрим более подробно методы класса point:
1. bool P.on_curve () const
Проверяет, на кривой ли точка P.
2. bool P.is_zero () const
Проверяет, является ли точка P точкой на бесконечности(O).
3. bool P.is_negative_of (const point< T > & Q) const
Проверяет, является ли P обратной к Q
4. bool P.is_affine_point () const
bool P.is_projective_point () const
Проверяют, в каком представлении находится точка P
5. T P.get_x () const
T P.get_y () const
T P.get_z () const
Возвращает соответствующую координату точки P
6. elliptic_curve< T > P.get_curve () const
Возвращает класс, представляющий кривую, на которой находится точка P
7. bigint order_point (const point< T > & P)
bigint order_point (const point< T > & P, rational_factorization & f)
Возвращает порядок точки P
8. bigint bg_algorithm (const point< T > & P, const point< T > & Q,
const bigint & l, const bigint & u)
Пытается решить проблему дискретного логарифмирования x·P = Q
Использует метод Babystep-Giantstep
9. bigint discrete_logarithm (const point< T > & P, const point< T > & Q,
bool info = false)
Использует метод Полига Хеллмана, для решения проблемы дискретного
логарифмирования.
29
1. Рабочее задание
1.1. Реализовать, используя пакет LiDIA протокол Диффи-Хеллмана для
заданной преподавателем кривой (т.е. коэффициенты, генератор группы
указывает преподаватель)
1.2. Реализовать выработку ключа данным протоколом для различных
ключей.
1.3. Убедиться в правильности реализации, используя контрольные примеры.
1.4. Написать отчет.
2. Выполнение задания
При написании программ должно быть выполнены следующие требования:
2.1 Входными данными программ являются коэффициенты уравнения
эллиптической кривой,характеристика поля, генератор группы
эллиптической кривой,
а также открытые и секретные ключи для каждого из абонентов.
2.2 Входные данные вводятся с помощью клавиатуры и отображаются на
дисплее.
2.3 В пакете LiDIA кривая задается уравнением (1)
2.4. Рекомендуется использовать компилятор MinGW, или MSVC, версии не
ниже 7.1
2.5 Необходимо включать следующие заголовочные файлы:
#include
<LiDIA/elliptic_curve.h>
#include
<LiDIA/point.h>
#include
<LiDIA/gf_element.h>
2.6 Неопходимо использовать пространство имен LiDIA при помощи
директивы using namespace LiDIA
3. Оформление отчета
В отчете должны содержаться:
1) листинги исходных текстов программ, моделирующих протокол Диффи-
Хеллмана.
30
2)Результаты работы программ – численное значение общего ключа.
4. Варианты заданий
1. char(K)=3462, модель – аффинная.
A1=303 A2=547 A3=293 A4=671 A6=13
G(207,2130)
2. char(K)=53, модель – аффинная.
A1=31 A2=51 A3=29 A4=16 A6=13
G(21,50)
3. char(K)=83, модель – аффинная.
A1=13 A2=25 A3=19 A4=62 A6=3
G(32,13)
4. char(K)=1361, модель – аффинная.
A1=326 A2=553 A3=209 A4=136 A6=813
G(1197,68)
5. char(K)=3989, модель – аффинная.
A1=237 A2=557 A3=397 A4=789 A6=149
G(3425,2585)
6. char(K)=631, модель – аффинная.
A1=553 A2=35 A3=129 A4=57 A6=143
G(356,368)
7. char(K)=2221, модель – аффинная.
A1=1351 A2=1363 A3=1337 A4=87 A6=23
G(1391,1595)
8. char(K)=23357, модель – аффинная.
A1=2003 A2=4487 A3=5529 A4=7781 A6=729
G(20160,14026)
31
§3.2 Лабораторная работа №2 Реализация дискретного
логарифмирования на эллиптических кривых.
ЦЕЛЬ РАБОТЫ: приобретение практических навыков реализации
эллиптических кривых, широко используемых в системах защиты информации.
Краткая теория
Алгоритм Полига-Хеллмана
Этот метод основан на известной для группы факторизации порядка N
группы по степеням простых чисел p
i
em
m
e
e
p
p
p
N
...
2
2
1
1
=
Применительно к группе точек ЭК, с генератором G порядка N имеем Q=kG.
Согласно известной китайской теореме об остатках[2], существует единственное
натуральное число k<N, такое, что
)
mod
......
..........
)
mod
)
(mod
2
2
2
1
1
1
em
m
m
e
e
p
k
k
p
k
k
p
k
k
≡
≡
≡
.
Решив эти сравнения, в дальнейшем, найти k не составит труда, используя
китайскую теорему об остатках.
Используемые классы и структуры.
Реализуемая кривая имеет следующий вид:
K
a
a
x
a
x
a
x
y
E
i
∈
+
+
+
=
,
:
6
4
2
2
3
2
Эллиптические кривые представлены в пакете шаблоном класса
elliptic_curve< T > , где Т – определяет поле, над которым задается кривая.
Кривая рассматривается в виде (1.1)
Т может принимать значение - bigint, bigrational, bigcomplex и gf_element.
Данный класс реализует методы работы с кривой в целом.
Перечислим основные методы этого класса.
1. T C.discriminant () const
32
Считает дискриминант кривой C
2. T C.get_a1 () const
T C.get_a2 () const
T C.get_a3 () const
T C.get_a4 () const
T C.get_a6 () const
Возвращает соответствующие коэффициенты уравнения (1.1).
3. T C.j_invariant () const
Считает j-инвариант кривой C.
4. int C.is_singular () const
Проверяет кривую на сингулярность.
5. bool C.is_supersingular ()
Проверяет кривую на суперсингулярность
6. unsigned int C.degree_of_definition () const
Возвращает степень расширения, над простым полем.
7. point< T > random_point (const elliptic_curve< T > & C)
Генерирует случайную точку кривой
8. bigint C.group_order ()
Определяет порядок группы кривой (использует теорему Хассе и алгоритм
Шуфа)
9. void C.isomorphism_type (bigint & m, bigint & n)
void C.isomorphism_type(bigint &m, bigint &n, point<T> &P,point<T> &Q)
Возвращает тип группы точек эллиптической кривой
10. bool C.is_cyclic ()
Проверяет, циклическая ли группа точек эллиптической кривой.
11. bool C.probabilistic_is_order (const bigint & r, unsigned int t = 5)
Проверяет, является ли r порядком группы точек.
Точка на эллиптической кривой представляется отдельным классом point<T>,
который представляет точки эллиптической кривой P(x,y) илм P(x,y,z) – для
проективных координат, над полем T.
Класс поддерживает основные операторы C++(+,-,+=,-=,*…)
33
Единственное ограничение – характеристика поля не должна быть равна 2 или
3.
Рассмотрим более подробно методы класса point:
1. bool P.on_curve () const
Проверяет, на кривой ли точка P.
2. bool P.is_zero () const
Проверяет, является ли точка P точкой на бесконечности(O).
3. bool P.is_negative_of (const point< T > & Q) const
Проверяет, является ли P обратной к Q
4. bool P.is_affine_point () const
bool P.is_projective_point () const
Проверяют, в каком представлении находится точка P
5. T P.get_x () const
T P.get_y () const
T P.get_z () const
Возвращает соответствующую координату точки P
6. elliptic_curve< T > P.get_curve () const
Возвращает класс, представляющий кривую, на которой находится точка P
7. bigint order_point (const point< T > & P)
bigint order_point (const point< T > & P, rational_factorization & f)
Возвращает порядок точки P
8. bigint bg_algorithm (const point< T > & P, const point< T > & Q,
const bigint & l, const bigint & u)
Пытается решить проблему дискретного логарифмирования x·P = Q
Использует метод Babystep-Giantstep
9. bigint discrete_logarithm (const point< T > & P, const point< T > & Q,
bool info = false)
Использует метод Полига-Хеллмана, для решения проблемы дискретного
логарифмирования.
34
1. Рабочее задание
1.1. Реализовать, используя пакет LiDIA, алгоритм Полига-Хеллмана на
заданной преподавателем кривой (т.е. коэффициенты, генератор группы
указывает преподаватель).
1.2. Убедиться в правильности реализации, используя контрольные примеры.
1.3. Написать отчет.
2. Выполнение задания
При написании программ должно быть выполнены следующие требования:
2.1 Входными данными программ являются коэффициенты уравнения
эллиптической кривой,характеристика поля, генератор группы
эллиптической кривой,
а также точка, которую надо прологарифмировать.
2.2 Входные данные вводятся с помощью клавиатуры и отображаются на
дисплее.
2.3 В пакете LiDIA кривая задается уравнением (1)
2.4. Рекомендуется использовать компилятор MinGW, или MSVC, версии не
ниже 7.1
2.5 Необходимо включать следующие заголовочные файлы:
#include
<LiDIA/elliptic_curve.h>
#include
<LiDIA/point.h>
#include
<LiDIA/gf_element.h>
2.6 Необходимо использовать пространство имен LiDIA при помощи
директивы using namespace LiDIA
3. Оформление отчета
В отчете должны содержаться:
1) листинги исходных текстов программ, моделирующих протокол Диффи-
Хеллмана.
35
2)Результаты работы программ –численное значение дискретного
логарифма.
4. Варианты заданий
1. char(K)=3463, модель – аффинная.
A1=303 A2=547 A3=293 A4=671 A6=13
G(781,1572) P(754,323) k=149
2. char(K)=53, модель – аффинная.
A1=31 A2=51 A3=29 A4=16 A6=13
G(21,50) P(22,23) k=149
3. char(K)=83, модель – аффинная.
A1=13 A2=25 A3=19 A4=62 A6=3
G(39,50) P(39, 5) k=89
4. char(K)=1361, модель – аффинная.
A1=326 A2=553 A3=209 A4=136 A6=813
G(1197,68) P(2,555) k=1137
5. char(K)=353, модель – аффинная.
A1=23 A2=5 A3=31 A4=7 A6=149
G(38,260) P(6336,184) k=177
6. char(K)=631, модель – аффинная.
A1=553 A2=35 A3=129 A4=57 A6=143
G(356,368) P(452,369) k=345
7. char(K)=2221, модель – аффинная.
A1=1351 A2=1363 A3=1337 A4=87 A6=23
G(1391,1595) P(1542, 1504) k=2343
8. char(K)=23357, модель – аффинная.
A1=2003 A2=4487 A3=5529 A4=7781 A6=729
G(20160,14026) P(13664, 23061) k=12367
36
Заключение.
Целью данной работы являлась разработка лабораторного практикума по теме
«Эллиптические кривые». Для создания практикума использовался пакет LiDIA .
Язык Си++ для реализации данной курсовой работы был выбран не случайно. Не
секрет, что студенты Института Физики и Информационных Технологий изучают
Си++ буквально с первого семестра, и прекрасно владеют им. Поэтому, думаю, что
разобраться с данным практикумом им не составит труда. Надеюсь, что данное
начинание не останется без внимания, и получит дальнейшее развитие.
37
Список используемой литературы:
[1] Бессалов А. В. Телиженко А. Б. Криптосистемы на эллиптических кривых.
Киев: Полiтехнiка, 2004
[2] Василенко О. Н. Теоретико числовые методы в криптографии, МЦНМО, 2003
[3] Ленг С. Эллиптические функции. М.:Изд-во «Наука», 1984
[4] Смарт Н. Криптография. М.: «Техносфера» 2003
[5] Страуструп Б. «Программирование на Си++»,М.: «Диалог МИФИ», 1996
[6] Silverman J. Arithmetic of elliptic curves , Springer GTM 106, 1986
[7] LiDIA User’s Manual
Информация о работе Эллиптические кривые. Особенности реализации. Разработка лабораторного практикума