Stomachion

venerdì 18 novembre 2016

Mondo Matematico: la crittografia

Proseguo con le recensioni/approfondimenti della collana da edicola Mondo Matematico. Dopo il volume sui numeri primi, nella seconda, doppia uscita erano proposti insieme due testi sul teorema di Pitagora e sulla crittografia. Oggi provo a raccontarvi quest'ultimo, un libro indubbiamente interessante e ricco di approfondimenti, sebbene in certi punti scritto da Joan Gomez Urgellés in maniera forse eccessivamente asettica:
Matematici, spie e pirati informatici
La storia della crittografia sembra intimamente legata con lo sviluppo della scrittura: uno dei primi esempi crittografici risale infatti ai babilonesi, con una tavoletta cui mancavano alcune lettere, e non perché si sono persi a causa del tempo trascorso (all'incirca 4500 anni fa).
Ad ogni buon conto, si possono clasificare i cifrari dell'antichità in due tipi diversi: per trasposizione e per sostituzione. Il primo si basa sulla trasposizione delle lettere che compongono il messaggio: supponendo che esse siano $n$, il numero di possibili messaggi che si possono comporre è pari a $n!$. Unico elemento che fece cadere in disuso il sistema era la difficoltà nel poter utilizare chiavi semplici per le operazioni di crittazione e decodifica.
Il secondo, che ebbe in Giulio Cesare il suo più noto utilizzatore (tanto che uno dei codici di critazione porta il suo nome) prevede la sostiuzione di ciascuna lettera dell’alfabeto con un’altra fornita grazie alla traslazione dell'intero alfabeto. Dal punto di vista matematico questi ultimi cifrari sono indubiamente i più interessanti, basandosi sulla matematica modulare.
L'operazione di modulo, $a \mod b$, restituisce il resto dela divisione di $a$ per $b$ e introduce una interessante classe di equivalenza (ovvero un sottoinsieme di oggetti di un dato insieme che godono di una stessa proprietà): avere lo stesso resto nella divisione per $b$. Così, per esempio $5 \equiv 14 (\mod 3)$, questo perché sia 5 sia 14 forniscono lo stesso resto quando li dividiamo per 3.
Anche il cifrario di Cesare aveva un punto debole: l'analisi delle frequenze. Come qualunque scherlockiano può dirvi, per ogni lingua si possono determinare le frequenze con cui ciascuna lettera compare all’interno del vocabolario. Così confrontando le frequenze delle lettere (o simboli) presenti nel messaggio da decifrare con le frequenze della lingua in cui si presume che tale messaggio sia stato scritto, è possibile risalire con buona precisione al messaggio originario. Per ovviare all'analisi delle frequenze, Blaise De Vigenère sviluppò l'omonimo quadrato, costituito come segue:
La cifrazione di una frase verrà fatta seguendo una semplice procedura che stabilisce di quanti posti bisogna spostarsi verso il basso per cifrare la prima lettera e a seguire tutte le altre.
Questo cifrario, che sembrava essere inattaccabile, venne alla fine vinto in maniera indipendente l’uno dall’altro da Charles Babbage e Friedrick Krasiski: nel frattempo era, però, arrivata l’era delle macchine, di cui Babbage fu, in un certo senso, uno dei pionieri.
Dalla seconda guerra mondiale all'era moderna
La ricerca di una macchina in grado di cifrare più velocemente e con più efficienza i messaggi segreti venne presa molto seriamente dalla Germania. I tedeschi, in occasione della prima guerra mondiale, avevano sviluppato un codice abbastanza interessante, detto ADFGVX, apparentemente infrangibile e basato parte sula sostituzione e parte sulla trasposizione. A farlo crollare ci pensò il francese George Painvin il 2 giugno del 1918.
La contromossa a questa nuova vittoria dei crittanalisti venne sviluppata da Arthur Scherbius e dalla sua macchina Enigma, brevettata nel 1923. Essa era costituita da un sistema di rotori, continuamente aggiornato, in grado di produrre un numero incredibile di codici basati su 10586916764424000 chiavi. L’avventura della decifrazione di Enigma, che ho avuto modo di raccontare, ha posto le basi per la progettazione dei moderni computer grazie al pionieristico lavoro di Alan Turing.
Se da un lato l'ingresso dei calcolatori artificiali ha permesso una maggiore potenza di calcolo per i crittanalisti, ha anche permesso ai codificatori di sviluppare tecnice di cifratura più raffinate. Le figure che più di tutte hanno giocato un ruolo nella moderna crittografia sono Claude Elwood Shannon del MIT, che oltre a interessarsi di crittografia, ha di fatto fondato la teoria della comunicazione; quindi Whitfield Diffie e Monte Hellman che idearono la base teorica per lo sviluppo dell'algoritmo RSA a chiave pubblica sviluppato da Ron Rivest, Adi Shamir e Len Adelman, basato peraltro sulla fattorizzazione in numeri primi; e infine Phil Zimmermann, che ha sviluppato un algoritmo analogo, il PGP (Pretty Good Privacy), ma dedicato agli utenti privati, in modo da permettere ai cittadini di proteggere la propria privacy contro l’invasività dello stato.
Il futuro della crittografia sembra che sia in questo momento nelle mani delle ricerche sui computer quantistici, che da un lato potrebbero aiutare i decodificatori a rompere i codici crittografici, grazie alla capacità di ridurre il tempo di calcolo con l'uso di appositi algoritmi, dall’altro aiutando anche a costruire codici ancora più inattaccabili, in quella che si prospetta come un'eterno inseguimento.

Nessun commento:

Posta un commento