TinyECC: A Configurable Library for
Elliptic Curve Cryptography
in Wireless Sensor Networks
(Version 2.0)
Released on 2/3/2011.
Introduction
TinyECC 2.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 2.0 is intended for sensor platforms running
TinyOS-2.x. The current version is implemented in nesC, with additional
platform-specific optimizations in inline assembly for popular sensor
platforms. It has been tested on MICA2/MICAz, TelosB/Tmote Sky, BSNV3,
and Imote2. TinyECC 2.0 supports SECG recommended 128-bit,
160-bit and 192-bit elliptic curve domain parameters.
For questions please contact Peng Ning at pning (at) ncsu.edu.
What's new in version 2.0
People
Platform
- MICAz, TelosB/Tmote Sky, and Imote2 running
TinyOS-2.x
Related Software
Related Documents
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
2.0)", http://discovery.csc.ncsu.edu/software/TinyECC/,
August 2010.
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 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 2n.
When used to reduce various numbers modulo a single number many
times, Barrett reduction can be faster than modular reductions
obtained by division.
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 pseudo-Mersenne primes to allow 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, 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.
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..
We implemented algorithms 2.7 and 2.8 in [5]
to speed up modular addition and modular subtraction.
We applied algorithm 3.48 in [5] to reduce
the signature verification time.
Copyright and Disclaimer
All new code in this distribution is Copyright
2010 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. |
|
