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

Matematica Discreta Lezione del 20/05/09

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 ^c modn, quella di decifratura ponendo g(y)=y ^d modn (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.

Fissiamo 3 numeri naturali x,k,n, con n>1, e calcoliamo la riduzione modulo n della potenza x ^k : x ^k modn

(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=a s-1 2 ^s-1 + a s-2 2 ^s-2 +….+a 1 2 ¹ +a 0 2 ⁰ (con ogni cifra a i =0,1) Costruiamo una successione y 0 ,y 1 ,...,y s di numeri naturali ponendo:

y 0 =1; per ogni i>0 y i = (y _{i  1} ² x ^{a s  i} ) ^modn

Per esempio: y 1 = (y ₀ ² x ^{a s  1} ) ^{modn, y 2 =} (y ₁ ² x ^{a s  2} ) ^{modn, y 3 =} (y ₂ ² x ^{a s  3} ) modn etc...

Ogni elemento della successione y i con i>0 si calcola dal precedente con due prodotti (il quadrato di y i-1 e il prodotto del risultato per _x ^{a s - i}

, quest’ultima potenza = x oppure =1 perché l’esponente è la cifra binaria a s-i =0,1) ed una divisione (per calcolare la riduzione modulo n), ossia si eseguono in totale non più di 3s operazioni, e dunque complessivamente l’algoritmo ha complessità polinomiale rispetto al numero s di cifre binarie dell’esponente k.

Dimostriamo che l’algoritmo fornisce il valore della riduzione x ^k modn, e precisamente che si ottiene y s = x ^k modn (quindi la riduzione cercata è semplicemente l’ultimo termine della successione y 0 ,y 1 ,...,y s costruita dall’algoritmo).

Infatti si ha:

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

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

-

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

2 - 2 s 1 -

x s ^{ } (mod n)

etc..

Alla fine si ottiene la congruenza:

y s  ^{(a 2 a 2 . a 2} 1 ^a 0 ^{2 0 )} 2 1

- 2 s - 1 s - 1 s -

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

Ma per costruzione ogni y i si calcola con una riduzione modulo n, quindi in particolare 0y t n-1, e allora, per definizione di riduzione modulo n, la precedente congruenza implica che y t = x ^k modn.

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. Come esempio di applicazione dell’algoritmo dell’esponenziazione modulare, sviluppiamo il calcolo della riduzione 33084 ¹⁶⁵⁶⁵ mod83411 (coinvolta nella simulazione del sistema RSA della lezione precedente).

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

16565 = (100000010110101)

con 15 cifre binarie a 14 =1, a 13 =a 12 =a 11 =a 10 =a 9 =a 8 =0, a 7 =1 , a 6 =0, a 5 =a 4 =1, a 3 =0, a 2 =1, a 1 =0 , a 0 =1.

Si costruisce la successione y 0 , y 1 ,….., y 15 : y 0 = 1

y 1 = y 0 2 y ¹ mod83411 = 33084 y 2 = y 1 2 y ⁰ mod83411 = 31914 y 3 = y 2 2 y ⁰ mod83411 = 55086 y 4 = y 3 2 y ⁰ mod83411 = 58627 y 5 = y 4 2 y ⁰ mod83411 = 8052 y 6 = y 5 2 y ⁰ mod83411 = 24357 y 7 = y 6 2 y ⁰ mod83411 = 44417 y 8 = y 7 2 y ¹ mod83411 = 12012 y 9 = y 8 2 y ⁰ mod83411 = 70525 y 10 = y 9 2 y ¹ mod83411 = 81908 y 11 = y 10 2 y ¹ mod83411 = 47057 y 12 = y 11 2 y ⁰ mod83411 = 49432 y 13 = y 12 2 y ¹ mod83411 = 34276 y 14 = y 13 2 y ⁰ mod83411 = 241 y 15 = y 14 2 y ¹ mod83411 = 12597

Il valore finale é appunto y 15 = 12597 = 33084 ¹⁶⁵⁶⁵ mod83411 (ed é quello previsto nella lezione precedente).

Tale valore é ottenuto con il calcolo di soli 15 numeri y 1 ,….,y 15 ognuno dei quali ha richiesto al più un quadrato, un prodotto e una divisione per n=83411.

Costruzione di numeri primi

Nell’implementazione del sistema RSA vi è la necessità di trovare dei numeri primi da porre alla base del sistema: per aumentare la resistenza del sistema agli attacchi, è anche opportuno che tali numeri primi siano abbastanza “grandi” (centinaia di cifre).

Come costruire numeri primi con un numero n fissato di cifre (per esempio con n=100 cifre) ? Un metodo potrebbe essere quello di scegliere a caso un numero naturale x di n cifre, e sottoporlo a qualche test che ci garantisca che x è un numero primo (si potrebbe naturalmente filtrare in modo opportuno la scelta scartando valori che certamente non sono primi: per esempio scartando i numeri pari, che sono multipli di 2, e quelli che hanno cifra delle unità 5, che sono multipli di 5 etc….).

Ma la nostra scelta random di un numero naturale di n cifre con quale probabilità ci fornisce un numero primo ?

Dobbiamo quindi studiare la distribuzione dei numeri primi nella successione dei numeri naturali:

da alcune osservazioni empiriche, si verifica che i numeri primi sono distribuiti in modo irregolare.

Vi sono numeri primi “vicini” come le coppie di numeri primi “gemelli” della forma p, p+2 (come 3,5 oppure 17,19), ma d’altra parte si possono costruire intervalli di k naturali consecutivi (con k intero >0 arbitrariamente grande) che non contengono nessun numero primo: basta considerare i numeri naturali consecutivi della forma (k+1)!+j dove j assume i valori 2,3,…,k+1

(k+1)!+2, (k+1)!+3, (k+1)!+4, …………., (k+1)!+(k+1)

ed osservare che nessuno di essi è primo, perché (k+1)! é multiplo di tutti i numeri 2,3,4,….,(k+1) dunque (k+1)!+2 è multiplo di 2, (k+1)!+3 è multiplo di 3, (k+1)!+4 è multiplo di 4, ………, (k+1)!

+(k+1) è multiplo di (k+1), quindi ognuno di tali numeri ha un divisore non banale.

Se poi ordiniamo in ordine crescente i numeri primi in una successione p 1 , p 2 , ….., p n ,….. (quindi p 1 =2, p 2 =3, p 3 =5, etc..) non esiste una formula algebrica che permetta di calcolare il numero primo p n di posto n.

Nell’ambito dello studio della distribuzione dei numeri primi, può essere interessante valutare il numero di primi in un certo intervallo [0,x] della semiretta positiva dell’asse reale. A tale scopo, per ogni numero reale x>0, indicheremo con (x) il numero dei numeri primi che sono  x.

Per esempio (22,3) = 8 (perché i numeri primi  22,3 sono in tutto 8 e sono 2,3,5,7,11,13,17,19).

Non esistono formule algebriche per il calcolo esatto di (x). Per esempio, usando i computers, si è verificato che :

(10 ¹⁴ ) = 3.204.941.750.802

(i valori massimi attualmente calcolati sono intorno a 10 ²² ).

Nel corso del tempo, i matematici hanno cercato funzioni che “approssimassero” (x). Il risultato più famoso è il seguente, che si dimostra con metodi analitici molto complicati

Teorema di Hadamard-De La Vallé Poussin.

Considerata la funzione f(x)=x/log(x) (dove log(x) è il logaritmo neperiano), si ha:

f(x) 1 lim π(x)

x 





Quindi, per x abbastanza grande, il rapporto ^π(x) _f(x) è abbastanza “vicino” a 1, e in questo senso la funzione f(x)=x/log(x) approssima (x).

Per esempio f(10 ¹⁴ )  3.102.103.442.166, da cui

) f(10

) π(10

14 14 

442.166 3.102.103.

750.802 3.204.941.

1.033.

Utilizzando tale approssimazione si può calcolare che il rapporto fra il numero di numeri primi di n cifre (in base 10) ed il numero di tutti i numeri naturali di n cifre è circa 1/[nlog10], dunque, tenendo conto che log(10)2,3, la probabilità che un numero x di n cifre, scelto casualmente fra i numeri naturali di n cifre, sia primo è 1/[2,3n]. Per esempio la probabilità che un numero di 100 cifre, scelto casualmente fra i numeri naturali di 100 cifre, sia primo è 1/230: se scegliamo casualmente 230 numeri di 100 cifre, statisticamente dovremmo aspettarci che uno di essi sia primo.

Ovviamente tale probabilità aumenta se il numero x scelto random viene filtrato a priori: per esempio se si limita la scelta di x ai numeri dispari (i numeri pari>2 non sono primi) la probabilità raddoppia, diventando 1/115.

Quindi per trovare un numero primo con un fissato numero n di cifre (in base 10), si può scegliere casualmente un numero di n cifre, sottoporlo a un “test di primalità” e se il test non è superato cambiare la scelta del numero, e così via: statisticamente dovrebbero bastare circa 2,3n tentativi per trovare un numero primo.

Test di primalità

Nasce allora il problema di implementare un test di primalità efficiente che, in tempi accettabili, immesso in input il numero x di n cifre, ci dica se esso è primo o no (se la risposta è negativa dobbiamo scegliere un altro valore di x e sottoporlo al test, e così via).

Il test AKS introdotto nel 2002 è l’unico test di primalità di complessità polinomiale, ma si è dimostrato troppo lento per gli usi pratici.

Esistono però dei tests di primalità di complessità polinomiale molto veloci di tipo “probabilistico”:

sono tests che, immesso in input il numero naturale x, elaborano dei calcoli e poi escono con output

“x è primo” oppure “x non è primo” ma con le seguenti condizioni

- Se l’input x è un numero primo, allora l’output è con certezza “x è primo”

- Se l’input x non è un numero primo, allora l’output può essere sia “x non è primo”

(correttamente) ma anche (non correttamente) “x è primo”; la probabilità di questo secondo evento (cioè la probabilità di output errato) è però  C (dove C<1 è una costante nota a priori)

Quindi se sottoponiamo ad un test di primalità probabilistico un numero x, e se l’output è “x non è primo” possiamo dedurre con certezza che il numero x non è primo; ma se l’output è “x è primo”

possiamo concludere che x è primo con una probabilità di errore che è C.

Per esempio vedremo in seguito il test probabilistico di Rabin-Miller in cui la costante C è =1/4: se l’output è “x è primo” possiamo concludere che x è primo con una probabilità di errore che è 1/4 (quindi con il 25% di probabilità di concludere in modo errato).

Se però sottoponiamo lo stesso input x al test un numero h di volte (con h abbastanza grande) e se tutte le volte l’output è “x è primo” allora (poiché la probabilità che si verifichino più eventi indipendenti è il prodotto delle probabilità del verificarsi dei singoli eventi) possiamo concludere che x è primo con una probabilità di errore che è C ^h (numero molto piccolo se h è grande, essendo C<1).

Per esempio se, sottoponendo l’input x al test probabilistico di Rabin-Miller, per 20 volte l’output è sempre “x è primo” possiamo concludere che x è primo con una probabilità di errore che è

(1/4) ¹⁰⁰ =1/(1.099.511.627.776) (quindi la probabilità di concludere in modo errato è in questo caso

minore di 1 su 1000 miliardi).