Abstract
The modular exponentiation on the finite field is the basic operation in most public key crypto systems. In this paper, we propose a multiplier/squarer which simultaneously processes the modular multiplication and squaring over GF(2m) based on cellular automata. For effective exponentiation on GF(2m), we use a proposed multiplier/squarer. Since the cellular automata architecture is simple, regular, modular and cascadable, it can 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, New York: Kluwer Academic, 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(4). pp. 469–472, July 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, April 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,July 1991.
P.L. Montgomery, “Modular multiplication without trial division”, Mathematics of Computation, 44(170):519–521, April, 1985.
M. Delorme, J. Mazoyer, Cellular Automata, KLUWER ACADEMIC PUBLISHERS 1999.
STEPHEN WOLFRAM, Cellular Automata and Complexity, Addison-Wesly Publishing Company, 1994.
ELWYN R. BERLEKAMP, “Bit-Serial Reed-Solomon Encoders”, IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-28, NO. 6, pp. 869–874, November, 1982.
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.
P.A. Scott, S.J. Simmons, S.E. Tavares, and L.E. Peppard, “Architectures for Exponentiation in GF(2m)”, IEEE J. Selected Areas in Comm., VOL.6., NO. 3, pp. 578–586, April, 1988.
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, October, 1999.
Kyo-Min Ku, Kyeoung-Ju Ha, Hyun-Sung Kim, Kee-Young Yoo, “New Parallel Architecture for Modular Multiplication and Squaring Based on Cellular Automata”., PARA 2002, LNCS 2367, pp.359–369, 2002
C.L. Wang, “Bit-Level Systolic Array for Fast Exponentiation in Gf(2m)”, IEEE TRANSACTIONS ON COMPUTERS, VOL. 43, NO. 7, pp. 838–841, July, 1994.
D. D. Gajski, Principles of Digital Design, Prentice-Hall International, Inc., 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ku, KM., Ha, KJ., Yoo, KY. (2003). Time-Space Efficient Exponentiation over GF(2m). In: Kumar, V., Gavrilova, M.L., Tan, C.J.K., L’Ecuyer, P. (eds) Computational Science and Its Applications — ICCSA 2003. ICCSA 2003. Lecture Notes in Computer Science, vol 2667. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44839-X_92
Download citation
DOI: https://doi.org/10.1007/3-540-44839-X_92
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40155-1
Online ISBN: 978-3-540-44839-6
eBook Packages: Springer Book Archive