ECC in practice

ECDSA, key sizes and traps

ECDH exchanges keys; it remains to sign and to understand why elliptic curves have conquered modern cryptography. This is the role of ECDSA, and the occasion for one of the most famous traps in the discipline.

The great advantage: tiny keys

The decisive asset of elliptic curves is key size. Since the ECDLP resists better than factoring, fewer bits are needed for the same security (n bits = 2^n operations to break the system).

Security (bits)	RSA key	ECC key	Ratio
80	1024 bits	160 bits	~6×
112	2048 bits	224 bits	~9×
128	3072 bits	256 bits	~12×
192	7680 bits	384 bits	~20×
256	15360 bits	512 bits	~30×

A 256-bit ECC key therefore offers the same security as a 3072-bit RSA key. Hence less data (lighter certificates) and faster computations, which matters on connected devices, smart cards and phones.

ECDSA: signing with a curve

ECDSA (Elliptic Curve Digital Signature Algorithm) is the adaptation of the digital signature to elliptic curves. Like any public-key signature, you sign with your private key (the secret scalar) and anyone verifies with the public key (the corresponding point).

But each signature also uses an ephemeral random number, the nonce (written k), drawn at random each time. ECDSA is everywhere: it protects TLS (HTTPS), authenticates SSH and signs Bitcoin transactions.

The deadly trap: reusing the nonce

The nonce k must be secret, random and unique for each signature — an absolute requirement. Because the mathematical structure of ECDSA is such that if the same k is used to sign two different messages, then, from the two public signatures, you can recover k, then deduce the private key.

   Two signatures (r, s1) and (r, s2) with the SAME k
                     │
                     ▼   (the identical r betrays the reuse)
        solve for k  =  (z1 − z2) / (s1 − s2)
                     │
                     ▼
        recover the private key d  =  (s1·k − z1) / r
                     │
                     ▼
             PRIVATE KEY FULLY REVEALED

In other words, a single lapse on the nonce destroys the entire system: the attacker can now sign in your place.

The PlayStation 3 affair

This is not theoretical. In 2010, the fail0verflow collective showed that Sony used, in the PlayStation 3, a constant ECDSA nonce to sign authorized software. As a result: anyone could extract the console's private key and sign their own programs as if they came from Sony. The whole chain of trust collapsed on this single mistake.

Since then, good implementations generate the nonce deterministically from the message and the private key (RFC 6979): it remains unique and unpredictable.

In summary