ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ ВЫЧИСЛЕНИЙ В ЭЛЛИПТИЧЕСКИХ КРИВЫХ

Александр Игоревич Скрипко, Александр Николаевич Велигура

Аннотация


В настоящее время повсеместно применяются стандартизированные криптоалгоритмы, использующие вычисления в эллиптических кривых. В силу постоянно возрастающих требований к скорости их выполнения, становится актуальной задача оптимизации их реализации. В связи с широким использованием вычислений в группе точек эллиптической кривой на различных технических устройствах, применяемых для обеспечения безопасности информационных технологий, целесообразно сформировать оптимизационную задачу вычислений в эллиптических кривых. Решение полученной задачи позволило бы находить оптимальный в данных условиях путь вычисления. Подобный подход привёл бы к повышению быстродействия криптоалгоритмов на устройствах, обеспечивающих защиту информации. В статье представлен один из возможных подходов к оптимизации вычислений в эллиптических кривых с точки зрения математического программирования. Для формирования соответствующей оптимизационной задачи вводятся понятия композиции операций в группе точек эллиптической кривой и композиции методов вычисления произведения. Сведение оптимизации вычислений в эллиптических кривых к задачам математического программирования позволяет исследовать вопрос применимости известных методов оптимизации к вычислениям указанного типа.


Ключевые слова


эллиптическая криптография; оптимизация вычислений; математическое программирование

Полный текст:

PDF

Литература


1. Bluhm M. Software optimization of binary elliptic curves arithmetic using modern processor architectures. 2013. 210 pp. URL (дата обращения: 11.06.2017): https://www.emsec.rub.de/media/attachments/files/2014/11/MA_Bluhm.pdf.

2. Longa, P. Accelerating the scalar Multiplication on Elliptic Curve Cryptosystems over Prime Fields : for the degree of Master of Applied Science 2007. — 173 pp.

3. Gueron S., Krasnov V. Fast Prime Field Elliptic Curve Cryptography with 256 Bit Primes. 2014. 17 pp. URL (дата обращения: 11.06.2017): https://eprint.iacr.org/2013/816.pdf.

4. Bernstein D., Lange T. Analysis and optimization of elliptic-curve single-scalar multiplication. 2008. 19 pp. URL (дата обращения: 11.06.2017): http://www.hyperelliptic.org/EFD/precomp.pdf.

5. Feng M., Zhu B., Xu M., Li S. Efficient Comb Elliptic Curve Multiplication Methods Resistant to Power Analysis. 2005. 31 pp. URL (дата обращения: 11.06.2017): https://eprint.iacr.org/2005/222.pdf.

6. Cohen H., Miyaji A., Ono T. Efficient Elliptic Curve Exponentiation Using Mixed Coordinates. 2002. 14 pp.

7. Болотов А. А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. 2006. 280 c.

8. Giorgia P., Imberta L., Izarda T. Optimizing Elliptic Curve Scalar Multiplication for small scalars. 2009. 10 pp.

9. Blake I. F., Seroussi G, Smart N. P. Elliptic Curves In Cryptography. 1999. 217 pp.

10. Hankeron D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography. 2004. 331 pp.

11. Мину М. Математическое программирование. Теория и алгоритмы. 1990. 488 с.

12. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. 1982, 416 с.

13. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. 1985. 512 с.

14. Jiang Y., Jiang Z. Robust Adaptive Dynamic Programming. 2017. 216 pp.




DOI: http://dx.doi.org/10.26583/bit.2017.3.08

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.