Cifrare RSA: applicare le caratteristiche dei numeri primi

Abbiamo visto nel post di tempo fa, principi di codifica e cifratura. Oggi sviluppiamo l'argomento introducendo l'algoritmo RSA, derivato da l'applicazione di numeri primi.

Fin dai tempi di Euclide, cioè circa dal 300 a.C., gli antichi Greci sapevano che ci sono infiniti numeri primi e che essi sono distribuiti in maniera irregolare tra i numeri naturali. Da allora, molti matematici eminenti, come Fermat, Mersenne, Leibniz, Eulero, Gauss ecc., hanno compilato e analizzato lunghi elenchi di numeri primi, nel tentativo di farsi un'idea della loro distribuzione e per cercare delle formule in grado di produrre, se non tutti, almeno "molti"numeri primi.

Per esempio, un importante risultato fu ottenuto nel 1896 da due matematici francesi, Hadamard e De la Vallie Poussin. Essi dimostrarono il seguente teorema, che era stato congetturato quasi un secolo prima da Gauss: il numero dei primi minori o uguali a n può essere approssimato da n/log n (al crescere di n).

D'altra parte, molti matematici dal '600 in poi, a partire da Mersenne, si de dicarono a studiare i numeri del tipo 2p-1, con p primo. Infatti Fermat aveva dimostrato che, se non sono primi, i numeri di questo tipo hanno fattori tutti della forma 2Kp+1, con k numero naturale. Questo semplifica molto il test di primalità, cioè la verifica se sono primi o meno. In effetti, i più grandi primi trovati finora sono proprio primi di Mersenne, cioè del tipo 2p-1. In particolare lo è l'ultimo, quello trovato lo scorso novembre dal ventenne canadese Michael Cameron: si tratta di 213.466.917-1, un numero con oltre 4 milioni di cifre!

Quello che spinge a cercare nuovi numeri primi può essere l'emulazione nei confronti degli illustri matematici del passato, il desiderio di gloria, il piacere di battere un record. Nello stesso tempo, ci possono essere risultati collaterali della ricerca svolta, di interesse indipendente. Dagli anni '50 in poi, i conti necessari a verificare che grandi numeri sono primi sono stati effettuati dalle macchine calcolatrici: i programmi per trovare numeri primi sono stati usati per testare del nuovo hardware, c'è stata quindi un'utilità pratica.

A partire dagli anni '80, grandi numeri primi sono stati usati per cifrare messaggi segreti con il metodo di crittografia a chiave pubblica detto RSA (dai nomi dei suoi ideatori Rivest, Shamir e Adleman, ricercatori del Massachussetts Institute of Technology).

I metodi di crittografia a chiave pubblica prevedono che, chi deve ricevere l'informazione, renda pubblica la chiave (alcuni numeri) e il metodo per cifrare i messaggi. Egli poi, in base a dei "numerisegreti" in suo possesso è in grado di decifrare i messaggi che gli vengono inviati.

Nel metodo RSA:

• i numeri segreti sono due numeri primi p, q e un numero N primo con (p-1)(q-1)
• la chiave pubblica è costituita dal prodotto pq e da un numero M tale che MN-1 sia multiplo di (p-1)(q-1)
• il messaggio da trasmettere è un numero intero positivo x, minore di pq;
• il messaggio cifrato è il numero y, ottenuto come resto della divisione di xM per pq
• per decifrare il messaggio, è sufficiente calcolare il resto della divisione di yN per pq.

Osserviamo che il messaggio deve essere un numero positivo e minore di pq. Pertanto se si tratta di un messaggio in lettere, bisogna innanzitutto trasformarlo in cifre con un metodo qualunque. Se il numero trovato è troppo grande, lo si spezza in numeri più piccoli da trasmettere separatamente.

La spiegazione del metodo si basa sul seguente teorema, che a sua volta segue da un famoso teorema, noto come piccolo teorema di Fermat.

Teorema Se 0≤x(x^M)^N è congruo a x modulo pq.

Nella pratica, bisogna scegliere p e q primi molto grandi, in modo che sia impossibile fattorizzare pq in tempo ragionevole. Il metodo infatti si basa sull'assunzione che sia estremamente difficile risalire a p e q conoscendo il loro prodotto.

Se chi intercettasse un messaggio fosse in grado di fattorizzare pq, di conseguenza conoscerebbe anche (p-1)(q-1), e per trovare N gli sarebbe sufficiente risolvere l'equazione

MN = 1 mod (p-1)(q-1),

con M e (p-1)(q-1) primi tra loro, entrerebbe così facilmente in possesso di tutte le informazioni necessarie a decifrare il messaggio.

Il rapido sviluppo di nuove tecniche per la fattorizzazione dei numeri composti sta rendendo problematico l'uso del metodo RSA. Si è infatti costretti a usare numeri p,q sempre più grandi, cosa che rende molto lungo il calcolo di y e di y^N mod pq. Ci si sta orientando dunque a tornare a metodi crittografici classici, trasmettendo col metodo RSA soltanto la chiave.

Per saperne di più, consiglio i libri:

K. Devlin, Dove va la matematica?, Boringhieri
D. M. Davis, The nature and power of mathematics, Princeton University Press
S. Singh, Codici e Segreti, Rizzoli

e i siti web:

http://www.utm.edu/research/primes
http://www.mersenne.org/prime.htm

Cenni di codifica e cifratura

Il problema di codificare o cifrare un messaggio è stato affrontato, generalmente per usi militari, attraverso tutta la storia della civiltà umana.

Plutarco descrive la scitala lacedemonica come un codice di cifratura in uso dai tempi di Licurgo (IX sec a.C.), circa tremila anni fa. Si trattava di un dispositivo di cifratura costituito da un bastone e da un nastro di cuoio avvolto a spirale cilindrica, su cui il messaggio veniva scritto per colonne. Sul nastro srotolato le lettere risultavano trasposte in modo tale che solo l'adozione di un bastone identico a quello originariamente usato per la scrittura del messaggio consentiva di ricomporre il testo.

Il primo trattato di crittografia risale al 400 a.C. circa, ad opera del generale arcadico Enea il Tattico, in cui vengono descritti prevalentemente sistemi di meccanici di cifratura analoghi alla scitala lacedemonica.

Con la civiltà dei Greci e l'Impero Romano, la cifratura di un messaggio avveniva per semplice sostituzione o traslitterazione. I codici di Cesare e di Augusto erano infatti basati proprio su questa tecnica, adottando l'alfabeto romano. Il codice di Atbash, basato sull'alfabeto ebraico, era una versione ancor più semplificata di codice per sostituzione: la prima lettera dell'alfabeto veniva scambiata con l'ultima, la seconda con la penultima e così via. Polibio con la sua scacchiera, ideò un metodo per sostituire lettere a coppie di numeri. La scacchiera di Polibio era costruita inserendo le lettere dell'alfabeto in una matrice rettangolare e sostituendo nel messaggio la riga e la colonna corrispondente ad ogni lettera.

Fig.1 Esempio di scacchiera di Polibio

La figura 1 è stata costruita utilizzando il metodo proposto da Polibio. Ad esempio, il termine (amore) viene codificato sostituendo il numero di riga e colonna per ogni lettera che lo compone, come in figura 2.

= 1113113421

Fig.2 Esempio di codifica di Polibio

A dispetto dell'apparente semplicità della codifica di Polibio, tale metodo suggeriva una interessante soluzione al problema della trasmissione del messaggio: una frase poteva venire trasmessa a distanza, infatti, mediante segnali luminosi.

Attraverso tutto il medioevo poi, la crittografia veniva utilizzata per scopi militari o diplomatici con varianti del metodo della sostituzione, utilizzando per lo più abbreviazioni, o nomenclature, di nomi, luoghi.

Dal XVI secolo, i codici del Della Porta, Bellasio, Alberti e Vigenere introducono, pur se con metodologie diverse, il concetto di chiave, talvolta definita verme letterale, per il controllo del processo di cifratura. L'idea è di utilizzare una sequenza di caratteri dedicata al fornire informazioni necessarie e sufficienti, unita ad un metodo, senza la quale sarebbe impossibile riottenere il messaggio originale. Ad esempio, l'Alberti utilizzava delle lettere di controllo inserite nel testo cifrato per determinare quale lista di lettere utilizzare per la cifratura locale del brano; Della Porta e Bellasio utilizzano la chiave come strumento di generazione del messaggio codificato; Vigenere unisce il metodo di sostituzione al concetto di chiave, utilizzando una matrice quadrata di sostituzione e la chiave come strumento di selezione della riga da utilizzare.

Thomas Jefferson, presidente degli Stati Uniti ed autore della dichiarazione di Indipendenza ideò un codice di cifratura meccanico, mediante un cilindro costituito da 36 dischi con le 26 lettere dell'alfabeto in ordine sparso. Il codice è considerato ancor oggi sicuro.

Ma è con l'avvento del XX secolo, della guerra e, quindi, dei calcolatori che la vita dei ideatori di codici si è fatta più complessa. Tutti i sistemi ideati fino ad allora avevano l'inconveniente di essere obsoleti non appena il metodo di decifrazione, meccanico o cartaceo che sia, fosse reso pubblico. Ottenuto il bastone originale nella scitala lacedemonica o il cilindro di Jefferson chiunque sarebbe in grado di procedere alla decodifica.

Alan Turing, matematico e padre de facto dell'informatica, è stato al centro di epiche vicende di decrittazione, a colpi di macchine calcolatrici sempre più potenti ed algoritmi sempre più efficaci che hanno costellato la storia della crittografia dalla seconda guerra mondiale in poi.

La vera sfida del ventesimo secolo era, quindi, l'ideazione di un codice per cui anche il più potente dei calcolatori impiegasse millenni per la decodifica. Il problema era, infatti, che i metodi ideati non erano in grado di resistere ad una analisi esaustiva di un calcolatore sufficientemente potente da tentare tutte le combinazioni possibili.

Nel 1975 IBM ha introdotto il Data Encryption System, o DES, un codice a chiave basato su una sequenza di sostituzioni e trasposizioni operate in base ad una chiave di 64 bit. Tale metodo fu al centro di un'aspra ed accesa polemica perché il numero di chiavi distinte a 64 bit è pari a 2⁶⁴, ulteriormente ridotto a 2⁵⁶ considerando che 8 bit della chiave sono destinati al controllo: un numero di combinazioni alla portata di molti computer moderni.

Il DES differisce dagli altri metodi per il fatto di non dover essere mantenuto segreto, il fatto che venga reso pubblico non garantisce affatto la possibilità di decodificare i messaggi. All'IBM va riconosciuto, infatti, di aver ideato un algoritmo sufficientemente complesso e caratterizzato da importanti vantaggi quali:

1. E' di dominio pubblico
2. La decodifica è interamente legata alla chiave
3. E' sufficientemente resistente ad un attacco esaustivo mediante calcolatore

La crittografia a chiave pubblica secondo Rivest, Shamir ed Adlemann

Nel 1978, R. Rivest, A. Shamir, L. Adleman, pubblicarono l'articolo "A Method for Obtaining Digital Signatures and Public-key Cryptosystems", destinato dare una soluzione al problema in grado di resistere alla potenza dei calcolatori per parecchi anni a venire. Il metodo di cifratura venne codificato in un algoritmo che prese il nome dalle iniziali dei tre matematici: algoritmo RSA.

Gli algoritmi di crittografia a chiave pubblica, come RSA, sono caratterizzati da una coppia di chiavi dette pubblica e privata. La chiave pubblica va distribuita ai destinatari dei messaggi e la chiave privata va mantenuta segreta dal mittente. Con la chiave privata vengono decodificati solo i messaggi codificati da chi possiede la chiave pubblica corrispondente. Le chiavi sono generate in modo tale che non sia possibile calcolare la chiave privata a partire da quella pubblica.

Supponiamo che due persone, A e B, debbano scambiarsi un messaggio:

1. B genera due chiavi, una pubblica e l'altra privata
2. B mantiene la chiave privata per se e comunica a A la chiave pubblica
3. A codifica il messaggio con la chiave pubblica di B e lo invia
4. B riceve il messaggio da A, e lo decodifica con la propria chiave privata

Prima di descrivere l'algoritmo RSA è necessario un richiamo sull'Aritmetica Modulare.

Supponiamo di avere a disposizione solo n cifre, diciamo 12, e di disporle come in un quadrante di orologio. Applichiamo i concetti di addizione e moltiplicazione usuali, salvo che, al superare il 11, ricominciamo a contare circolarmente da 0.

Nell'aritmetica usuale l'addizione

7 + 8 = 15

diviene, nell'aritmetica modulo 12

7 + 8 = 3 (mod 12)

ci si convince facilmente di ciò osservando il proprio orologio ed assegnando le cifre come da fig. 3

Fig. 3 Aritmetica modulo 12 sul quadrante di un orologio

Così aggiungendo 8 al 7, si arriva al 3.

Nell'aritmetica modulo n la moltiplicazione è definita in modo analogo all'aritmetica ordinaria come:

a*b (mod n) = a+a+a+...<b volte>...+a (mod) n

e lo stesso vale per la potenza

a^b (mod n) = a* <...b volte ...>* a (mod n)

L'algoritmo RSA è quindi definito come segue:

Generazione delle chiavi pubbliche e private

1. Siano p e q due numeri primi molto grandi
2. sia m = (p-1)(q-1)
3. sia n = pq
4. si trovi un numero d non necessariamente grande, relativamente primo ad n
5. si trovi e tale che de = 1 (mod m)
6. la chiave pubblica è la coppia (d,n)
7. la chiave privata è la coppia (e,n)

Codifica di un messaggio M

Il messaggio codificato è C(M) = M^d (mod n)

Decodifica di un messaggio C

Il messaggio decodificato è M (C) =C^e (mod n)

Pur conoscendo il meccanismo di codifica, la decodifica di un messaggio senza conoscere la chiave privata e è un operazione per cui anche il più potente dei calcolatori impiegherebbe secoli, riconducendo a noti problemi intrattabili nella scienza dei calcolatori, infatti:

1. Ignorando la chiave pubblica bisognerebbe calcolare la radice di ordine d , in aritmetica modulo n di M. Problema intrattabile.
2. Anche conoscendo la chiave pubblica d, il calcolo di e implicherebbe la necessità di trovare i numeri primi p e q che, se scelti nell'ordine di 10²⁰⁰, producono di nuovo un problema intrattabile.

Si noti che un algoritmo come RSA può difficilmente divenire obsoleto perché riconduce a problemi la cui tecnica di soluzione è nota, ma coinvolge necessariamente un tempo di calcolo enorme, allo stato attuale della ricerca.

Verità impossibili

Alcuni concetti, dati per scontati e che fanno parte del nostro bagaglio culturale, sono in pratica, impossibili da verificare. Altri, sebbene vengono intuiti sottoposti a ragionamento, crollano nell'impossibilità da definirli.

Vediamone alcuni.

Cos'è per definizione una retta?
"La retta o linea retta è uno dei tre enti geometrici fondamentali della geometria euclidea. Viene definita da Euclide nei suoi Elementi come un concetto primitivo. Un filo di cotone o di spago ben teso tra due punti è un modello materiale che ci può aiutare a capire cosa sia la retta, un ente geometrico immateriale senza spessore e con una sola dimensione. La retta è inoltre illimitata in entrambe le direzioni, cioè è infinita. Viene generalmente contrassegnata con una lettera minuscola dell'alfabeto latino." (da Wikipedia)

Fin qui tutto semplice e comprensibile...
Resta da verificare in pratica la possibilità di disegnarla! Quale uomo, macchina o strumento conosciuto, detiene la capacità di disegnare qualcosa che non ha un inizio e non ha una fine?

Il famoso PI greco
"La costante matematica π (si scrive "pi" dove le lettere greche non sono disponibili) è utilizzata moltissimo in matematica e fisica. Nella geometria piana, π viene definito come il rapporto tra la circonferenza e il diametro di un cerchio, o anche come l'area di un cerchio di raggio 1" (da Wikipedia)

Ottimo, in pratica il rapporto fra la circonferenza e il diametro: come si calcola la circonferenza? 2rπ ovvero il diametro per PI greco!
Insomma un paradosso. Continuando si legge che a questo numero si arriva per sperimentazione, calcolando n poligoni ecc., ecc.

Tutto basato su pura immaginazione: Quale strumento può concretamente misurare al decimale infinitesimo un raggio? Costruendo una circonferenza con una corda di misura nota, cosa fare per verificare nella pratica quale sia il raggio?

Eppure il mondo è basato su questi concetti. Tutto si regge su questi calcoli. Questo non deve stupire. L'incredibile è che pare funzioni... Finchè si è in vita chiaro. Poi?... bhe la scienza non risponde a cosa succede della coscienza quando il corpo fisico cessa di funzionare. Reputa questo problema assurdo ed illogico. (!) Perchè quanto sopra è dimostrabile in pratica? O lo è solo per via matematica, immaginaria e delimitata con simboli per rappresentare pensieri?

Proviamo ora a raccontare la storia dell'universo.

Humm.. e da dove s'inizia? Per quanto si cerchi di dare un punto di partenza, ci si arrende all'evidenza della domanda: "e prima?"

Così per il racconto, come finirlo se sempre ci sarà: "e dopo?"

In pratica tutto è solo una parte, siamo un segmento ci possiamo immaginare un infinito solo come conseguenza di fatti che riportino alla situazione iniziale e ripartire per infiniti giri, sulla stessa ruota.

Molte filosofie descrivono la vita, come un cerchio, ad indicare che il percorso continua, non importa l'inizio o la fine, che tanto si ripete.

Immaginandolo, ci si rende conto che non si può contemplarlo se non distaccandosene. All'interno del cerchio (la nostra vita), non possiamo contemplarlo, assurdamente, lo vediamo da un punto di vista esterno nel quale però dobbiamo accettare il fatto che ne facciamo parte...

Solo Dio può disegnare una retta, solo Dio può misurare una circonferenza; in modo diretto e non per calcolo.

Il problema è che sebbene metta a tacere l'inquietudine dei fedeli e ne sostenga la grandezza, questa affermazione riporta a quanto sopra, con un dilemma ancora più indigesto per la nostra logica, così come la conosciamo. Cos'è Dio?