Abstract
Finite field multiplication plays the main role determining the efficiency of public key cryptography systems based on RSA and elliptic curve cryptography (ECC). Most recently, quantum-safe cryptographic systems are proposed based on supersingular isogenies on elliptic curves which require large integer multiplications over extended prime fields. In this work, we present two Montgomery multiplication architectures for special primes used in a post-quantum cryptography system known as supersingular isogeny key encapsulation (SIKE). We optimize two existing Montgomery multiplication algorithms and develop area-efficient and time-efficient Montgomery multiplication architectures for hardware implementations of post-quantum cryptography. Our proposed time-efficient architecture is \(32\%\) to \(42\%\) faster than the leading one (depending on the prime size) available in the literature which has been used in original SIKE submission to the NIST standardization process. The area-efficient architecture is \(42\%\) to \(50\%\) smaller than the counterparts and is about \(3\%\) to \(11\%\) faster depending on the NIST security level.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, FOCS 1994, pp. 124–134 (1994)
Chen, L., et al.: Report on Post-Quantum Cryptography (2016). NIST IR 8105
Jao, D., et al.: Supersingular isogeny key encapsulation. Submission to the NIST Post-Quantum Standardization Project (2019)
Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_2
Koziel, B., Azarderakhsh, R., Mozaffari-Kermani, M., Jao, D.: Post-quantum cryptography on FPGA based on isogenies on elliptic curves. IEEE Trans. Circuit. Syst. I: Regul. Pap. 64(1), 86–99 (2017)
Koziel, B., Azarderakhsh, R., Mozaffari-Kermani, M.: Fast hardware architectures for supersingular isogeny Diffie-Hellman key exchange on FPGA. In: Dunkelman, O., Sanadhya, S.K. (eds.) INDOCRYPT 2016. LNCS, vol. 10095, pp. 191–206. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49890-4_11
Koziel, B., Azarderakhsh, R., Mozaffari-Kermani, M.: A high-performance and scalable hardware architecture for isogeny-based cryptography. IEEE Trans. Comput. 67(11), 1594–1609 (2018)
Roy, D.B., Mukhopadhyay, D.: Post quantum ecc on fpga platform. Cryptology ePrint Archive, Report 2019/568 (2019). https://eprint.iacr.org/2019/568
Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985)
Mrabet, A., et al.: High-performance elliptic curve cryptography by using the CIOS method for modular multiplication. In: Cuppens, Frédéric, Cuppens, Nora, Lanet, Jean-Louis, Legay, Axel (eds.) CRiSIS 2016. LNCS, vol. 10158, pp. 185–198. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-54876-0_15
McIvor, C., McLoone, M., McCanny, J.V.: High-radix systolic modular multiplication on reconfigurable hardware. In: IEEE International Conference on Field-Programmable Technology, pp. 13–18 (2005)
Jao, D., et al.: Supersingular isogeny key encapsulation. Submission to the NIST Post-Quantum Standardization Project (2017)
McIvor, C., McLoone, M., McCanny, J.V.: FPGA Montgomery multiplier architectures - a comparison. In: 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, pp. 279–282, April 2004
Alrimeih, H., Rakhmatov, D.: Fast and flexible hardware support for ECC over multiple standard prime fields. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 22(12), 2661–2674 (2014)
Blum, T., Paar, C.: High-radix montgomery modular exponentiation on reconfigurable hardware. IEEE Trans. Comput. 50(7), 759–764 (2001)
Chen, G., Bai, G., Chen, H.: A high-performance elliptic curve cryptographic processor for general curves over \({\rm GF}(p)\) based on a systolic arithmetic unit. IEEE Trans. Circ. Syst. II: Express Briefs 54(5), 412–416 (2007)
Eberle, H., Gura, N., Shantz, S.C., Gupta, V., Rarick, L., Sundaram, S.: A public-key cryptographic processor for RSA and ECC. In: Proceedings of 15th IEEE International Conference on Application-Specific Systems, Architectures and Processors, pp. 98–110, September 2004
Ghosh, S., Alam, M., Roy Chowdhury, D., Sen Gupta, I.: Parallel crypto-devices for GF(p) elliptic curve multiplication resistant against side channel attacks. Comput. Electr. Eng. 35, 329–338 (2009)
Sakiyama, K., Mentens, N., Batina, L., Preneel, B., Verbauwhede, I.: Reconfigurable modular arithmetic logic unit for high-performance public-key cryptosystems. In: Bertels, K., Cardoso, J.M.P., Vassiliadis, S. (eds.) ARC 2006. LNCS, vol. 3985, pp. 347–357. Springer, Heidelberg (2006). https://doi.org/10.1007/11802839_43
Tenca, A.F., Koç, Ç.K.: A scalable architecture for montgomery nultiplication. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 94–108. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48059-5_10
Vliegen, J., et al.: A compact FPGA-based architecture for elliptic curve cryptography over prime fields. In: ASAP 2010–21st IEEE International Conference on Application-specific Systems, Architectures and Processors, pp. 313–316, July 2010
Kaya Koc, C., Acar, T., Kaliski, B.S.: Analyzing and comparing montgomery multiplication algorithms. IEEE Micro 16(3), 26–33 (1996)
Dussé, S.R., Kaliski, B.S.: A cryptographic library for the motorola DSP56000. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 230–244. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46877-3_21
Acknowledgement
The authors would like to thank the reviewers for their comments. This work is supported in parts by NSF CNS-1801341, NIST-60NANB16D246, and ARO W911NF-17-1-0311.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
El Khatib, R., Azarderakhsh, R., Mozaffari-Kermani, M. (2019). Optimized Algorithms and Architectures for Montgomery Multiplication for Post-quantum Cryptography. In: Mu, Y., Deng, R., Huang, X. (eds) Cryptology and Network Security. CANS 2019. Lecture Notes in Computer Science(), vol 11829. Springer, Cham. https://doi.org/10.1007/978-3-030-31578-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-31578-8_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-31577-1
Online ISBN: 978-3-030-31578-8
eBook Packages: Computer ScienceComputer Science (R0)