Cyber Defense Laboratory

 

 

TinyECC: Elliptic Curve Cryptography for Sensor Networks
(Version 0.3)

Released on 02/06/07.

Introduction

TinyECC is a software package providing Elliptic Curve Cryptography (ECC) operations on TinyOS. It supports all elliptic curve operations over Fp, including point addition, point doubling and scalar point multiplication, as well as ECDSA operations over Fp (signature generation and verification). We plan to include other ECC schemes (e.g. ECDH, ECAES) in this package in the future.

The current version of TinyECC supports MICAz, TelosB and Imote2 motes. It 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 or
Panos Kampanakis at pan_kamp (at) ncsu.edu.

What's new in version 0.3

  • Support for Intel Mote 2

People

Platform

  • MICAz, TelosB and Imote2 motes running TinyOS

Related Software

Related Document

Download

  • Click here to download.

How to Use

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

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

Performance Results

The following performance results were measured on MICAz, TelosB and Imote2 running TinyOS. Secp128r1, secp128r2, secp160k1, secp160r1, secp160r2, secp192k1, secp192r1 are elliptic curve domain parameters over Fp[7] recommended by Standards for Efficient Cryptography Group (SECG).

  • Code size

We used the sliding window method to speed up scalar point multiplication operation. Table 1 and Table 2 show the code size for different curves and window sizes. Note that the code size changes with different parameters due to the changes in the ECC parameters and some internal state. Because of the small SHA1 code size, the total code size has been reduced a lot compared with TinyECC 0.1.The code size of SHA1 is only 3,680 bytes for MICAz, 2,442 bytes for TelosB and 3,532 bytes for Imote2.

Table 1: Code size when the window size w = 2
Parameters MICAz TelosB
ROM (bytes) RAM (bytes) ROM (bytes) RAM (bytes)
secp128r1 13,120 762 12,528 830
secp128r2 13,102 762 12,494 830
secp160k1 13,912 938 12,566 1,006
secp160r1 13,880 938 12,560 1,006
secp160r2 13,988 938 12,564 1,182
secp192k1 13,510 1,114 12,628 1,182
secp192r1 13,204 1,114 12,718 1,182

 Table 2: Code size when the window size w = 4
Parameters MICAz TelosB Imote2
ROM (bytes) RAM (bytes) ROM (bytes) RAM (bytes) ROM (bytes) RAM (bytes)
secp128r1 13,094 1,168 12,532 1,254

26,404

1,468

secp128r2 13,076 1,168 12,498 1,254

26,420

1,468

secp160k1 13,890 1,440 12,570 1,526

26,416

1,740

secp160r1 13,858 1,440 12,564 1,526

26,368

1,740

secp160r2 13,966 1,440 12,568 1,526

26,436

1,740

secp192k1 13,488 1,712 12,632 1,798

26,508

2,012

secp192r1 13,182 1,712 12,722 1,798

26,572

2,012

  • Computational cost

Since we use the sliding window method and Shamir's trick, ECDSA module needs to pre-compute intermediate points before doing any signature generation and verification. Table 3 shows the  initialization time of ECDSA module on MICAz, TelosB and Imote2. Although ECDSA initialization is expensive, it is performed just one time.

Table 3: ECDSA initialization time (window size w = 4)
Parameters MICAz
(secs)
TelosB
(secs)
Imote2 (secs)
core freq: 13MHz core freq: 104MHz
secp128r1 2.522 3.861

1.164

0.145

secp128r2 2.518 3.847

1.162

0.145

secp160k1 3.553 5.208

1.313

0.164

secp160r1 3.548 5.225

1.288

0.161

secp160r2 3.543 5.197

1.311

0.163

secp192k1 4.992 7.190

1.732

0.216

secp192r1 4.992 7.204

1.736

0.217

We measure the time for signature generation and verification for both MICAz, TelosB and Imote2. Table 4 shows the timing results. Since we haven't implemented hybrid multiplication for TelosB, TelosB is much slower than MICAz. Also, Imote2 32-bit processor and higher frequency improve more than 10-fold the performance of the motes.

Table 4: Time for signature generation and verification (window size w = 4)
Parameters MICAz TelosB Imote2
sign (secs) verify (secs) sign (secs) verify (secs) core freq: 13MHz core freq: 104MHz
sign (secs) verify (secs) sign (secs) verify (secs)
secp128r1 1.923 2.418 4.059 5.056

2.234

2.815

0.279

0.351

secp128r2 2.069 2.674 4.325 5.618

2.416

3.146

0.301

0.393

secp160k1 2.059 2.441 4.433 5.209

1.854

2.197

0.231

0.274

secp160r1 1.925 2.433 4.361 5.448

1.699

2.161

0.212

0.270

secp160r2 2.066 2.615 4.457 5.609

1.857

2.359

0.232

0.294

secp192k1 3.070 3.612 6.695 7.840

2,710

3,184

0.338

0.398

secp192r1 2.991 3.776 6.651 8.331

2.709

3.409

0.338

0.426

The greater RAM capabilities of Imote2 allow us to increase the window size to improve the timing results even more (Table 5).
Table 5: Time for signature generation and verification
(window size w = 8)
Parameters Imote2
core freq: 104MHz
sign (secs) verify (secs)
secp128r1

0.238

0.352

secp128r2

0.261

0.393

secp160k1

0.200

0.274

secp160r1

0.183

0.269

secp160r2

0.200

0.294

secp192k1

0.292

0.397

secp192r1

0.292

0.425

  • Energy cost

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. As for Imote2, the default mode used is deep sleep mode where the nominal current is 390μA and the core voltage is set to 850mV and 950mV for 13 MHz and 104 MHz core frequency respectively. Table 6 shows the results.

Table 6: Energy cost of signature generation and verification (secp160r1)
Window size (bits) MICAz TelosB Imote2
sign (mJ) verify (mJ) sign (mJ) verify (mJ) core freq: 13MHz core freq: 104MHz
sign (mJ) verify (mJ) sign (mJ) verify (mJ)
2 52.9 58.4 27.5 29.4

0.64

0.71

0.09

0.11

4 46.2 58.4 23.5 29.4

0.56

0.72

0.08

0.10

Techniques Adopted in TinyECC

We have implemented several well known optimizations for TinyECC from the previous version of TinyECC. The same techniques are still supported in TinyECC0.3 and are listed below. However, this implementation does not include all known optimizations, such as Non-Adjacent Forms.

  • Projective Coordinate Systems

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

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 (The m-ary Method)

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

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] to speed up critical operations such as multiplication and squaring for MICAz motes. In particular, hybrid multiplication in [2] is implemented in inline assembly, which can speed up TinyECC effectively. Note that this cannot be used with sensor nodes that do not use ATmega128 (e.g. TelosB).

  • 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

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

Copyright and Disclaimer

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."

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.

Sponsors

This project has been generously supported by

NSF
ARO
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.
 
 
2007 Peng Ning, Last Updated February 06, 2007 .