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

How to Cite

Markovskyi, O., & Al-Mrayat, G. A. J. H. (2024). Method for accelerated modular squaring of long length numbers for cryptographic application. Problems of Informatization and Control, 1(77), 68–79. https://doi.org/10.18372/2073-4751.77.18659

Issue

Vol. 1 No. 77 (2024)

Section

Статті

License

The scientific journal adheres to the principles of Open Access and provides free, immediate, and permanent access to all published materials without financial, technical, or legal barriers for readers.

All articles are published in Open Access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.

Copyright

Authors who publish their works in the journal:

  • retain the copyright to their publications;

  • grant the journal the right of first publication of the article;

  • agree to the distribution of their materials under the CC BY 4.0 license;

  • have the right to reuse, archive, and distribute their works (including in institutional and subject repositories), provided that proper reference is made to the original publication in the journal.