2 / 14
Keywords
:
fast algorithms, elliptic curves, precomputations, computational
complexity, scalar multiplication of point.
Введение.
Преобразования на основе эллиптических кривых ши-
роко используются в криптосистемах с открытым ключом, в частности
при вычислении цифровых подписей в отечественном (ГОСТ Р 34.10–
2012) и зарубежных (FIPS PUB 186, ANSI X9.62, SECG) стандартах.
Такие криптосистемы, построенные на эллиптических кривых, обес-
печивают снижение вычислительных затрат, энергопотребления и па-
мяти при обеспечении высокого уровня безопасности. Преобразования
на основе эллиптических кривых также находят свое применение в ал-
горитмах факторизации целых чисел (метод Ленстры— ECM, Elliptic
Curve Factorization Method) и в алгоритмах тестирования натураль-
ных чисел на простоту. Такие алгоритмы представляют практический
и теоретический интерес. Несмотря на значительные успехи многих
исследователей в данной области, интерес к получению новых резуль-
татов по ускорению преобразований сохраняется вследствие большой
актуальности приведенных выше задач.
Критерий эффективности.
Рассмотрим поле
F
p
, такое, что
p
—
простое число и для
a, b
∈
F
p
выполняется неравенство
4
a
3
+
+ 27
b
2
6
≡
0 (mod
p
)
.
Тогда эллиптическая кривая
E(
F
p
)
над
F
p
,
опре-
деленная параметрами
a, b
∈
F
p
, состоит из набора решений или точек
P
= (
x, y
)
, x, y
∈
F
p
, уравнения
E
(
F
p
) :
y
2
=
x
3
+
ax
2
+
b
(mod
p
)
,
вместе с особой точкой
O
, называемой точкой в бесконечности.
Уравнение
y
2
=
x
3
+
ax
2
+
b
( mod
p
)
задано в форме Вейерштрасса и
называется определяющим уравнением
E
(
F
p
)
. Для точки
P
= (
x
P
, y
P
)
x
P
является
x
-координатой
P
, а
y
P
—
y
-координатой точки
P
. Такого
рода интерпретация точки называется аффинными координатами.
Набор точек на
E
(
F
p
)
представляет собой абелевую
группу точек
эллиптической кривой
с операцией сложения
(
E
(
F
p
)
,
)
[1].
Главная операция преобразования на основе эллиптических кри-
вых —
скалярное умножение точки
: дано
k
∈
Z
и точка
P
∈
E
(
F
p
)
,
скалярное умножение — процесс сложения точки
P
с собой
k
раз:
dP
=
P . . . P
| {z }
k
. Результат скалярного умножения обозначается
kP
.
Операцией
мультискалярного умножения
называется преобразование
вида:
n
i
=1
k
i
Q
i
,
k
i
∈
Z
,
Q
i
∈
E
(
F
p
)
[2].
Для построения эффективных алгоритмов на основе эллиптиче-
ских кривых и оценки их вычислительной сложности воспользуемся
иерархическим подходом. Рассмотрим математическую архитектуру
алгоритмов (рис. 1) на основе эллиптических кривых, состоящую из
пяти уровней. Каждый уровень представляет собой множество алго-
ритмов, являющихся основой для получения алгоритмов вышестоя-
щего уровня методом композиции.
66 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3