1 Introduzione alle curve ellittiche. 2 I principali problemi sui quali si basano i sistemi...

1

Introduzione alle curve Introduzione alle curve ellitticheellittiche

2

I principali problemi sui quali si basano i sistemi I principali problemi sui quali si basano i sistemi crittografici moderni sono:crittografici moderni sono:

• Il problema della fattorizzazione di interi grandi Il problema della fattorizzazione di interi grandi ((Integer Factorization Problem – IFPInteger Factorization Problem – IFP ))

• Il problema del calcolo del logaritmo discreto su Il problema del calcolo del logaritmo discreto su campi finiti (campi finiti (Discrete Discrete Logarithm ProblemLogarithm Problem – DLP – DLP ))

• Il problema del calcolo del logaritmo discreto su Il problema del calcolo del logaritmo discreto su curve ellittiche (curve ellittiche (Elliptic Curve Discrete Elliptic Curve Discrete Logarithm Logarithm ProblemProblem – ECDLP – ECDLP ))

Riassumendo... Riassumendo...

3

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

Crittografia e curve ellitticheCrittografia e curve ellittiche

4

o Definizione 1Definizione 1Sia K un campo di caratteristica pSia K un campo di caratteristica p2,3 e sia 2,3 e sia xx33+ax+b, con a,b+ax+b, con a,bK, un polinomio cubico privo di K, un polinomio cubico privo di radici multiple; una radici multiple; una curva ellitticacurva ellittica su K è l’insieme su K è l’insieme costituito dalle coppie (x,y) con x,ycostituito dalle coppie (x,y) con x,yK che K che soddisfano l’equazionesoddisfano l’equazione

yy22=x=x33axaxbbpiù un punto isolato più un punto isolato OO, detto , detto punto all’infinitopunto all’infinito

Se p=2, l’equazione delle curve ellittiche può Se p=2, l’equazione delle curve ellittiche può assumere le due forme…assumere le due forme…

yy22cy=xcy=x33axaxbb curva curva supersingolaresupersingolare yy22xy=xxy=x33axaxbb curva curva non supersingolarenon supersingolare ……e per p=3e per p=3

yy22=x=x33axax22bxbxcc

Le curve ellittiche Le curve ellittiche

5

Curve ellittiche realiCurve ellittiche reali

6

Grafici delle curve ellittiche sul campo Grafici delle curve ellittiche sul campo di di equazione (a) yequazione (a) y22=x=x33x, (b) yx, (b) y22=x=x331, (c) y1, (c) y22=x=x335x5x66

Le curve ellitticheLe curve ellittiche

7

Curva ellittica su numeri reali Curva ellittica su numeri reali

8

Curva ellittica su numeri reali Curva ellittica su numeri reali

9

Curve ellittiche su ZCurve ellittiche su Zpp

10


11


12

o Definizione 2Definizione 2

Sia E una curva ellittica su Sia E una curva ellittica su , e siano P e Q punti di , e siano P e Q punti di E; si definiscono l’opposto di P e la somma PE; si definiscono l’opposto di P e la somma PQ, in Q, in base alle seguenti regolebase alle seguenti regole

• Se P coincide con il punto all’infinito Se P coincide con il punto all’infinito OO, allora , allora P=P=OO e P e PQ=Q, cioè Q=Q, cioè OO è l’elemento neutro per è l’elemento neutro per l’addizione di puntil’addizione di punti

• Altrimenti, l’opposto Altrimenti, l’opposto P di P è il punto con P di P è il punto con ascissa x uguale a quella di P ed ordinata ascissa x uguale a quella di P ed ordinata opposta, cioè opposta, cioè P=(x,P=(x,y)y)

• Se Q=Se Q=P, PP, PQ= Q= OO

Le curve ellitticheLe curve ellittiche

13

• 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, PQ=R.


14

• 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 PQ=2P=R


15

Come si calcolano le coordinate di PCome si calcolano le coordinate di PQ ?Q ?

• Se P=(xSe P=(x11,y,y11) e Q=(x) e Q=(x22,y,y22) con x) con x11xx22, sia , sia y=y=xx l’equazione della retta l’equazione della retta rr per P e Q per P e Q (che non è verticale); in questo caso, (che non è verticale); in questo caso, =(y=(y22yy11)/(x)/(x22xx11) e ) e =y=y11xx11; i punti di ; i punti di rr, , (x,(x,xx), giacciono anche sulla curva ), giacciono anche sulla curva ellittica E se e solo se soddisfano ellittica E se e solo se soddisfano l’uguaglianza xl’uguaglianza x33((xx))22axaxb=0b=0


16


17


18


19

Curve ellitticheCurve ellittiche

20


21


22


23


24


25


26

• Due soluzioni dell’equazione cubica sono Due soluzioni dell’equazione cubica sono note e corrispondono ai punti P e Q; note e corrispondono ai punti P e Q; poiché in un polinomio monico di grado poiché in un polinomio monico di grado n, la somma delle radici coincide con il n, la somma delle radici coincide con il coefficiente del termine di grado ncoefficiente del termine di grado n1, 1, 22=x=x11xx22xx33, da cui…, da cui…

xx33=[(y=[(y22yy11)/(x)/(x22xx11)])]22xx11xx22

ee

yy33= = yy11[(y[(y22yy11)/(x)/(x22xx11)](x)](x11xx33))


Un polinomio si dice monico se il coefficiente del termine di grado massimo è uguale ad 1.

27

• Se P=QSe P=Q, , =dy/dx==dy/dx=[[ff(x,y)/(x,y)/x]/[x]/[ff(x,y)/(x,y)/y]y]||PP, ,

con con ff(x,y)=y(x,y)=y22(x(x33axaxb), cioè b), cioè =(3x=(3x112 2 a)/2ya)/2y11, ,

da cui…da cui…

xx33=[(3x=[(3x112 2 a)/2ya)/2y11]]2 2 2x2x11

ee

yy33= = yy11[(3x[(3x1122 a)/2ya)/2y11](x](x11xx33))

I punti di una curva ellittica E formano I punti di una curva ellittica E formano un gruppo abeliano relativamente un gruppo abeliano relativamente all’operazione di sommaall’operazione di somma


28


29

Come in ogni gruppo abeliano, si userà la Come in ogni gruppo abeliano, si userà la notazione nP, per indicare l’operazione di notazione nP, per indicare l’operazione di somma del punto P con se stesso somma del punto P con se stesso effettuata n volte, se n>0, ovvero la effettuata n volte, se n>0, ovvero la somma di somma di P con se stesso effettuata P con se stesso effettuata nn volte, per n negativovolte, per n negativo

Per definizione, il punto all’infinito Per definizione, il punto all’infinito OO

rappresenta il “terzo punto di rappresenta il “terzo punto di intersezione” delle rette verticali con la intersezione” delle rette verticali con la curva Ecurva E


30

Sia K il campo finito ZSia K il campo finito Znn, costituito da n = p, costituito da n = pq q elementielementi

Sia E una curva ellittica definita su ZSia E una curva ellittica definita su Znn

E è composta da al più 2nE è composta da al più 2n1 punti, il punto 1 punti, il punto all’infinito all’infinito O O e 2n coppie (x,y)e 2n coppie (x,y)ZZnnZZnn, ovvero per , ovvero per ciascuna delle n possibili ascisse xciascuna delle n possibili ascisse xZZn n esistono al più esistono al più 2n ordinate y2n ordinate yZZnn che soddisfano l’equazione di E che soddisfano l’equazione di E

In realtà, vale il seguente…In realtà, vale il seguente…

o Teorema di HasseTeorema di Hasse

Sia N il numero di punti in ZSia N il numero di punti in Znn appartenenti ad una appartenenti ad una curva ellittica E, definita su Zcurva ellittica E, definita su Znn; vale la ; vale la disuguaglianzadisuguaglianza

|N |N (n (n1)|1)| 2 2nn

Curve ellittiche su campi finiti Curve ellittiche su campi finiti

31

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

rkj, 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 s1, corrispondente ad un elemento di Zn

Da plaintext a punti su E Da plaintext a punti su E 1 1

32

Pertanto, dato r, per ogni Pertanto, dato r, per ogni 1≤j<k, si ottiene un 1≤j<k, si ottiene un elemento xelemento xccZZnn, coincidente con , coincidente con rkrkjj

Per tale xPer tale xcc, si calcola , si calcola yy22=x=xcc33axaxccb, e si cerca di b, e si cerca di

estrarre la radice quadrata per calcolare il estrarre la radice quadrata per calcolare il corrispondente valore di ycorrispondente valore di ycc

• Se si riesce a calcolare un ySe si riesce a calcolare un ycc, tale che y, tale che ycc22==ff(x(xcc), si ), si

ottiene Pottiene Prr=(x=(xcc, y, ycc))

• Se invece tale ySe invece tale ycc non esiste, allora si incrementa j non esiste, allora si incrementa j di un’unità e si riprova a calcolare ydi un’unità e si riprova a calcolare ycc a partire a partire xxcc==rkrkjj11


33

Posto di riuscire a trovare un xPosto di riuscire a trovare un xcc t.c. esiste y t.c. esiste ycc

calcolato come sopra, per jcalcolato come sopra, per j≤k, r può essere ≤k, r può essere ricalcolato da ricalcolato da PPrr=(x=(xcc,y,ycc) come r=[(x) come r=[(x1)k)], con 1)k)], con xxccx (mod n) e xx (mod n) e x Z Znn

Poiché Poiché ff(x) è un quadrato in Z(x) è un quadrato in Znn approssimativamente nel 50% dei casi (tale approssimativamente nel 50% dei casi (tale probabilità vale esattamente N/2n, che è probabilità vale esattamente N/2n, che è molto vicino ad ½), la probabilità che il molto vicino ad ½), la probabilità che il metodo proposto fallisca nel calcolare il punto metodo proposto fallisca nel calcolare il punto PPrr la cui coordinata x la cui coordinata xcc è compresa fra rk è compresa fra rk1 e 1 e rkrkk è k è 2 2kk


34

I vantaggi dei crittosistemi costruiti attraverso curve I vantaggi dei crittosistemi costruiti attraverso curve ellittiche rispetto ai codici su campi finiti sono:ellittiche rispetto ai codici su campi finiti sono:

• Gran numero di gruppi abeliani (costituiti dai punti di Gran numero di gruppi abeliani (costituiti dai punti di una curva) che si possono costruire su uno stesso una curva) che si possono costruire su uno stesso campo finitocampo finito

• Non esistenza di algoritmi subesponenziali per risolvere Non esistenza di algoritmi subesponenziali per risolvere il problema del logaritmo discreto su curve non il problema del logaritmo discreto su curve non supersingolarisupersingolari

• Chiavi più corte per garantire lo stesso grado di Chiavi più corte per garantire lo stesso grado di sicurezzasicurezza

Crittosistemi su curve ellittiche Crittosistemi su curve ellittiche

35

Le curve ellittiche permettono di formulare un Le curve ellittiche permettono di formulare un problema analogo a quello del logaritmo discreto problema analogo a quello del logaritmo discreto su un campo finito (su un campo finito (DLPDLP, , Discrete Logarithm Discrete Logarithm ProblemProblem))

ProblemaProblema

Siano dati una curva ellittica E su ZSiano dati una curva ellittica E su Znn ed un punto ed un punto BBE; il problema del logaritmo discreto su E in E; il problema del logaritmo discreto su E in base B (base B (ECDLPECDLP, , Elliptic Curve Discrete Logarithm Elliptic Curve Discrete Logarithm ProblemProblem) è) è

dato dato PPEE trovare, se esiste, trovare, se esiste, xxZZ tale che tale che xB=PxB=P

Crittosistemi su curve ellittiche Crittosistemi su curve ellittiche

36

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)

Crittosistemi su curve ellittiche Crittosistemi su curve ellittiche 3 3

37

Supponiamo che Alice e Bob vogliano accordarsi su Supponiamo che Alice e Bob vogliano accordarsi su una chiave segreta da utilizzare per un crittosistema una chiave segreta da utilizzare per un crittosistema classicoclassico

1)1) Alice e Bob devono fissare un campo finito ZAlice e Bob devono fissare un campo finito Znn, dove n=p, dove n=prr, , ed una curva ellittica E definita su questo campoed una curva ellittica E definita su questo campo

2)2) Il passo successivo consiste nel rendere pubblico un punto Il passo successivo consiste nel rendere pubblico un punto BBE, detto E, detto basebase (che avrà un ruolo analogo al generatore g (che avrà un ruolo analogo al generatore g nel caso del Diffienel caso del DiffieHellman classico); non è necessario che Hellman classico); non è necessario che B sia un generatore di E, ma si suppone che abbia ordine o B sia un generatore di E, ma si suppone che abbia ordine o “sufficientemente” grande“sufficientemente” grande

3)3) Alice sceglie un numero a costituito dallo stesso numero di Alice sceglie un numero a costituito dallo stesso numero di cifre (o), che terrà segreto, ed invia pubblicamente a Bob la cifre (o), che terrà segreto, ed invia pubblicamente a Bob la quantità aBquantità aB

4)4) Allo stesso modo, Bob sceglie b dello stesso ordine di Allo stesso modo, Bob sceglie b dello stesso ordine di grandezza ed invia ad Alice la quantità bBgrandezza ed invia ad Alice la quantità bB

5)5) Entrambi possono calcolare abB che servirà da chiave Entrambi possono calcolare abB che servirà da chiave segretasegreta

DiffieDiffieHellman su curve ellittiche Hellman su curve ellittiche

38

Sia data la curva ellittica ySia data la curva ellittica y22=x=x33xx11 e il suo punto e il suo punto B(1;1)B(1;1)

Alice sceglie a=2, calcola aB e lo pubblica Alice sceglie a=2, calcola aB e lo pubblica aB=(2;aB=(2;3)3)

Bob sceglie b=3, calcola bB e lo pubblica Bob sceglie b=3, calcola bB e lo pubblica bB= bB= (13;47)(13;47)

La chiave segreta è abB, cioè il punto di La chiave segreta è abB, cioè il punto di coordinate 7082/2209 e 615609/103823coordinate 7082/2209 e 615609/103823

Esempio Esempio

39

Viene fissata una curva ellittica E su un campo ZViene fissata una curva ellittica E su un campo Znn ed ed un punto Bun punto BEE

Ogni utente sceglie un intero casuale a, che Ogni utente sceglie un intero casuale a, che rappresenterà la sua chiave segreta, e pubblica aBrappresenterà la sua chiave segreta, e pubblica aB

Se Alice vuole spedire a Bob il messaggio MSe Alice vuole spedire a Bob il messaggio ME, si E, si attua il protocollo seguenteattua il protocollo seguente1)1) Alice sceglie un intero casuale k ed invia a Bob la Alice sceglie un intero casuale k ed invia a Bob la

coppia (kB, Mcoppia (kB, Mk(bB)), dove (bB) e la chiave pubblica k(bB)), dove (bB) e la chiave pubblica di Bobdi Bob

2)2) Bob può decodificare il messaggio originale Bob può decodificare il messaggio originale calcolandocalcolando

M=MM=Mk(bB)k(bB)b(kB)b(kB)

utilizzando la propria chiave segreta b utilizzando la propria chiave segreta b È evidente che un intruso che sapesse risolvere il È evidente che un intruso che sapesse risolvere il

problema ECDLP potrebbe ricavare b e da questo problema ECDLP potrebbe ricavare b e da questo risalire al paintextrisalire al paintext

ElGamal su curve ellittiche ElGamal su curve ellittiche

40

Il programma Il programma PGPPGP ( (Pretty Good PrivacyPretty Good Privacy, , Philip R. Philip R. Zimmerman, 1991) è a chiave pubblica e utilizza Zimmerman, 1991) è a chiave pubblica e utilizza il seguente protocollo di comunicazione:il seguente protocollo di comunicazione:• Un utente invia la propria chiave pubblica ad un Un utente invia la propria chiave pubblica ad un

corrispondente; l’eventuale intercettazione è corrispondente; l’eventuale intercettazione è irrilevante; chiunque vi abbia accesso, infatti, può irrilevante; chiunque vi abbia accesso, infatti, può spedire posta cifrata al proprietario della chiave spedire posta cifrata al proprietario della chiave privata, ma una volta effettuata la cifratura di un privata, ma una volta effettuata la cifratura di un messaggio, nemmeno l’autore è in grado di messaggio, nemmeno l’autore è in grado di rileggerlorileggerlo

• Il corrispondente codifica il messaggio con la chiave Il corrispondente codifica il messaggio con la chiave pubblica ricevuta e lo invia al proprietario della pubblica ricevuta e lo invia al proprietario della chiave; se anche il messaggio venisse intercettato, chiave; se anche il messaggio venisse intercettato, solo il legittimo destinatario, in possesso della solo il legittimo destinatario, in possesso della chiave privata, è in grado di decifrarlochiave privata, è in grado di decifrarlo

““What one man can invent another can discover.” What one man can invent another can discover.” [Sherlock Holmes] [Sherlock Holmes]

The Adventure of the Solitary Cyclist, Sir Arthur Conan DoyleThe Adventure of the Solitary Cyclist, Sir Arthur Conan Doyle

PGP PGP 1 1

41

Chiave di sessioneChiave di sessione• Poiché la cifratura asimmetrica è molto più lenta Poiché la cifratura asimmetrica è molto più lenta

della crittografia simmetrica, la tecnologia PGP della crittografia simmetrica, la tecnologia PGP utilizza un approccio ibrido al problema della utilizza un approccio ibrido al problema della sicurezza:sicurezza: Il messaggio viene inizialmente cifrato con un Il messaggio viene inizialmente cifrato con un

algoritmo di cifratura a chiave segreta (algoritmo di cifratura a chiave segreta (IDEAIDEA o o CASTCAST): viene automaticamente creata una chiave ): viene automaticamente creata una chiave casuale temporanea, detta casuale temporanea, detta chiave di sessionechiave di sessione, che , che viene utilizzata per cifrare soltanto quel documentoviene utilizzata per cifrare soltanto quel documento

La chiave di sessione viene a sua volta cifrata La chiave di sessione viene a sua volta cifrata mediante la chiave pubblica del ricevente (RSA o mediante la chiave pubblica del ricevente (RSA o DiffieDiffieHellman)Hellman)

• Quando il messaggio giunge a destinazione, il Quando il messaggio giunge a destinazione, il ricevente utilizza la propria chiave privata per ricevente utilizza la propria chiave privata per decifrare la chiave di sessione, che poi impiega decifrare la chiave di sessione, che poi impiega per decifrare il messaggioper decifrare il messaggio

PGP PGP 2 2

42

Firma digitaleFirma digitale• Per essere certo della provenienza di un Per essere certo della provenienza di un

messaggio, il destinatario può richiedere al messaggio, il destinatario può richiedere al mittente di apporre al messaggio la propria firma mittente di apporre al messaggio la propria firma digitale, utilizzando la propria chiave privata: digitale, utilizzando la propria chiave privata: viene così creato un file cifrato che non può viene così creato un file cifrato che non può essere duplicato in alcun modoessere duplicato in alcun modo

• Chiunque sia in possesso della chiave pubblica del Chiunque sia in possesso della chiave pubblica del mittente può leggere la firma ed identificare la mittente può leggere la firma ed identificare la provenienza del messaggioprovenienza del messaggio

• Un documento, cui sia stata apposta una firma Un documento, cui sia stata apposta una firma digitale, non può essere falsificato, né digitale, non può essere falsificato, né disconosciutodisconosciuto

• La possibilità di autenticare la provenienza e la La possibilità di autenticare la provenienza e la sicurezza dei messaggi digitali hanno aperto la sicurezza dei messaggi digitali hanno aperto la strada all’estrada all’ecommerce: la cifratura e le firme commerce: la cifratura e le firme digitali, infatti, hanno reso “sicuri” i pagamenti via digitali, infatti, hanno reso “sicuri” i pagamenti via Internet tramite carta di creditoInternet tramite carta di credito

PGP PGP 3 3

1 Introduzione alle curve ellittiche. 2 I principali problemi sui quali si basano i sistemi...

Documents

Transcript of 1 Introduzione alle curve ellittiche. 2 I principali problemi sui quali si basano i sistemi...