Cyber Defense Laboratory 



TinyECC: Elliptic Curve Cryptography for Sensor Networks

Parameters  ROM (bytes)  RAM (bytes) 
secp128r1  43,198  410 
secp128r2  43,216  410 
secp160k1  43,338  490 
secp160r1  43,360  490 
secp160r2  43,376  490 
Parameters  ROM (bytes)  RAM (bytes) 
secp128r1  43,202  1224 
secp128r2  43,220  1224 
secp160k1  43,342  1496 
secp160r1  43,364  1496 
secp160r2  43,380  1496 
Though the word size on MICAz (ATmega128) is 8 bits, the compiler can provide 16bit operations and can usually speed up the computation in pure nesC implementation. We measured the time for signature generation and verification for both 8bit and 16bit word sizes and different window sizes on MICAz, where the 8bit versions used inline assembly for some critical functions. Table 3 shows the timing results.
Word size (bits)  Window size (bits)  Signature generation (seconds)  Signature verification (seconds) 
8  2  7.233  13.733 
8  4  6.094  12.242 
16  2  8.267  16.632 
16  4  7.074  14.293 
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. Typically, U = 3.0 V if two new AA batteries are used. Table 4 shows the results.
Word size (bits)  Window size (bits)  Signature generation (Joule)  Signature verification (Joule) 
8  2  0.174  0.330 
8  4  0.146  0.294 
16  2  0.198  0.399 
16  4  0.170  0.343 
We implemented several well known optimizations for TinyECC, which are listed below. However, this implementation does not include all known optimizations, such as NonAdjacent Forms, Optimizing Multiplication for Memory Operations proposed in [2].
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.
For all NIST and most SECG curves, the underlying field primes p were chosen as pseudoMersenne primes to allow for optimized modular reduction [2]. We implemented this optimized modular reduction algorithm to speed up modular multiplication and modular square.
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. It scans 1 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 precompute 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.
The natural number operations in TinyECC are based on the implementation in RSAREF2.0 [6]. The natural number operations in RSAREF2.0 are platform independent, but they are not efficient. We used inline assembly code [4] in functions NN_Add, NN_Sub, NN_AddDigitMult and NN_SubDigitMult to eliminate unnecessary shift operations and conditional sentences. Note that this can not be used with sensor nodes that do not use ATmega128 (e.g. TelosB).
We implemented algorithms 2.7 & 2.8 in [5] to speed up modular addition and modular subtraction.
All new code in this distribution is Copyright 2005 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."
The natural number operations in TinyECC are based on the implementation in RSAREF 2.0 [6].
[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 8bit CPUs. In Proceedings of the 2004 Workshop on Cryptographic Hardware and Embedded Systems (CHES 2004), August 2004.
[3] Çetin Kaya Kac. HighSpeed RSA Implementation, RSA Laboratories Technical Report TR201, Version 2.0, November 22, 1994.
[4] 8bit 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/aid386/sec2_final.pdf, September 2000.
This project has been generously supported by
This material is based upon work supported by the National Science Foundation (NSF) under grant CAREER0447761 and US Army Research Office (ARO) under grant W911NF0510247. 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.