Isn’t Elliptical Curve Cryptography (ECC) overkill for a small embedded IoT device? This is a question we hear from time to time, but based on its computation requirements and security properties, ECC might be a better choice for IoT devices than RSA.

Because asymmetric encryption methods require much more computation than symmetric AES encryption, most systems use asymmetric encryption only for key exchange and then use symmetric AES encryption for basic communications.

ECC and RSA are both asymmetric encryption algorithms. The RSA algorithm is based on the problem of factoring the product of two large numbers. It requires first the generation of large random numbers, checking for primeness, and then multiplying two large numbers. RSA not really an acronym, but an abbreviation of the authors last names – Rivest, Shamir, & Adleman.

Implementing RSA at 2048 bits on a small embedded 32-bit processor is not going to be fast. Multiplication of two 2048 bit numbers requires a 64 word by 64 word long multiply operation. This requires is 4096 long multiply with 64-bit resultant and accumulate (UMLAL) instructions on the M3 or M4 processor, or 32768 multiply with 32-bit resultant (MULS) and add (ADDS) instructions on the M0.

The approximate computation times for a 2048 bit multiply on the Cortex M processors running at 25 MHz are:

• Cortex M4 – 500 us
• Cortex M3 – 1.5 ms
• Cortex M0 – 25 ms

An RSA key of 2048 bits is equivalent to a symmetric AES key of 128-bits. The NSA suite B standard requires a 3072 bit RSA key, which is equivalent to 256-bit symmetric key encryption. The computation time for increasingly higher levels of security increases exponentially using RSA.

Elliptical Curve Cryptography is based on solving the Discrete Logarithm problem. Stated simply, it is not easy to find the discrete logarithm of a point on an elliptical curve. The main benefit of ECC is that it provides a high level of security using a relatively short key. Shorter keys use less memory and dramatically decrease the computational requirements. ECC using a 256-bit key and the 256-bit prime curve is roughly equivalent to RSA 2048.

With a little bit of extra hardware to accelerate modular multiplication, ECC can potentially offer better performance and use less memory than RSA.

Internet security suites provide a comprehensive solution for security which includes key agreement, symmetric encryption with authentication, hash codes, and digital signature. The Transport Layer Security (TLS) specification includes several security suites using different algorithms.

Note that RSA is a full security suite by itself that provides asymmetric encryption and signature. However, the alternatives to using RSA for everything are generally to use one method for key exchange and a different method for signatures.

RSA specified a method for generating key pairs. Rather than using RSA generated key pairs, the alternative is to use the Diffie-Hellman (D-H) key exchange algorithm. This is another algorithm named for the authors - Whitfield Diffie and Martin Hellman.

Diffie-Hellman has some advantages over RSA. However, both RSA and Diffie-Hellman require relatively long keys (2048-bits or more). A variant of the Diffie-Hellman Algorithm using elliptical curve cryptography is Elliptical Curve Diffie-Hellman (ECDH). This key exchange algorithm allows the use of much smaller keys and is well suited for small IoT wireless devices.

The alternatives to using RSA for digital signatures are the Digital Signature Algorithm (DSA) and the variant Elliptical Curve DSA (ECDSA). Again, the elliptical curve variant has the advantage of using a smaller key.

While various combinations are possible, the three passionate solutions are -- use RSA for everything, use DH for key exchange and DSA for signatures, or embrace ECC and use ECDH for key exchange and ESDSA for digital signatures.

Going forward, there is a strong preference for ECDH-ECDSA. Most TLS clients will send a list of security suites in order of preference. The preference for Mozilla Firefox lists ECDH-ECDSA first and RSA as a last resort.

You can check out the Given Cipher Suites supported by your browser using How’s My SSL?

As of this writing, the draft of TLS1.3 does not support using RSA for everything and also deprecates DSA as a signature option. RSA remains as a signature option in combination with DH or ECDH for key exchange.

Diffie-Hellman and Elliptical Curve Diffie-Hellman are favored because they support ephemeral keys and forward secrecy. The Diffie-Hellman algorithm generates a new unique ephemeral key for each key exchange process.

Forward secrecy is a property of a security suite that ensures that if the present key is compromised this does not compromise past session keys. Without forward security, it may be possible to record sessions, then by breaking one key the whole past history is unraveled. 

As proposed, TLS 1.3 will only support ephemeral keys and methods with forward secrecy. DH and ECDH support ephemeral keys and forward secrecy, but RSA does not.

Based on the lower computational requirements of ECC and the desirable properties of Diffie-Hellman key exchange, we predict that IoT products will increasingly use ECDH for key exchange and ECDSA for digital signatures.