# Crittografia ellittica

In crittografia la crittografia ellittica (in inglese Elliptic Curve Cryptography o anche ECC) è una tipologia di crittografia a chiave pubblica basata sulle curve ellittiche definite su campi finiti. L'utilizzo di questo metodo crittografico è stato proposto da Neal Koblitz e Victor S. Miller nel 1985.
Le curve ellittiche sono utilizzate in diversi metodi di fattorizzazione di numeri interi che sono utilizzati in crittologia come per esempio la fattorizzazione a curve ellittiche Lenstra che pur utilizzando le curve ellittiche non sono normalmente classificate come metodi crittografici.

## Introduzione

Le chiavi pubbliche si basano sulla creazione di un problema matematico molto difficile da risolvere senza informazioni, ma che con l'utilizzo di alcune informazioni (la chiave privata) diventa di semplice e rapida risoluzione. L'utente distribuisce pubblicamente il problema (la chiave pubblica) e tiene nascoste le informazioni aggiuntive (la chiave privata). Il problema viene utilizzato per mescolare i messaggi da trasmettere in modo da renderli non comprensibili. Il primo sistema a chiave pubblica sviluppato è stato l'algoritmo RSA e si basava sull'utilizzo di due numeri primi di grandi dimensioni che venivano moltiplicati tra di loro, il cui prodotto era distribuito come chiave pubblica. Per decifrare i messaggi era necessario risalire ai due numeri o fattori primi componenti, ma l'operazione di fattorizzazione è un'operazione molto onerosa a livello computazionale, se non si hanno ulteriori informazioni, mentre se si conosce uno dei due numeri primi l'operazione diventa banale. Con l'evoluzione della potenza di calcolo dei computer e delle tecniche di fattorizzazione per ottenere però una sicurezza adeguata con tale metodo bisogna utilizzare numeri primi di migliaia di cifre con conseguenti chiavi molto lunghe e quindi scomode da usare.
Un'altra tipologia di problemi matematici richiedono invece la risoluzione dell'equazione $a^{x}=b$ con $x$ ignoto e $a$ e $b$ noti (in sostanza l'equazione è $x=\log _{a}(b)$, ovvero $x$ uguale al logaritmo in base $a$ di $b$). Questa classe di equazioni può essere risolta con semplicità nel campo dei numeri reali e complessi tramite l'uso dei logaritmi. Ma se queste equazioni vengono portate in un campo finito in molti casi diventano estremamente difficili da risolvere dato che coinvolgono il noto problema complesso del logaritmo discreto.
In particolare una curva ellittica è una curva piana definita da un'equazione del tipo:
    $y^{2}=x^{3}+ax+b$
L'insieme delle soluzioni di questa equazione sono i punti che formano la curva (tutte le soluzioni dell'equazioni con il punto all'infinito formano un gruppo abeliano se si considera il punto all'infinito come l'elemento identico). Se le coordinate $x$ e $y$ sono scelte in un campo finito le soluzioni formano un gruppo abeliano finito. Il problema del logaritmo discreto utilizzato nella crittografia a curva ellittica è molto più difficile del problema della fattorizzazione di numeri primi, a parità di dimensione del campo, e quindi a parità di sicurezza questa crittografia richiede chiavi pubbliche di dimensione inferiore, e quindi più facilmente utilizzabili rispetto a quelle utilizzate dal metodo RSA.
Allo stato attuale (2006), non esistono articoli matematici che abbiano stabilito il grado di difficoltà del sistema basato su curve ellittiche; in ogni caso, la National Security Agency ha acquisito una tecnologia basata su curve ellittiche, che è stata inserita tra gli algoritmi raccomandati per la NSA Suite B. Inoltre, mentre i brevetti sul metodo RSA sono scaduti, alcuni brevetti sui sistemi ECC sono ancora validi.
Un esempio di applicazione della crittografia basata sulle curve ellittiche è l'ECDSA.