We describe and analyze architectural extensions to accelerate the public key cryptosystem elliptic curve cryptography (ECC) on 8-bit microprocessors. We show that simple extensions of the data path suffice to efficiently support ECC over GF(2/sup m/). These extensions include an extended multiplier that generates results for both integer multiplications and multiplications in fields GF(2/sup m/) and a multiply-accumulate instruction for efficiently performing multiple precision multiplications. To our knowledge, this is the first paper that quantifies performance of standard NIST and SECG elliptic curves over GF(2/sup m/) on an 8-bit microprocessor equipped with a dual field multiplier. On the ATmegal28 microprocessor running at 8 MHz we measured an execution time of 0.29 s for a 163-bit ECC point multiplication over GF(2/sup m/), 0.81s for a 160-bit ECC point multiplication over GF(p), and 11 s for a 1024-bit RSA private key operation - the chosen key sizes provide equivalent security strength.

This paper introduces Sizzle, the first fully implemented end-to-end security architecture for highly constrained embedded devices. According to popular perception, public-key cryptography is beyond the capabilities of such devices. We show that elliptic curve cryptography (ECC) not only makes public-key cryptography feasible on these devices, it allows one to create a complete secure Web server stack including SSL, HTTP and user application that runs efficiently within very tight resource constraints. Our small footprint HTTPS stack needs less than 4 KB of RAM and interoperates with an ECC-enabled version of the Mozilla Web browser. We have implemented Sizzle on the 8-bit Berkeley/Crossbow Mica2 "mote" platform where it can complete a full SSL handshake in less than 4 seconds (session reuse takes under 2 seconds) and transfer 450 bytes of application data over SSL in about 1 second. We present additional optimizations that can further improve performance. To the best of our knowledge, this is the world's smallest secure Web server (in terms of both physical dimensions and resources consumed) and significantly lowers the barrier for connecting a variety of interesting new devices (e.g. home appliances, personal medical devices) to the Internet without sacrificing end-to-end security.

In this paper, we quantify the energy cost of authentication and key exchange based on public-key cryptography on an 8-bit microcontroller platform. We present a comparison of two public-key algorithms, RSA and elliptic curve cryptography (ECC), and consider mutual authentication and key exchange between two untrusted parties such as two nodes in a wireless sensor network. Our measurements on an Atmel ATmega128L low-power microcontroller indicate that public-key cryptography is very viable on 8-bit energy-constrained platforms even if implemented in software. We found ECC to have a significant advantage over RSA as it reduces computation time and also the amount of data transmitted and stored.

We describe a cryptographic processor for elliptic curve cryptography (ECC). ECC is evolving as an attractive alternative to other public-key schemes such as RSA by offering the smallest key size and the highest strength per bit. The processor performs point multiplication for elliptic curves over binary polynomial fields GF(2/sup m/). In contrast to other designs that only support one curve at a time, our processor is capable of handling arbitrary curves without requiring reconfiguration. More specifically, it can handle both named curves as standardized by NIST as well as any other generic curves up to a field degree of 255. Efficient support for arbitrary curves is particularly important for the targeted server applications that need to handle requests for secure connections generated by a multitude of heterogeneous client devices. Such requests may specify curves which are infrequently used or not even known at implementation time. Our processor implements 256 bit modular multiplication, division, addition and squaring. The multiplier constitutes the core function as it executes the bulk of the point multiplication algorithm. We present a novel digit-serial modular multiplier that uses a hybrid architecture to perform the reduction operation needed to reduce the multiplication result: hardwired logic is used for fast reduction of named curves and the multiplier circuit is reused for reduction of generic curves. The performance of our FPGA-based prototype, running at a clock frequency of 66.4 MHz, is 6955 point multiplications per second for named curves over GF(2/sup 163/) and 3308 point multiplications per second for generic curves over GF(2/sup 163/).

Elliptic Curve Cryptography (ECC) is evolving as an attractive alternative to other public-key schemes such as RSA by offering the smallest key size and the highest strength per bit. The importance of ECC has been recognized by the US government and the standards bodies NIST and SECG. Standards for preferred elliptic curves over prime fields GF(p) and binary polynomial fields GF(2m) as well as the Elliptic Curve Digital Signature Algorithm (ECDSA) have been created. A security protocol based on ECC requires support for different curves representing different security levels. This is particularly true for server applications that are exposed to requests for secure connections with different parameters generated by a multitude of client devices. Reported implementations of ECC over GF(2m) typically choose to implement each curve as a special case so that modular reduction can be optimized, thus improving the overall performance. In contrast, this paper focuses on generic implementations of ECC point multiplication for arbitrary curves over GF(2m). We present a novel reduction algorithm that allows hardware and software implementations for variable field degrees m. Though not as high in performance as an implementation optimized for a specific curve, it offers an attractive solution to supporting infrequently used curves or curves not known at the time of the implementation.