ВУЗ:
Составители:
23
yxaxb
=
++
над полем GF(p) вместе с дополнительной точкой ∞ называемой точкой в
бесконечности или нулевой точкой О (поскольку эта точка выполняет роль
нейтрального элемента в группе точек). Такое представление эллиптиче-
ской кривой носит название эллиптической кривой в форме Вейерштрасса.
Если обозначить количество точек на эллиптической кривой Е через
#Е, то по теореме Хассе #E = p + 1 – t, где
2tq≤
.
#Е называется порядком кривой E, a t – следом кривой Е.
Множество точек эллиптической кривой Е с заданной бинарной опе-
рацией образует абелеву группу.
Если #Е = р + 1, то кривая Е называется суперсингулярной.
Эллиптическая не являющаяся суперсингулярной кривая Е над полем
GF(2
m
) характеристики 2 задается следующим образом.
Пусть т > 3 – целое число. Пусть a, b ∈ GF(2
m
), b ≠ 0. Эллиптической
кривой Е над полем GF(2
m
) называется множество решений (х, у) уравне-
ния
23
yxyxaxb
+
=++
над полем GF(2
m
) вместе с дополнительной точкой ∞, называемой точкой в
бесконечности.
Количество точек на кривой Е также определяется теоремой Хассе:
12qq
+
−≤
#E
12qq≤++
, где q = 2
m
, a #Е – четно.
В этом случае множество точек эллиптической кривой Е с заданной
бинарной операцией также образует абелеву группу.
Группа точек на кривой имеет простую структуру, а именно она явля-
ется абелевой группой ранга 1 или 2, т.е. изоморфна прямому произведе-
нию двух циклических групп
12nn
Z
Z
×
, где п
1
и п
2
– целые числа, п
2
делит п
1
и n
2
делит q – 1, где q – порядок поля коэффициентов, при этом п
1
может
быть равно 1. Индекс подгруппы Z
n
в группе точек называют кофактором
эллиптической кривой.
Пользуясь операцией сложения точек на кривой, можно естественным
образом определить операцию умножения точки Р ∈ Е на произвольное
целое число п: пР = Р + Р + ... + Р, где операция сложения выполняется п
раз.
Теперь построим одностороннюю функцию, на основе которой можно
будет создать криптографическую систему.
Пусть Е – эллиптическая кривая, Р ∈ Е – точка на этой кривой. Выбе-
рем целое число п < #Е. Тогда в качестве прямой функции выберем произ-
ведение пР. Для его вычисления по оптимальному алгоритму потребуется
не более 2log
2
n операций сложения. Обратную задачу сформулируем сле-
дующим образом: по заданным эллиптической кривой Е, точке Р ∈ Е и
произведению пР найти п. В настоящее время все известные алгоритмы
решения этой задачи требуют экспоненциального времени.
Теперь можно описать криптографический протокол, аналогичный из-
вестному протоколу Диффи-Хеллмана. Для установления защищенной свя-
зи два пользователя А и В совместно выбирают эллиптическую кривую Е и
точку Р на ней. Затем каждый из пользователей выбирает свое секретное
целое число, соответственно а и b. Пользователь А вычисляет произведение
аР, а пользователь В – bР. Далее они обмениваются вычисленными значе-
ниями. При этом параметры самой кривой, координаты точки на ней и зна-
чения произведений являются открытыми и могут передаваться по неза-
щищенным каналам связи. Затем пользователь А умножает полученное
значение на а, а пользователь В умножает полученное им значение на b. В
силу свойств операции умножения на число аbР = bаР. Таким образом, оба
пользователя получат общее секретное значение (координаты точки аbР),
которое они могут использовать для получения ключа шифрования. Отме-
тим, что злоумышленнику для восстановления ключа потребуется решить
сложную с вычислительной точки зрения задачу определения а и b по из-
вестным Е, Р, аР и bР.
3.4. Применение асимметричных алгоритмов
Страницы
- « первая
- ‹ предыдущая
- …
- 58
- 59
- 60
- 61
- 62
- …
- следующая ›
- последняя »
