Abstract
The significant cost of RSA computations affects the efficiency and responsiveness of SSL/TLS servers, and therefore software implementations of RSA are an important target for optimization. To this end, we study here efficient software implementations of modular exponentiation, which are also protected against software side channel analyses. We target superior performance for the ubiquitous ×86_64 architectures, used in most server platforms. The paper proposes optimizations in several directions: the Montgomery multiplications primitives, the w-ary modular exponentiation flow, and reduced cost of side channel mitigation. For a comparison baseline, we use the current OpenSSL version, 1.0.0e. Our implementation—called “RSAZ”—is more than 1.6 times faster than OpenSSL for both 1,024 and 2,048-bit keys, on the previous generation 2010 Intel® Core™ processors and on the 2nd generation Intel® Core™ processors. The RSAZ code was contributed to OpenSSL as a patch, and improvements proposed in an earlier version of this paper have already been incorporated into the future OpenSSL version.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aciiçmez, O., Gueron, S., Seifert, J.P.: New Branch Prediction Vulnerabilities in Open SSL and necessary software countermeasures. In: Cryptography and Coding, 11th IMA International Conference (IMA Int. Conf. 2007), Lecture Notes in Computer Science, vol. 4887, pp. 185–203 (2007)
Aciiçmez, O., Kocç, C.K., Seifert, J.P.: Predicting secret keys via branch prediction. In: Lecture Notes in Computer Science, vol. 4377, pp. 225–242 (2007)
Aciiçmez, O., Schindler, W.: A vulnerability in RSA implementations due to instruction cache analysis and its demonstration on OpenSSL. In: CT-RSA 2008, pp. 256–273 (2008)
Barker, E., Roginsky, A.: Transitions: Recommendation for transitioning the use of cryptographic algorithms and key lengths. In: NIST Special Publication 800-131A, p. 5 (2011). http://csrc.nist.gov/publications/nistpubs/800-131A/sp800-131A.pdf
Brent, R., Zimmermann, P.: Modern Computer Arithmetic. Cambridge University Press (2010). (retrieved from http://www.loria.fr/~zimmerma/mca/pub226.html)
Brumley, D., Boneh, D.: Remote timing attacks are practical. In: Proceedings of the 12th USENIX Security Symposium. pp. 1–14 (2003)
Gopal, V., Guilford, J., Ozturk, E., Feghali, W., Wolrich, G., Dixon, M.: Fast and constant-time implementation of modular exponentiation. In: 28th International Symposium on Reliable Distributed Systems. Niagara Falls, New York, USA (2009). http://www.cse.buffalo.edu/srds2009/escs2009_submission_Gopal.pdf
Gueron, S., Krasnov, V.: Efficient and side channel analysis resistant 512-bit and 1,024-bit modular exponentiation for optimizing RSA1024 and RSA2048 on ×86_64 platforms, OpenSSL #2582 patch. http://rt.openssl.org/Ticket/Display.html?id=2582&user=guest&pass=guest (posted Aug 2011)
Gueron, S., Krasnov, V.: Speeding up Big-Number Squaring. (to be published; ITNG 2012)
Gueron, S.: Efficient Software Implementations of Modular Exponentiation. eprint (2011) http://eprint.iacr.org/2011/239
Gueron, S.: Enhanced Montgomery multiplication. In: Cryptographic Hardware and Embedded Systems (CHES 2002), Lecture Notes in Computer Science, vol. 2523, pp. 46–56 (2002)
Intel: Intel® 64 and IA-32 Architectures Optimization Reference Manual (2011) http://www.intel.com/Assets/PDF/manual/248966.pdf
Koç, Ç.K., Walter, C.D.: Montgomery arithmetic. In: van Tilborg, H. (ed.) Encyclopedia of Cryptography and Security. pp. 298–394, Springer (2005)
Koc, Ç.K., Kaliski, B.S.: Analyzing and comparing Montgomery multiplication algorithms. Micro 16(3), 26–33 (1996) http://islab.oregonstate.edu/papers/j37acmon.pdf
Kounavis, M.E., Kang, X., Grewal, K., Eszenyi, M., Gueron, S., Durham, D.: Encrypting the internet. In: Proceedings of the ACM SIGCOMM 2010 Conference on SIGCOMM (2010) http://portal.acm.org/citation.cfm?id=1851182.1851200
Menezes, A.J., van Oorschot P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (2001) (5th printing)
Montgomery, P.L.: Modular Multiplication Without Trial Division. In: Mathematics of Computation, Volume 44:519–521 (1985)
OpenSSL: The Open Source toolkit for SSL/TLS. http://www.openssl.org/
OpenSSL: CVS Repository, http://cvs.openssl.org/
Percival C.: Cache missing for fun and profit. http://www.daemonology.net/papers/htt.pdf (2005)
Polyakov, A., OpenSSL Team (2011) (personal communications)
Schindler, W.: A timing attack against RSA with the Chinese Remainder Theorem. In: Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, pp. 109–124. Springer (2000)
Walter, C.D.: Montgomery exponentiation needs no final subtractions. Electron. Lett. 35, 1831–1832 (1999)
Walter, C.D.: An overview of Montgomery’s multiplication technique: how to make it smaller and faster. In: Paar, C., Koç, Ç.K. (eds.) Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science, vol. 1717, pp. 80–93 (1999)
Walter, C.D.: Precise Bounds for Montgomery Modular Multiplication and Some Potentially Insecure RSA Moduli. In: CT-RSA, vol. 2010, pp. 30–39 (2002)
Yanık T., Savaş E., Koc Ç.K.: Incomplete reduction in modular arithmetic. IEEE Proc. Comput. Digital Tech. 149, 46–52 (2002)
Ying, H.: Optimization for 1024 bit RSA on ×86_64 platform, OpenSSL #2175 patch, http://rt.openssl.org/Ticket/Display.html?id=2175&user=guest&pass=guest (posted Feb 20, 2010)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gueron, S. Efficient software implementations of modular exponentiation. J Cryptogr Eng 2, 31–43 (2012). https://doi.org/10.1007/s13389-012-0031-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13389-012-0031-5