Elliptic Curve Cryptography and Its Applications to Mobile Devices.
Elliptic Curve Cryptography and Its Applications to Mobile Devices.
Wendy Chou, University of Maryland, College Park. Advisor: Dr. Lawrence Washington, Department of Mathematics Abstract: The explosive growth in the use of mobile and wireless devices demands a new generation of PKC schemes that has to accommodate limitations on power and bandwidth, at the same time, to provide an adequate level of security for such devices. This paper examines the use of ECC in such constrained environments and discusses the basis of its security, explores its performance and lastly, surveys the use of ECC applications on the market today.
1
Introduction
In 1976, Whitfield Diffie and Martin Hellman introduced the concept of public key cryptography (PKC). Since then, many implementations of it have been proposed, and many of these cryptographic applications base their security on the intractability of hard mathematical problems, namely the integer factorization problem (IFP) and the finite field discrete logarithm problem (DLP). Over the years, sub-exponential time algorithms were developed to solve these problems. As a result, key sizes grew to more than 1000 bits, so as to attain a reasonable level of security. In constrained environments where computing power, storage and bandwidth are limited, carrying out thousand-bit operations becomes an impractical approach to providing adequate security. This is most evident in hand-held devices such as the mobile phones, pagers and PDAs that have very limited processing power and battery life. Proposed independently by Neal Koblitz and Victor Miller in 1985, elliptic curve cryptography (ECC) has the special characteristic that to date, the best known algorithm that solves it runs in full exponential time. Its security comes from the elliptic curve logarithm, which is the DLP in a group defined by points on an elliptic curve over a finite field. This results in a dramatic decrease in key size needed to achieve the same level of
Wendy Chou, University of Maryland, College Park. Advisor: Dr. Lawrence Washington, Department of Mathematics Abstract: The explosive growth in the use of mobile and wireless devices demands a new generation of PKC schemes that has to accommodate limitations on power and bandwidth, at the same time, to provide an adequate level of security for such devices. This paper examines the use of ECC in such constrained environments and discusses the basis of its security, explores its performance and lastly, surveys the use of ECC applications on the market today.
1
Introduction
In 1976, Whitfield Diffie and Martin Hellman introduced the concept of public key cryptography (PKC). Since then, many implementations of it have been proposed, and many of these cryptographic applications base their security on the intractability of hard mathematical problems, namely the integer factorization problem (IFP) and the finite field discrete logarithm problem (DLP). Over the years, sub-exponential time algorithms were developed to solve these problems. As a result, key sizes grew to more than 1000 bits, so as to attain a reasonable level of security. In constrained environments where computing power, storage and bandwidth are limited, carrying out thousand-bit operations becomes an impractical approach to providing adequate security. This is most evident in hand-held devices such as the mobile phones, pagers and PDAs that have very limited processing power and battery life. Proposed independently by Neal Koblitz and Victor Miller in 1985, elliptic curve cryptography (ECC) has the special characteristic that to date, the best known algorithm that solves it runs in full exponential time. Its security comes from the elliptic curve logarithm, which is the DLP in a group defined by points on an elliptic curve over a finite field. This results in a dramatic decrease in key size needed to achieve the same level of
References: 1. 2. 3. 4. 5. 6. 7. 8. Menezes, A. J. Elliptic curve public key cryptosystems. Kluwer Academic Publishers, 1993. Schneier, B. Applied cryptography. John Wiley & Sons, Inc., 1994. Enge, A. Elliptic curves and their applications to cryptography. Kluwer Academic Publishers, 1999. Menezes, A.., Oorschot, P., and Vanstone, S. Handbook of Applied Cryptography. CRC Press, 1997. Weisstein, E. W. “Number Field Sieve”. Wolfram Research, Inc. Stallings, W. Cryptography and Network Security. Prentice Hall, 2003. Silverman, R. D. “An Analysis of Shamir’s Factoring Device”. RSA Security. May 3, 1999 Shamir, A. “Factoring Large Numbers with the TWINKLE Device”. In proceedings of Cryptographic Hardware and Embedded Systems: First International Workshop, CHES '99. Lecture notes in Computer Science, vol.1717. Springer-Verlag Heidelberg, January 1999: p 2 – 12. Lercier, R. Homepage. Schneier, B. “Elliptic Curve Public Key Cryptography”. Cryptogram ENewsletter. November 15, 1999 “Remarks on the Security of the Elliptic Curve Cryptosystem”. Certicom, whitepaper. September 1997. Blake, I., Seroussi, G., and Smart, N. Elliptic Curves in Cryptography. Cambridge University Press, 1999. Menezes, A., Okamoto, T., and Vanstone, S. “Reducing elliptic curve logarithms to logarithms in a finite field”. Proceedings of the twenty-third annual ACM symposium on Theory of computing. Annual ACM Symposium on Theory of Computing. ACM Press, 1991: p 80 – 89. Satoh, T. and Araki, K. “Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves”. Commentarii Mathematici Universitatis Sancti Pauli 47, 1998: p 81 – 92. Semaev, I. A. “Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p”. Mathematics of Computation 67, 1998: p 353 – 356. Smart, N. “The discrete logarithm problem on elliptic curves of trace one”. Journal of Cryptography, vol. 12 no. 3. Springer-Verlag New York, October 1999: p 193 – 196. Certicom Press Release. “Certicom Announces Elliptic Curve Cryptosystem (ECC) Challenge Winner”. November 6, 2002. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. National Institute of Standards and Technology (NIST). Digital Signature Standard. Federal Information Processing Standards Publication (FIPS) 186-2, January 27 2000. 19. Omura, J. and Massey, J. Computational method and apparatus for finite field arithmetic. U.S. Patent number 4,587,627, May 1986. 20. Brown, M., Hankerson, D., Lopez, J., and Menezes, A. “Software Implementation of the NIST Elliptic Curves over Prime Fields”. In proceedings of Cryptographer’s Track at RSA Conference 2001 San Francisco. Lecture Notes in Computer Science, vol. 2020. Springer-Verlag Heidelberg, January 2001: 250 – 265. 22 21. Lopez, J. and Dahab, R. “Performance of Elliptic Curve Cryptosystems”. Technical report IC-00-08, May 2000. Available at 22. Boneh, D. and Daswani, N. “Experimenting with electronic commerce on the PalmPilot”. In proceedings of Financial Cryptography '99. Lecture Notes in Computer Science, vol. 1648. Springer-Verlag Heidelberg, 1999: p 1 – 16. 23. Li, Z., Higgins, J., and Clement, M. “Performance of finite field arithmetic in an elliptic curve cryptosystem”. Ninth Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems. IEEE Computer Society, 2001: p 249 – 258. 24. Itoh, T., Teecha, O., Tsujii, S. “A Fast Algorithm for computing Multiplicative Inverses in GF(2m) using Normal Basis”. Information and Computation, vol. 79. Elvisor Academic Press, 1988: p 171 – 177. 23