Abstract
In this paper we examine the development of a high-speed implementation of a system to perform exponentiation in fields of the form GF(2n). For sufficiently large n, this device has applications in public-key cryptography. The selection of representation and observations on the structure of multiplication have led to the development of an architecture which is of low complexity and high speed. A VLSI implementation has being fabricated with measured throughput for exponentiation for cryptographic purposes of approximately 300 kilobits per second.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Diffie, W., and M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, Vol. 22, 1976, pp. 472–492.
Diffie, W., The first ten years of public-key cryptography, Proceeding of the IEEE, Vol. 76, May 1988, pp. 560–577.
Rivest, R., A. Shamir, and L. Adleman, A method of obtaining digital signatures and public-key cryptosystems, Communications of the ACM, Vol. 21, pp. 120–126.
Blake, I., P. Van Oorschot, and S. Vanstone, Complexity issues for public-key cryptography, Proceedings of the Nato Advance Research Institute Conference, Ciocco, Italy, July 1986.
Coppersmith, D., Cryptography, IBM Journal of Research and Development, March 1987, pp. 244–248.
Beth, T., and D. Gollman, Algorithm engineering for public-key algorithms, IEEE Journal on Selected Areas in Communication, Vol. 7, No. 4, May 1989, pp. 458–466.
Brickell, E., A survey of hardware implementations of RSA, Proceedings of Crypto '89, Santa Barbara, CA, August, 1989.
ElGamal, T., A public-key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, Vol. 31, 1985, pp. 469–472.
Hastad, J., On using RSA with low exponent in a public-key network, Advances in Cryptography—Crypto '85, Springer-Verlag, New York, 1986, pp. 403–408.
Ore, O., On a special class of polynomials, Transactions of the American Mathematical Society, Vol. 35, 1933, pp. 559–584.
Lenstra, H. W., and R. J. Schoof, Primitive normal bases for finite fields, Mathematics of Computation, Vol. 48, 1987, pp. 217–232.
Wah, P., and M. Wang, Realization and application of the Massey-Omura lock, Proceedings of the 1984 International Zurich Seminar on Digital Communications, March 1984, pp. 175–182.
Agnew, G., R. Mullin, and S. Vanstone, Arithmetic operations in GF(2n), Submitted to the Journal of Cryptology.
Omura, J., and J. Massey, U.S. patent #4,587,627, May, 1986.
Onyszchuk, I., R. C. Mullin, and S. A. Vanstone, U.S. patent #4,745,568, May 1988.
Mullin, R. C., I. M. Onyszchuk, S. A. Vanstone, and R. M. Wilson, Optimal normal bases in GF(pn). Discrete Applied Mathematics, Vol. 22, 1988–89, pp. 149–161.
Rosati, T., A high-speed data encryption processor for public key cryptography, Proceeding of IEEE Custom Integrated Circuits Conference, San Diego, CA, May 1989, pp. 12.3.1–12.3.5.
Agnew, G., R. Mullin, and S. Vanstone, An interactive data exchange protocol based on discrete exponentiation, Proceedings of Eurocrypt '88, May 1988, Lecture Notes in Computer Science, Vol. 330, Springer-Verlag, Berlin, pp. 159–166.
Rueppel, R., Correlation immunity and the summation generator, Proceedings of Crypto '85, Lecture Notes in Computer Science, Vol. 218, Springer-Verlag, Berlin, pp. 260–272.
Ash, D., I. Blake, and S. Vanstone, Low complexity normal bases, Discrete Applied Mathematics, Vol. 25, 1989, pp. 191–210.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Agnew, G.B., Mullin, R.C., Onyszchuk, I.M. et al. An implementation for a fast public-key cryptosystem. J. Cryptology 3, 63–79 (1991). https://doi.org/10.1007/BF00196789
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00196789