Digital Signature - RSA vs ECDSA

From SEGGER Wiki
Jump to: navigation, search

A common way to validate the integrity of data and to authenticate the creator of the data is the use of digital signatures. This is a step up from a simple checksum, which can only be used for integrity checks. For authentication, digital signature algorithms use public key cryptography with a key pair of public and private key. The private key is kept secret by its owner and used to create a digital signature. The public key can be shared and is used to verify that data has been signed with the private key and as such has been created by the private key owner (authentication) and has not been modified afterwards (integrity).

There are two major public key algorithms used for digital signatures: RSA and ECDSA.

What are the differences between RSA and ECDSA? Which algorithm should be used in embedded systems?

Comparison

Security Level

For comparison of different cryptographic algorithms, the level of security which each algorithm provides should be known. Different researches and papers analyzed how secure algorithms are, e.g. how long will it take until the algorithms could be broken (with reasonable resources).

The security level is measured in bits and usually corresponds to a symmetric key cipher of that size.

With variable key length, RSA and ECDSA can achieve virtually any security level. This table describes the security level of common key lengths, which are used for further comparison.

Security Level RSA ECDSA
80 bits 1024 bits 160 bits
112 bits 2048 bits 224 bits
128 bits 3072 bits 256 bits
192 bits 7680 bits 384 bits
256 bits 15360 bits 512 bits

Resource Use

In an embedded system, the implementation of RSA requires less code ROM (Flash) as well as a bit less dynamic memory (RAM) than ECDSA.

For most applications, the public key is also stored in ROM. ECDSA keys are significantly smaller than RSA keys at the same security level, and the savings get bigger with higher levels.

The same applies for signatures, which are stored or transmitted. Although ECDSA signatures are twice the size of the key, ECDSA can save storage and bandwidth compared to RSA.

RSA ECDSA
Resource Use
ROM Use 6 kB 10 kB
RAM Use 3.0 kB 3.2 kB
Key Store 1 * Key length 1 * Key length
Signature Store 1 * Key length 2 * Key length

Performance

The performance between signing and verifying data is different for both algorithms, RSA and ECDSA. (EC)DSA performs different operations for signing and verifying, while RSA can benefit from using a much smaller public exponent for verification.

On embedded systems, the most common use for digital signatures is verification of data.

RSA performs significantly faster at currently used security levels, but performance degrades about exponentially with rising key lengths. ECDSA signature verification is a slower process, but can be faster than RSA at higher security levels.

RSA ECDSA
Verification Performance
80 bit 2.18 ms (1024 bit) 43.45 ms (P-192)
112 bit 7.40 ms (2048 bit) 53.87 ms (P-224)
128 bit 15.89 ms (3072 bit) 78.70 ms (P-256)
192 bit 92.94 ms (8192 bit) 129.17 ms (P-384)
256 bit 333.19 ms (16384 bit) 145.68 ms (P-521)


Conclusion

As of today, and for at least the next 10 years, the cost (for memory use and computation) of using RSA at recommended security levels is lower than its ECDSA equivalent.

Since security level requirements will steadily rise, there will be a break even at which ECDSA becomes more efficient for signature verification. For storage requirements that is at ~160 bit security level, and for computation speed at ~200 bit security level.

Notes

All resource use and performance values have been measured with emCrypt, on a Cortex-M7 microcontroller at 200 MHz.