Matematica Discreta Lezione del giorno 10 maggio 2010

(1)

Matematica Discreta

Lezione del giorno 10 maggio 2010

Dimostriamo ora il Teorema su cui si basa il sistema crittografico a chiave pubblica RSA:

Teorema RSA.

Sia n un numero naturale prodotto di 2 primi distinti p,q e sia t un numero naturale tale che:

t1 (mod (n))

dove (n) è la funzione di Eulero.

Allora per ogni intero x0 si ha: x

^t

x (mod n).

Dimostrazione:

Se x=0 la tesi è banale, quindi sia x>0, cioè sia x un numero naturale.

Calcolando la funzione di Eulero con la nota formula (dimostrata nella prima parte del corso) si ha

(n)= (pq)=(p-1)(q-1): per ipotesi si ha t-1=k(p-1)(q-1) con k intero, cioè t=1+k(p-1)(q-1) Dimostriamo dapprima che p è divisore della differenza x

^t

-x.

Se p è divisore di x, ciò è banale perché sarà x=ph con h intero, da cui x

^t

-x = p

^t

h

^t

-ph = p(p

^t-1

h

^t

-h).

Supponiamo allora p non divisore di x; per il Piccolo Teorema di Fermat si ha:

x

^p-1

1 (mod p)

Ricordando che la congruenza è compatibile con il prodotto, possiamo moltiplicare membro a membro tale congruenza per sé stessa k(q-1) volte ottenendo:

x

k(p-1)(q-1)

1 (mod p)

e moltiplicando ancora per la congruenza x x (mod p) (sempre per la compatibilità della congruenza con il prodotto) otteniamo:

x

1+k(p-1)(q-1)

x (mod p) ossia: x

^t

x (mod p)

quindi p è divisore della differenza x

^t

-x.

Con ragionamenti analoghi si ha che q è divisore della differenza x

^t

-x.

Per un risultato dimostrato nella prima parte del corso (prima del Teorema di Fattorizzazione Unica), essendo p,q primi distinti, anche il loro prodotto n=pq è divisore di x

^t

-x, e si ottiene dunque la tesi x

^t

x (mod n).

Illustriamo ora come si implementa il sistema crittografico RSA.

Ricordiamo che esso è un sistema a chiave pubblica, in cui la chiave di cifratura è pubblica (conosciuta da tutti) e la chiave di decifratura è segreta (conosciuta solo dal soggetto destinatario che deve decifrare i messaggi): per un intruso il calcolo della chiave di decifratura (conoscendo quello di cifratura) deve essere “difficile” cioè comportare lunghi tempi di calcolo.

Il soggetto destinatario B sceglie 2 numeri primi distinti p,q (in genere molto grandi, anche con centinaia di cifre) e calcola il loro prodotto n=pq, rendendo pubblico n, ma tenendo segreti i fattori primi p,q .

L’insieme dei messaggi in chiaro X (e anche di quelli cifrati Y) é l’insieme {0,1,….,n-1}.

Il soggetto B sceglie poi a suo piacere un numero naturale c coprimo con (n), cioè tale che mcd(c,(n))=1: sappiamo che nel monoide Z

(n)

delle classi di congruenza modulo (n) (rispetto al prodotto di classi) la classe [c] è simmetrizzabile.

Il soggetto B calcola il simmetrico di [c] nel monoide Z

(n)

: per il calcolo di tale simmetrico si può usare, come sappiamo, l’algoritmo Euclideo delle divisioni successive (algoritmo “veloce” che non comporta lunghi tempi di calcolo anche per numeri molto grandi).

In pratica B trova con l’algoritmo Euclideo delle divisioni successive i coefficienti interi relativi x,y

tal che 1=mcd(c, (n))=cx+(n)y: il simmetrico di [c] nel monoide Z

(n)

è la classe [x].

(2)

Il soggetto B calcola poi d=xmodn, cioè la riduzione di x modulo n (quindi d è l’unico intero tale che 0dn-1 e tale che [d]=[x] in Z

(n)

): ovviamente essendo [d]=[x] anche [d] è simmetrico di [c]

nel monoide Z

(n)

. Poiché [0] in Z

(n)

non è simmetrizzabile, siamo certi che d>0, quindi anche d è un numero naturale.

La chiave di cifratura (resa pubblica) è il numero naturale c; la chiave di decifratura (tenuta segreta dal destinatario B) è il numero naturale d.

La funzione di cifratura f : {0,1,….,n-1}  {0,1,….,n-1} è definita ponendo f(x)=x

^c

modn (è la riduzione modulo n del numero x

^c

).

La funzione di cifratura g : {0,1,….,n-1}  {0,1,….,n-1} è definita ponendo g(y)=y

^d

modn (è la riduzione modulo n del numero y

^d

)

Dobbiamo però verificare che per ogni messaggio in chiaro x (quindi per ogni x numero intero compreso fra 0 ed n-1) si abbia g(f(x))=x.

Osserviamo che (essendo [d] simmetrico di [c] nel monoide Z

(n)

) si ha [c][d]=[cd]=[1] in Z

(n)

quindi:

cd 1 (mod (n)).

Posto t=cd, possiamo allora applicare il Teorema RSA ottenendo:

x

^cd

= x

^t

 x (mod n).

Ma posto y=f(x)=x

^c

modn segue (per la definizione della riduzione modulo n):

y  x

^c

(mod n).

Analogamente posto z=g(f(x))=g(y)=y

^d

modn segue:

z  y

^d

(mod n).

Moltiplicando membro a membro la congruenza y  x

^c

(mod n) per sé stessa d volte si ha (per la compatibilità della congruenza con il prodotto):

y

^d

 x

^cd

(mod n)

e per la proprietà transitiva della relazione di congruenza:

z  x

^cd

(mod n)

ma x

^cd

= x

^t

 x (mod n) e di nuovo per la proprietà transitiva:

z  x (mod n)

Ma z,x sono entrambi numeri appartenenti all’insieme {0,1,…,n-1}, dunque, se sono congrui modulo n, sono certamente uguali fra loro (ricordiamo che le classi di congruenza modulo n con rappresentante compreso fra 0,1,…,n-1 sono tutte distinte), e si conclude che:

x = z = g(f(x)).

E’ dunque vero che decifrando la cifratura del messaggio in chiaro x, si riottiene x.

Esempio di cifratura con il sistema RSA. Supponiamo che il testo da trasmettere sia la seguente indicazione di una rotta da seguire

“15GRADISUD”.

Codifichiamo nel codice ASCII i singoli caratteri del testo:

Carattere Valore numerico In binario

1 49 (00110001)

2

5 53 (00110101)

2

G 71 (01000111)

2

R 82 (01010010)

2

A 65 (01000001)

2

D 68 (01000100)

2

I 73 (01001001)

2

S 83 (01010011)

2

(3)

U 85 (01010101)

2

D 68 (01000100)

2

Il testo in chiaro (come successione di 80 bits 0,1) è allora:

00110001001101010100011101010010010000010100010001001001010100110101010101000100 Il destinatario sceglie 2 numeri primi distinti, per esempio p=239, q=349 (segreti) e rende pubblico il loro prodotto n=83411 (nel nostro esempio i numeri coinvolti sono ovviamente troppo piccoli per rendere “sicuro” il sistema). I blocchi da cifrare (e spedire) devono avere valore numerico <n;:

poiché il più grande numero naturale esprimile con 16 bits in base 2 è 2

¹⁶

-1=65535, possiamo suddividere la successione di 80 bits in 5 blocchi di 16 bits ciascuno.

Il primo blocco di 16 bits da cifrare è dunque 0011000100110101 (valore numerico x=12597).

Il destinatario calcola la funzione di Eulero (n)=(p-1)(q-1)=82824 e sceglie come chiave di cifratura (rendendola pubblica) per esempio il numero naturale c=5 (resa pubblica); notiamo che c è coprimo con (n)=82824 come dimostra l’algoritmo Euclideo (con 3 divisioni):

82824 = 516564+4 (q

1

=16564, r

1

=4) 5 = 41+1 (q

2

=1, r

2

=1)

4 = 14+0 (q

3

=4, r

3

=0) quindi mcd(82824, 5)=1

(si può anche ottenere la stessa conclusione notando che 5, 82824 non hanno in comune divisori tranne 1).

Il mittente cifra il primo blocco di 16 bits di valore numerico x=12597 con la funzione di cifratura e la chiave di cifratura c=5:

y = f(x) = x

^c

modn = 12597

⁵

mod83411 = 317201802686979902757mod83411 = 33084 (il numero 33084 é il resto della divisione di 12597

⁵

per 83411).

Poi il mittente rappresenta in base 2 il blocco cifrato y (sempre utilizzando 16 bits):

33084 = (1000000100111100)

2

e spedisce i 16 bits lungo il canale di trasmissione (facendo lo stesso con gli altri 4 blocchi di 16 bits: li cifra e li spedisce di seguito al primo).