Elliptic Curve Cryptography on FPGA for Low-Power Applications

ABSTRACT

Elliptic curve cryptography has generated a lot of research interest due to its ability to provide greater security per bit compared to public key systems such as RSA. The designer of an elliptic curve hardware accelerator is faced with many choices at design time, each of which can impact the performance of the accelerator in different ways. There are many examples in the literature of how these design choices can effect the area and/or speed of an elliptic curve hardware accelerator. The effect of design choices on power and energy consumption in elliptic curve hardware has been less well studied. This article studies the effect of design choices on the power and energy consumption of an FPGA-based reconfigurable elliptic curve hardware accelerator. A reconfigurable processor has been used for different system parameters and the power and energy consumption measured. The power and energy results are presented and compared.

REFERENCES

• 1: Avanzi, R. M., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., and Vercauteren, F. 2005. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC.
• 2: Batina, L., Mentens, N., Sakiyama, K., Preneel, B., and Verbauwhede, I. 2006. Low-cost elliptic curve cryptography for wireless sensor networks. In Proceedings of the European Workshop on Security and Privacy in Ad hoc and Sensor Networks (ESAS’06). Lecture Notes in Computer Science, vol. 4357. Springer-Verlag, 6--17.
• 3: Berlekamp, E. R. 1968. Algebraic Coding Theory. McGraw-Hill.
• 4: Daniel J. Bernstein , Tanja Lange , Reza Rezaeian Farashahi, Binary Edwards Curves, Proceeding sof the 10th international workshop on Cryptographic Hardware and Embedded Systems, August 10-13, 2008, Washington, DC, USA [doi>10.1007/978-3-540-85053-3_16]
• 5: Ian F. Blake , G. Seroussi , N. P. Smart, Elliptic curves in cryptography, Cambridge University Press, New York, NY, 1999
• 6: Eric Brier , Marc Joye, Weierstraß Elliptic Curves and Side-Channel Attacks, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.335-345, February 12-14, 2002
• 7: Byrne, A., Meloni, N., Tisserand, A., Popovici, E. M., and Marnane, W. P. 2007. Comparison of simple power analysis attack resistant algorithms for an elliptic curve cryptosystem. J. Comput. 2, 10, 52--62.
• 8: Byrne, A., Popovici, E., and Marnane, W. P. 2008. Versatile processor for GF(p^m) arithmetic for use in cryptographic applications. IET Comput. Digit. Tech. 2, 4, 253--264.
• 9: Crowe, F., Daly, A., and Marnane, W. 2005. Optimised Montgomery domain inversion on FPGA. In Proceedings of the European Conference on Circuit Theory and Design 1, 277--280.
• 10: Alan Daly , William Marnane, Efficient architectures for implementing montgomery modular multiplication and RSA modular exponentiation on reconfigurable logic, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503055]
• 11: Guerric Meurice de Dormale , Jean-Jacques Quisquater, High-speed hardware implementations of Elliptic Curve Cryptography: A survey, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.2-3, p.72-84, February, 2007 [doi>10.1016/j.sysarc.2006.09.002]
• 12: Edwards, H. M. 2007. A normal form for elliptic curves. Bull. Am. Math. Soc. 44, 393--422.
• 13: Daniel M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, v.27 n.1, p.129-146, April 1998 [doi>10.1006/jagm.1997.0913]
• 14: IEEE. 2000. IEEE standard specifications for public-key cryptography. IEEE Std 1363-2000.
• 15: Toshiya Itoh , Shigeo Tsujii, A fast algorithm for computing multiplicative inverses in GF(2^m) using normal bases, Information and Computation, v.78 n.3, p.171-177, Sept. 1988 [doi>10.1016/0890-5401(88)90024-7]
• 16: Burton S. Kaliski, The Montgomery Inverse and Its Applications, IEEE Transactions on Computers, v.44 n.8, p.1064-1065, August 1995 [doi>10.1109/12.403725]
• 17: Keller, M. and Marnane, W. 2007. Low power elliptic curve cryptography. In Proceedings of the International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS’07). Lecture Notes in Computer Science, vol. 4644. Springer-Verlag, 310--319.
• 18: Sandeep Kumar , Thomas Wollinger , Christof Paar, Optimum Digit Serial GF(2^m) Multipliers for Curve-Based Cryptography, IEEE Transactions on Computers, v.55 n.10, p.1306-1311, October 2006 [doi>10.1109/TC.2006.165]
• 19: Julio López , Ricardo Dahab, Fast Multiplication on Elliptic Curves over GF(2m) without Precomputation, Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, p.316-327, August 12-13, 1999
• 20: Robert J. McEliece, Finite field for scientists and engineers, Kluwer Academic Publishers, Norwell, MA, 1987
• 21: Montgomery, P. L. 1985. Modular multiplication without trial division. Math. Comput. 44, 519--521.
• 22: Montgomery, P. L. 1987. Speeding the pollard and elliptic curve methods of factorisation. Math. Comput. 48, 243--264.
• 23: NIST. 1999. Recommended elliptic curves for federal government use. National Institute of Standards and Technology. NIST Special Publication.
• 24: Öztürk, E., Sunar, B., and Savaş, E. 2004. Low-power elliptic curve cryptography using scaled modular arithmetic. In Proceeding of the Cryptographic Hardware and Embedded Systems (CHES’04). Lecture Notes in Computer Science, vol. 3156. Springer-Verlag, 107--118.
• 25: Sheueling Chang Shantz, From Euclid's GCD to Montgomery Multiplication to the Great Divide, Sun Microsystems, Inc., Mountain View, CA, 2001
• 26: Leilei Song , Keshab K. Parhi, Low-Energy Digit-Serial/Parallel Finite Field Multipliers, Journal of VLSI Signal Processing Systems, v.19 n.2, p.149-166, July 1998 [doi>10.1023/A:1008013818413]
• 27: Walter, C. D. 1999. Montgomery exponentiation needs no final subtractions. Electronics Lett. 35, 21, 1831--1832.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Performance

Keywords:
Cryptography, FPGA, elliptic curves, low-power