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 формат).

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

Скопируйте DOI статьи и перейдите по ссылке https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

В комментарии к заказу обязательно укажите DOI статьи.

Eng

This article is available in electronic format (PDF).

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

Copy the article DOI and follow the link https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

Please specify the article DOI in the order comments.