Метод прискореного модулярного піднесення до квадрату довгих чисел для криптографічних застосувань

Автор(и)

  • О.П. Марковський Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» https://orcid.org/0000-0003-3483-4233
  • Гассан Абдель Жаліль Аль-Мріят Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

DOI:

https://doi.org/10.18372/2073-4751.77.18659

Ключові слова:

модулярне експоненціювання, модулярне піднесення до квадрату, модулярна редукція Монтгомері, технології скороченого множення, криптографія з відкритим ключем

Анотація

В статті теоретично обґрунтовано та розроблено метод прискореного модулярного піднесення до квадрату чисел великої розрядності.

Прискорення обчислення модулярного квадрату досягається за рахунок комбінованого застосування технологій скороченого множення, перемежування циклів мультиплікативних операцій та групової редукції, а також організації одночасної обробки групи розрядів з використанням передобчислень при реалізації модулярної редукції.

Детально викладено методику побудови таблиці передобчислень для групової редукції Монтгомері а також запропоновану процедуру швидкого обчислення модулярного квадрату з застосуванням технологій скороченого множення та одночасної редукції Монтгомері групи розрядів. Виклад проілюстровано числовим прикладом.

Показано, що запропонований метод дозволяє прискорити в 5-6 раз обчислювальну реалізацію важливої для криптографічних застосувань операції модулярного множення довгих чисел в порівнянні з відомими технологіми.

Посилання

Schneier B. Applied Cryptography. Protocols. Algorithms and Source codes in C. New York : John Wiley & Sons, Inc., 1996. 758 p.

Giorgi P., Imbert L., Izard T. Parallel modular multiplication on multi-core processors. 2013 IEEE 21st Symposium on Computer Arithmetic : proceedings, Austin, TX, USA, 7–10 April 2013 / IEEE. Piscataway, 2013. P. 135–142. DOI: 10.1109/ARITH.2013.20

Jurcut A. D., Ranaweera P. Xu L. Introduction to IoT Security. IoT Security: Advances in Authentication / ed. by M. Liyanage et al. Hoboken, 2020. P. 27–64.

Zuras D. More on squaring and multiplying larges integers. IEEE Transactions on Computers. 1994. Vol. 43, no. 8. Р. 899–908.

Markovskyi O. et al. An Accelerate Approach for Public Key Cryptography Implementation on IoT Terminal Platforms. 2023 13th International Conference on Dependable Systems, Services and Technologies (DESSERT) : proceedings, Greece, Athens, 13–15 October / IEEE. Danvers, 2023. 4 p. DOI: 10.1109/DESSERT61349.2023.10416516

Menezes A. J., van Oorschot P. C., Vanstone S. A, Handbook of Applied Cryptography. 1st ed. Boca Raton : CRC Press, 1996. 780 p.

Barrett P. Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. Lecture Notes in Computer Science. Vol. 263. Advances in Cryptology - CRYPTO '86. Proceedings / ed. by A. M. Odlyzko. Berlin, 1987. P. 311–323.

Montgomery P. Modular multiplication without trial. Mathematics of Computation. 1985. Vol. 44, no. 170. P. 519–521.

Dhem J.-F., Quisquater J.-J. Recent results on modular multiplications for smart cards. Lecture Notes in Computer Science. Vol. 1820. Smart Card. Research and Applications. Third International Conference, CARDIS'98, Louvain-la-Neuve, Belgium, September 14-16, 1998. Proceedings / ed. by J.-J. Quisquater, B. Schneier. Berlin, 2000. P. 336–352.

Karatsuba A., Ofman Y. Multiplication of many-digital numbers by automatic computers. Proc. USSR Acad. Sci. 1962. Vol. 145, no. 2. P. 293–294.

Schὅnhage A., Strassen V. Schnelle Multiplikation grosser Zahlen. Computing. 1971. Vol. 7. 1971. P. 281–292.

Fừrer M. Faste Integer Multiplication. SIAM Journal on Computing. 2009. Vol. 39, no. 3. P. 979–1005.

##submission.downloads##

Опубліковано

2024-04-01

Номер

Том 1 № 77 (2024)

Розділ

Статті

Ліцензія

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

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.

  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.

  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).