Crittografia in Informatica - Università degli Studi di ...leporati/crittografia/Curve...

Crittosistemi basati sulle Curve

Ellittiche

Dipartimento di Inform

atica, Sistemistica e Comunicazione

Universitàdegli Studi di Milano –Bicocca

Alberto Leporati

e-mail: [email protected]

[email protected]

Crittografia

—Corso di Laurea Specialistica —

—in Inform

atica —

Alberto Leporati

Corso di Crittografia

2

�vantaggio:

�sembrano offrire lo stesso

livello di sicurezzadei

crittosistemi a chiave pubblica

tradizionali

�le chiavi sono molto piùcorte

Crittosistemi basati su Curve E

llittiche

5120

320

2048

210

1024

160

RSA

ECC

�l’uso di chiavi piùcorte comporta:

�maggiore velocità

per cifratura/decifratura

�memorizzazione efficiente

�minore utilizzo della larghezza di banda

Alberto Leporati


3

�esempio: velocità

di esecuzione su una sm

art card

a 8 bit, senza coprocessore crittografico:


llittiche

1654.0 ms

7.3 ms

Scambio chiavi

(Diffie-Hellman)

12.7 ms

10.7 ms

Verifica

228.4 ms

3.0 ms

Firma

4708.3 ms

3.8 ms

Generazione chiavi

RSA 1024 bit

ECC 163 bit

Funzione

Alberto Leporati


4

�si tenga presente che:

�firm

a e verifica sono state realizzate decifrando e

cifrando con un crittosistema a chiave pubblica

�i tempi di esecuzione variano molto a secondo della curva

e degli esponenti di RSA usati

�la Certicom

(http://www.certicom

.com

/) afferm

a che le loro soluzioni basate su ECC non

necessitano di sm

art card con coprocessori

crittografici

Øsi ha una riduzione dei costi di circa

3 –5 dollari per carta


llittiche

Alberto Leporati


5

�siano a, b œ

�due costanti tali che

4a3+ 27b2∫0

�una curva ellitticanon singolareèl’insieme

Edi soluzioni(x, y) œ

�ä�dell’equazione:

y2= x3+ ax + b

insiem

e a un punto speciale O, detto punto

all’infinito

�la quantità4a3+ 27b2si chiama discrimi-

nantedella curva

Curve E

llittiche su � ��

Alberto Leporati


6

�ad esempio, se a = -4

e b = 0.67abbiamo…

Curve E


Alberto Leporati


7

�la condizione 4a3+ 27b2∫0ènecessaria e

sufficienteaffinchéx3+ ax + b = 0abbia tre

radici distinte(reali o complesse)

�se 4a3+ 27b2= 0, la curva viene detta singolare

�equazioni cubiche in xe ypiùgenerali possono

essere tutte ridotte alla forma norm

ale di

Weierstrass:

y2= x3+ ax + b

tram

ite trasform

azioni razionali, cioè

del tipo:

DCx

BAx

x++

→

Curve E


Alberto Leporati


8

�mentre le equazioni quadratichesono ben

comprese dai matem

atici, quelle cubichesono

ancora oggetto di studio

�le curve ellittiche sono un ponte

tra Algebra

e

Geom

etria, gettato nel XIX

secolo da Abel,

Gauss, Jacobi e Legendre

�una curva ellittica nonèun’ellisse !

�il nom

e corretto sarebbe varietà

Abeliana di

dimensione uno

�il term

ine “ellittiche”

deriva dal fatto che gli

integrali ellitticisono molto importanti nello

studio delle curve ellittiche

Curve E


Alberto Leporati


9

�data una curva Esu �, vogliamo calcolare

P + Q, con P = (x 1, y 1 ) e Q = (x 2, y 2 )

�consideriamo tre casi:

�x 1

∫x 2

�x 1= x2e y 1= -y 2

�x 1= x2e y 1= y2 (i due punti coincidono)

�otterrem

o che (E, +)èun gruppo Abeliano,

nel quale Oèl’identità:

"P œE P + O = O + P = P

Somma tra due punti

Alberto Leporati


10

Somma tra due punti: primo caso

se x1∫x 2,

�sia Lla retta passante per Pe per Q

�Linterseca Ein un terzo punto, che chiamiamo R’

�sia Ril simmetrico di R’rispetto all’asse delle x

�poniam

o P + Q = R

12

12

13

13

21

2

3

)(

xx

yy

yx

xy

xx

x

−−=

−−

=

−−

=

λ

λλ

�in pratica, le coordinate di

R = (x 3, y 3 ) sono:

Alberto Leporati


11

Somma tra due punti: primo caso

Alberto Leporati


12

�se x 1= x2e y1= -y 2, allora P + Q = O

�infatti, poniamo:

(x, y) + (x, -y) = O

per tutti gli (x, y) œE

�questo significa che (x, -y)èl’inverso

di

(x, y)rispetto alla som

matra due punti

Somma tra due punti: secondo caso

Alberto Leporati


13

Somma tra due punti: secondo caso

Alberto Leporati


14

�nel terzo caso, stiamo sommando Pa se stesso

�possiamo assumere y1∫0, altrimenti ricadremmo

nel secondo caso

�il terzo caso viene trattato come il primo, dove L

èla retta tangentea Enel punto P

Somma tra due punti: terzo caso

1

2 1

13

13

21

2

3

2

3

)(

y

ax

yx

xy

xx

x

+=

−−

=

−−

=

λ

λλ

�in pratica, le coordinate di

R = (x 3, y 3 ) sono:

Alberto Leporati


15

Somma tra due punti: terzo caso

Alberto Leporati


16

�in crittografia non si usano le curve su �, ma

quelle su GF(p)e GF(2

m)

�il loro uso èstato proposto nel 1985 da Victor

Miller e da Neal Koblitz

�non si inventano nuovi crittosistem

i, ma si

riadattano

quelli giàesistenti

�non sembra esserci differenza tra la sicurezza

offerta dai cam

pi GF(p)e GF(2

m)

�da un punto di vista implementativo, le

realizzazioni su GF(2

m)sono piùvelocie più

economiche

Curve ellittiche in Crittografia

Alberto Leporati


17

�sia p > 3un num

ero primo

�le curve su GF(p)sono definite esattam

ente

come quelle su �; le operazioni su �

vengono

sostituite con le analoghe operazioni su GF(p)

�la curva èform

ata da tutti i punti (x, y)che

soddisfano la congruenza:

y2ªx3+ ax + b modp

piùil puntoO = (0,0)

Curve ellittiche su GF(p)

Alberto Leporati


18

Curve ellittiche su GF(p): esempio

Alberto Leporati


19

�se x3+ ax + b = 0 non contiene radici

multiplein GF(p), ovvero se:

4a3+ 27b2T0 modp

allora la curva ellittica può essere usata

per definire un gruppo Abeliano (E,+

)finito

�la som

masu E èdefinita usando le stesse

form

ulesulle coordinate che risultano per

le curve definite su �

Somma tra due punti

Alberto Leporati


20

�siano a, b œGF(2

m), con b ∫0

�poichéGF(2

m)ha caratteristica 2, l’equazione

della curva èleggerm

ente diversa:

y2 + xy =x3+ ax + b

�le formule per la som

mavanno aggiustate

di

conseguenza

�l’opposto

di un punto (x, y)èil punto (x, x + y),

dove x + yèlo xor

bit a bit tra xe y

Curve ellittiche su GF(2m)

Alberto Leporati


21

�sia Euna curva ellittica, definita su GF(p)

o su GF(2

m), e sia B

un punto su E

�ECDLP(Elliptic Curve Discrete Logarithm

Problem) èil seguente problema:

dato un punto P œE, trovare un

intero k(se esiste) tale che kB = P

�kèdetto il logaritm

o(discreto) di Pin

base B

Logaritm

i discreti

Alberto Leporati


22

�una volta definito ECDLP, si possono realizzare:

�lo scambio di chiavi di Diffie-Hellman

�il crittosistema di El Gam

al

�sui gruppi prodotti dalle curve ellittiche, gli

algoritm

i Rho di Pollard, Pohlig-Hellm

ane Index

Calculusnon sono applicabili

�tuttavia, esistono anche curve “deboli”dal punto

di vista crittografico

�ECDLP su curve supersingolaripuò essere ridotto al

logaritm

o discreto su un campo “piccolo”

[ Menezes, Okamoto, Vanstone-1993]

Crittosistemi (E

CC)

Alberto Leporati


23

�siano pe qdue num

eri primi(grandi), che devono

rimanere segreti

�sia n = pÿq

�si scelgono a caso

due interi ae btali che:

E: y2= x3+ ax + b

definisce una curva ellitticasia su GF(p)che su

GF(q)

�per cifrareil testo in chiaro P œE, si calcola

eP m

odn, dove eèla chiave pubblica

di cifratura

�per decifrareoccorre conoscere il numero di

puntisu E, sia modulo pche modulo q

RSA basato sulle curve ellittiche

Alberto Leporati


24

�esistono diverse proposte

di analoghi di RSA

�esistono test probabilisticidi primalitànei quali la

risposta èsempre esatta (solo il tempo di

esecuzione ècasuale)

�le curve ellittiche hanno ispirato il metodo ECMdi

fattorizzazionedi Lenstra, e un algoritm

o (di

Kaliski) per generare bit pseudocasuali

�nel 1989 Koblitz ha proposto di usare anche le

curve iperellittiche, ma da allora sono state fatte

poche ricerchesulla loro sicurezza

Altri strumenti

Alberto Leporati


25

�sia pprimooppure una potenza di 2

�sia Euna curva ellittica su GF(p)

�sia Aun punto su Eavente ordine qprimo, tale

che ECDLP sia intrattabile in ‚AÚ

�lo spazio dei messaggièP = {0,1}*

�lo spazio delle firmeèA = �

q*ä�

q*

�lo spazio delle chiavi èK = {(p, q, E, A, k, B) :

B = kA}, con 0 §k §q-1

�la chiave pubblica

(per verificare) è(p, q, E, A, B)

�la chiave privata

(per firm

are) èk

Elliptic curve D

SA

Alberto Leporati


26

�per firm

arex œPcon la chiave k, si sceglie a caso

r, con 1 §r §q-1, e si calcola:

sigk(x, r) = (t, s)

dove:

rA = (u, v)

t = u modq

s = (SHA-1(x) + kt)r-1 modq

�se viene t = 0oppure s = 0, occorre scegliere un

altro valore

di r

Elliptic curve D

SA

Alberto Leporati


27

�per verificare

che (t, s) œ�

q*ä�

q*èuna firm

a per x œ{0,1}*, si calcola:

w = s-1

modq

i = w ÿSHA-1(x) m

odq

j = wt m

odq

(u, v) = iA + jB

e si accettala firma come valida(cioèver k(x,(t,s))

= true) se e solo se:

u modq = t

Elliptic curve D

SA

Alberto Leporati


28

�infatti, i = s-1ÿSHA-1(x) m

odq, e j = s-1t

modq, da cui:

iA + jB = iA + jkA = (i + jk)A

= s-1(SHA-1(x) + tk)A

�poichés-1= r(SHA-1(x) + tk)-1

modq, vale:

iA + j = rA = (u, v)

e quindi, in particolare, u ªt m

odq

Elliptic curve D

SA

Crittografia in Informatica - Università degli Studi di ...leporati/crittografia/Curve...

Documents

Transcript of Crittografia in Informatica - Università degli Studi di ...leporati/crittografia/Curve...