Matematica Discreta II Lezione del giorno 29 ottobre 2007

Matematica Discreta II

Lezione del giorno 29 ottobre 2007

Nel sistema crittografico RSA è “computazionalmente difficile” per un intruso ricavare dalla chiave di cifratura c (resa pubblica) quella di decifratura d. Infatti si può notare che per calcolare la chiave di decifratura d è necessario conoscere il valore della funzione di Eulero (n)=(p-1)(q-1), e sappiamo (da osservazioni precedenti) che ciò è equivalente a conoscere i fattori primi p,q di n: il problema è quindi equivalente a quello di fattorizzare in numeri primi il numero n, e per un generico valore n non è a tutt’oggi noto un algoritmo di fattorizzazione di complessità polinomiale.

Ciò non toglie che per particolari valori di n, alcuni algoritmi di fattorizzazione riescano in modo efficiente a calcolare i fattori primi p,q di n, e quindi a rompere il sistema RSA, per cui anche la scelta di p,q deve essere fatta con cura, per assicurare la massima sicurezza del sistema.

Possiamo 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”).

L’esponente c per la cifratura (reso pubblico 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, la chiave di decifratura d, e decifrare quindi 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 chiave di decifratura:

d=106698614368578024442868771328920154780709906633937862801226224 496631063125911774470873340168597462306553968544513277109053606095 e decifrare il messaggio.

Esempio.

Supponiamo di scegliere come base di un sistema RSA i numeri primi p=13, q=17 e il loro prodotto n=221, con (221)=(p-1)(q-1)=192 (ovviamente i valori scelti in questo esempio sono troppo piccoli per costruire un sistema crittografico sicuro). La spazio dei messaggi in chiaro (e di quelli cifrati) è Z221 = {0,1,2,…..,220}.

Fissiamo come chiave di cifratura c=5 (numero coprimo con (221)=192) e calcoliamo il suo inverso modulo 192 con l’algoritmo Euclideo, ottenendo la chiave di decifratura d=77.

Se il messaggio in chiaro è x=2, il messaggio cifrato sarà y=2⁵mod221=32; la decifratura di y ricalcolerà il messaggio in chiaro: y⁷⁷mod221=32⁷⁷mod221=2=x.

Notiamo che nel calcolo della riduzione di potenze modulo n (funzione di cifratura e di decifratura) possono essere coinvolti numeri molto grandi (nell’esempio precedente 32⁷⁷ ha più di 100 cifre in

base 10), e la complessità di calcolo può essere alta. Questo problema si risolve con un algoritmo efficiente detto della esponenziazione modulare.

Esponenziazione modulare.

E’ un algoritmo mediante il quale, fissati 3 numeri naturali x,k,n, con n>1, si calcola la riduzione modulo n della potenza x^k: x^kmodn

con una complessità polinomiale, relativamente all’esponente k.

Sia t il numero di cifre binarie dell’esponente k; quindi la rappresentazione di k in base 2 sia:

k=at-12^t-1+ at-22^t-2+….+a12+a0 (con 0ai1)

Costruiamo una successione y0,y1,...,yt di numeri interi ponendo:

y0=1; per ogni i>0 yi=

(y

x

)

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^ati , quest’ultimo uguale ad x oppure ad 1) ed una divisione (per calcolare la riduzione modulo n), ossia si eseguono in totale non più di 3t operazioni, e dunque complessivamente l’algoritmo ha complessità polinomiale rispetto all’esponente k.

Dimostriamo che l’algoritmo fornisce il valore della riduzione x^kmodn, e precisamente che si ottiene yt= x^kmodn.

Non è infatti difficile dimostrare per induzione che per ogni i>0 si ha:

yi  ^{(a 2 a 2}-i2 ^{. a}ti-1^{2 a}ti-⁾ 2

1 -t 1 -i

x -t ^{   } (mod n) In particolare, per i=t, si ottiene la congruenza:

yt  x^{(at-12t-1at-22t-2.a12a0)= xk (mod n)}

Ma per costruzione ogni yi si calcola con una riduzione modulo n, quindi 0ytn-1, e allora, per definizione di riduzione modulo n, la precedente congruenza implica che yt = x^kmodn.

Notiamo che nell’algoritmo anche la grandezza dei numeri coinvolti nei calcoli è limitata, rispetto al modulo n: ad ogni passo si moltiplicano fattori <n e si riduce il risultato modulo n.

Esempio.

Siano n=341, a=2, e calcoliamo con l’esponenziazione modulare la riduzione 2³⁴⁰mod341.

La rappresentazione binaria dell’esponente 340 è:

340 = 12⁸+02⁷+12⁶+02⁵+12⁴+02³+12²+02¹+0 = (101010100)2

Seguendo i passi dell’algoritmo, costruiamo la successione y0,y1,y2,y3,y4,y5,y6,y7,y8,y9 con y0=1 e per i>0 yi=

(y

2

)

Si ottiene :

y1=(1²2^a8)mod341=2 ; y2=(1²2^a7)mod341=4 ; y3=(4²2^a6)mod341=32 ; y4=(32²2^a5) mod341=1 ;

y5=(1²2^a4)mod341=2 ; y6=(2²2^a3)mod341=4 ; y7=(4²2^a2)mod341=32 ; y8=(32²2^a1) mod341=1 ;

y9=(1²2^a0)mod341=1=2³⁴⁰mod341.

Possiamo allora concludere che 2³⁴⁰mod341=1 .