Быстрые алгоритмы вычисления преобразований на основе эллиптических кривых с предварительными вычислениями

Эффективные алгоритмы вычисления преобразований на основе эллиптических кривых - сравнительно новая область исследований, представляющая огромный интерес. Рассмотрено эффективное скалярное умножение точки эллиптической кривой, определенной над простым полем, с использованием предварительных вычислений. В основе предлагаемых алгоритмов лежат методы несовместного представления скаляра (Non-Adjacent Form, NAF) с окном фиксированной и переменной ширины (скользящим окном). Для оценки эффективности полученных и ранее предложенных алгоритмов введен критерий эффективности, основанный на средней вычислительной сложности. Для получения новых более эффективных алгоритмов использованы эффективные операции в простом поле, операции с точкой: сложение (ADD); удвоение (DBL и DBLjJ; операция "удвоить и сложить" (DA); масштабирование (SCALE); свойства аффинной координатной системы; свойства координатной системы Якоби; свойства координатной системы Якоби-Чудновского. Для алгоритмов сформулированы и доказаны утверждения относительно их вычислительной сложности.

Литература

[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örn 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).