Understanding elliptic-curve cryptography - Embedded.com

Understanding elliptic-curve cryptography

The risk of intrusion and eavesdropping goes up as electronic communication equipment becomes increasingly wireless and ubiquitous. With the spectre of hackers/crackers looming, security is becoming a major consideration in a growing number of embedded systems. Although sometimes mandated through standards, security is often added as feature to make a well-designed system more competitive in the marketplace.

While the benefits of strong, efficient security may be obvious, implementing it is not always straightforward and can be daunting when the security must function in extraordinary environments where battery life and processing power are low. Public-key cryptography, specifically elliptic-curve cryptography (ECC), has many advantages when deployed in these types of environments, in other words, embedded systems. ECC, which has all the advantages of public key, uses small key sizes and is efficient for both private and public operations, such as signing and verifying.

ECC is successfully in use with the postal service in several countries, including Canada and the United Kingdom, where advanced digital-signature schemes are being used to secure the production of digital postal marks to prevent fraud. Command and control networks, such as ZigBee sensors, are an example where encryption and validation of commands and responses can be used to prevent tampering of control and protect the confidentiality of information.

This article will describe public-key systems, their advantages and disadvantages, techniques of optimizing ECC, and how ECC is used in practice.

Public vs. private key systems
Before public-key cryptosystems, there were private-key cryptosystems. Private-key cryptosystems assume that the communicating parties both know a shared secret. Using this secret as a key, messages can be tagged to show that someone possessing the secret produced it or encrypted it using the key so others can't see it, or both.

Private-key (symmetric) encryption and “MAC-ing” (message authentication code) are efficient cryptographic schemes, but assume knowledge of a shared secret key. Private-key systems used the Data Encryption Standard (DES) algorithm in the past but have moved to the Advanced Encryption Standard (AES) for new deployments since it's stronger, offering 128, 192, or 256 bits of security (single DES keys are only 56 bits in length, making it feasible to attack DES by exhausting all the key possibilities).

Because all parties need a secret key (or every pair of parties in a network), systems using private-key cryptography are difficult to initialize or to recover in the event that secret keys are lost or compromised. For these reasons, private key systems are not easily scalable in the number of deployed nodes.

Public-key (asymmetric) cryptography is also called two-key cryptography because keys come in pairs: secret and public keys. The secret key can be used to sign a message or to decrypt a message. The public key is used to verify that the private key holder produced the message or to encrypt a message for a private key holder.

In public-key cryptography, shared keys are established only when they're needed. When the public key is signed by an already trusted key, the resulting data is called a certificate because it certifies the new public key. However, in an embedded system, public keys are often embedded into the devices at manufacturing or system provisioning, which avoids having to deploy a public key infrastructure (PKI) to manage the public keys.

In an embedded system the keys might be used to authenticate other units. For example, when new units are added to the system and they're signed with the unit's authentication private key, the older units can validate their authenticity by performing a signature verification against the unit authentication public key embedded into them.

Other public keys might be embedded as backups against key compromise and failure recovery, or they may be used to validate new versions of system software or other data or key updates.

Given the usefulness of public-key schemes, it would be reasonable to ask why they're not used all the time. Public-key cryptosystems are slower than private-key systems and the data that they exchange may also be much longer, often many thousands of bits. Consequently, private-key schemes are very often used in conjunction with public-key schemes to set up the private keys for encryption or to sign and verify signatures on message.

Elliptic-curve cryptography
As we said, public-key schemes are often used to set up private (symmetric) keys for encryption. Because hackers will attack the weakest link, it's necessary to match the strength of the private key used with that of the public, or asymmetric, key.

ECC is a public-key system that's increasingly being used by organizations. It uses smaller key lengths than those used by older schemes (RSA, DSA) to achieve the same given security level. ECC is widely standardized–by National Institute of Standards and Technology (NIST), Federal Information Processing Standard (FIPS), and American National Standards Institute (ANSI)–and forms the basis for the next cryptographic standard for U.S. government use, known as Suite B.1

With AES replacing DES, NIST has published its recommendations for pairing public-key systems with the different AES key sizes. As you can see from Table 1, the much smaller ECC key sizes mean more efficient implementations of security mechanisms such as smaller signatures and certificates.

View the full-size image

As the name implies, the Elliptic-Curve Digital Signature Algorithm (ECDSA) is a digital signature scheme based on ECC. Like all digital signatures, ECDSA is used for authentication and integrity, but because it's based on ECC, its keys are smaller and its implementation is more efficient. Let's take a look at how we sign and verify a message using ECDSA.

An elliptic-curve group for cryptography comes from the multiples of a generating point G, a two-dimensional point on an elliptic curve over a finite field. In practice, the finite fields used are either integers modulo large primes, or a similar construction using 0/1 polynomials.

Using routines for arithmetic in finite fields, other routines can be built that will compute scalar multiples of the generating point, written kG , or of other points D = dG .

Public keys are created by multiplying the generator (which is defined in standards), that is, D is the public key for d if D = dG on the elliptic curve. Key generation, which is the production of (d ,D ) is therefore very basic and efficient in ECC. In RSA key generation involves coming up with large prime numbers, and takes much longer.

Suppose user D wants to sign a message. First he computes K = kG for k random.

Note that this (major part) of the computation can be completed before the message is in hand, which is often useful in embedded systems.

Now the message (or more likely the cryptographic hash of the message) is also an integer, m . The signature is computed with the much less intensive modular computations:

r = x _coord(K = kG ) mod n
s = k ^(-1) ( m + d r )

Here n is another number called the point order. The signature on m is (r ,s ).

Someone knowing public key D can verify this signature on m :

K ' = (s ^(-1) m ) G + (s ^(-1) r ) D .
r ' = x _coord(K ')

Accept if r == r '

In practice it's prudent to make other, more technical, checks on public keys D and on signatures.

We see here that verification involves two elliptic-curve multiplications–in fact, a linear combination, which can be done a little more efficiently. We could then assume that verification is roughly two times slower than signatures, but the ratio is less than that because only the linear combination, not the two multiples, are computed. In any case, verification is slower than signing.

In many applications, the ability to quickly generate signatures is a benefit and even a requirement. Two such cases are the production of signatures in an electronic check-image–signing machine and the production of signatures for digital postal marks in a letter-processing machine, both processes that require large quantities of units to be signed quickly. In these applications fast signature verification is also desired.

Speeding up verifications
While signing with ECDSA has always been significantly faster than signing with RSA, until recently verification with RSA was faster than with ECC, unless the key sizes used were extremely large. However, recent research by Certicom has found a way to speed up the verification of ECDSA by as much as 40%, making ECDSA more competitive.

In ECDSA signatures, normally the r component is a truncation of the per-signature key K , r = x _coord(K ). If K itself (or enough information to recover K from r ) is sent, then the multiplications in the signature verification can be scaled to be roughly half the size of the original scheme.

This technique is useful to accelerate ECDSA verification on many elliptic curves.

Optimizing ECC
So far we have focused on ECDSA because digital signatures are one of the most common security mechanisms used. However, cryptographic operations are used for more than signatures and additional techniques can be used to make other ECC operations even more efficient, a feature especially beneficial to embedded systems.

ECC is built upon finite-field arithmetic, and the speed of any implementation therefore depends on the underlying speed of the finite-field implementation.

Finite fields have the operations {+,-,*,/}. The multiplication operation *, is the dominant operation in ECC in terms of execution time.

The finite fields for standards-based ECC are either integers modulo a prime or binary polynomial-based. The elements are on the order of 200 or 300 bits (and this likely will not always fit into registers).

If the finite field is integers modulo a prime, then multiplication may use the processor's multiplication instruction, with careful code that builds up several-hundred-bit multiplication from these single-word operations.

Assembly code is often helpful, since double-length results from multiplication and carry handling are often much more efficiently implemented in machine language than in high-level languages.

The reduction modulo the prime is quite efficient for standard elliptic curves, since the primes are often selected as sparse integers with +/- 1 located only on 32-bit word boundaries.

On systems where there is the flexibility to add hardware, adding a hardware assist to perform finite-field multiplications can yield significant advantages in speed and power usage.

Case studies
The strength and efficiency of ECC makes it a ideal for many of today's applications that have code-size or battery-life constraints or need quick signature generation and verification. We'll look at a couple of these examples now.

RIM BlackBerry
The 32-bit ARM processor family is popular in embedded systems and offers an elegant regular instruction set. Its low power usage makes it a favorite for phones and other wireless terminals such as the BlackBerry from Research In Motion (RIM). Let's take a look at the performance we can expect from a low-end ARM7TDMI running at 50MHz.

Using optimized techniques, the curve sect163k1 from The Standards for Efficient Cryptography Group (SECG)2 can be implemented on this part in 4K to 5K of code space (for signature alone, or signature plus verification) using the ARM processor “Thumb” instruction set. This implementation performs ECDSA signatures at 35ms and the corresponding verification in 65ms. This low cost–in terms of code and time–makes ECDSA suitable for authenticated communication with embedded devices.

If we consider a larger curve suitable for use alongside AES-192 and also suitable for the U.S. Government's Suite B cryptography, we would select secp384r1. This curve matches the security strengths of the private- and public-key cryptosystem as mandated by NIST.

Signatures on this curve (using the 50-MHz ARM7TDMI) take 100ms, while verification time is 300ms. Employing the fast ECDSA verification technique, which I just described, reduces this time by roughly 40% with verification now taking 158ms, which is much closer to the signing time.

Digital postage marks
Now let's implement digital signatures in a postage processing machine that was identified at the outset of this article as one of the embedded systems needing security. The system in question implemented ECDSA signatures with sect163k1 in target hardware using the Hitachi SH-2 family processor HD64F7044F28 running at 24MHz.

By careful optimization of the finite-field routines, it was possible to perform digital signatures in roughly 50ms, which met the required speed of letter processing. With this implementation, the system developers avoided the expense and development time of adding special hardware to accelerate the ECDSA signatures.

Equally important, because ECC uses smaller key sizes to offer equivalent security, the machine can produce a printed signature notably smaller than competing schemes. This is a major consideration affecting the final size of the mark and the space it occupies on a piece of mail, as Figure 1 shows.

View the full-size image

By having small key sizes and producing efficient signatures, elliptic-curve cryptography is suitable for securing many embedded systems, from the digital postage application I just described to the command-and-control sensor network mentioned at the outset. As more embedded devices become interconnected, ECC offers huge advantages when you need to embed security. In fact, for the smallest systems it's often the only standards-based solution.

Rob Lambert is director of new technology at Certicom Corp. His main industrial interest is in the efficient implementation of ECC for embedded systems. He has a Ph.D in electrical engineering from the Univ. of Waterloo and has worked in the industry for 10 years. You can contact him at .

Endnotes:

1. For more information on the U.S. Government's Suite B see www.nsa.gov/ia/industry/crypto_suite_b.cfm?MenuID=10.2.7 and www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm?MenuID=10.2.7

2. For curve sect163k1 see the Standards for Efficient Cryptography Group (SECG) at www.secg.org.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.