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

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 264, ulteriormente ridotto a 256 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

ab
(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) = Md (mod n)

Decodifica di un
messaggio C

Il messaggio
decodificato è M (C) =Ce
(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 10200, 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.