Abstract
Modular exponentiation in a finite field is the basic computation involved in most public key crypto systems, such as Diffie-Hellman key exchange, ElGamal, etc. The current paper presents a new parallel architecture whereby the modular multiplication and squaring can be processed simultaneously in GF(2m) in m clock cycles using a cellular automata. Since the proposed cellular automata architecture is simple, regular, modular, cascadable, it can also be utilized efficiently for the implementation of VLSI.
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
Preview
Unable to display preview. Download preview PDF.
References
R.J. McEliece: Finite Fields for Computer Scientists and Engineerings, Kluwer Academic, New York, 1987
W. Diffie and M.E. Hellman: New directions in cryptography, IEEE Trans. on Info. Theory, Vol. 22, pp. 644–654, Nov. 1976.
T. ElGamal: A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. on Info. Theory, Vol. 31, No 4., pp. 469–472, 1985.
A.J. Menezes: Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, 1993.
C.-S. Yeh, Irving S. Reed, T.K. Truong: Systolic Multipliers for Finite Fields GF(2m), IEEE Transactions on Computers, Vol. C-33, No. 4, pp. 357–360, 1984.
C.L. Wang, J.L. Lin: Systolic Array Implementation of Multipliers for Finite Fields GF(2m), IEEE Transactions on Circuits and Systems, Vol. 38, No. 7, pp. 796–800, 1991.
P.L. Montgomery, Modular multiplication without trial division, Mathematics of Computation, Vol. 44, No. 170, pp. 519–521, 1985.
M. Delorme, J. Mazoyer: Cellular Automata, Kluwer Academic Publishers 1999.
S. Wolfram: Cellular Automata and Complexity, Addison-Wesly Publishing Company, 1994.
E. R. Berlekamp: Bit-Serial Reed-Solomon Encoders, IEEE Transactions on Information Theory, Vol. IT-28, No. 6, pp. 869–874, 1982.
C. Parr: Fast Arithmetic for Public-Key Algorithms in Galois Fields with Composite Exponents, IEEE Transactions on computers, Vol. 48, No. 10, pp. 1025–1034, 1999.
P.P. Choudhury, R. Barua, Cellular Automata Based VLSI Architecture for Computing Multiplication And Inverse In GF(2m), IEEE Proceeding of the 7th International Conference on VLSI Design, pp. 279–282, January 1994.
Knuth, The Art of Computer Programming, Vol. 2/Seminumerical Algorithms, Addison-Wesley, 1969.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ku, KM., Ha, KJ., Kim, HS., Yoo, KY. (2002). New Parallel Architecture for Modular Multiplication and Squaring Based on Cellular Automata. In: Fagerholm, J., Haataja, J., Järvinen, J., Lyly, M., Råback, P., Savolainen, V. (eds) Applied Parallel Computing. PARA 2002. Lecture Notes in Computer Science, vol 2367. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48051-X_36
Download citation
DOI: https://doi.org/10.1007/3-540-48051-X_36
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43786-4
Online ISBN: 978-3-540-48051-8
eBook Packages: Springer Book Archive