Perché i numeri primi sono intimamente connessi con i metodi di puntamento (dalle testine dei cd-rom ai radar) e con la crittografia?
(risponde Carlo Consoli)

Breve storia della crittografa

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.