Crittografia a Curve Ellittiche¶
La Storia Dietro la Matematica¶
A metà degli anni '80, RSA era ben consolidato ma aveva un problema crescente: la dimensione delle chiavi. Man mano che i computer diventavano più veloci, le chiavi RSA dovevano crescere per restare sicure. Esisteva una struttura matematica che potesse offrire la stessa sicurezza con chiavi più piccole?
Nel 1985, Neal Koblitz e Victor Miller proposero indipendentemente la risposta: le curve ellittiche — oggetti studiati dai matematici puri dal XIX secolo — potevano costituire la base di un nuovo sistema crittografico.
L'intuizione chiave: Le curve ellittiche su campi finiti formano un gruppo abeliano sotto un'operazione geometrica di addizione. Il problema del logaritmo discreto su queste curve è ancora più difficile della fattorizzazione di interi. Questo significa che ECC può raggiungere la stessa sicurezza di RSA con chiavi drasticamente più piccole.
Una chiave ECC a 256 bit offre circa la stessa sicurezza di una chiave RSA a 3072 bit.
Perché È Importante¶
- TLS/HTTPS — La sicurezza web moderna usa ECDHE per default
- Signal Protocol — La cifratura end-to-end usa Curve25519
- Bitcoin e Ethereum — La firma delle transazioni usa la curva secp256k1
- Chiavi SSH — Le chiavi Ed25519 sono ora preferite rispetto a RSA
- Smart card e IoT — Le chiavi piccole rendono ECC praticabile su dispositivi con risorse limitate
Le Formule¶
La Curva Ellittica¶
dove \(4a^3 + 27b^2 \neq 0\) (per garantire che la curva sia non-singolare).
Addizione di Punti¶
Dati due punti \(P = (x_1, y_1)\) e \(Q = (x_2, y_2)\), la loro somma \(R = P + Q = (x_3, y_3)\) è:
dove:
Il Problema del Logaritmo Discreto su Curve Ellittiche (ECDLP)¶
Dato un punto base \(G\) e un punto \(Q = nG\), trovare l'intero \(n\).
Derivazione¶
Passo 1: Le Curve Ellittiche come Gruppi¶
Una curva ellittica \(E\) su un campo, insieme al punto all'infinito \(\mathcal{O}\), forma un gruppo abeliano:
Regola geometrica: Per sommare \(P\) e \(Q\), si traccia la retta passante per entrambi. Questa retta interseca la curva in un terzo punto \(R'\). Si riflette \(R'\) rispetto all'asse \(x\) per ottenere \(R = P + Q\).
Passo 2: Le Formule di Addizione¶
La retta per \(P\) e \(Q\) ha pendenza \(\lambda\). Sostituendo nell'equazione della curva e usando le formule di Vieta, si ottengono le coordinate del terzo punto.
Per il raddoppio (\(P = Q\)), la "retta" è la tangente alla curva in \(P\):
Passo 3: Campi Finiti¶
Per la crittografia, si lavora su \(\mathbb{F}_p\) (interi modulo un primo \(p\)):
Per il teorema di Hasse, il gruppo ha approssimativamente \(p\) elementi:
Passo 4: Scambio di Chiavi ECDH¶
- Alice sceglie il segreto \(a\), calcola \(A = aG\), invia \(A\)
- Bob sceglie il segreto \(b\), calcola \(B = bG\), invia \(B\)
- Alice calcola \(S = aB = abG\)
- Bob calcola \(S = bA = abG\)
Entrambi ottengono lo stesso segreto \(S = abG\).
Confronto di Sicurezza¶
| Livello di Sicurezza | Chiave RSA | Chiave ECC | Rapporto |
|---|---|---|---|
| 80 bit | 1024 bit | 160 bit | 6.4× |
| 128 bit | 3072 bit | 256 bit | 12× |
| 256 bit | 15360 bit | 521 bit | 29.5× |
Errori Comuni¶
- Usare curve con piccoli sottogruppi: Il punto base \(G\) deve avere ordine primo grande.
- Non validare i punti: Verificare sempre che un punto ricevuto giaccia sulla curva.
- Creare le proprie curve: Usare curve standardizzate e verificate (Curve25519, P-256).
- Pensare che ECC sia quantum-safe: Come RSA, ECC è vulnerabile all'algoritmo di Shor.
Formule Correlate¶
- RSA — L'alternativa basata sulla fattorizzazione
- Scambio di Chiavi Diffie-Hellman — La versione con aritmetica modulare di ECDH
Riferimenti¶
- Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177), 203–209.
- Miller, V. S. (1986). Use of Elliptic Curves in Cryptography. Advances in Cryptology — CRYPTO '85.
- Bernstein, D. J. (2006). Curve25519: New Diffie-Hellman Speed Records. PKC 2006.