Undolog.com

Prima di tutto, come accennato nel Post Crittografia il sistema RSA è una cifratura a chiave pubblica e sfrutta le proprietà dei numeri primi. Inoltre l’aritmetica adottata (nei calcoli) non è quella ordinaria, bensì la cosidetta artirmetica finita o modulare. Iniziamo proprio da quest’ultima per procedere passo dopo passo nella realizzazione di una cifratura RSA.

L’artimetica finita, come dice il nome stesso, tratta insiemi di numeri finiti. Un esempio chiarificatore, che renderà tutto molto chiaro, è il calcolatore a orologio. Prendiamo un classico orologio a lancette a cui tutti noi siamo abituati. Esso rappresenta un sistema finito in quanto le ore rappresentate sul quadrante sono 12. La lancetta, infatti, ad ogni giro ritornerà - o presto o tardi - sulle stesse posizioni. Così accade che 3+12=3, nel nostro calcolatore a orologio. Più esattamente le operazioni di addizione e moltiplicazione nell’aritmetica finita si svolgono allo stesso identico modo dell’aritmentica ordinaria, con la differenza che al risultato finale si esegue l’operazione di modulo (spesso indicata con mod e presente in tutti i linguaggi di programmazione; in C, Javascript o PHP è il simbolo %). Nel caso del nostro orologio a 12 ore, infatti, l’operazione di addizione è proprio 3+12=15 mod 12 che darà come risultato 3 - come visivamente siamo abituati.
In pratica - relativamente all’orologio - facciamo proprio questa operazione, anche se non in modo consapevole. L’operazione di modulo 12, per comprenderla, corrispondere a dividere un numero per 12 e prendere il resto della divisione:

Es. 15 mod 12 = 15/12 = (resto 15-12) = 3
Es. 24 mod 12 = 24/12 = (resto 0) = 0
Es. 26 mod 12 = 26/12 = (resto 14-12) = 2

Il numero di ore sul qudrante può essere un numero qualsiasi; 12, 24, 5, 128, …
Tuttavia si è scoperto che scegliendo un numero primo, come numero di ore, si aveva una formidabile caratteristica. Prima di tutto quando si sceglie un numero primo non troviamo mai un zero come risultato. Inoltre un qualsiasi numero su un quadrante formato da un numero primo elevato al numero primo scelto come numero di ore restituisce sempre il numero dato. Per esempio se prendiamo un orologio con 5 ore sul quadrante e eleviamo ad esempio 2⁵ otteniamo di nuovo 2, il numero di partenza:

2⁵ = 32 mod 5 = 2

Il che si traduce in:

x^p = x (mod p)

Pierre de Fermat, il matematico che si accorse di questo comportamento, notò che la lancetta dell’orologio sembrava tracciare un andamento ripetitivo. In pratica, nel nostro caso, dopo cinque passi la lancetta tornava nella posizione di partenza.

Con un orologio a 13 ore (provate voi fino a 3¹³) otteniamo:

3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3

A differenza di prima la nostra lancetta non si fermerà su tutti i numeri possibili, ma l’andamento ripetitivo compare ugualmente e, anche in questo caso, la lancetta tornerà sul 3 dopo che 3 è stato moltiplicato per se stesso 13 volte!

Nel 1736, Leonhard Euler riuscì ad estendere questa caratteristica, oltre che a darne una spiegazione. Egli dimostrò che dato un orologio con N ore sul quadrante, dove N=p*qè il prodotto di due numeri primi p e q, l’andamento avrebbe cominciato a ripetersi dopo (p-1)*(q-1)+1 passaggi.

Questa caratteristica sta alla base della cifratura RSA. Si comprese che questo andamento ciclico poteva - nei fatti - far sparire un’informazione per poi magicamente riportarla alla luce. Vediamo che N rappresenta il prodotto di due numeri primi p e q, sarà questo l’artifizio in grado di rendere pubblico N e mantenere segreti p e q.

Nella pratica, quindi, quello che si viene a realizzare ricorda un trucco con le carte. Immaginiamo di avere un mazzo composto da un numero enorme di carte, così grande che per scriverlo ci servirebbero almeno cento cifre. Il codice che vogliamo cifrare è una di queste carte che, dopo essere stata posta in cima al mazzo, quest’ultimo viene mescolato così da far perdere - apparentemente - l’ubicazione della nostra carta (il messaggio). Grazie all’aritmetica dell’orologio, in pratica, è molto facile far sparire la carta ma non è altrettanto facile farla ricomparire, a meno che non si conosca il numero esatto di mosse da compiere sul mazzo in modo tale da far ricomparire la carta in cima ad esso.
Facciamo quindi un esempio completo, così da vedere tutte le formule necessarie per creare questa specie di magia.
Nel nostro esempio useremo numeri piccoli giusto per comprendere il meccanismo e immagineremo di dover inviare il numero della nostra carta di credito a un sito Web.

PASSO 1

Il sito Web comunica - al nostro browser - la prima chiave pubblica, calcolata come N=p*q (il sito Web terrà gelosamente per se i numeri p e q, solo il prodotto viene reso pubblico); essa rappresenta il numero di ore usate sul nostro orologio. Considerate che nella realtà i numero p e q sono di almeno 60 cifre!! Noi useremo numeri più umani:

N=p*q = 5*11 = 55

Cinquantacinque è la nostra chiave pubblica che, grazie alla sicurezza del codice, il sito Web può distribuire tranquillamente e indistintamente a tutti i suoi clienti. Nonostante sia stato reso pubblico il numero N, i fattori primi che lo compongono p e q rimangono segreti; saranno loro a decodificare il numero della nostra carta di credito!

PASSO 2

A questo punto riceviamo un secondo numero E, chiamato numero di codifica. Questo numero è anch’esso pubblico e uguale per tutti, allo stesso modo di N. Tramite il nostro browser possiamo codificare il numero della nostra carta di credito C, in pratica mischiamo il mazzo di carte, E rappresenta il numero di scozzate sul mazzo:

C^E(modulo N)

Il numero E è generalmente piccolo e viene calcolato a partire dalla formula che abbiamo incontrato sopra quando abbiamo visto che su un orologio con un numero di ore formato da un numero primo, vi era una sequenza che si ripeteva dopo (p-1)*(q-1)+1 passaggi (per dettagli clicca qui)!
Prima di tutto si calcola un numero b:

b=(p-1)*(q-1)=(5-1)*(11-1)=(4)*(10)=40

Il numero E deve essere un numero primo tale da non avere divisori con b; MCD(E,b)=1
Per semplificare andiamo a tentativi - esistone tecniche diverse per questo:

Se E = 2 allora MCD(2, 40) = 2 non va bene
Se E = 3 allora MCD(3, 40) = 1 va bene

A questo punto possiamo cifrare il nostro numero di carte di creditoC. Se C vale ad esempio 32 sia ha:

C^E mod N = 32³ mod 55 = 43 = C_cf

Fantastico, 43 è il nostro numero di carta di credito cifrato! Possiamo inviarlo!

PASSO 3

Il sito Web riceve il nostro numero di carta di credito C_cf cifrato, ovvero 43. A questo punto sfrutta la seguente proprietà:

C = C_cf^d mod N

Il numero d è l’inverso del numero E nell’aritmetica finita di ordine b, la nostra aritmetica dell’orologio. Questo per semplicità viene calcolato in modo che d*E mod b = 1
Andando per tentaivi scopriamo che:

Per d = 1 sia ha 1*3 mod 40 = 3 mod 40 = 3 - non va bene
Per d = 2 sia ha 2*3 mod 40 = 6 mod 40 = 6 - non va bene
Per d = 3 sia ha 3*3 mod 40 = 9 mod 40 = 9 - non va bene
….
Per d = 27 sia ha 27*3 mod 40 = 81 mod 40 = 1 - trovato!

Ora il sito Web è in grado di rimescolare il mazzo in modo da far ricomparire il nostro numero di carta di credito:

C = C_cf^d mod N = 43²⁷ mod 55 = 32

Riassumendo

Se volete fare delle prove con numeri scelti a caso cliccate qui.
Inoltre, come spiegato sullo stesso sito del RSA:

Suppose Alice wants to send a message m to Bob. Alice creates the ciphertext c by exponentiating: c = m^e mod n, where e and n are Bob’s public key. She sends c to Bob. To decrypt, Bob also exponentiates: m = c^d mod n; the relationship between e and d ensures that Bob correctly recovers m. Since only Bob knows d, only Bob can decrypt this message.

Hacker e sicurezza

Il nostro numero di carta di credito, cifrato, viaggia sulla rete e qualsiasi hacker potrebbe leggerlo. Quello che serve ad un hacker per decifrare il nostro codice è un numero che, moltiplicato E volte per se stesso sul calcolatore a orologio di N ore, fornisca il numero cifrato della carta di credito (C_cf=C^E mod N). Inoltre su un calcolatore ordinario il risultato di una serie di moltiplicazione autmenta progressivamente, cosa che non accade su un calcolatore ad orologio, dove il punto di partenza si perde di vista molto rapidamente, dato che le dimensioni del risultato non hanno alcun rapporto con la posizione da cui si è partiti. Inoltre, in casi reali, il numero N ha più di cento cifre; ci sono più ore sul quadrante del calcolatore a orologio che atomi nell’universo. È solo grazie al numero di decodifica d che il sito Web riesce a recuperare il numero della carta di credito, ma tale numero d è recuperabile solo se si conoscono p e q. Nonostante il numero N=p*q sia pubblico, la difficoltà di fattorizzare N rende sostanzialmente impossibile decifrare il codice.

Tuttavia nessuno ha mai dimostrato che non esista un algoritmo matematico che possa far sì che numeri molto grandi vengano scomposti rapidamente adoperando un computer. Se ciò dovesse accadere si avrebbe il tracollo dell’economia del mondo sviluppato in men che non si dica.

Bibliografia

• Colin Bruce, I conigli di Schrodinger - Fisica qunatistica e universi paralleli, Raffaello Cortina Editore
• Marcus Du Sautoy, L’enigma dei numeri primi. L’ipotesi di Riemann, il più grande mistero della matematica, BUR
• Simon Singh, L’ultimo teorema di Fermat. L’avventura di un genio, di un problema matematico e dell’uomo che lo ha risolto, Rizzoli
• Liceo Foscarini - Venezia: http://www.liceofoscarini.it/studenti/crittografia/
• RSA: http://www.rsasecurity.com/

Post correlati

• As3Crypto ActionScript 3 Cryptography Library (0)
• Crittografia (2)
• reCAPTCHA: STOP allo SPAM (0)
• Il pericolo digitale (0)
• Bollettino sicurezza: WordPress e XBox 360 (2)