Introduzione alle curve ellittiche
1
Riassumendo...
 I principali problemi sui quali si basano i sistemi
crittografici moderni sono:
• Il problema della fattorizzazione di interi grandi (Integer
Factorization Problem – IFP )
• Il problema del calcolo del logaritmo discreto su campi
finiti (Discrete Logarithm Problem – DLP )
• Il problema del calcolo del logaritmo discreto su curve
ellittiche (Elliptic Curve Discrete Logarithm Problem –
ECDLP )
2
Crittografia e curve ellittiche
 Negli ultimi tempi l’interesse degli appassionati di teoria dei
numeri verso le curve ellittiche è andato crescendo, forse a
causa del loro impiego per la famosa dimostrazione
dell’ultimo teorema di Fermat da parte di Andrew Wiles
 I cifrari basati sulle curve ellittiche furono proposti in maniera
indipendente da Victor Miller e Neal Koblitz verso la metà
degli anni ottanta
 Le curve ellittiche possono interpretarsi come una “versione
analogica” del concetto di gruppo moltiplicativo in un campo
finito
 Per comprendere come questa particolare classe di cubiche
possa essere impiegata per costruire una categoria di metodi
crittografici, attualmente ritenuti i più sicuri, occorre
introdurne le proprietà matematiche fondamentali
3
Le curve ellittiche
o Definizione 1
Sia K un campo di caratteristica p2,3 e sia x3+ax+b, con
a,bK, un polinomio cubico privo di radici multiple; una
curva ellittica su K è l’insieme costituito dalle coppie (x,y)
con x,yK che soddisfano l’equazione
y2=x3axb
più un punto isolato O, detto punto all’infinito
 Se p=2, l’equazione delle curve ellittiche può assumere le
due forme…
y2cy=x3axb
curva supersingolare
y2xy=x3axb
curva non supersingolare
 …e per p=3
y2=x3ax2bxc
4
Curve ellittiche reali
5
Le curve ellittiche
Grafici delle curve ellittiche sul campo  di
equazione (a) y2=x3x, (b) y2=x31, (c) y2=x35x6
6
Curva ellittica su numeri reali
7
Curva ellittica su numeri reali
8
Curve ellittiche su Zp
9
Curve ellittiche su Zp
10
Curve ellittiche su Zp
11
Le curve ellittiche
o Definizione 2
Sia E una curva ellittica su , e siano P e Q punti di E; si
definiscono l’opposto di P e la somma PQ, in base alle
seguenti regole
• Se P coincide con il punto all’infinito O, allora P=O e
PQ=Q, cioè O è l’elemento neutro per l’addizione di
punti
• Altrimenti, l’opposto P di P è il punto con ascissa x
uguale a quella di P ed ordinata opposta, cioè
P=(x,y)
• Se Q=P, PQ= O
12
Le curve ellittiche
• Se P e Q hanno ascisse distinte, allora r= PQ interseca
la curva E esattamente in un ulteriore punto R (se r non
è tangente ad E in P, nel qual caso R=P, o in Q, così che
R=Q); se R è distinto da P e Q, PQ=R.
13
Le curve ellittiche
• Se P=Q, sia t la tangente alla curva in P e sia R (l’unico)
ulteriore punto di intersezione di t con la curva, allora
PQ=2P=R
14
Le curve ellittiche
Come si calcolano le coordinate di PQ ?
• Se P=(x1,y1) e Q=(x2,y2) con x1x2, sia y=x
l’equazione della retta r per P e Q (che non è
verticale); in questo caso, =(y2y1)/(x2x1) e
=y1x1; i punti di r, (x,x), giacciono anche
sulla curva ellittica E se e solo se soddisfano
l’uguaglianza x3(x)2axb=0
15
Curve ellittiche su Zp
16
Curve ellittiche su Zp
17
Curve ellittiche su Zp
18
Curve ellittiche
19
Curve ellittiche
20
Curve ellittiche
21
Curve ellittiche
22
Curve ellittiche
23
Curve ellittiche
24
Curve ellittiche
25
Le curve ellittiche
• Due soluzioni dell’equazione cubica sono note
e corrispondono ai punti P e Q; poiché in un
polinomio monico di grado n, la somma delle
radici coincide con il coefficiente del termine di
grado n1, 2=x1x2x3, da cui…
x3=[(y2y1)/(x2x1)]2x1x2
e
y3= y1[(y2y1)/(x2x1)](x1x3)
Un polinomio si dice monico se il coefficiente del termine di grado
massimo è uguale ad 1.
26
Le curve ellittiche
• Se P=Q, =dy/dx=[f(x,y)/x]/[f(x,y)/y]|P,
con f(x,y)=y2(x3axb), cioè =(3x12  a)/2y1,
da cui…
x3=[(3x12  a)/2y1]2 2x1
e
y3= y1[(3x12  a)/2y1](x1x3)
I punti di una curva ellittica E formano
un gruppo abeliano
all’operazione di somma
relativamente
27
Le curve ellittiche
28
Le curve ellittiche
 Come in ogni gruppo abeliano, si userà la
notazione nP, per indicare l’operazione di
somma del punto P con se stesso effettuata n
volte, se n>0, ovvero la somma di P con se
stesso effettuata n volte, per n negativo
 Per
definizione, il punto all’infinito O
rappresenta il “terzo punto di intersezione”
delle rette verticali con la curva E
29
Curve ellittiche su campi finiti
 Sia K il campo finito Zn, costituito da n = pq elementi
 Sia E una curva ellittica definita su Zn
 E è composta da al più 2n1 punti, il punto all’infinito
O e 2n coppie (x,y)ZnZn, ovvero per ciascuna delle
n possibili ascisse xZn esistono al più 2n ordinate
yZn che soddisfano l’equazione di E
In realtà, vale il seguente…
o Teorema di Hasse
Sia N il numero di punti in Zn appartenenti ad una
curva ellittica E, definita su Zn; vale la disuguaglianza
|N  (n1)| 2n
30
Da plaintext a punti su E  1
 Supponiamo di codificare il plaintext x come un intero r
 Sia E una curva ellittica definita su Zn, con n=pq, numero
intero “grande” e dispari
 Un
metodo probabilistico (non esistono algoritmi
deterministici per risolvere questo problema!) per codificare
r mediante Pr può essere schematizzato come segue:
• Si sceglie k (≤50 è sufficiente); sia 0≤r<R, e n>Rk
• Gli interi compresi fra 1 ed Rk possono essere scritti nella forma rkj,
con 1≤j<k  si stabilisce una corrispondenza biunivoca fra detti
interi ed un sottoinsieme degli elementi di Zn
• Per esempio, ciascun numero 1≤i<Rk può essere scritto come un
intero ad s cifre in base p, ciascuna cifra del quale rappresenta il
relativo coefficiente di un polinomio di grado s1, corrispondente ad
un elemento di Zn
31
Da plaintext a punti su E  2
 Pertanto, dato r, per ogni 1≤j<k, si ottiene un elemento
xcZn, coincidente con rkj
 Per tale xc, si calcola y2=xc3axcb, e si cerca di estrarre la
radice quadrata per calcolare il corrispondente valore di yc
• Se si riesce a calcolare un yc, tale che yc2=f(xc), si
ottiene Pr=(xc, yc)
• Se invece tale yc non esiste, allora si incrementa j di
un’unità e si riprova a calcolare yc a partire xc=rkj1
32
Da plaintext a punti su E  3
 Posto di riuscire a trovare un xc t.c. esiste yc
calcolato come sopra, per j≤k, r può essere
ricalcolato da Pr=(xc,yc) come r=[(x1)k)], con
xcx (mod n) e x Zn
 Poiché
f(x)
è
un
quadrato
in
Zn
approssimativamente nel 50% dei casi (tale
probabilità vale esattamente N/2n, che è molto
vicino ad ½), la probabilità che il metodo proposto
fallisca nel calcolare il punto Pr la cui coordinata xc
è compresa fra rk1 e rkk è  2k
33
Crittosistemi su curve ellittiche
 I vantaggi dei crittosistemi costruiti attraverso curve ellittiche
rispetto ai codici su campi finiti sono:
• Gran numero di gruppi abeliani (costituiti dai punti di una
curva) che si possono costruire su uno stesso campo
finito
• Non esistenza di algoritmi subesponenziali per risolvere il
problema del logaritmo discreto su curve non
supersingolari
• Chiavi più corte per garantire lo stesso grado di sicurezza
34
Crittosistemi su curve ellittiche
 Le
curve ellittiche permettono di formulare un
problema analogo a quello del logaritmo discreto su
un campo finito (DLP, Discrete Logarithm Problem)
 Problema
Siano dati una curva ellittica E su Zn ed un punto BE;
il problema del logaritmo discreto su E in base B
(ECDLP, Elliptic Curve Discrete Logarithm Problem) è
dato PE trovare, se esiste, xZ tale che xB=P
35
Crittosistemi su curve ellittiche  3
 Osservazioni
• Per i campi finiti esiste un algoritmo, detto index calculus, che permette
di calcolare il logaritmo discreto (ovvero di risolvere il DLP) con
complessità subesponenziale
• Tale algoritmo si fonda sulla definizione delle operazioni di somma e
prodotto, e quindi non è applicabile sulle curve ellittiche che possiedono
esclusivamente una struttura additiva
• La sicurezza dei crittosistemi su curve ellittiche risiede nell’attuale non
conoscenza di algoritmi subesponenziali per risolvere l’ECDLP
• Esistono tuttavia algoritmi subesponenziali per particolari classi di curve
ellittiche (in particolare per le curve supersingolari)
36
DiffieHellman su curve ellittiche
 Supponiamo che Alice e Bob vogliano accordarsi su una
chiave segreta da utilizzare per un crittosistema classico
1)
2)
3)
4)
5)
Alice e Bob devono fissare un campo finito Zn, dove n=pr, ed
una curva ellittica E definita su questo campo
Il passo successivo consiste nel rendere pubblico un punto
BE, detto base (che avrà un ruolo analogo al generatore g nel
caso del DiffieHellman classico); non è necessario che B sia
un generatore di E, ma si suppone che abbia ordine o
“sufficientemente” grande
Alice sceglie un numero a costituito dallo stesso numero di cifre
(o), che terrà segreto, ed invia pubblicamente a Bob la
quantità aB
Allo stesso modo, Bob sceglie b dello stesso ordine di
grandezza ed invia ad Alice la quantità bB
Entrambi possono calcolare abB che servirà da chiave segreta
37
Esempio
 Sia data la curva ellittica y2=x3x1 e il suo punto B(1;1)
 Alice sceglie a=2, calcola aB e lo pubblica  aB=(2;3)
 Bob sceglie b=3, calcola bB e lo pubblica  bB= (13;47)
 La chiave segreta è abB, cioè il punto di coordinate
7082/2209 e 615609/103823
38
ElGamal su curve ellittiche
 Viene fissata una curva ellittica E su un campo Zn ed un
punto BE
 Ogni utente sceglie un intero casuale a, che
rappresenterà la sua chiave segreta, e pubblica aB
 Se Alice vuole spedire a Bob il messaggio ME, si attua
il protocollo seguente
1) Alice sceglie un intero casuale k ed invia a Bob la coppia
(kB, Mk(bB)), dove (bB) e la chiave pubblica di Bob
2) Bob può decodificare il messaggio originale calcolando
M=Mk(bB)b(kB)
utilizzando la propria chiave segreta b
 È evidente che un intruso che sapesse risolvere il
problema ECDLP potrebbe ricavare b e da questo risalire
al paintext
39
PGP  1
“What one man can invent another can discover.” [Sherlock Holmes]
The Adventure of the Solitary Cyclist, Sir Arthur Conan Doyle
 Il programma PGP (Pretty Good Privacy, Philip R.
Zimmerman, 1991) è a chiave pubblica e utilizza il
seguente protocollo di comunicazione:
• Un
utente invia la propria chiave pubblica ad un
corrispondente; l’eventuale intercettazione è irrilevante;
chiunque vi abbia accesso, infatti, può spedire posta cifrata
al proprietario della chiave privata, ma una volta effettuata
la cifratura di un messaggio, nemmeno l’autore è in grado
di rileggerlo
• Il corrispondente codifica il messaggio con la chiave
pubblica ricevuta e lo invia al proprietario della chiave; se
anche il messaggio venisse intercettato, solo il legittimo
destinatario, in possesso della chiave privata, è in grado di
decifrarlo
40
PGP  2
 Chiave di sessione
• Poiché la cifratura asimmetrica è molto più lenta della
crittografia simmetrica, la tecnologia PGP utilizza un
approccio ibrido al problema della sicurezza:
 Il messaggio viene inizialmente cifrato con un algoritmo
di cifratura a chiave segreta (IDEA o CAST): viene
automaticamente
creata
una
chiave
casuale
temporanea, detta chiave di sessione, che viene
utilizzata per cifrare soltanto quel documento
 La chiave di sessione viene a sua volta cifrata mediante
la chiave pubblica del ricevente (RSA o DiffieHellman)
• Quando
il messaggio giunge a destinazione, il
ricevente utilizza la propria chiave privata per
decifrare la chiave di sessione, che poi impiega per
decifrare il messaggio
41
PGP  3
 Firma digitale
• Per essere certo della provenienza di un messaggio, il
destinatario può richiedere al mittente di apporre al
messaggio la propria firma digitale, utilizzando la
propria chiave privata: viene così creato un file cifrato
che non può essere duplicato in alcun modo
• Chiunque sia in possesso della chiave pubblica del
mittente può leggere la firma ed identificare la
provenienza del messaggio
• Un documento, cui sia stata apposta una firma
digitale, non può essere falsificato, né disconosciuto
• La possibilità di autenticare la provenienza e la
sicurezza dei messaggi digitali hanno aperto la strada
all’ecommerce: la cifratura e le firme digitali, infatti,
hanno reso “sicuri” i pagamenti via Internet tramite
carta di credito
42