Cyber Defense Laboratory

TinyECC: A Configurable Library for Elliptic Curve Cryptography
in Wireless Sensor Networks
(Version 1.0)

Released on 11/2/07.

Introduction

TinyECC 1.0 is a software package providing ECC-based PKC operations that can be flexibly configured and integrated into sensor network applications. It provides a digital signature scheme (ECDSA),  a key exchange protocol (ECDH), and a public key encryption scheme (ECIES). TinyECC uses a number of optimization switches, which can turn specific optimizations on or off based on developer's needs.

TinyECC 1.0 is intended for sensor platforms running TinyOS. The current version is implemented in nesC, with additional platform-specific optimizations in inline assembly for popular sensor platforms. It has been tested on MICAz, TelosB, Tmote Sky, and Imote2. TinyECC 1.0 supports SECG recommended 128-bit, 160-bit and 192-bit elliptic curve domain parameters.

For questions please contact An Liu at aliu3 (at) ncsu.edu.

What's new in version 1.0

• Support for ECIES and ECDH
  • Point compress and uncompress form of ECIES
  • Point compress form enabled by default
• Configurability
  • All optimizations can be turned on or off at compile time with switches
• Support of more optimization techniques (for faster execution or more compact code size)
  • Barrett reduction
  • Mixed Jacobian-affine points addition
  • Repeated point doubling
  • Affine coordinate point addition and doubling
• Support for hybrid multiplication and squaring (inline assembly) for TelosB/Tmote Sky and Imote2
  

People

• An Liu (main contributor)
• Dr. Peng Ning

Platform

• MICAz, TelosB/Tmote Sky, and Imote2 running TinyOS

Related Software

• TinyECC Version 0.3
• TinyECC Version 0.2
• TinyECC Version 0.1
• TinyKeyMan

Related Documents

• An Liu, Peng Ning, "TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks," in Proceedings of the 7th International Conference on Information Processing in Sensor Networks (IPSN 2008), SPOTS Track, pages 245--256, April 2008. (Full version)
• An Imote 2 Beginner's Tutorial by Panos Kampanakis

Download

• Click here to download.

How to Use

• Please check README for details.
• If you need to cite the TinyECC paper, please use the following:

An Liu, Peng Ning, "TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks," in Proceedings of the 7th International Conference on Information Processing in Sensor Networks (IPSN 2008), SPOTS Track, pages 245--256, April 2008.

• If you need to cite the TinyECC distribution site, please use the following:

  An Liu, Peng Ning, "TinyECC: Elliptic Curve Cryptography for Sensor Networks (Version 1.0)", http://discovery.csc.ncsu.edu/software/TinyECC/, November 2007.

Performance Results

The following performance results were measured on MICAz, TelosB/Tmote Sky, and Imote2 running TinyOS using secp160r1, which is elliptic curve domain parameter over F_p[7] recommended by Standards for Efficient Cryptography Group (SECG). We enable all optimization switches and disable all optimization switches to show the most computation-efficient case and most storage-efficient case.

• Most computation efficient case

First, we enable all optimization switches to show how fast TinyECC could be.

Figure 1: Execution time (ms) when all optimization switches enabled

As figure 1 shows, TelosB(4 MHz) is the slowest platform, Imote2(416 MHz) is the fastest platform. TelosB(4 MHz) needs 3,169 ms for signature generation, and 4040 ms for signature verification. Imote2(416 MHz) only needs 12 ms for signature generation, and 14 ms for signature verification. Figure 2 shows the code size in most computation efficient case. Imote2 requires largest RAM usage due to its 32-bit word size. MICAz has the largest ROM usage due to its additional inline assembly code for curve specific optimization.

Figure 2: Code size (byte) when all optimization switches enabled

We used the formula E = U*I*t to estimate the energy consumption of signature generation and verification. For MICAz, when processor is in active mode, I = 8 mA. For TelosB, I = 1.8mA for active mode. Typically, U = 3.0 V if two new AA batteries are used. When Imote2 runs at 13 MHz, the core voltage is set to 850mV and current draw is 31mA with radio off. When it runs at 104 MHz, the core voltage is set to 950mV and current draw is 66mA with radio on. All these data are from datasheets of crossbow product[12].

Figure 3: Energy consumption (mJ) when all optimization switches enabled

As figure 3 shows, MICAz is the most energy consuming platform, Imote2 is energy efficient even when it runs at 104 MHz with radio on. 

• Most storage efficient configuration

Due to the resource constraint of low end sensor platforms (e.g. MICAz, TelosB/Tmote Sky), sometimes we need to reduce the code size (by disabling some optimization switches) to integrate TinyECC with other TinyOS applications. Next, we disable all the optimization switches to show how compact TinyECC could be.

Figure 4: Execution time (ms) when all optimization switches disabled

When all optimization switches are disabled, although all ECDSA, ECIES, and ECDH operations are slowed down, the code size is reduced dramatically as figure 5 shows. For example, the RAM requirement is only around 150 bytes for MICAz. The ROM size of ECIES for MICAz is reduced from 20,768 bytes to 12,442 bytes.

Figure 5: Code size (byte) when all optimization switches disabled

Figure 6: Energy consumption (mJ) when all optimization switches disabled

Since the execution time is increased lot, the energy consumption of all platforms are increased too. MICAz even needs 15 and 25 times more energy for ECDSA signature generation and verification compared with most computation efficient case.

Techniques Adopted in TinyECC

We have implemented several well known optimizations for TinyECC. We provide several switches to enable and disable each of them according to developer's needs. However, this implementation does not include all known optimizations, such as Non-Adjacent Forms.

• Barrett Reduction (BARRETT)

Barrett reduction is an alternative method for modular reduction [9]. It converts the reduction modulo an arbitrary integer to two multiplications and a few reductions modulo integers of the form 2ⁿ. When used to reduce various numbers modulo a single number many times, Barrett reduction can be faster than modular reductions obtained by division.

• Projective Coordinate Systems (PROJECTIVE)

There is no division instruction for ATmega128, so the inverse operation is significantly more expensive than multiplication. It is efficient to implement elliptic curve operations in projective coordinates instead of affine coordinates. We used weighted projective representation (Jacobian representation) [1] in TinyECC to speed up point addition, point doubling and scalar point multiplication.

• Curve-Specific Optimizations (CURVE_OPT)

For all NIST and most SECG curves, the underlying field primes p were chosen as pseudo-Mersenne primes to allow optimized modular reduction [2]. We implemented this optimized modular reduction algorithm to speed up modular multiplication and modular square.

• Sliding Window Method (SLIDING_WIN) 

We implemented the sliding window method to speed up scalar point multiplication. The traditional method to do scalar point multiplication is binary method. Binary method scans bits of scalar n from left to right, one bit at a time. A point doubling is performed at each step. Depending on the scanned bit value, a subsequent point addition is performed. Sliding window method [3] scans k bits at a time. Point doubling is performed k times at each step, depending on the scanned k bits value a subsequent point addition is performed. We have to pre-compute all the added points, which is the result of possible k bits value multiply the base point. The sliding window method can speed up scalar point multiplication by reducing the total number of point additions, but extra memory is required.

• Inline Assembly and Hybrid Multiplication (HYBRID_MULT, HYBRID_SQR)

The natural number operations in TinyECC are based on the implementation in RSAREF2.0 [6]. The natural number operations in RSAREF 2.0 are platform independent, but they are not efficient. We used inline assembly code [4][10][11] to speed up critical operations such as multiplication and squaring for MICAz, TelosB/Tmote Sky, and Imote2 motes. In particular, hybrid multiplication in [2] is implemented in inline assembly, which can speed up TinyECC effectively..

• Optimization for Modular Addition and Modular Subtraction

We implemented algorithms 2.7 and 2.8 in [5] to speed up modular addition and modular subtraction.

• Shamir's Trick (SHAMIR_TRICK)

We applied algorithm 3.48 in [5] to reduce the signature verification time.

Copyright and Disclaimer

All new code in this distribution is Copyright 2007 by North Carolina State University. All rights reserved. Redistribution and use in source and binary forms are permitted provided that this entire copyright notice is duplicated in all such copies, and that any documentation, announcements, and other materials related to such distribution and use acknowledge that the software was developed at North Carolina State University, Raleigh, NC. No charge may be made for copies, derivations, or distributions of this material without the express written consent of the copyright holder. Neither the name of the University nor the name of the author may be used to endorse or promote products derived from this material without specific prior written permission.

IN NO EVENT SHALL THE NORTH CAROLINA STATE UNIVERSITY BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE NORTH CAROLINA STATE UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE NORTH CAROLINA STATE UNIVERSITY HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."

Acknowledgment

The natural number operations in TinyECC are based on the implementation in RSAREF 2.0 [6].

References

[1] I. Blake, G. Seroussi, and N. Smart. Elliptic Curves in Cryptography. Cambridge University Press, 1999. London Mathematical Society Lecture Note Series 265.

[2] N. Gura, A. Patel, and A. Wander. Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In Proceedings of the 2004 Workshop on Cryptographic Hardware and Embedded Systems (CHES 2004), August 2004.

[3] Çetin Kaya Kac. High-Speed RSA Implementation, RSA Laboratories Technical Report TR-201, Version 2.0, November 22, 1994.

[4] 8-bit AVR Instruction Set. http://www.atmel.com/dyn/resources/prod_documents/DOC0856.PDF

[5] D. Hankerson, A. Menezens, and S. Vanstone. Guide to Elliptic Curve Cryptography. Springer, 2004.

[6] RSA Laboratories. RSAREF: A cryptographic toolkit (version 2.0), March 1994.

[7] Certicom Research. Standards for efficient cryptography - SEC2: Recommended elliptic curve domain parameters. http://www.secg.org/download/aid-386/sec2_final.pdf, September 2000.

[8] D. Eastlake, P. Jones. US Secure Hash Algorithm 1 (SHA1). RFC 3174, September 2001.

[9] A. Menezes, P. Oorschot, and S. Vanstone, "Handbook of Applied Cryptography," CRC Press, 1997.

[10] MSP430x1xx Family User's Guide (Rev. F), http://focus.ti.com/lit/ug/slau049f/slau049f.pdf.

[11] ARM v5TE Architecture Reference Manual, http://www.arm.com/documentation/Instruction_Set/index.html.

[12] Crossbow, http://www.xbow.com.

Sponsors

This project has been generously supported by

This material is based upon work supported by the National Science Foundation (NSF) under grant CAREER-0447761 and US Army Research Office (ARO) under grant W911NF-05-1-0247. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the NSF or the ARO.