Crittografia a chiave pubblica e curve ellittiche. Una panoramica per profani. Terza parte: Usare le curve ellittiche per le firme digitali

Nella prima e nella seconda parte abbiamo visto le basi della crittografia a doppia chiave e cosa sono le curve ellittiche, matematicamente parlando. 

Dalle curve rappresentate su un piano cartesiano classico, con x e y appartenenti ai numeri reali, passiamo a un piano più "particolare", con x e y interi positivi, appartenenti a GF(p). GF è un Campo di Galois, p è il numero primo che lo caratterizza. Un Campo di Galois è un insieme composto da tutti i numeri interi da zero a (p-1). Il fatto che p sia un numero primo gli da delle proprietà particolari. Sul campo posso riportare tutte le operazioni aritmetiche classiche, nella loro versione in modulo "mod n". Il piano cartesiano, continuo e infinito, diventerà quindi una matrice discreta e finita. I parametri A e B della curva sono anche essi numeri interi appartenenti a GF(p). Sulla matrice possiamo tracciare tutti i punti appartenenti a una curva definita. Un modo è quello di partire da una coordinata x e calcolare le due soluzioni in y, se esistono, nel dominio GF(p).

Prendiamo per esempio la curva:

Y^2 == X^3 -3*X +5

e GF(109)

ricaviamo le Y

Y == ±SQRT(X^3 -3*X +5) mod 109

per ogni X appartenente a GF(109)

la radice quadrata in modulo non è uguale a quella classica. Può anche non avere soluzioni in GF(p).

Per esempio:

SQRT(2) mod 7 == 3

l'operazione "SQRT() mod n" risponde alla domanda: quale è il numero "x" tale che

x^2 mod 7 == 2

la soluzione in questo caso è 3, perchè

3^2 == 9

e

9 mod 7 == 2 (il resto della divisione per 7, o il "giro delle lancette" su un orologio con 7 ore)

Tornando alla curva, con x == 5 non abbiamo soluzioni. Quindi la curva in GF(109) non avrà punti con x == 5

Con x == 6 invece otteniamo y == 51 e y == 58. Quindi i punti P1 (6, 51) e P2 (6, 58) sono punti appartenenti alla curva.

Proviamo a tracciare tutta la "curva" su GF(109) su una matrice 109x109. Vedremo che non ha proprio la forma di una curva a cui siamo abituati. Ma ne rispetta la definizione, ovvero "tutti i punti che rispettano l'equazione Y^2 == X^3 -3*x +5 mod 109".

Anche il GF(p) in due dimensioni presenta il cosiddetto "effetto PacMan" (o "effetto orologio a lancette"). Ogni volta che calcolando un punto, questo ha coordinate fuori dalla matrice, "rientra dall'altra parte" grazie all'operazione in modulo p. Notate che la simmetria dei punti della curva rispetto a un asse orizzontale continua a valere. I punti della curva formano un cosiddetto "Gruppo Ciclico Algebrico". Su questi punti e sul GF(p) possiamo riportare tutte le operazioni di somma tra punti e somma di un punto con se stesso, definite in precedenza. 

Su una curva ellittica definita in GF(p) possiamo individuare un punto "speciale" G, detto "punto generatore". Questo punto, sommato a se stesso un certo numero di volte, ci permette di coprire un insieme più o meno grande dei punti appartenenti alla curva. 

Tracciamo la stessa curva precedente, ma sul campo GF(11), molto più piccolo e semplice da maneggiare.

Il punto G (0,4) evidenziato è un punto generatore. Sommandolo a se stesso otteniamo:

(0,4) → (1,6) → (3,1) → (9,5) → (5,4) → (6,7) → (8,3) → (8,8) → (6,4) → (5,7) → (9,6) → (3,10) → (1,5) → (0,7) → ∞

"∞" è il cosiddetto "Punto all'infinito". Anche in GF(p) è ottenuto sommando tra loro due punti allineati in verticale (stessa x). E anche qui rappresenta l'elemento neutro nell'operazione di somma tra punti di una curva ellittica. Sommato a un qualsiasi punto, il risultato è sempre lo stesso punto iniziale.

P + ∞ == P

Qui l'abbiamo ottenuto sommando tra loro il punto (0, 7) e il punto generatore G (0, 4). Quanto è grande l'insieme di punti generato da G? Dipende dal co-fattore della curva. Se la curva ha co-fattore 1, come nell'esempio, dal generatore G posso generare tutti i punti della curva. Che sarà formata quindi da un singolo Gruppo Ciclico. Altrimenti, se la curva ha per esempio co-fattore 4, con un punto generatore potrò generare solo 1/4 dei punti totali della curva. Questi punti generati apparterranno a un singolo sotto-gruppo ciclico. Per generare tutti i punti della curva in caso di co-fattore 4, avrò bisogno di 4 punti generatori diversi. Coi quali potrò generare tutti e 4 i sottogruppi, che compongono la totalità dei punti della curva. I sottogruppi hanno tutti la stessa dimensione e tra loro non si sovrappongono. 

Il numero "r" di punti totali della curva è detto anche "ordine della curva". E sarà dato dal co-fattore "h" per il numero "n" dei punti di un singolo sotto-gruppo, detto anche ordine del sotto-gruppo. Tutti i sottogruppi hanno quindi lo stesso ordine "n"

r = h * n 

il co-fattore "h" sarà dato quindi da:

h = r / n 

Ogni sotto-gruppo avrà tra i suoi punti sia il suo punto generatore G che il punto all'infinito. Per un totale di "n" punti per ogni sotto-gruppo. 

Notare che:

n*G == 0*G == "punto all'infinito" == ∞

∞ + G == 0*G + 1*G == G 

Ora la domanda è: come possiamo usare tutto questo per fare, ad esempio, un'operazione di firma digitale sicura? 

Innanzitutto dobbiamo individuare la curva con la quale vogliamo lavorare, quindi i suoi parametri, i numeri A e B. Definiamo il campo GF(p) scegliendo il numero primo p. E troviamo un punto generatore G. In grado di generare tutti i punti della curva, se il co-fattore è 1. Oppure solo un sottogruppo di ordine n se il co-fattore è maggiore. 

Tutte le curve usate per operazioni crittografiche, sono curve ellittiche standardizzate, pensate e costruite per questo scopo. Alcune sono addirittura coperte da brevetto. Ma esistono tantissime curve standard, di "pubblico dominio", utilizzabili liberamente. 

Importante: le curve ellittiche standard sono state sia progettate per lo scopo, che già state analizzate a fondo. Sono scelte e costruite usando parametri che hanno un formato particolare che ci agevola nei calcoli. E in quasi due decenni, su queste curve non sono state ancora trovate vulnerabilità significative. Quindi la prima raccomandazione è quella di non inventarsi le proprie curve per poi usarle in applicazioni crittografiche, ma di affidarsi sempre alle curve standard. Una di queste curve standard è, per esempio, la cosiddetta curva "secp256r1" definita dal NIST, l'Istituto Nazionale USA per gli Standard e la Tecnologia. Su questa curva, il numero primo "p" che definisce il campo GF(p) è un numero su 256 bit:

p == 2^256 – 2^224 + 2^192 + 2^96 – 1

Sono numeri a 256 bit anche le coordinate dei punti sulla curva x e y, e i parametri A e B. Cominciamo a vedere come generiamo la coppia di chiavi, pubblica e privata.

La chiave privata sarà un numero casuale "d", scelto su 256 bit modulo n, l'ordine del sottogruppo. "d" è quindi un numero di circa 78 cifre decimali. Quindi decisamente un numero grande.

La chiave pubblica Q sarà un punto sulla curva, individuato dalle sue cordinate (xQ, yQ) e calcolato moltiplicando la chiave privata "d" per il punto generatore G

Q == d*G 

Questa è la nostra Trapdoor Function, la "funzione botola". Calcolare il punto Q partendo da "d" e dal generatore G è un'operazione facile e veloce. Si fa con una serie di somme e raddoppi consecutivi sui punti. Ma l'unico modo per ricavare la chiave privata "d" conoscendo Q e G, è paragonabile a provare tutti i numeri d possibili. 

Come facciamo adesso a firmare digitalmente un messaggio M usando la nostra chiave privata "d"? 

Ricapitoliamo i parametri della curva: 

p, il numero primo che individua GF(p) 

a, primo parametro della curva. Nella curva secp256r1 presa da esempio, a è uguale a (p - 3)

b, secondo parametro della curva

G = (xG, yG), un punto generatore della curva

n, la dimensione del sottogruppo individuato dal generatore G.

La curva secp256r1 presa da esempio ha co-fattore 1. Quindi partendo dal generatore G, posso generare tutti i punti della curva. Le curve ellittiche standard per operazioni crittografiche hanno tutte un co-fattore molto piccolo, in genere minore o uguale a 8. 

L'algoritmo di firma digitale con curve ellittiche si chiama ECDSA (Elliptic Curve Digital Signature Algorithm), ed è così descritto: 

Dato il messaggio M da firmare e data una funzione digest o una funzione hash nota (per esempio SHA256), calcoliamo la sua firma digitale usando la chiave privata "d":

Generiamo un numero casuale "k" minore di "n", e ne calcoliamo l'inverso in modulo n

k^-1 mod n

l'inverso x == INV(k) mod n è un numero "x" tale che:

k * x == 1 mod n 

(si legge "k per x è coerente con 1 modulo n")

il numero casuale "k" serve ad introdurre casualità nella firma, in modo da evitare gli attacchi con dizionari (firma,hash). In questo caso parliamo di "firma digitale non deterministica".

Calcoliamo il punto sulla curva R == k*G ; R avrà (xR, yR) (coordinate x e y del punto R)

calcoliamo il numero r = xR mod n ; "r" sarà la prima parte della firma 

Dal messaggio M, calcoliamo l'hash H == Sha256(M) ; oppure usando un'altra funzione hash sicura. H sarà un numero su 256 bit, lo interpreto come un numero scalare "e".

Alla fine calcoliamo il numero s == (k^-1 * (e + d * r)) mod n ; ricordiamo che "d" è la chiave privata. Il numero "s" sarà la seconda parte della firma. 

firma(M, d) == (r, s) 

Vediamo ora il processo di verifica della firma (r, s) del messaggio M, usando la stessa funzione hash e la chiave pubblica Q del firmatario

Abbiamo il messaggio ricevuto M. Col messaggio M abbiamo ricevuto anche la sua firma (r, s). Abbiamo tutti i parametri della curva usata. Conosciamo la funzione hash usata per la firma (es. Sha256()). Abbiamo la chiave pubblica Q del firmatario.

Calcoliamo l'hash del messaggio ricevuto H == Sha256(M) ; lo interpretiamo come un numero scalare "e" 

calcoliamo il numero w == s^-1 mod n 

calcoliamo il numero u1 = e * w mod n 

calcoliamo il numero u2 = r * w mod n 

calcoliamo il punto R == (xR, yR) come: R == u1*G + u2*Q 

Alla fine, calcoliamo v == xR mod n 

se v == r, allora la firma del messaggio è verificata. Altrimenti no. 

C'è da fare un discorso di differenza di prestazioni rispetto per esempio a RSA.

L'operazione di generazione delle chiavi in ECDSA è molto veloce. La chiave privata è un numero casuale, la chiave pubblica è ricavata con un prodotto scalare.

In RSA la generazione di chiavi è molto lenta. Dobbiamo generare due numeri primi molto grandi. Da circa 250 cifre decimali cadauno. Generare un numero primo di queste dimensioni significa generare un numero casuale dispari e sottoporlo ad una serie di "test di primalità". Per determinare se è "sufficientemente primo" per applicazioni crittografiche. Questa operazione è molto lenta.

L'operazione di firma digitale in ECDSA è abbastanza veloce. C'è un'operazione di calcolo di un inverso che è la parte più lenta. Tutte le operazioni sono fatte su 256 bit.

In RSA l'operazione di firma digitale consiste nel calcolare:

H^d mod m

dove H, d e m sono numeri su 2048 bit. L'elevamento a potenza si riduce a una serie di prodotti e di calcolo di quadrati in modulo, ma i numeri sono molto grandi e i passi dell'algoritmo sono tanti quanti i bit dell'esponente, quindi 2048 nel caso di RSA2048.

L'operazione di verifica della firma digitale in ECDSA è molto lenta. Nonostante si lavori con numeri piccoli (256 bit nel caso della curva secp256r1) i passi sono tanti e le operazioni complesse.

In RSA invece l'operazione di verifica della firma è molto più veloce di ECDSA. Anche se ECDSA lavora in 256 bit e RSA2048 lavora su 2048 bit. L'operazione da fare in RSA è la stessa della firma, un elevamento a potenza. Ma l'esponente è molto piccolo. In genere viene scelto il numero 65537 (2^16+1 == 0x10001) che sta su soli 17 bit, e ha solo due bit a 1. Quindi è vero che si lavora con numeri grandi, ma gli step da fare sono molto pochi. Quindi RSA potrebbe essere ancora una scelta vincente se nella mia applicazione devo fare solo una verifica di una firma digitale, e ho bisogno di farla in fretta.

Un altro vantaggio importante di ECDSA rispetto ad altri algoritmi di firma digitale, è quello di poter ricavare la chiave pubblica partendo dalla firma. Chiaramente dobbiamo sempre verificare la corretta appartenenza di questa chiave al legittimo proprietario. Calcolando la chiave pubblica dalla firma si possono ricavare due chiavi pubbliche valide possibili, se il co-fattore della curva è uno. Oppure un numero maggiore se il co-fattore è più alto. Una di queste chiavi ricavate sarà comunque uguale alla chiave pubblica "ufficiale", e questo potrebbe essere, per esempio, un metodo ulteriore per validare la correttezza firma. 

Si conclude qui la "panoramica per profani, ma non troppo" in tre parti, sulla crittografia a chiave pubblica e sull'utilizzo di curve ellittiche per operazioni di firma digitale. Spero l'abbiate trovata interessante. Commenti, suggerimenti sono ovviamente ben venuti.