Abstract
This paper proposes a new fast method for calculating modular multiplication. The calculation is performed using a new representation of residue classes modulo M that enables the splitting of the multiplier into two parts. These two parts are then processed separately, in parallel, potentially doubling the calculation speed. The upper part and the lower part of the multiplier are processed using the interleaved modular multiplication algorithm and the Montgomery algorithm respectively. Conversions back and forth between the original integer set and the new residue system can be performed at speeds up to twice that of the Montgomery method without the need for precomputed constants. This new method is suitable for both hardware implementation; and software implementation in a multiprocessor environment. Although this paper is focusing on the application of the new method in the integer field, the technique used to speed up the calculation can also easily be adapted for operation in the binary extended field GF(2m).
Chapter PDF
Similar content being viewed by others
Keywords
- Residue Class
- Modular Multiplication
- Ular Multiplication
- Cryptographic Application
- Digital Signature Algorithm
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
ANSI X9.30. Public Key Cryptography for the Financial Services Industry: Part 1: The Digital Signature Algorithm (DSA). American National Standard Institute. American Bankers Association (1997)
Blakley, G.R.: A Computer Algorithm for Calculating the Product AB Modulo M. IEEE Trans. Computers C-32(5), 497–500 (1983)
Brickell, E.F.: A fast modular multiplication algorithm with application to two key cryptography. In: Chaum, D., et al. (eds.) Advances in Cryptology, Proc. CRYPTO 1982, pp. 51–60. Plenum, New York (1983)
Diffie, W., Hellman, M.E.: New Directions in Cryptography. IEEE Trans. Information Theory 22(11), 644–654 (1976)
ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Information Theory IT-31(4), 469–472 (1985)
Kornerup, P.: High-Radix Modular Multiplication for Cryptosystems. In: Jullien, G., Irwin, M.J., Swartzlander, E. (eds.) Proc. 11th IEEE Symp. Computer Arithmetic, pp. 277–283. Windsor, Canada (1993)
Montgomery, P.L.: Modular Multiplication without Trial Division. Mathematics of Computation 44(170), 519–521 (1985)
Morita, H.: A fast modular multiplication algorithm with application to two key cryptography. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 387–399. Springer, Heidelberg (1990)
Orup, H.: Simplifying quotient determination in high-radix modular multiplication. In: Knowles, S., McAllister, W.H. (eds.) Proc. 12th IEEE Symp. Computer Arithmetic, pp. 193–199. Bath, England (1995)
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Sloan, K.R.: Comments on ‘A Computer Algorithm for Calculating the Product AB Modulo M’. IEEE Trans. Computers C-34(3), 290–292 (1985)
Takagi, N.: A radix-4 modular multiplication hardware algorithm for modular exponentiation. IEEE Trans. Comput. 41(8), 949–956 (1990)
Tenca, A.F., Todorov, G., Koç, Ç.K.: High-Radix Design of a Scalable Modular Multiplier. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 185–201. Springer, Heidelberg (2001)
Walter, C.D.: Space/Time Trade-offs for Higher Radix Modular Multiplication using Repeated Addition. IEEE Trans. Computers 46(2), 139–141 (1997)
Walter, C.D.: Systolic Modular Multiplication. IEEE Trans. Computers 42(3), 376–378 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kaihara, M.E., Takagi, N. (2005). Bipartite Modular Multiplication. In: Rao, J.R., Sunar, B. (eds) Cryptographic Hardware and Embedded Systems – CHES 2005. CHES 2005. Lecture Notes in Computer Science, vol 3659. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11545262_15
Download citation
DOI: https://doi.org/10.1007/11545262_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28474-1
Online ISBN: 978-3-540-31940-5
eBook Packages: Computer ScienceComputer Science (R0)