Hardware complexity of modular multiplication and exponentiation
(2007) IEEE Transactions on Computers — Vol. 56, n° 10, p. 1308-1319 (2007)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- Large integer Modular Multiplication (MM) and Modular Exponentiation (ME) are the foundation of most public-key cryptosystems, specifically RSA, Diffie-Helleman, ElGamal, and the Elliptic Curve Cryptosystems. Thus, MM algorithms have been studied widely and extensively. Most of the work is based on the well-known Montgomery Multiplication Method and its variants, which require standard multiplication operations. Despite their better complexity orders, Karatsuba and FFT algorithms seem to rarely be used for hardware implementation. In this paper, we review their hardware complexity and propose original implementations of MM and ME that become useful for 24-bit operators (Karatsuba algorithm) or 373-bit operators (FFT algorithm).
- Affiliations
Citations
David, J. P., Kalach, K., & Tittley, N. (2007). Hardware complexity of modular multiplication and exponentiation. IEEE Transactions on Computers, 56(10), 1308-1319. https://doi.org/10.1109/TC.2007.1084 (Original work published 2007)