DOI
10.34229/KCA2522-9664.24.5.15
UDC 004.421
IMPLEMENTATION OF MONTGOMERY MULTIPLICATION TO SPEED UP
THE COMPUTATION OF MODULAR EXPONENTIATION OVER MULTI-BIT NUMBERS
Abstract. A comparison and analysis of the use of the developed software implementation of the
class MontgomeryArithmetic for computing modular exponentiation are conducted. The computation speed of the developed Montgomery modular multiplication is compared to the regular modular multiplication for calculating the modular exponentiation based on the right-to-left binary elevation method for a fixed basis with a preliminary calculation of a reduced set of remainders. The obtained results of performing modular exponentiation computations with parallelization based on multithreading on general-purpose computers speed up the computations by an average of 1.5 times using the developed modular Montgomery multiplication compared to the modular exponentiation functions of the MPIR, OpenSSL, and Crypto++ software libraries.
Keywords: modular multiplication, modular exponentiation, multithreading, precomputation, large numbers.
full text
REFERENCES
- 1. Zadiraka V.K., Tereshchenko A.M. Computer arithmetic of multi-bit numbers in serial and parallel computing models [in Ukrainian]. Kyiv: Nauk. Dumka, 2021. 152 p.
- 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: https://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: https://www.ijser.org/onlineResearchPaperViewer.
- 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. /doi.org/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. ttps://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. https://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: https://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: http://www.openssl.org/.
- 19. PARI/GP home. URL: 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: 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., P. (Eds.). LNCS. 2014. Vol. 8282. doi.org/10.1007/978-3-662-43414-7_24.
- 27. Protsko I.O., Rykmas R.V., Hryschuk O.V. Comparative analysis of functions for calculating the modular exponent. Ukrainian Journal of Information Technologies. 2022. Vol. 4, N 1. P. 63–67. doi.org/10.23939/ujit2022.01.063.
