10.14489/vkit.2025.04.pp.045-051

DOI: 10.14489/vkit.2025.04.pp.045-051

Наурас Х. С., Левина А. Б.
МЕТОД УМНОЖЕНИЯ ТОЧЕК НА ЭЛЛИПТИЧЕСКОЙ КРИВОЙ EDWARDS25519 ДЛЯ УСТРОЙСТВ С ОГРАНИЧЕННЫМИ РЕСУРСАМИ
(с. 45-51)

Аннотация. Разработан метод умножения точек эллиптической кривой, адаптированный для устройств с ограниченными ресурсами, таких, как Микроконтроллер ATmega2560. С использованием кривой Edwards25519 в однородной системе координат в данном исследовании интегрируются принципы циклической группы точек эллиптической кривой, свойства противоположного числа из теории групп и оконный метод для умножения точек. Предложенный подход способствует сокращению вычислительных циклов до 60 %, снижению использования полупроводниковой оперативной памяти до 78,66 % и уменьшению потребления флеш-памяти до 28,21 %, а значит, его целесообразно использовать для сред с ограниченными ресурсами.

Ключевые слова: эллиптическая кривая; умножение точек; Edwards25519; однородная система координат; устройства с ограниченными ресурсами.

Nawras H. S., Levina A. B.
METHOD OF POINT MULTIPLICATION ON THE EDWARDS25519 ELLIPTIC CURVE APPLIED TO RESOURCE-CONSTRAINED DEVICES
(pp. 45-51)

Abstract. As secure communication becomes increasingly important for IoT devices, such as those used in smart city applications and healthcare, there is a critical need to improve the efficiency of cryptographic operations, especially on embedded microcontrollers with limited computational power and memory. Advanced optimization techniques are essential to enable efficient and secure cryptographic implementations in such environments. Elliptic Curve Cryptography (ECC) emerges as the optimal choice due to its combination of small key sizes and high security levels, making it particularly well-suited for resource-constrained devices. Implementing point multiplication on elliptic curves, which is the core operation of ECC applications such as digital signatures and Diffie-Hellman key exchange, poses a significant challenge in resource-constrained devices. To address these challenges, this study focuses on optimizing elliptic curve point multiplication in resource-constrained environments by proposing an optimized method tailored for the Arduino Atmega 2560 microcontroller as a resource-constrained device. By leveraging the Edwards25519 curve in a homogeneous coordinate system, the study introduces a technique that integrates principles of cyclic groups of elliptic curve points, the additive inverse property, and the windowing method for point multiplication. The proposed method is implemented using the C programming language and assembly code, using the Arduino IDE. The approach achieves notable improvements, including a reduction in computation cycles by up to 60 %, a decrease in SRAM usage by up to 78.66 %, and a reduction in Flash-memory consumption by up to 28.21 %, highlighting its suitability for resource-limited environments.

Keywords: Elliptic curve; Point multiplication; Edwards25519; Homogeneous coordinate system; Resource-constrained devices.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

Х. С. Наурас, А. Б. Левина (Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» имени В. И. Ульянова (Ленина), Санкт-Петербург, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

H. S. Nawras, A. B. Levina (Saint Petersburg Electrotechnical University “LETI”, Saint Petersburg, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Ullah S., Zahilah R. Curve25519 based light-weight end-to-end encryption in resource constrained autonomous 8-bit IoT devices // Cybersecurity. 2021. V. 4, No. 11. DOI: 10.1186/s42400-021-00078-6
2. Park D., Chang N. S., Lee S., Hong S. Fast implementation of NIST P-256 elliptic curve cryptography on 8-bit AVR processor // Applied Sciences. 2020. V. 10, No. 24, P. 8816. DOI: 10.3390/app10248816
3. Twisted edwards curves / D. J. Bernstein, P. Birkner, M. Joye, et al // Progress in Cryptology–AFRICACRYPT 2008: First International Conference on Cryptology in Africa. June 11–14 2008. Casablanca, Morocco, Proceedings 1. Berlin: Springer Berlin Heidelberg, 2008. P. 389–405.
4. Hankerson D., Menezes A. Elliptic curve cryptography // Encyclopedia of Cryptography, Security and Privacy. Berlin: Springer Berlin Heidelberg, 2021. P. 1–2.
5. Paar C., Pelzl J. Understanding cryptography. V. 1. Berlin: Springer-Verlag Berlin Heidelberg, 2010.
6. Izu T., Möller B., Takagi T. Improved elliptic curve multiplication methods resistant against side channel attacks // Progress in Cryptology–INDOCRYPT 2002: Third International Conference on Cryptology in India. December 16–18 2002. Hyderabad, India. Proceedings 3. Berlin: Springer Berlin Heidelberg, 2002. P. 296–313.
7. Shenets N. N., Petushkov A. S. New Regular Sliding Window Algorithms for Elliptic Curve Scalar Point Multiplication // Automatic Control and Computer Sciences. 2021. V. 55, No. 8. P. 1029–1038.
8. Teske E. Speeding up Pollard's rho method for computing discrete logarithms // Algorithmic Number Theory (ANTS 1998)/ Lecture Notes in Computer Sci-ence, V. 1423. P. 541–554. Springer-Veralag Berlin Hei-delberg, 2006. DOI: 10.1007/BFb0054891
9. Josefsson S., Ilari L. Edwards-Curve Digital Signature Algorithm (EdDSA) // RFC 8032 (2017): 1-60.
10. Langley A., Hamburg M., Turner S. Elliptic Curves for Security // RFC 7748. DOI: 10.17487/RFC7748, January 2016. URL: https://www.rfc-editor.org/info/rfc7748 (дата обращения: 13.12.2024).
11. Hutter M., Schwabe P. Multiprecision multiplication on AVR revisited // J. Cryptogr Eng. 2015. V. 5, No. 3. P. 201–214. DOI: 10.1007/s13389-015-0093-2
12. Hutter M., Schwabe P. NaCl on 8-bit AVR microcontrollers // In Progress in Cryptology–AFRICACRYPT 2013: 6th International Conference on Cryptology in Africa, Cairo, Egypt, June 22–24, 2013. Proceedings 6. P. 156–172. Springer Berlin Heidelberg, 2013.

Eng

1. Ullah S., Zahilah R. (2021). Curve25519 based lightweight end-to-end encryption in resource constrained autonomous 8-bit IoT devices. Cybersecurity, 4(11). DOI: 10.1186/s42400-021-00078-6
2. Park D., Chang N. S., Lee S., Hong S. (2020). Fast implementation of NIST P-256 elliptic curve cryp-tography on 8-bit AVR processor. Applied Sciences, 10. DOI: 10.3390/app10248816
3. Bernstein D. J., Birkner P., Joye M. et al. (2008). Twisted edwards curves. Progress in Cryptology–AFRICACRYPT 2008: First International Conference on Cryptology in Africa. Berlin: Springer Berlin Heidelberg.
4. Hankerson D., Menezes A. (2021). Elliptic curve cryptography. Encyclopedia of Cryptography, Security and Privacy, 1 – 2. Berlin: Springer Berlin Heidelberg.
5. Paar C., Pelzl J. (2010). Understanding crypto-graphy. 1. Berlin: Springer-Verlag Berlin Heidelberg.
6. Izu T., Möller B., Takagi T. (2002). Improved elliptic curve multiplication methods resistant against side channel attacks. Progress in Cryptology–INDOCRYPT 2002: Third International Conference on Cryptology in India, 296 – 313. Berlin: Springer Berlin Heidelberg.
7. Shenets N. N., Petushkov A. S. (2021). New Regular Sliding Window Algorithms for Elliptic Curve Scalar Point Multiplication. Automatic Control and Computer Sciences, 55(8), 1029 – 1038.
8. Teske E. (1998). Speeding up Pollard's rho method for computing discrete logarithms. Algorithmic Number Theory. (ANTS 1998). Lecture Notes in Computer Science, 1423, 54 1– 554. DOI: 10.1007/BFb0054891
9. Josefsson S., Ilari L. (2017). Edwards-Curve Digital Signature Algorithm (EdDSA). RFC 8032: 1-60.
10. Langley A., Hamburg M., Turner S. (2016). Elliptic Curves for Security. RFC 7748. Retrieved from https://www.rfc-editor.org/info/rfc7748 DOI: 10.17487/RFC7748
11. Hutter M., Schwabe P. (2015). Multiprecision multiplication on AVR revisited. Journal of Cryptographic Engineering, 5(3), 201 – 214. DOI: 10.1007/s13389-015-0093-2
12. Hutter M., Schwabe P. (2013). NaCl on 8-bit AVR microcontrollers. In Progress in Cryptology–AFRICACRYPT 2013: 6th International Conference on Cryptology in Africa, Proceedings 6, 156 – 172. Cairo: Springer Berlin Heidelberg.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 700 руб. (в том числе НДС 20%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2025.04.pp.045-051

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 700 rubles. (including VAT 20%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2025.04.pp.045-051

and fill out the form