La matematica degli 007

Crittografia

di Angelo Guerraggio

Solo il destinatario potrà capire; a lui toccherà il compito di decifrare (o decrittare) il messaggio ricevuto in modo da risalire a quello vero, “in chiaro”.  La crittografia è quella disciplina, una vera e propria scienza, che cerca di escogitare sistemi per cifrare e decifrare messaggi riservati: il termine viene dal greco cryptòs che significa “seppellito”, nel senso di “nascosto sotto”.

La crittografia viene da lontano. Risale addirittura all’antica Grecia e all’esercito spartano. Famoso è rimasto il cifrario additivo usato da Giulio Cesare nella guerra contro i Galli nel 58 a. C., che vede l’esordio di un algoritmo di sostituzione delle lettere cifrate a quelle in chiaro. Il cifrario di Cesare usa una traslazione: ogni lettera dell’alfabeto viene spostata in avanti di un certo numero di posti. Per esempio, se si spostano in avanti le lettere di 2 posti, la a diventa c, la b diventa d, fino alla z che diventa b. Anziché “Veni, Vidi, Vici”, Cesare avrà scritto “Agpm, Amfm, Amem”.

La segretezza di un sistema di cifratura risiede tutta nella segretezza dell’algoritmo di sostituzione, ma trovare quello usato all’interno di sole 21 possibilità come fa il cifrario di Cesare (in realtà 20 perché ovviamente non si considera la sostituzione che ad a associa a, a b ancora b ecc. e che non cifra niente) è fin troppo facile. Occorre allora trovare metodi che diano luogo a un numero decisamente superiore di cifrari ma che conservino la semplicità di un meccanismo che si dovrebbe poter ricordare a memoria, in modo da non lasciare in giro appunti compromettenti.

Un significativo passo in avanti in questa direzione avviene nel Rinascimento con l’introduzione di una parola chiave. La si sceglie senza lettere ripetute (per esempio, la parola libro) e si usano le sue lettere come le prime da impiegare nell’alfabeto cifrato, a partire da un certo posto; le altre seguono in ordine alfabetico, saltando le lettere già usate. Ecco la sostituzione cui si va incontro se si sceglie la parola libro, ad esempio dopo il quinto posto, vale a dire facendo corrispondere la prima lettera l di libro alla sesta lettera dell’alfabeto, cioè f:

a b c d e f g h i l m n o p q r s t u v z
s t u v z l i b r o a c d e f g h m n p q

La chiave, facile da memorizzare, è costituita in questo caso dalla coppia (libro, 5). Siccome non possiamo precisare quante sono le parole chiave, i cifrari sembrano davvero tanti ma, per abili decrittatori, anche assaltare questo fortino rimane relativamente semplice. Conoscono la frequenza con cui le varie lettere dell’alfabeto si ripetono (per esempio, nella lingua italiana quasi tutte le parole terminano con una vocale) e con un certo numero di messaggi, dopo un po’ di congetture e di tentativi, sono in grado di risalire in breve tempo alla chiave. L’analisi statistica delle frequenze è resa possibile dal fatto che la sostituzione impiegata è monoalfabetica ovvero ogni lettera viene cifrata sempre con la stessa lettera. Il successivo passo in avanti si ha allora con le sostituzioni polialfabetiche.

ABBONATI A PRISMA

Già Leon Battista Alberti nel ‘400 conosceva dei cifrari dinamici costituiti da due copie dell’alfabeto collocate sul perimetro di due dischi mobili e in grado, ruotando, di corrispondersi in diversi modi; dopo aver cifrato una lettera del messaggio, basta ruotare uno dei due dischi per cambiare la corrispondenza con cui verrà cifrata quella successiva. Per il destinatario del messaggio è sufficiente conoscere la situazione iniziale dei dischi e la rotazione da effettuare dopo ogni operazione di cifratura.

crittografia

Per esempio, scegliamo di nuovo libro come parola chiave e supponiamo di voler cifrare il messaggio “questa rivista davvero interessante”. Effettueremo allora le seguenti operazioni:

1) sotto il messaggio in chiaro riportiamo la parola chiave, ripetuta quante volte occorre:

crittografia

2) per ogni lettera in chiaro utilizziamo nella successiva tabella la riga indicata dalla corrispondente lettera della parola chiave (per esempio, alla lettera q che apre il messaggio corrisponde la lettera l; per cifrare q, useremo allora la riga del cifrario che inizia con l; in questa riga a q corrisponde la lettera c.

crittografia

Per il messaggio “questa rivista davvero interessante”, abbiamo così trovato la cifratura:

c f f m i a c l p z e d b u p h g f l d t v u v g p d t s c f o.

È su sistemi di questo tipo che si sono sostanzialmente basate, fino all’inizio del secolo scorso, tutte le procedure di cifratura e decifratura realizzate in ambito militare. Anche se le chiavi sono diventate nel frattempo sempre più lunghe e i meccanismi per realizzare l’algoritmo di cifratura sempre più sofisticati, quello che rimane centrale è il problema della trasmissione della chiave in modo che non giunga alle orecchie di chi si vuole intromettere nella comunicazione senza essere autorizzati. Un minimo di prudenza esige che l’informazione relativa alla chiave sia trasmessa prima di ogni altro messaggio in codice, quando chi vuole inserirsi fraudolentemente non si è ancora allertato. I rischi di intercettazione rimangono comunque alti ed è proprio questa valutazione che ha portato all’introduzione della chiave pubblica. Quando i sistemi crittografici erano impiegati all’interno di comunità limitate, si poteva pensare che con opportune cautele la divulgazione della chiave fosse sicura. La situazione è diventata molto più critica in tempi recenti, con una comunicazione elettronica aperta a milioni di utenti: se anche un solo membro di questa grande comunità risulta corrotto, tutti coloro che condividono la conoscenza e l’uso della chiave sono in pericolo.

Per illustrare il funzionamento dei sistemi a chiave pubblica, introduciamo i personaggi di Alice e Bob (con cui spesso sono presentate le procedure della moderna crittografia) e supponiamo che sia Alice a voler mandare a Bob una comunicazione riservata. Il suo messaggio conterrà lettere, numeri e altri caratteri speciali quali punti, virgole, spazi ecc. Seguendo alcune tecniche standard, Alice trasforma il messaggio in una sequenza di 0 e 1 interpretabili come la rappresentazione binaria di un numero m. L’obiettivo di Alice è dunque quello di trasmettere in via assolutamente riservata a Bob il numero m.

Vediamo come Alice e Bob procedono, seguendo il sistema RSA che prende il nome dalle iniziali dei tre informatici e matematici statunitensi del Mit (Ron Rivest, Adi Shamir e Leonard Adleman) i quali pubblicarono il loro primo lavoro sull’argomento nel 1978. Comincia Bob, il quale ha una particolare competenza matematica perché sa calcolare, in corrispondenza a ogni numero intero positivo n, la cosiddetta funzione di Eulero (chiamiamola P) che dice quanti sono i numeri interi positivi minori di n e che non hanno fattori in comune con n diversi da 1.

Il calcolo di P(n) è impossibile, o comunque estremamente lungo e difficile, per valori di n rilevanti, con molte cifre, ma Bob conosce la formula che ne assegna facilmente il valore a partire dalla scomposizione di n in fattori primi. Comunica allora ad Alice la chiave pubblica n – pubblica perché tutti ne possono venire a conoscenza, come se fosse il numero di telefono di Bob – costruita però a partire dalla sua scomposizione in fattori primi.

Facciamo un esempio, naturalmente molto semplice, con numeri piccoli (in realtà, si usano numeri con centinaia di cifre! Nel sistema RSA si usano chiavi pubbliche della lunghezza di 2.048 bit). Bob sceglie di lavorare con il 2 e il 5, li eleva a determinate potenze, diciamo 2 al cubo e 5 al quadrato, 8 e 25, che moltiplica tra loro ottenendo 200. Siccome sa che risulta P(2)=1 (c’è un solo numero minore di 2 e primo rispetto a lui) e P(5)=4 (ci sono 4 numeri minori di 5 e primi rispetto a lui), con la formula in suo possesso calcola P(200) e a questo punto comunica ad Alice la chiave pubblica 200, tenendo sempre riservato il valore di P(200). Alice fa determinate operazioni con il suo m (il messaggio codificato che vuole trasmettere) e con la chiave pubblica 200 ricevuta da Bob, operazioni di cui tutti possono essere a conoscenza, e comunica all’amico il loro risultato. Bob lo riceve, lo decodifica e ricava il messaggio m. Il problema è: perché quello che è riuscito a Bob non riesce a nessun altro, che pure poteva conoscere gli stessi dati e le stesse operazioni, assicurando in questo modo la riservatezza del messaggio inviato da Alice? Il fatto è che nella decodifica interviene P(n) (cioè P(200) nel nostro esempio elementare, valore che solo Bob sa calcolare rapidamente perché aveva costruito n come prodotto di potenze di numeri primi. Chi tenta di introdursi fraudolentemente nella comunicazione tra Alice e Bob conosce n, ma non la sua scomposizione in fattori primi. È facile fare i prodotti, non lo è altrettanto l’operazione inversa della scomposizione in fattori primi. Per questo, il prodotto è detto operazione a senso unico o one way.

Chi l’avrebbe detto che gli “inutili” numeri primi sarebbero stati alla base della sicurezza delle comunicazioni, anche nelle transazioni economiche a distanza e nei sistemi che sono entrati in pianta stabile a far parte della nostra vita quotidiana? Stiamo parlando dei bancomat e del riconoscimento che un istituto di credito opera nei confronti di chi sta prelevando dei soldi da un distributore automatico. Il sistema RSA è di 40 anni fa. Recente, ma non troppo. Così adesso, in alcuni protocolli e in particolare per la firma digitale, l’RSA è stato sostituito dal crittosistema a chiave pubblica Ecc basato sulle curve ellittiche definite su campi finiti – di nuovo un uso avanzato della matematica! – e proposto da N. Koblitz e V.S. Miller nel 1985. Sempre verso la fine del secolo scorso è nata infatti l’esigenza di definire sistemi crittografici resistenti ad attacchi provenienti da computer quantistici, dato che già nel 1994 il matematico P. Shor aveva inaugurato un algoritmo per computer quantistici capace di risolvere il problema della fattorizzazione di grandi numeri interi in tempi ragionevoli (polinomiali). Vita sempre più dura per gli 007.

da Prisma n.9 | Luglio 2019

Condividi