Cyber Defense
Laboratory

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

Released on 09/29/06.

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 and TelosB 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.

What's new in version 0.2

Support both MICAz and TelosB

Support all SECG recommended
128-bit, 160-bit and 192-bit elliptic curve domain parameters

Hybrid multiplication in assembly code for MICAz

Shamir's trick to reduce the signature verification time

More compact SHA1 implementation based on C code in RFC 3174

For questions about this implementation, please contact An Liu at
aliu3 (at) ncsu.edu.

People

Dr. Peng Ning

An Liu (main contributor)

Platform

MICAz motes and TelosB motes running TinyOS

Related Software

TinyECC
Version 0.1

TinyKeyMan

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, Peng Ning, "TinyECC: Elliptic Curve Cryptography for Sensor
Networks (Version 0.2)",
http://discovery.csc.ncsu.edu/software/TinyECC/, September
2006.

Performance Results

The following performance results were measured on MICAz and TelosB
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, and 2,442 bytes for
TelosB.

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

ROM (bytes)

RAM (bytes)

ROM (bytes)

RAM (bytes)

secp128r1

13,094

1,168

12,532

1,254

secp128r2

13,076

1,168

12,498

1,254

secp160k1

13,890

1,440

12,570

1,526

secp160r1

13,858

1,440

12,564

1,526

secp160r2

13,966

1,440

12,568

1,526

secp192k1

13,488

1,712

12,632

1,798

secp192r1

13,182

1,712

12,722

1,798

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 and TelosB. Although ECDSA
initialization is expensive, it is performed just one time.

Table 3: ECDSA initialization time (window size w = 4)

Parameters

ECDSA.init() on MICAz (seconds)

ECDSA.init() on TelosB (seconds)

secp128r1

2.522

3.861

secp128r2

2.518

3.847

secp160k1

3.553

5.208

secp160r1

3.548

5.225

secp160r2

3.543

5.197

secp192k1

4.992

7.190

secp192r1

4.992

7.204

We measure the time for signature generation and verification for
both MICAz and TelosB. Table 4 shows the timing results. Since we
haven't implemented hybrid multiplication for TelosB, TelosB is much
slower than MICAz.

Table 4: Time for signature generation and verification
(window size w = 4)

Parameters

MICAz

TelosB

sign (seconds)

verify (seconds)

sign (seconds)

verify (seconds)

secp128r1

1.923

2.418

4.059

5.056

secp128r2

2.069

2.674

4.325

5.618

secp160k1

2.059

2.441

4.433

5.209

secp160r1

1.925

2.433

4.361

5.448

secp160r2

2.066

2.615

4.457

5.609

secp192k1

3.070

3.612

6.695

7.840

secp192r1

2.991

3.776

6.651

8.331

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. Table 5
shows the results.

Table 5: Energy cost of signature generation and verification
(secp160r1)

Window size (bits)

MICAz

TelosB

sign (mJ)

verify (mJ)

sign (mJ)

verify (mJ)

2

52.9

58.4

27.5

29.4

4

46.2

58.4

23.5

29.4

Techniques Adopted in TinyECC (Version 0.2)

We implemented several well known optimizations for TinyECC, which
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

©2006 Peng Ning, Last
Updated September 29, 2006 .