Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Архів
Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
Том 60 >>> № 5 ВЕРЕСЕНЬ — ЖОВТЕНЬ 2024
-->

DOI 10.34229/KCA2522-9664.24.5.15
УДК 004.421

І.О. ПРОЦЬКО
Національний університет «Львівська політехніка», Львів, Україна,
 ihor.o.protsko@lpnu.ua

О.В. ГРИЩУК
ТОВ «SoftServe», Львів, Україна,  ocr@ukr.net


РЕАЛІЗАЦІЯ МНОЖЕННЯ МОНТГОМЕРІ
ДЛЯ ПРИСКОРЕННЯ ОБЧИСЛЕННЯ МОДУЛЯРНОГО
ЕКСПОНЕНЦIЮВАННЯ БАГАТОРОЗРЯДНИХ ЧИСЕЛ

Анотація. Проведено порівняння та аналіз використання розробленої програмної реалізації класу MontgomeryArithmetic для обчислення модулярного експоненцiювання. Виконано порівняння швидкості виконання розробленого модулярного множення Монтгомері та звичайного модулярного множення для обчислення модулярного експоненцiювання на основі методу двійкового піднесення справа наліво для фіксованої основи з попереднім обчисленням скороченого набору залишків. Отримані результати обчислень модулярного експоненцiювання з розпаралелюванням на основі багатопотоковості та з використанням розробленого модулярного множення Монтгомері на комп’ютерах загального призначення свідчать про пришвидшення обчислень у середньому в 1.5 раза порівняно з функціями модулярного піднесення до степеня з програмних бібліотек MPIR, OpenSSL, Crypto++.

Ключові слова: модулярне множення, модулярне експоненцiювання, паралельні багатопотокові обчислення, передобчислення, багаторозрядні числа.


повний текст

СПИСОК ЛІТЕРАТУРИ

  • 1. Задірака В.К., Терещенко А.М. Комп’ютерна арифметика багаторозрядних чисел у послідовній та паралельній моделях обчислень. Київ: Наук. думка, 2021. 152 с.

  • 2. St. Denis T., Rose G. BigNum Math: Implementing cryptographic multiple precision arithmetic. Syngress Publishing, 2006. 296 p.

  • 3. Montgomery P.L. Modular multiplication without trial division. Mathematics of Computation. 1985. Vol. 44, N 170. P. 519–521. URL: www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777282-X/S0025-5718-1985-0777282-X.pdf .

  • 4. Bajard J.-C., Eynard J., Merkiche N. Montgomery reduction within the context of residue number system arithmetic. Journal of Cryptographic Engineering. 2018. Vol. 8, Iss. 3. P. 189–200. doi.org/10.1007/s13389-017-0154-9.

  • 5. Will M.A., Ko R.K.L. Computing mod with a variable lookup table. Proc. 4th International Symposium “Security in Computing and Communications” (SSCC 2016) (21–24 September 2016, Jiapur, India). Jiapur, 2016. P. 3–17. doi.org/10.1007/978-981-10-2738-3_1.

  • 6. Kawamura S., Komano Y., Shimizu H., Yonemura T. RNS Montgomery reduction algorithms using quadratic residuosity. Journal of Cryptographic Engineering. 2019. Vol. 9, Iss. 4. P. 313–331. doi.org/10.1007/s13389-018-0195-8.

  • 7. Knezevic M., Vercauteren F., Verbauwhede I. Faster interleaved modular multiplication based on Barrett and Montgomery reduction methods. IEEE Transactions on Computers. 2010. Vol. 59, Iss. 12. P. 1715–1721. doi.org/10.1109/TC.2010.93.

  • 8. Bansal M., Kumar A., Devrari A., Bhat A. Implementation of modular exponentiation using Montgomery algorithms. International Journal of Scientific Engineering Research (IJSER). 2015. Vol. 6, Iss. 11. P. 1272–1277. URL: www.ijser.org/onlineResearchPaperViewer. aspx?IMPLEMENTATION-OF-MODULAR-EXPONENTIATION-USING-MONTGOMERY -ALGORITHMS.pdf .

  • 9. Boiarshyn I., Markovskyi O., Ostrovska B. Organization of parallel execution of modular multiplication to speed up the computational implementation of public-key cryptography. Information, Computing and Intelligent Systems. 2022. N 3. P. 26–32. doi.org/10.20535/2708-4930.3.2022.265418.

  • 10. Buhrow B., Gilbert B., Haider C. Parallel modular multiplication using 512-bit advanced vector instructions: RSA fault-injection countermeasure via interleaved parallel multiplication. Journal of Cryptographic Engineering. 2022. N 12. P. 95–105. doi.org/10.1007/s13389-021-00256-9.

  • 11. Li B., Wang J., Ding G., Fu H., Lei B., Yang H., Bi J., Lei S. A high-performance and low-cost Montgomery modular multiplication based on redundant binary representation. IEEE Trans. Circuits Syst. II Express Briefs. 2021. Vol. 68, Iss. 7. P. 2660–2664. 10.1109/TCSII.2021.3053630.

  • 12. Bajard J.-C., Merkiche N. Double level Montgomery cox-rower architecture, new bounds. Proc. 13 International Conference on Smart Card Research and Advanced Applications (CARDIS) (6–7 November 2014, Paris, France). Paris, 2014. Lecture Notes in Computer Science. 2015. Vol. 8968. P. 139–153. doi.org/10.1007/978-3-319-16763-3_9.

  • 13. Erdem S.S., YanЗk T., elebi A. A general digit-serial architecture for Montgomery modular multiplication. IEEE Trans. Very Large Scale Integr. VLSI Syst. 2017. Vol. 25, Iss. 5. P. 1658–1668. doi.org/10.1109/TVLSI.2017.2652979.

  • 14. Celebi E., Gozutok M., Ertaul L. Implementations of Montgomery multiplication algorithms in machine languages. Proc. International Conference on Security Management (SAM 2008) (14–17 July 2008, Las Vegas, Nevada, USA). Las Vegas, 2008. P. 491–497. URL: www.researchgate.net/publication/221199495_Implementations_of_Montgomery_Multiplication_Algorithms_in_Machine_Languages .

  • 15. Robert J.-M., Negre C., Plantard T. Efficient fixed base exponentiation and scalar multiplication based on a multiplicative splitting exponent recoding. Journal of Cryptographic Engineering. 2019. Vol. 9, Iss. 2. P. 115–136. doi.org/10.1007/s13389-018-0196-7.

  • 16. Prots’ko I., Gryshchuk O. The modular exponentiation with precomputation of redused set of resedues for fixed-base. Radio Electronics, Computer Science, Control. 2022. N 1. P. 58–65. doi.org/10.15588/1607-3274-2022-1-7.

  • 17. Crypto++ Library 8.6. URL: www.cryptopp.com .

  • 18. OpenSSL. Cryptography and SSL/TLS Toolkit, 2021. URL: .

  • 19. PARI/GP home. URL: http://pari.math.u-bordeaux.fr/.

  • 20. MPIR: Multiple Precision Integers and Rationals. URL: http://mpir.org/.

  • 21. Menezes A.J., van Oorschot P.C., Vanstone S.A. Handbook of applied cryptography. Taylor Francis India, 2018. 780 p.

  • 22. Nti R. B., Ryoo K. Area-efficient design of modular exponentiation using Montgomery multiplier for RSA cryptosystem. In: Advanced Multimedia and Ubiquitous Engineering. Park J.J., Loia V., Choo K.-K.R., Yi G. (Eds.). LNEE. 2019. Vol. 518. P. 431–437. doi.org/10.1007/ 978-981-13-1328-8_56.

  • 23. Montgomery multiplication. URL: https://cp-algorithms.com/algebra/montgomery_ multiplication.html #implementation .

  • 24. Prots’ko I., Kryvinska N., Gryshchuk O. The runtime analysis of computation of modular exponentiation. Radio Electronics, Computer Science, Control. 2021. N 3. P. 42–47. doi.org/10.15588/1607-3274-2021-3-4.

  • 25. Prots’ko I., Gryshchuk A., Riznyk V. Efficient multithreading computation of modular exponentiation with pre-computation of residues for fixed-base. Proc. 6th International Workshop on Computer Modeling and Intelligent Systems (CMIS 2023) (3 May 2023, Zaporizhzhia, Ukraine). Zaporizhzhia, 2023. P. 224–234. doi.org/10.32782/cmis/3392-19.

  • 26. Bos J.W., Montgomery P.L., Shumow D., Zaverucha G.M. Montgomery multiplication using vector instructions. In: Selected Areas in Cryptography (SAC 2013). Lange T., Lauter K., Lisonek P. (Eds.). LNCS. 2014. Vol. 8282. doi.org/10.1007/978-3-662-43414-7_24.

  • 27. Процько І.О., Рикмас Р.В., Грищук О.В. Порівняльний аналіз функцій обчислення модульної експоненти. Український журнал інформаційних технологій. 2022. Т. 4, № 1. C. 63–67. doi.org/10.23939/ujit2022.01.063.




Інформація редакції Аннотації статей Автори Архів
Журнал Тематичні Розділи Редакція Редакційна колегія Приклади документів Передплата Контакти
© 2024 Kibernetika.org. All rights reserved.