Crittosistemi a Chiave Pubblicaleporati/crittografia... · 2009. 2. 26. · logaritmo discreto...

Crittosistemi a Chiave Pub

blic

a

Dip

artim

ento

di In

form

atic

a, S

iste

mistica

e C

om

unic

azio

ne

Univ

ersità

deg

li S

tudi di M

ilan

o –

Bic

occ

a

Alberto Leporati

e-m

ail: [email protected]

[email protected]

Crittografia

—Corso di Laurea Specialistica —

—in Informatica —

Alberto Leporati

Corso di Crittografia

2

�prob

lemacon i crittosistem

i simmetrici:

Alic

e e Bob

devono cono

scere la stessa

chiave

segreta

k

�ci vuole un canale privato

(cioèsicuro) pe

r comunicarsi la ch

iave

�questo non sem

preèpo

ssibile

�se esiste un canale sicuro, pe

rchéno

n utilizza

rlo pe

r comunicare il testo in ch

iaro?

�la crittog

rafia a ch

iave pub

blic

arisolve il

prob

lema alla rad

ice: non è

nece

ssario

nessun

canale privato

Crittosistemi a chiave pubblica

Alberto Leporati


3

�idea

:le chiavi usate per cifrare e per

dec

ifrare sono diverse

�pe

r questo m

otivo, a volte li si chiama anch

e crittosistem

i asim

metrici

�og

nuno crea una prop

riacopp

ia di ch

iavi,

pubblic

a e privata

�la chiave per cifrare

vien

e resa pub

blic

a,

quella per dec

ifrare

rimane segreta

�quindi, chiunque

èin grado di cifrare, m

a solo il destinatarioèin grado di dec

ifrare


Alberto Leporati


4

Consideriamo il seg

uente prob

lema: Alic

e vuole

sped

ire a Bob

un messagg

io m

(su un fog

lio di carta)

Prim

a soluzione:

�Bob

invia ad Alice

una cassetta di sicurezz

a con

un lucch

etto ape

rto, di cui solo lui ha la chiave

�Alice

mette il foglio nella cassetta, chiude il

lucchetto e spe

disce

la cassetta a Bob

�Bob

èl’unico a poter aprire la cassetta

Svantaggio: Eve può interce

ttarela cassetta aperta,

e im

personificareAlice


Alberto Leporati


5

Sec

onda soluzione:

�Alice

scrive il m

essagg

io e lo ch

iude in una propria

cassetta (dotata di due

ane

llidi ch

iusura), con

una

chiave che èin grado di aprire solo lei

�Alice

spe

disce

la cassetta a Bob

�Bob

non

èin grado di aprire la cassetta; invece

, ch

iudeil sec

ondo anello con

una propria

chiave e

risped

isce

la cassetta ad

Alic

e�Alice

tog

lieil proprio lucch

etto e spe

disce

a Bob

la cassetta

�Bob

tog

lieil proprio lucch

etto, apre

la cassetta e

legg

eil m

essagg

io


Alberto Leporati


6

�rimaniamo a un livello astratto

�Bob

sce

glie due

algoritmi:

�EB: cifratura

�D

B: dec

ifratura

tali ch

e:�D

Bdec

ifra i m

essagg

i cifrati con EB:

"m

œP

T, D

B(E

B(m

)) =

m

�èestrem

amen

te difficile

(problema

intrattabile

) ricavare D

Ba partire da EB

�Bob

ren

de pu

bblic

oEB, e tien

e segretoD

B

Formalizzazione: prima soluzione

Alberto Leporati


7

�se Alic

e vuole inviare un m

essagg

io m

a Bob

, calcola

EB(m

)e lo spe

disce

a Bob

�Bob

, rice

vuto E

B(m

), calcola D

B(E

B(m

)) =

m

�se Eve interce

tta

EB(m

), pe

r ricavare D

B

dovrebbe risolvereun problema ch

e ab

biamo supp

osto essere intrattabile

�prob

lema: se Alic

e fa parte di una grossa

rete

di uten

ti, deve conoscere gli algo

ritm

i di cifratura di tutti(poco pratico)

Øsi può usare il second

o protocollo

Formalizzazione: prima soluzione

Alberto Leporati


8

�Alic

e e Bob

sce

lgono ciascuno:

�un algoritmo di cifratura(E

A, EB)

�un algoritmo di dec

ifratura

(DA, D

B)

tali ch

e:�"

m œ

PT

, E

B(E

A(m

)) =

EA(E

B(m

))

(gli algoritmi di cifraturacommutano)

�"

m œ

PT

, D

B(D

A(m

)) =

DA(D

B(m

))

(gli algoritmi di dec

ifratura

commutano)

�no

nèpiùne

cessario

rend

ere pu

bblici E

Aed

EB,

men

tre ène

cessario

tene

re seg

reti D

Ae D

B

Formalizzazione: seconda soluzione

Alberto Leporati


9

�se Alic

e vuole inviare un m

essagg

io m

a Bob

, calcola

EA(m

)e lo spe

disce

a Bob

�rice

vuto E

A(m

), Bob

lo cifra con

EBe lo

risped

isce

ad Alic

e

�Alic

e rice

ve E

B(E

A(m

)), applica

DA, ottien

e D

A(E

B(E

A(m

)))e lo spe

disce

a Bob

�Bob

app

lica

DBe ottien

e:

DB(D

A(E

B(E

A(m

))))

= D

A(D

B(E

B(E

A(m

))))

=

DA(E

A(m

)) =

m

Formalizzazione: seconda soluzione

Alberto Leporati


10

�in rea

ltà, basta che solo uno

dei due

tipi di

algo

ritm

i (cifratura o dec

ifratura) commuti

�vantaggio: Alice

usa solo EAe D

A

�se Alice

pen

sa che D

Ano

n sia piùsicuro, cambia

la cop

pia (E

A, D

A) senz

a influe

nzaregli altri

uten

ti

�come ab

biamo visto pe

r i crittosistem

i simmetrici,

al posto di sceg

liere EA(risp., D

A), Alice

selez

iona

un elemen

to di una famiglia

di algo

ritm

i di

cifratura (risp., dec

ifratura), sce

gliend

o una

chiave pub

blica

k pA(risp., privata

k sA)


Alberto Leporati


11

Quind

i, deve valere:

�"

m œ

PT

, D

k sA(E

k pA(m

)) =

m

�deve essere difficile

ricavare k

s Aa pa

rtire da

k pA

Inoltre:

�prim

o protocollo: k p

Adeveessere resa pub

blica, k s

Adeve

rimanere segreta

�second

o protocollo: k p

Apu

òessere resa pu

bblica, k s

Adeve

rimanere segreta

Dom

ande:

�come si fa ad

implem

entare in matem

atica una cassetta con

i

lucchetti?

�come si fa a ge

nerare la copp

ia (

k pA, k s

A)?


Alberto Leporati


12

�soluzion

epe

r il prim

o prob

lema: funzioni

one-way

con trapdoor

�idea

: una funz

ione

f: �Ø

�èone-way

se:

�dato

x, calcolare f

(x)èfacile

�dato

y, calcolare x

tale che

f(x)

= y

èdifficile

�la funzion

e one-way è

con trapdoorse:

�dato

y, calcolare x

tale che

f(x)

= y

èfacile

conoscen

doun’inform

azione

seg

reta k

�dato

y, calcolare x

tale che

f(x)

= y

èdifficile

se non si conosce

k

Funzioni one-way

Alberto Leporati


13

�def

inizione

formale: f

: �Ø

�èon

e-way

se:

�fècalcolab

ile in tempo

polinom

iale

da una MdT

deterministica

(cioèèfacile da calcolare)

�esistono due

polinom

i p

(∏)e

q(∏

)tali ch

e:

p(|

x|) §

|f(x

)| §

q(|

x|)

(cioènondeve prod

urre un ou

tput tropp

o corto)

�pe

r og

nialgo

ritm

o A esegu

ibile

su una MdT

prob

abilistica, e per ogn

ipo

linom

io p

(∏)esiste

un

numero naturale n

A,ptale che:

)(1

)]'(

)(

:))

((

';

}1,0{

Pr[

,n

px

fx

fx

fA

xx

nn

n

pA

≤=

←←

≥∀

Funzioni one-way

Alberto Leporati


14

�osservaz

ione

: se P = N

P, allo

ra non esistono

funz

ioni one

-way !

�contronominale: se esiste

una funz

ione

one

-way,

allora P ∫

NP

�d’altra parte, po

treb

be essere P ∫

NP senz

ach

e esistano funzioni one-way

(l’inversione

di una funz

ione

one

-way deve essere

“ quasi sem

pre”

difficile)

�in crittog

rafia, spe

sso si lavora con pe

rmutazioni

(su

{0,1

}n) on

e-way

�no

n sape

ndo se P = N

P op

pure P ∫

NP, si supp

one

che esistano

funzioni one-way

Funzioni one-way

Alberto Leporati


15

�prim

o esem

piodi funz

ione

che sembra essere

one-way: l’esponen

ziazione

mod

ulare

�sia p un num

ero prim

o

�consideriamo il cam

po �

p, e in particolare il suo

grup

po m

oltiplicativo �

p* =

{1,2

,…,p

-1}

�si dim

ostra ch

e �

p*èun grupp

o ciclico

Ø$

g œ

�p*

tale che �

p* =

{g

0,

g1,…

, g

p-2

}

�l’esponen

ziazione

mod

ulare èla funzione

f : �Ø

�p*def

inita come segu

e:

f(z)

= g

zm

od

p

Esponenziazione modulare

Alberto Leporati


16

Esempio:

��

5* =

{1,2

,3,4

} èil grupp

o moltiplicativo

conten

uto ne

l campo

�5

= {

0,1

,2,3

,4}

�2èun gen

eratoredi �

5*; infatti:

�5*

= {

20,2

1,2

2,2

3}

= {

1,2

,4,3

}

�po

ssiamo def

inire la seg

uente espo

nenz

iazione

mod

ulare:

f(z)

= 2

zm

od

5

�og

niespo

nenz

iazione mod

ulare prod

uce una

perm

utazione

(one

-way) deg

li elem

enti di �

p*


Alberto Leporati


17

�dato

x, possiam

o calcolare

gxm

od

pin tem

po

polin

omiale

�po

ssiamo supp

orre che

0 §

x §

p-2

�la dim

ension

e dell’inp

utèil numero di bit

nece

ssari pe

r rapp

resentare gli elem

enti di �

p*,

quindi

n =

log

2 p

�vale:

∑− =

=1 0

2n j

j

jx

x

dove

(xn-1

,…,x

1,x

0 )èla rappresen

tazione binaria

di

x


Alberto Leporati


18

�prim

o tentativo:

Mod

Exp(p, g, x)

risultato = 1

while x > 0

do risultato = risultato * g mod

px = x –1

return risultato

�in pratica, ne

lla variabile risultato calcola:

g0, g

1,

g2, …

, g

x(sem

pre mod

n)

�prob

lema: fa un num

ero di iterazioni pari a

x @

2n

(espon

enziale rispetto a n)


Alberto Leporati


19

�soluzion

e corretta: po

ichévale:

pg

gg

gn j

xn j

xx

xj

jj

j

n j

jj

mod

)(

1 0

21 0

22

1 0

∏∏

− =

− =

==

∑=

− =

allora ci basta calcolare i valori

g2

j , pe

r j œ

{0,1

,…,n

-1}, e m

oltiplicare tra loro solo quelli per

cui

x j=

1

�il tutto può essere fatto in tem

po polinom

iale

(rispe

tto a

n) tram

ite il cosiddetto algoritmo

“ square-and-m

ultiply”


Alberto Leporati


20

�algo

ritm

o “square-and-m

ultiply”:

Mod

Exp(p, g, x)

ris = 1

for j = n-1 dow

nto 0

do ris = (ris * ris) m

od p

if x

j= 1 then

ris = (ris * g) mod

preturn ris

�esem

pio: 8

7mod

11

Øp = 11, g = 8, x = 7, n = 4

osservaz

ione

: 87= 209715

2


Alberto Leporati


21

268-

ris*g

26

214

4

6411

ris*ris

20

971

52

512

8-

ris*g

30

111

06

90

111

18

10

111

21

10

111

31

ris*ris

xj

jris

�esec

uzione

dell’algoritmo: nella prima colonna, il

valore di ris all’iniziodella j-esima iterazione

�ne

lle ultim

e due

colon

ne, non èstata fatta la

riduz

ione

mod

ulo

p


Alberto Leporati


22

�l’ope

razione inversa si chiama logaritm

o discreto

�def

inizione

del problema: dati:

�pprim

o

�gge

neratore di �

p*

�y œ�

p*

calcolare

x œ

{0,1

,…,p

-2}tale che

gxª

y m

od

p

�il calcolo dei log

aritmi discreti sembra essere

intrattabile

: non si con

oscono

algo

ritm

i ch

e lo

risolvon

o in tem

po polinom

iale (rispetto a

n =

log

2 p) pe

r tutte le istanze

�pe

r farsi un’idea

, provarea calcolare a manoi

logaritm

i in base 3 in �

11

3*

Logaritmi discreti

Alberto Leporati


23

�osservazioni:

�113 è

trop

po piccolo

per applicaz

ioni

crittografiche

�elen

care

gli elem

enti di �

p*rich

iede tempo

O

(p)

= O

(2n)

�quindi, l’esponen

ziazione

mod

ularepu

ò essere usata per “nascon

dere”

il valore di

x œ

{0,1

,2,…

,p-2

}in g

xm

od

p

�ècome ch

iudere

xin una cassettach

e no

n pu

òpiùessere ape

rta

�ab

biamo la funzione one-way, manca la trapdoo

r

Logaritmi discreti

Alberto Leporati


24

�altro esem

piodi funz

ione

che sembra

essere

one-way: il prod

otto tra num

eri

interi

�def

inizione

molto sem

plice: dati due

num

eri

prim

ipe

q, calcolare

n =

pÿq

�il prob

lema inversoèla fattorizz

azione

: dato un num

ero intero

n, ch

e si sa essere

il prod

otto di due

num

eri prim

i pe

q,

calcolare

p(o q)

Fattorizzazione

Alberto Leporati


25

�la dim

ension

e dell’inp

utèil numero di bit

nece

ssari pe

r rapp

resentare gli elem

enti n

, pe

q; po

niam

o quindi m

= log

2n

�algo

ritm

o banale: si prova a dividere

npe

r tutti

gli interi com

presi tra

2e

Øquesto algoritmo rich

iede pe

rò tem

po

che èespo

nenz

iale

rispetto a m

�vedremo altri algo

ritm

i, che pe

rò in ge

nerale

rich

iedono tempo

espon

enziale

n

)2(

)2

()

(2/

mm

OO

nO

==

Fattorizzazione

Alberto Leporati


26

�alternativo all’uso dei crittosistemi a ch

iave

pubblica

�serve ad

accordarsi sul valore di una ch

iave

segreta

�pu

bblicato nel 1976

�Alice

e Bob

sce

lgono (pub

blic

amen

te) un num

ero

prim

o q, e un gen

eratore del grupp

o ciclico �

q*

�Alice

sce

glie a caso un intero

x A, con

0 <

xA

< q

-1,

e lo tiene

seg

reto

�Bob

sce

glie a caso un intero

x B, con

0 <

xB

< q

-1,

e lo tiene

seg

reto

Protocollo di Diffie-Hellman

Alberto Leporati


27

�Alice

calcola g

x Am

od

qe lo invia a Bob

�Bob

calcola g

x Bm

od

qe lo invia ad Alice

�Alice

calcola (

gx B

)x A=

gx A

ÿxB

= k

�Bob

calcola (

gx A

)x B=

gx A

ÿxB

= k

�kèil valore della chiave seg

reta

Sicurez

za:

�Eve ved

e passare sul canale:

q, g, g

x Ae

gx B

�pe

r ricavare x

Ao

x Bdeve calcolare un log

aritmo

discreto


Alberto Leporati


28

�pu

ò darsi che si possa ricavare

gx A

ÿxBa

partire da

gx A

e g

x B(problema di Diffie-

Hellman), m

a sembra essereun problema

intrattabile

�esem

pio:

�Alice

e Bob

si accord

ano pe

r usare

q =

25307e

g=

2(che èun gen

eratore di �

253

07*)

�Alice

sce

glie x

A=

3578

�Bob

sce

glie x

B=

19956


Alberto Leporati


29

�Alice

calcola g

x A=

23

578

= 6

11

3(m

od

25

307)e lo

sped

isce

a Bob

�Bob

calcola g

x B=

219

956

= 7

984

(mod

253

07)e lo

sped

isce

ad Alice

�rice

vuto g

x A=

61

13da Alice

, Bob

calcola k

=

(gx A

)x B=

6113

199

56

= 3

69

4(m

od

253

07)

�rice

vuto g

x B=

79

84da Bob

, Alic

e calcola

(gx B

)x A

= 7

98

435

78

= 3

694

(mod

253

07), che èlo stesso

valore k

calcolato da Bob

�ora Alice

e Bob

possono usare k

come ch

iave

segreta da usare con un crittosistema

simmetrico


Alberto Leporati


30

�pu

bblic

ato da El Gam

al nel 1984

�la difficoltàdi ricavare k

sda

k p, e la

difficoltàdi ricavare m

da

Ek p

(m)derivano

dalla (cong

etturata) difficoltàdi calcolare

i logaritm

i discreti

�ge

nerazione della cop

pia di ch

iavi: og

ni

uten

te�sceg

lie un num

ero prim

o q

�considera il grupp

o moltiplicativo �

q*

�sceg

lie un gen

eratore

gdi �

q*

Crittosistema di El Gamal

Alberto Leporati


31

�sceg

lie a caso un intero a

tale che

0 <

a <

q-1,

e calcola

gam

od

q

�la chiave seg

reta è

k s=

a

�la chiave pub

blica è

k p=

(q, g,

ga)

�volend

o calcolare

k sda

k p, bisog

nerebbe

calcolare

log

gg

a

�cifratura:

�supp

oniamo ch

e Alice

vog

lia m

andare un

messagg

io m

œ�

q*a Bob

(se m

èpiùlung

o di

log

2q bit, lo si suddivide in blocchi)


Alberto Leporati


32

�preleva la chiave pub

blica k

pB

= (

q,

g,

ga)di Bob

�sceg

lie a caso l, con

0 <

l <

q-1

�calcola γ

= g

lm

od

qe δ

= mÿ(

ga)l

mod

q

�invia a Bob

il testo cifrato

c =

(γ

,δ)

�dec

ifratura:

�quando Bob

riceve

c, utiliz

za la prop

ria ch

iave

privata

k sB

= a

per calcolare

mcome segu

e:

m =

g-a

l ÿδ=

γ-aÿδ

= γ

q-1

-aÿδ

�l’unica informazione

non pub

blica è

a


Alberto Leporati


33

�analisi:

�le unich

e inform

azioni

che transitano sul canale

sono γ

= g

le δ

= mÿ(

ga)l

�se

Eve ricavasse lda

glpo

treb

be calcolare

(ga)l

e po

i m

= δ

(ga

l )-1

= δÿg

-al

Ødeve calcolare un log

aritmo discreto

�se

Eve calcolasse

galda

gae

gl , po

treb

be po

i

calcolare

g-a

l=

(g

al )

-1e infine

m =

δÿg

-al

�la sicurez

za si basa sulle

stesse assunz

ioni

fatte pe

r il protocollo

di Diffie-Hellm

an


Alberto Leporati


34

�con i crittosistem

i a ch

iave pub

blica

si può

comunicare senz

acanali privati

Øi crittosistem

i simmetrici non servono

più?

�i crittosistem

i simmetrici:

�sono

molto più

veloci

e difficili da crittoanalizza

re�

nonbasano la sicurez

za su ipotesi matem

atichenon

dim

ostrate

�i crittosistem

i simmetrici

sono veloci ma

rich

iedono una ch

iave seg

reta

�i crittosistem

i a ch

iave pub

blic

asono len

tima non

rich

iedono una ch

iave seg

reta

�idea

: unire il m

eglio

dei due

tipi di crittosistem

i

Confronto tra crittosistemi

Alberto Leporati


35

�crittosistem

i ibridi:

�si usa un crittosistem

a a ch

iave pub

blic

ape

r stab

ilire una ch

iave sim

metrica (di sessione

)

�si passa a un crittosistem

a simmetrico

per

cifrare/

dec

ifrare i dati

�in alternativa:

�si usa il protocollo di Diffie-Hellm

anpe

r stab

ilire la chiave di sessione

�si passa a un crittosistem

a simmetrico

per

cifrare/

dec

ifrare i dati

Crittosistemi ibridi

Alberto Leporati


36

�èil crittosistema a ch

iave pub

blica

piùfamoso, più

utilizza

to e più

stud

iato

�il nom

ederiva dalle iniziali deg

li autori: Rivest,

Sham

ir e Adleman

�siano

pe

qdue

num

eri prim

i distinti (p

∫q), circa

della stessa grandez

za, di almen

o15

0 cifre in

base 10

�po

niam

o n =

pÿq

(mod

ulodi RSA)

�calcoliamo φ

(n)

= φ

(pÿq

) =

φ(p

)ÿφ

(q)

= (

p-1

)(q

-1)

�sceg

liamo a caso

dtale che

1 <

d <

φ(n

)e

MC

D(d

, φ

(n))

= 1

(dinvertibilene

ll’anello �

φ(n

))

RSA

Alberto Leporati


37

�usando l’algoritmo di Euclide esteso,

calcoliamo

e =

d-1

mo

d φ

(n)

�po

niam

o k p

= (

n,

e)e k

s=

d

�i valori p,

qe φ

(n)vann

o mantenuti seg

reti

�cifratura: si usa la funzion

e:

RS

A(n

, e,

x)

= x

em

od

n

che ècong

etturata

essere one

-way

�dec

ifratura: si usa la funz

ione

:

RS

A(n

, d,

x) =

xdm

od

n

RSA

Alberto Leporati


38

�supp

oniamo ch

e Alice

vog

lia m

andare un m

essagg

io

ma Bob


blica di Bob

: (n

B, e B

)

�se m

–{0

, 1,

…,

nB-1

}, lo suddivide in blocchi

�calcola

c =

me B

mod

nBe sped

isce

ca Bob

�Bob

, rice

vuto c:

�calcola

cdBm

od

nBª

(me B

)dBª

me B

dBm

od

nB

�po

iché

e Bd

Bª

1 m

odφ

(nB), $

k œ�

tale che

e Bd

B=

1 +

kφ

(nB), da cui:

cdBm

od

nBª

m1

+kφ

(nB

)ª

mÿ(

mφ(

nB

) )km

od

nB

RSA

Alberto Leporati


39

�pe

r il piccolo teorem

a di Fermat

(teo

rema di

Eulero), vale m

φ(n

B) ª

1 m

od

nB, e quindi:

cdBm

od

nBª

m m

od

nB

�osservazione

:

�il piccolo teo

rema di Fermat vale se M

CD

(m,n

B)

= 1, cioè

se m

non èmultiplodi

po di q

�tuttavia, anch

e se m

èmultiplo di po di

qsi

dim

ostrach

e la dec

ifratura funziona

correttamen

te

RSA

Alberto Leporati


40

�supp

oniamo ch

e Bob

sce

lga

p =

101e

q =

113, da

cui

nB

= pÿq

= 1

1413e φ

(nB)

= (

p-1

)(q-1

) =

11200

�ora Bob

deve sceg

liere d

B, compreso tra

2e

φ(n

B)-

1 =

111

99, tale che

MC

D(d

B,φ

(nB))

=

MC

D(d

B,

1120

0)

= 1. S

uppo

niam

o ch

e scelga

dB

= 6

597

�usando l’algoritmo di Euclide esteso, Bob

calcola

e Bª

dB

-1m

odφ

(nB)ª

35

33

mod

112

00

�la chiave pub

blica

di Bob

è(n

B,

e B)

= (

11

413,

353

3),

men

tre la chiave privata

èd

B=

65

97

RSA: esempio

Alberto Leporati


41

�se Alic

e vuole inviare a Bob

il messagg

io

m =

97

26, calcola:

c =

97

26

3533m

od

114

13

= 5

76

1

e lo invia a Bob

�Bob

rec

upera

mcalcolando:

cdB

= 5

76

16597m

od

11

413

= 9

726

RSA: esempio

Alberto Leporati


42

�ricord

iamo ch

e p, qe φ

(n)devono rimanere

segreti

�supp

oniamo ch

e Eve con

osca p

e q

�calcola φ

(n)

= (

p –

1)(

q –

1)

�cono

sce

e(fa pa

rte della chiave pub

blic

a)

�calcola

d ª

e-1m

odφ

(n)

�lo stessoaccade se Eve conosce

soloφ

(n)

�quindi,

�se Eve sa fattorizza

re n, rompe

RSA

�non èdetto

che valga il viceversa, ma si conge

tturach

e sia vero Ø

rompe

re RSA sareb

be eq

uivalentea

fattorizza

re n

Alcuni attacchi a RSA

Alberto Leporati


43

�se Eve conosce

soloφ

(n), non solo riesce

a

rompe

re RSA, ma riesce

anche a

fattorizza

ren:

�sa che

n =

pÿq

e φ

(n)

= (

p –

1)(

q –

1)

=

pq –

(p+

q)

+ 1

= n

–(p

+q)

+ 1

�ricava p

+q =

n –φ

(n)

+ 1

�conoscen

do sommae prod

otto

di pe

q, li può

ricavare

risolven

do l’equazione

di second

o grad

o:

x2–

(p+

q)x

+ p

q =

0


Alberto Leporati


44

�mostriamo ora alcuni accorgimen

tida ad

ottare

nella

sce

lta dei param

etri p, qe φ

(n)

�i valori di

pe

qnondevono essere tropp

o vicini:

�supp

oniamo ch

e sia

p >

q

�se p

e qsono

vicini, allora

(p-q

)/2èpiccolo, e

(p+

q)/

2èpo

co più

grandedi

�dall’ugu

aglianza

(sempre valida)

(p+

q)2

/4 –

n =

(p

-q)2

/4

si ded

uce ch

e (p

+q

)2/4

–nèun quadrato perfe

tto

�ce

rchiamo allora gli interi x

>

pe

r cui x2

–nè

un quadrato perfe

tto, che ch

iamiamo

y2


n

n

Alberto Leporati


45

�da

x2–

n =

y2ricaviam

o:

n =

x2

–y2

= (

x +

y)(

x -

y)

e quindi p

= x

+ y

e q

= x

–y

�bisog

na fare attenz

ione

anche al valore di φ

(n):

�supp

oniamo ch

e M

CD

(p-1

, q

-1)sia grande

�di conseg

uenz

a,

�sarà

piccolorispetto a φ

(n)

)1,1

(

)(

)1,1

(

)1)(1

()1

,1(

−−

=−

−

−−

=−

−=

qp

MC

D

n

qp

MC

D

qp

qp

mcm

uφ


Alberto Leporati


46

�osservaz

ione

: se d

’ª

e-1m

od

u, si può usare d

’al posto di

dpe

r dec

ifrare (questo fatto deriva

dal teo

rema di Eulero)

�dato ch

e uèrelativamen

te piccolo, pu

ò essere

cercato pe

r tentativi

Øèmeg

lio che

p –

1e

q –

1no

n ab

biano

fattori

comunigrandi

�cattiva idea

: usare lo stesso

npe

r un

grup

po di uten

ti (es: un ente o un’azien

da)

�supp

oniamo ch

e un utente deb

ba mandare

ma

due

(o più) utenti


Alberto Leporati


47

�detti e

1ed

e2gli espo

nenti di cifratura, calcola:

c 1=

me 1

mod

n

c 2=

me 2

mod

n

�se M

CD

(e1,

e 2)

= 1

allora Eve, usando

l’algoritmo di Euclid

e esteso, calcola

r, stali ch

e

re1

+ s

e 2=

1

�calcolati

red

s, Eve può calcolare:

c 1r c

2sª

mre

1m

se2ª

mre

1+

se2ª

m m

od

n


Alberto Leporati


48

�altra cattivaidea

: usare lo stessovalore (piccolo)

di

e(es: e

= 3) e valori diversi per n

�supp

oniamo ch

e un utente voglia spe

dire

ma

tre uten

ti A, B, C, ch

e hanno m

oduli n

A, n

Be

nC.

Calcola:

c A=

m3

mod

nA

c B=

m3 m

od

nB

c C=

m3

mod

nC

�se n

A, n

Bed

nCsono a due

a due

cop

rimi, Eve

può usare il Teo

rema Cinese del Resto (CRT) e

calcolare

xtale che:


Alberto Leporati


49

x ª

c Am

od

nA

x ª

c Bm

od

nB

x ª

c Cm

od

nC

�Eve trova un’unica soluzione

x*compresa tra

0

ed <

-1, dove

< =

nAn

Bn

C

�po

iché

m3èminore di

nA, di n

Be di

nC, allora

m3

< <

, ovvero x

* =

m3

�Eve calcola la radice cubica intera

di

x*

(Kob

litz, capitolo 1) pe

r calcolare

m


Alberto Leporati


50

�calcolare

dsembra essere difficile

�teorem

a(S

alom

aa, pag. 143): un algo

ritm

o pe

r calcolare

dpu

ò essere convertito in un

algo

ritm

o prob

abilisticope

r fattorizza

re n

�quindi, rom

pere RSA sem

brerebbeessere

equivalentea fattorizzare n

Attacchi a RSA: conclusioni

Alberto Leporati


51

�supp

oniamo di dover cifrare con

RSA una

sequen

za dibit(uno alla

volta)

�prob

lema: per ogn

i scelta di

(n,

e), vale:

0eª

0 m

od

n

1eª

1 m

od

n

quindi, c

= m

!�si dim

ostra ch

e in RSA, il bit m

eno sign

ificativo di

m( lsb(m

)) èun hard-core bitpe

r m

em

od

n

�idea

: metto il bit da cifrare in lsb

(m), e sce

lgo gli

altri bit a caso

RSA randomizzato

Alberto Leporati


52

�supp

oniamo ch

e Alic

e deb

ba mandare il bit

b œ

{0,1

}a Bob


blica (

nB,

e B) di Bob

�sceg

lie a caso un intero x

< n

B/2

(quind

i, 2

x <

n)

�trasmette a Bob

y =

(2x

+ b

)e B m

od

nB

�Bob

, rice

vuto y:

�calcola y

dB

mod

nB

= 2

x +

b

�pren

de il bit m

eno sign

ificativo del risultato

RSA randomizzato

Alberto Leporati


53

�osservazione

: non si sase gli altri bit di

m(in particolare, quali e quanti) sono hard-

core bit per RSA

�quindi, per cifrare in mod

o sicuro

un

messagg

io m

, si può cifrare ogn

i bit

di

mcon RSA random

izza

to�la crittoanalisidiven

ta m

olto difficile

�se il messagg

io è

lung

o, il metod

o èinef

ficien

te

RSA randomizzato

Date post:	02-Jan-2021
Category:	Documents
Upload:	others
View:	2 times
Download:	1 times

Crittosistemi a Chiave Pubblicaleporati/crittografia... · 2009. 2. 26. · logaritmo discreto...

Documents