gb flag  it flag

Crittografia delle Curve Ellittiche

Message in a Bottle usa un motore crittografico a chiave pubblica basato sulla Crittografia delle Curve Ellittiche (ECC).

La Crittografia delle Curve Ellittiche è un sistema crittografico a chiave pubblica, ideato separamente da Neal Kiblitz e Victor Miller nel 1985, basato sulla teoria delle curve ellittiche definite su campi finiti (per una approfondimento sulla crittografia a chiave pubblica si veda l'articolo "La Crittografia per la protezione delle informazioni sulla rete")

Una curva ellittica

Una curva ellittica è una curva piana definita da un'equazione del tipo

y2 =  x3 + a x + b.

Le soluzioni di tale equazioni, insieme al punto all'infinito, formano un gruppo abeliano (se si considera il punto all'infinito come l'elemento identico). Restringendo la scelta delle coordinate x e y ad un campo finito (ossia contenente un numero finito di punti) l'insieme delle soluzioni forma un gruppo abeliano finito.

Logaritmo discreto

Il problema del logaritmo discreto è alla base della crittografia delle curve ellittiche.
Il logaritmo discreto è definito come il logaritmo, in una certa base n, su un gruppo algebrico (a differenza del logaritmo tradizionale che è definito sull'insieme dei numeri reali).
Ad esempio,  si consideri il gruppo moltiplicativo degli interi modulo p:

G = Z*p    con p numero primo (in pratica l'insieme degli interi {1,2....p})

Si consideri poi l'equazione:

ax =  b mod p     (mod calcola il resto della divisione b/p)

Il problema del logaritmo discreto consiste nel trovare il valore di x tale che l'equazione è soddisfatta.

Non sono noti ad oggi algoritmi efficienti per il calcolo dei logaritmi discreti. Si tratta in pratica di un problema NP (non-polinomial) la cui soluzione richiede un tempo di calcolo esponenziale rispetto alle dimensione del gruppo algebrico G.
E' proprio l'appartenenza alla classe dei problemi NP che pone il problema del logaritmo discreto alla base nella realizzazione di  sistemi crittografici a chiave pubblica.

Il problema del logaritmo discreto viene sfruttato per implementare l'algoritmo Diffie-Hellmann di scambio delle chiavi.

Diffie-Hellmann (scambio delle chiavi)

Alice e Bob voglio scambiarsi messaggi cifrati. Prima di inviare messaggi, però, Alice e Bob devono accordarsi su una chiave segreta di cifatura con la quale cifrare i messaggi. Quindi il problema è: come possono Alice e Bob scambiarsi in sicurezza tale chiave di cifratura? L'algoritmo Diffie-Hellmann di scambio delle chiavi consente di risolvere questo problema.

1) Alice e Bob scelgono una particolare curva ellittica  y2 =  x3 + a x + b assegnando degli opportuni valori ad a e b

2) Alice e Bob scelgono su tale curva un punto G (x, y) detto generatore.

3) Alice sceglie un intero m abbastanza grande (chiave privata) e calcola la quantita mG (chiave pubblica) che invia a Bob

4) Bob sceglie un intero n abbastanza grande (chiave privata) e calcola la quantita nG (chiave pubblica) che invia ad Alice

5) Alice e Bob hanno entrambi la quantitò mnG che rappresenta la chiave crittografica cercata all'inizio.

E' stato dimostrato che il problema di calcolare mnG conoscendo solo mG o nG (problema di Diffie-Hellmann per le curve ellittiche) è analogo al problema del logaritmo discreto descritto in precendenza (per la dimostrazione dettagliata si veda N. Koblitz, "Elliptic curve cryptosystems", in Mathematics of Computation 48, 1987, pp. 203–209).

Sicurezza della Crittografia delle Curve Ellittiche

Il problema del logaritmo discreto usato nell'ambito della crittografia a curva ellittiche, a parità di dimensione del campo,  è considerato più complesso del problema della fattorizzazione di interi  usato dalla crittografia RSA. Pertanto, a parità di sicurezza, la crittografia delle curve ellittiche richiede chiavi di dimensione inferiori a quelle utilizzate dal crittosistema RSA.

Tempo richiesto per risolvere il problema del logaritmo discreto
(in MIPS/anno)		 Lunghezza chiavi RSA
(in bit)		 Lunghezza chiavi ECC
(in bit)		 Confronto RSA/ECC
104 512 106 5 : 1
108 768 132 6 : 1
1011 1024 160 7 : 1
1020 2048 210 10 : 1
1078 21000 600 35 : 1

Allo stato attuale (2006) non esistono lavori che abbiano stabilito il grado di difficoltà del sistema basato su curve ellittiche. Tuttavia la National Security Agency ha acquisito una tecnologia basata su curve ellittiche che è stata inserita tra gli algoritmi raccomandati per la "NSA Suite B".

Semplicità di calcolo

Un'altro aspetto che differenzia la crittografia delle curve ellittiche dal crittosistema RSA è la maggiore semplicità delle  operazioni matematiche richieste per il calcolo delle quantità crittografiche.
Le operazioni richieste dalle curve ellittiche sono principalmente addizioni e moltiplicazioni tra valori scalari e/o punti della curva. Viceversa il crittosistema RSA richiede operaioni in modulo considerevolmente più pesanti in termini di risorse di calcolo. Pertanto il crittosistema a curve ellittiche meglio si addice ad implementazioni su dispositivi con ridotte capacità di calcolo quali smart card, telefoni cellulari, ecc.

Curve ellittiche e SMS

La crittografia delle curve ellittiche ha quindi diverse caratteristiche molto gradevoli ai fini dell'implementazione su telefoni cellulari per proteggere SMS. In primo luogo, come detto in precedenza, a parità di sicurezza consente di avere chiavi di lunghezza notevolmente inferiore a quelle della crittografia RSA. Facendo riferimento alla figura in alto, una chiave ellittica con soli 160 bit offre lo stesso livello di sicurezza di una chiave RSA da 1024 bit. Pertanto le dimensioni dei messaggi cifrati/firmati sono ridotte (a parità di sicurezza) rispetto q auella che si avrebbe con la crittografia RSA.
In secondo luogo, come già accennato, le operazioni matematiche richieste dal crittosistema a curve ellittiche sono molto più semplici e richiedono quindi minore potenza di calcolo. Pertanto, la crittografia delle curve ellittica risulta essere la tecnologia crittografica più adeguata per l'implementazione su dispositivi con ridotte risorse di calcolo quali i telefoni celluari.