13 / 14
координат Якоби; метода замены умножений в поле
F
p
возведением в
квадрат; метода Монтгомери и быстрых композитных операций
DA
и
T
(“утроения”). Операция
c
−→
˜
c
обозначает преобразование и со-
хранение точки из координат
c
в
˜
c
, если
c
не совпадают с
˜
c
и только
сохранение, если совпадают.
Проанализирован метод несовместной формы представления ска-
ляра со скользящим окном
w
(
s
\
w
NAF
) и на его основе получен новый
более быстрый, чем известный
s
\
w
NAF
-алгоритм Хенкерсона ска-
лярного умножения точки эллиптической кривой
a
s
\
w
NAF
. Доказано
утверждение относительно вычислительной сложности предложенно-
го алгоритма
a
s
\
w
NAF
. Для алгоритма
a
s
\
w
NAF
выполняется соотноше-
ние
S
a
s
\
w
NAF
=
4
3
(2
w
−
2
−
1)
.
ЛИТЕРАТУРА
1.
Hankerson D.
,
Menezes A.
,
Vanstone S.
Guide to elliptic curve cryptography.
Springer-Verlag, 2004.
2.
Matthieu R.
Fast and regular algorithms for scalar multiplication over elliptic curves
// IACR Cryptology. 2011. No. 338.
3.
Rokhlin V.
,
Tygert M.
Fast algorithms for spherical harmonic expansions // SIAM J.
Sci. Computing. 2008. No. 27 (6). P. 1903–1928.
4.
Hisil H.
,
Carter G.
. Ed. Dawson E. New formulae for efficient elliptic curve
arithmetic. 2007.
5.
Bernstein Daniel J
.,
Lange T.
Explicit-formulas database. 2014. URL:
http://hyperelliptic.org/EFD(дата обращения: 03.01.2015).
6.
Хлебородов Д.С.
Эффективные алгоритмы скалярного умножения точки эллип-
тической кривой без предварительных вычислений // Глобальный научный по-
тенциал. 2014. № 5 (38). 35 с.
7.
Bj¨orn F
. Double-and-add with relative Jacobian coordinates // Cryptology. 2014.
ePrint Archive.
8.
Bernstein Daniel J.
,
Lange T.
Faster addition and doubling on elliptic curves. 2007.
P. 29–50.
9.
Dygin D.M.
,
Grebnev S.V.
Efficient implementation of the GOST R 34.10 digital
signature scheme using modern approaches to elliptic curve scalar multiplication,
2013.
10.
Edwards H.M.
A normal form for elliptic curves // Bulletin of the
American Mathematical Society. 2007. No. 44. P. 393–422. URL:
http://www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html(дата
обращения: 18.03.2015).
REFERENCES
[1] Hankerson D., Menezes A., Vanstone S. Guide to elliptic curve cryptography.
Springer-Verlag, 2004.
[2] Matthieu R. Fast and regular algorithms for scalar multiplication over elliptic curves.
IACR Cryptology
, 2011, no. 338.
[3] Rokhlin V., Tygert M. Fast algorithms for spherical harmonic expansions.
SIAM J.
Sci. Computing
, 2008, no. 27 (6), pp. 1903–1928.
[4] Hisil H., Carter G., Ed.: Dawson E. New formulae for efficient elliptic curve
arithmetic, 2007.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3 77