Method for accelerated modular squaring of long length numbers for cryptographic application

Authors

  • O.P. Markovskyi National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute” https://orcid.org/0000-0003-3483-4233
  • Ghassan Abdel Jalil Halil Al-Mrayat National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”

DOI:

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

Keywords:

modular exponentiation, modular squaring, Montgomary modular reductions, abridged multiplication technologies, open key cryptography

Abstract

The article theoretically substantiates and proposes a method for accelerated modular squaring of long length numbers.

Acceleration modular square calculation is achieved through the combined using of abridged multiplication technology, alternating cycles of multiplicative operations and partial modular reduction, as well as organizing simultaneous processing of a group of bits using pre-calculations under reduction.

The methodology for constructing of precomputations table for group Montgomery reduction is described in detail, as well as the proposed procedure for quickly calculating a modular square using abridged multiplication technologies and simultaneous Montgomery reduction of several digits. The presentation is illustrated with a numerical example.

It is shown that the proposed method makes it possible to speed up the computational implementation of the modular squaring operation, which is important for cryptographic applications, by 5-6 times compared to known technologies.

References

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.

Downloads

Published

2024-04-01

Issue

Vol. 1 No. 77 (2024)

Section

Статті

License

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

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

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

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