Matematica Discreta Lezione del giorno 12 maggio 2010

Matematica Discreta

Lezione del giorno 12 maggio 2010

Continuiamo a sviluppare l’esempio di cifratura e decifratura con il sistema RSA.

Il primo blocco cifrato di 16 bits ricevuto dal destinatario è 1000000100111100 (di valore numerico y=33084); a tale blocco il destinatario deve applicare la funzione di decifratura.

Per fare ciò il destinatario deve calcolare prima la chiave di decifratura d secondo la procedura indicata nel sistema RSA.

Abbiamo detto che la chiave di cifratura scelta era c=5, numero naturale coprimo con (n)=82824 come dimostra l’algoritmo Euclideo (con 3 divisioni):

82824 = 516564+4 (q1=16564, r1=4) 5 = 41+1 (q2=1, r2=1)

4 = 14+0 (q3=4, r3=0) quindi mcd(82824, 5)=1

Per calcolare la chiave di decifratura d, il destinatario calcola il simmetrico di [c] in Z(n) = Z82824, calcolando i coefficienti interi relativi che permettono di rappresentare 1 come combinazione lineare di 82824, 5 con l’algoritmo Euclideo esteso.

In pratica calcola i termini delle successioni si, ti : s0=1, s1=0, s2=s0-s1q1=1, s3=s1-s2q2= -1

t0=0, t1=1, t2=t0-t1q1= -16564, t3=t1-t2q2= 16565 ottenendo i coefficienti s3= -1, t3 =16565 tali che 1 = 82824(-1)+516565

Dunque [16565] è il simmetrico di [5] in Z(n) = Z82824.

La chiave di decifratura d (tenuta segreta dal destinatario) è la riduzione modulo (n) di tale valore:

d=16565mod82824=16565

(in questo caso la riduzione coincide con il numero stesso perché esso è già compreso nell’intervallo [0,(n)-1]).

Il destinatario può dunque applicare la funzione di decifratura g al primo blocco (di valore numerico y=33084) e facendo i calcoli ottiene come previsto il valore numerico del primo blocco in chiaro x:

g(y) = y^dmodn = 33084¹⁶⁵⁶⁵mod83411 = 12597 = x

(teoricamente il valore 12597 si dovrebbe ottenere come resto della divisione di 33084¹⁶⁵⁶⁵ per 83411).

Infine il destinatario rappresenta in binario il blocco x (sempre utilizzando 16 bits):

12597 = (0011000100110101)2

e (dopo avere decifrato gli altri 4 blocchi) dispone in successione i bits ottenendo il messaggio in chiaro da 80 bits (che attraverso il codice ASCII si decodificano nelle lettere del testo

“15GRADISUD”).

Nell’esempio precedente si può notare il seguente problema : il soggetto destinatario che vuole decifrare il messaggio, si trova a dovere calcolare 33084¹⁶⁵⁶⁵mod83411. Teoricamente questo valore si dovrebbe ottenere considerando il resto della divisione di 33084¹⁶⁵⁶⁵ per 83411: in effetti i numeri coinvolti nel calcolo sono molto grandi (il numero 33084¹⁶⁵⁶⁵ ha più di 80000 cifre in base 10) ed il nostro esempio è basato su numeri primi p,q di soli 3 cifre, mentre nella realtà i sistemi RSA sono basati su numeri con centinaia di cifre, e ciò renderebbe “astronomici” i valori da manipolare.

Esiste un algoritmo efficiente per risolvere tale problema, che riduce moltissimo la grandezza dei valori coinvolti nei calcoli , ed è la cosiddetta esponenziazione modulare, che esamineremo in seguito.

RSA-129 challenge.

La sicurezza del sistema RSA si basa sulla difficoltà di trovare i fattori primi di un numero naturale molto “grande”: ovviamente però la valutazione di tale sicurezza deve essere fatta con cura, tenendo conto dell’evoluzione degli algoritmi e dei mezzi informatici, per evitare valutazioni errate e troppo ottimistiche.

Possiamo a tale riguardo ricordare il cosiddetto “RSA-129 challenge”: una sfida lanciata nel 1977 dagli inventori del sistema RSA, relativa alla fattorizzazione del numero RSA-129, di 129 cifre in base 10; tale numero (prodotto di 2 primi p,q di 64 e 65 cifre):

(1143816257578888676692357799761466120102182967212423625625618429357069352457338 978 30597123563958705058989075147599290026879543541) =

(3490529510847650949147849619903898133417764638493387843990820577) * (32769132993266709549961988190834461413177642967992942539798288533)

era alla base di un sistema RSA con cui era cifrato il messaggio testuale “the magic words are squeamish ossifrage” (letteralmente “le parole magiche sono schizzinoso avvoltoio”).

La chiave c di cifratura (resa pubblica insieme al valore di n) era c=9007.

Le previsioni, basate sulla efficienza degli algoritmi di fattorizzazione dell’epoca, erano che fossero necessari “milioni di anni” per calcolare i fattori primi p,q, e quindi la chiave di decifratura d, con la quale decifrare il messaggio.

Ma lo sviluppo di nuovi algoritmi (in particolare del cosiddetto “crivello quadratico” di Pomerance) e il lavoro in parallelo di più di 1000 computers messi a disposizione da utenti Internet, permise, dopo 8 mesi di lavoro, di calcolare nel 1994 la seguente chiave di decifratura (con 129 cifre):

d=106698614368578024442868771328920154780709906633937862801226224496631063125911 774470873340168597462306553968544513277109053606095

e decifrare quindi il messaggio.

Esponenziazione modulare.

Abbiamo visto che nell’implementazione del sistema crittografico RSA era necessario il calcolo della riduzione di una potenza sia per cifrare che per decifrare i messaggi: la funzione f di cifratura era definita ponendo f(x)=x^cmodn, quella di decifratura ponendo g(y)=y^dmodn (dove c,d sono le chiavi di cifratura e decifratura rispettivamente).

Nei casi concreti i numeri coinvolti hanno centinaia di cifre, quindi le potenze da calcolare possono avere grandezza astronomica.

Illustreremo dunque l’algoritmo della esponenziazione modulare che permette di calcolare in modo efficiente la riduzione di una potenza modulo n.

Obiettivo: Fissati 3 numeri naturali x,k,n, con n>1, calcoliamo la riduzione modulo n della potenza x^k:

x^kmodn

(ricordiamo che per definizione è l’unico numero intero t tale che tx^k (mod n) e tale che 0tn-1).

Sia s il numero di cifre binarie dell’esponente k; la rappresentazione di k in base 2 è allora della forma:

k=as-12^s-1+ as-22^s-2+….+a12¹+a02⁰ (con ogni cifra ai=0,1) Costruiamo una successione y0,y1,...,ys di numeri naturali ponendo:

y0=1; per ogni i>0 yi=(y_i1²x^asi)^modn

Per esempio: y1=(y₀²x^as1)^{modn, y2=}(y₁²x^as2)^{modn, y3=}(y₂²x^as3)modn etc...

Ogni elemento della successione yi con i>0 si calcola dal precedente con due prodotti (il quadrato di yi-1 e il prodotto del risultato per _x^asi : osserviamo che quest’ultima potenza è = x oppure =1 perché l’esponente è la cifra binaria as-i è =0,1), e con una riduzione modulo n (che rende il risultato

<n): questo permette di coinvolgere nei calcoli numeri non troppo “grandi” .

Dimostriamo che l’algoritmo fornisce appunto il valore della riduzione x^kmodn, e precisamente che si ottiene ys= x^kmodn (quindi la riduzione cercata è semplicemente l’ultimo termine della successione y0,y1,...,ys costruita dall’algoritmo).

Infatti si ha:

y1=(y₀²x^as1)modn da cui y1(y₀²x^as1) ^{(mod n)}

y2=(y₁²x^as2)modn da cui y2(y₁²x^as2) (mod n) e dunque y2 ^{(a 2}1 ^a s-2²⁰⁾ 1

-

x s ^ (mod n) y3=(y₂²x^as3)modn da cui y3(y₂²x^as3) (mod n) e dunque y3 ^{(a 2 a 2}1 ^as-3²⁰⁾

2 - s 2 1 -

x s ^{ } (mod n)

etc..

Così procedendo alla fine si ottiene la congruenza:

ys  ^{(a 2 a 2 . a 2}1 ^a0²⁰⁾ 2 1

- 2 s - 1 s - 1 s -

x s ^{  } = x^k (mod n)

Ma per costruzione ogni yi si calcola con una riduzione modulo n, quindi in particolare 0ytn-1, e allora, per definizione di riduzione modulo n, la precedente congruenza implica che yt è proprio la riduzione di x^k modulo n, come si voleva:

yt = x^kmodn.

Esempio. Come esempio di applicazione dell’algoritmo dell’esponenziazione modulare, sviluppiamo il calcolo della riduzione 33084¹⁶⁵⁶⁵mod83411 (coinvolta nella simulazione del sistema RSA visto nell’esempio precedente).

Si rappresenta l’esponente d=16565 in base 2:

16565 = (100000010110101)

con 15 cifre binarie a14=1, a13=a12=a11=a10=a9=a8=0, a7=1, a6=0, a5=a4=1, a3=0, a2=1, a1=0, a0=1.

Si costruisce la successione y0, y1,….., y15: y0 = 1

y1 = y02y¹mod83411 = 33084 y2 = y12y⁰mod83411 = 31914 y3 = y22y⁰mod83411 = 55086 y4 = y32y⁰mod83411 = 58627 y5 = y42y⁰mod83411 = 8052 y6 = y52y⁰mod83411 = 24357 y7 = y62y⁰mod83411 = 44417 y8 = y72y¹mod83411 = 12012 y9 = y82y⁰mod83411 = 70525 y10 = y92y¹mod83411 = 81908 y11 = y102y¹mod83411 = 47057 y12 = y112y⁰mod83411 = 49432 y13 = y122y¹mod83411 = 34276 y14 = y132y⁰mod83411 = 241 y15 = y142y¹mod83411 = 12597

Il valore finale é appunto y15 = 12597 = 33084¹⁶⁵⁶⁵mod83411 (ed é quello indicato come risultato nell’esempio precedente).