Abstract
In this paper, we answer the question whether binary extension field or prime-field based processors doing multi-precision arithmetic are better in the terms of area, speed, power, and energy. This is done by implementing and optimizing two distinct custom-made 16-bit processor designs and comparing our solutions on different abstraction levels: finite-field arithmetic, elliptic-curve operations, and on protocol level by implementing the Elliptic Curve Digital Signature Algorithm (ECDSA). On the one hand, our \(\mathbb{F}_{2^{m}}\) based processor outperforms the \(\mathbb{F}_p\) based processor by 19.7% in area, 69.6% in runtime, 15.9% in power, and 74.4% in energy when performing a point multiplication. On the other hand, our \(\mathbb{F}_p\) based processor (11.6kGE, 41.4,μW, 1,313kCycles, and 54.3μJ) improves the state-of-the-art in \(\mathbb{F}_{p_{192}}\) ECC hardware implementations regarding area, power, and energy results. After extending the designs for ECDSA (signature generation and verification), the area and power-consumption advantages of the \(\mathbb{F}_{2^{m}}\) based processor vanish, but it still is 1.5-2.8 times better in terms of energy and runtime.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
American National Standards Institute (ANSI). American National Standard X9.62-2005. Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA) (2005)
Auer, A.: Scaling Hardware for Electronic Signatures to a Minimum. Master thesis, University of Technology Graz (October 2008)
Avanzi, R.M., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC (2005)
Batina, L., Mentens, N., Sakiyama, K., Preneel, B., Verbauwhede, I.: Low-Cost Elliptic Curve Cryptography for Wireless Sensor Networks. In: Buttyán, L., Gligor, V.D., Westhoff, D. (eds.) ESAS 2006. LNCS, vol. 4357, pp. 6–17. Springer, Heidelberg (2006)
Blake, I.F., Seroussi, G., Smart, N.P.: Elliptic Curves in Cryptography. London Mathematical Society Lecture Notes Series, vol. 265. Cambridge University Press, Cambridge (1999)
Bock, H., Braun, M., Dichtl, M., Hess, E., Heyszl, J., Kargl, W., Koroschetz, H., Meyer, B., Seuschek, H.: A Milestone Towards RFID Products Offering Asymmetric Authentication Based on Elliptic Curve Cryptography. Invited talk at RFIDsec 2008 (July 2008)
Cadence Design Systems, Inc., San Jose, California, United States (2011). The Cadence Design Systems Website, http://www.cadence.com/
de Rooij, P.: Efficient Exponentiation Using Precomputation and Vector Addition Chains. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 389–399. Springer, Heidelberg (1995)
El Gamal, T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985)
Faraday Technology Corporation. Faraday FSA0A_C 0.13,μm ASIC Standard Cell Library (2004), http://www.faraday-tech.com
Fürbass, F., Wolkerstorfer, J.: ECC Processor with Low Die Size for RFID Applications. In: Proceedings of 2007 IEEE International Symposium on Circuits and Systems. IEEE (May 2007)
Großschädl, J., Savaş, E.: Instruction Set Extensions for Fast Arithmetic in Finite Fields GF(p) and GF(2m). In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 133–147. Springer, Heidelberg (2004)
Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, Heidelberg (2004)
Hein, D.: Elliptic Curve Cryptography ASIC for Radio Frequency Authentication. Master thesis, Technical University of Graz (April 2008)
Hein, D., Wolkerstorfer, J., Felber, N.: ECC Is Ready for RFID – A Proof in Silicon. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 401–413. Springer, Heidelberg (2009)
Hutter, M., Feldhofer, M., Plos, T.: An ECDSA Processor for RFID Authentication. In: Ors Yalcin, S.B. (ed.) RFIDSec 2010. LNCS, vol. 6370, pp. 189–202. Springer, Heidelberg (2010)
Hutter, M., Joye, M., Sierra, Y.: Memory-Constrained Implementations of Elliptic Curve Cryptography in Co-Z Coordinate Representation. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 170–187. Springer, Heidelberg (2011)
Itoh, T., Tsujii, S.: Effective recursive algorithm for computing multiplicative inverses in GF(2m). Electronic Letters 24(6), 334–335 (1988)
Joye, M., Yen, S.-M.: The Montgomery Powering Ladder. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2003)
Kaliski, B.: The Montgomery Inverse and its Applications. IEEE Transactions on Computers 44(8), 1064–1065 (1995)
Kern, T., Feldhofer, M.: Low-Resource ECDSA Implementation for Passive RFID Tags. In: Proceedings of 17th IEEE International Conference on Electronics, Circuits and Systems (ICECS 2010), Athens, Greece, December 12-15, pp. 1236–1239. IEEE (2010)
Koblitz, N.: Elliptic Curve Cryptosystems. Mathematics of Computation 48, 203–209 (1987)
Koblitz, N.: A Course in Number Theory and Cryptography. Springer, Heidelberg (1994) ISBN 0-387-94293-9
Kumar, S.S., Paar, C.: Are standards compliant Elliptic Curve Cryptosystems feasible on RFID? In: Workshop on RFID Security (RFIDSec 2006), Graz, Austria, July 12-14 (2006)
Lee, Y.K., Sakiyama, K., Batina, L., Verbauwhede, I.: Elliptic-Curve-Based Security Processor for RFID. IEEE Transactions on Computers 57(11), 1514–1527 (2008)
López, J., Dahab, R.: Improved Algorithms for Elliptic Curve Arithmetic in GF(2n). In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 201–212. Springer, Heidelberg (1999)
López, J., Dahab, R.: Fast Multiplication on Elliptic Curves over GF(2m). In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 316–327. Springer, Heidelberg (1999)
Miller, V.S.: Use of Elliptic Curves in Cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
National Institute of Standards and Technology (NIST). FIPS-180-3: Secure Hash Standard (October 2008), http://www.itl.nist.gov/fipspubs/
National Institute of Standards and Technology (NIST). FIPS-186-3: Digital Signature Standard (DSS) (2009), http://www.itl.nist.gov/fipspubs/
Öztürk, E., Sunar, B., Savaş, E.: Low-Power Elliptic Curve Cryptography Using Scaled Modular Arithmetic. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 92–106. Springer, Heidelberg (2004)
Satoh, A., Takano, K.: A Scalable Dual-Field Elliptic Curve Cryptographic Processor. IEEE Transactions on Computers 52(4), 449–460 (2003)
Wenger, E., Feldhofer, M., Felber, N.: A 16-Bit Microprocessor Chip for Cryptographic Operations on Low-Resource Devices. In: Proceedings of Austrochip 2010, Villach, Austria, October 6, pp. 55–60 (2010) ISBN 978-3-200-01945-4
Wenger, E., Feldhofer, M., Felber, N.: Low-Resource Hardware Design of an Elliptic Curve Processor for Contactless Devices. In: Chung, Y., Yung, M. (eds.) WISA 2010. LNCS, vol. 6513, pp. 92–106. Springer, Heidelberg (2011)
Wenger, E., Hutter, M.: A Hardware Processor Supporting Elliptic Curve Cryptography for Less Than 9kGEs. In: Proceedings of the Tenth Smart Card Research and Advanced Application Conference, CARDIS 2011, Leuven, Belgium, September 15-16 (2011)
Wolkerstorfer, J.: Is Elliptic-Curve Cryptography Suitable for Small Devices? In: Workshop on RFID and Lightweight Crypto, Graz, Austria, July 13-15, pp. 78–91 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wenger, E., Hutter, M. (2012). Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations. In: Laud, P. (eds) Information Security Technology for Applications. NordSec 2011. Lecture Notes in Computer Science, vol 7161. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29615-4_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-29615-4_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29614-7
Online ISBN: 978-3-642-29615-4
eBook Packages: Computer ScienceComputer Science (R0)