Digital Signature - RSA vs ECDSA
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?
Contents
RSA
RSA is a well-established public key algorithm, invented in 1977 and standardized for digital signatures in the 1990s.
To compute and verify a digital signature, rather simple modular arithmetic equations are used. While relatively simple to compute, there is no known solution to get the private key from the knowledge of the public key and a signature. This is the RSA problem and makes RSA secure.
Key Size
RSA can work with private keys of any size. Commonly used key lengths are: 1024 bits ("industrial grade") and 2048 bits ("military grade"), while NIST recommends a minimum key length of 2048 - 3072 bits for new systems.
Resource Use
RSA digital signature verification can be implemented in about 6 kB ROM and requires about 3 kB of stack memory. (Implementation of RSA in emSecure)
Storage requirements for the public key are equal to the key size. The digital signature size is equal to the key size, too.
Performance
The performance of RSA signature verification can be split into two parts:
- Hashing the data, which depends on the data size and the hash algorithm.
- Signature decryption and verification, which depends on the public key size.
| Hashing | |
|---|---|
| emCrypt SHA-1 Hash computation | 12.51 MB/s |
| emCrypt SHA-224 Hash computation | 3.66 MB/s |
| emCrypt SHA-256 Hash computation | 3.66 MB/s |
| emCrypt SHA-512 Hash computation | 2.82 MB/s |
| Signature verification | |
| emCrypt RSA 512 bit signature verification | 0.87 ms |
| emCrypt RSA 1024 bit signature verification | 2.18 ms |
| emCrypt RSA 2048 bit signature verification | 7.40 ms |
| emCrypt RSA 3072 bit signature verification | 15.89 ms |
| emCrypt RSA 8192 bit signature verification | 92.94 ms |
| emCrypt RSA 16384 bit signature verification | 333.19 ms |
ECDSA
ECDSA (Elliptic Curve Digital Signature Algorithm) is a version of the digital signature algorithm (DSA), using elliptic curve cryptography (ECC) as its public key algorithm. It was developed in 1985 and standardized in 1999 (ANSI) and 2000 (IEEE, NIST).
For ECDSA, an elliptic curve is selected, which defines the key size and security level. ECDSA signatures are secure, because of the difficulty to compute discrete logarithms in the group of points on the chosen curve.
Key Size
The key size of ECDSA keys depends on the elliptic curve which shall be used. There are different defined and commonly used curves with different characteristics. For example NIST P-192, P-224, P-256, P-384, P521.
Resource Use
ECDSA digital signature verification can be implemented in about 10 kB ROM and requires about 3.2kB of stack memory. (Implementation of ECDSA in emSecure)
Storage requirements for the public key are equal to the key size. The ECDSA signature is twice the size of the key.
Performance
The performance of ECDSA signature verification can also be split in two parts:
- Hashing the data.
- Signature verification, which depends on the chosen elliptic curve.
| Hashing | |
|---|---|
| emCrypt SHA-1 Hash computation | 12.51 MB/s |
| emCrypt SHA-224 Hash computation | 3.66 MB/s |
| emCrypt SHA-256 Hash computation | 3.66 MB/s |
| emCrypt SHA-512 Hash computation | 2.82 MB/s |
| Signature verification | |
| emCrypt ECDSA P-192 signature verification | 43.45 ms |
| emCrypt ECDSA P-224 signature verification | 53.87 ms |
| emCrypt ECDSA P-256 signature verification | 78.70 ms |
| emCrypt ECDSA P-384 signature verification | 129.17 ms |
| emCrypt ECDSA P-521 signature verification | 245.68 ms |
Comparison
To better compare key size and performance of different cryptographic algorithms, the level of security for any algorithm and key size can be estimated.
| 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 |
| 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 |
| 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) |
As of today, and for at least the next 10 years, the cost of using RSA with
recommended key sizes (1024 - 3072 bit) is lower than its ECDSA equivalent.
When in the future security level requirements rise,
there will be a break even at which it may be more efficient to use ECDSA.
That is for storage requirements at ~160 bit security level (4096 bit RSA)
and for performance at ~200 bit security level (10240 bit RSA).
Notes
All resource use and performance values have been measured with emCrypt, on a Cortex-M7 microcontroller at 200 MHz.
