Alan Turing, la crittografia e i numeri primi

La disciplina della crittografia deve il suo nome ai vocaboli greci kryptos (nascosto) e graphein (scrittura) e si occupa di trasmettere messaggi tra due persone (o enti) in modo tale che il messaggio stesso sia inintelligibile a terzi. È una materia studiata fin da tempi antichissimi, essendo evidente la sua importanza in campo militare e diplomatico. Alcuni esempi storici sono la scìtala lacedemone, il metodo di Cesare, il disco cifrante di Leon Battista Alberti, il codice di Vernam e le famose macchine utilizzate nella Seconda Guerra Mondiale: Enigma e Purple.

La storia del contributo dato da Marian Rejewski e Alan Turing alla violazione del crittosistema Enigma è oggi ben nota. Esempi di crittogrammi (testi cifrati contenenti informazioni, da ottenere per poter poi compiere una determinata azione o scelta) sono anche stati usati in letteratura; ricordiamo il Viaggio al centro della Terra di Jules Verne, Lo scarabeo d’oro di Edgar Allan Poe e I pupazzi ballerini di Arthur Conan Doyle.

Fino quasi alla fine degli anni Settanta del secolo scorso la crittografia prevedeva che la comunicazione tra due utenti potesse essere stabilita in modo confidenziale e sicuro solamente nel caso in cui essi condividessero un ben determinato parametro, detto chiave crittografica, la cui conoscenza era essenziale sia per poter cifrare (ossia passare dal testo in chiaro a quello codificato) che per decifrare (ossia eseguire il procedimento inverso).
Per esempio, nel metodo di Cesare la chiave è il numero di posizioni in cui l’inusuale alfabeto va spostato in avanti (se la A va in D, la B va in E, ecc, la chiave è il numero 3) mentre nel caso della scìtala, la chiave è il diametro del bastone utilizzato per avvolgere su di esso la striscia di cuoio su cui va scritto il messaggio da inviare. Tutti questi metodi, però, richiedevano che gli utenti si accordassero a priori sulla chiave da utilizzare per poi non comunicarla mai a nessun altro.

Nel 1978 Leonard Adleman, Ronald Rivest e Adi Shamir separarono il ruolo della chiave di cifratura da quello della chiave di decifratura costruendo un metodo, detto RSA, in cui è necessario che la chiave da utilizzare per inviare un messaggio all’utente A (la chiave di cifratura di A) sia pubblicamente dichiarata da A stesso e che solo il parametro necessario per decifrare (la chiave di decifratura di A) vada mantenuto segreto, ossia noto al solo A. Non solo: violare il sistema, ossia ottenere la chiave di decifratura (segreta) a partire dalla conoscenza della chiave di cifratura (pubblica), venne a essere legato alla capacità di risolvere in breve tempo un problema matematico di estrema difficoltà.

Ebbene, questa vera e propria rivoluzione nelle fondamenta della crittografia si basava su un teorema di Euler-Fermat della prima metà del Settecento e sul fatto che sia computazionalmente facile generare numeri primi grandi (a oggi sono noti algoritmi molto efficienti che permettono di generare, con calcoli della durata di pochi secondi su un comune computer, due primi distinti aventi almeno 300 cifre ognuno) ma sia estremamente difficile determinare almeno un fattore di interi grandi accuratamente scelti. Se n=pq con p, q primi aventi circa 300 cifre, si stima che sia necessario, allo stato attuale delle conoscenze, un tempo di calcolo di circa un migliaio di anni per fattorizzare n.

Legando la capacità di violare il sistema RSA a quella di fattorizzare tali interi grandi, Rivest, Shamir e Adleman consentirono lo sviluppo di una serie di applicazioni che sono ormai parte della vita di tutti i giorni e che utilizziamo quasi senza rendercene conto. Possiamo infatti dire che effettuare transazioni elettroniche sicure o firmare digitalmente un documento è ora possibile (anche) grazie ai numeri primi.