Scienze & Tecnologia

96001, 96013, 96017, 96043, 96053… I numeri primi: codici segreti

di Angelo Nardone

crittografia-gestione

Nel 1903 Frank Nelson Cole, professore di matematica alla Columbia University di New York, tenne una conferenza assai curiosa. Cole scrisse su una lavagna uno dei numeri di Mersenne (numeri scritti in forma “2x-1”, che arrivano facilmente a formare cifre molto grandi). Sulla lavagna accanto scrisse due numeri più piccoli e li moltiplicò. In mezzo piazzò un segno di uguaglianza. Dopodiché si sedette, il tutto senza pronunciare una parola.

267-1 = 193.7070721 x 761.838.257.287

Il pubblico si alzò in piedi ad applaudirlo, colto da un’esplosione di entusiasmo rara per un convegno matematico. Eppure moltiplicare due numeri non era così difficile, neanche per i matematici di inizio secolo. O no? Il fatto è che Cole aveva compiuto l’operazione opposta. Già da tempo si sapeva che 267-1 non era un numero primo, ma nessuno sapeva le due cifre che si dovevano moltiplicare per comporlo. A Cole occorsero tre anni di “pomeriggi domenicali” per scoprirle.

Non fu solo il pubblico del 1903 ad apprezzare la sua impresa. Nel 2000, un esoterico spettacolo off-Broadway intitolato Il teorema delle cinque ragazze isteriche rese omaggio a quel calcolo facendo risolvere a una delle ragazze il problema della fattorizzazione di Cole. Nessuno però poteva pensare che da questa conferenza sarebbe scaturita l’idea che sta alla base della sicurezza di internet. Infatti ogni volta che si procede ad un acquisto in rete si attiva un sistema sicurezza che non permette agli hacker di riuscire a raggiungere i nostri dati, ad esempio il codice di sicurezza della nostra carta di credito con cui abbiamo effettuato il pagamento. Fulcro di questo sistema di sicurezza sono ancora i numeri primi.

Decifrare codici

«Se Gauss fosse vivo oggi, sarebbe un hacker» [Peter Sarnak]

Da quando siamo stati in grado di comunicare, abbiamo avuto la necessità di recapitare messaggi segreti. Già i nostri progenitori, per impedire che importanti informazioni cadessero in mani sbagliate, escogitarono sistemi complessi con cui mascherare il contenuto di un messaggio. Uno dei più antichi metodi usati per nascondere messaggi fu ideato dall’esercito di Sparta più di duemilacinquecento anni fa. Il mittente e il destinatario dei messaggi possedevano entrambi uno scitale, un sottile cilindro di legno di dimensioni perfettamente identiche. Per cifrare un messaggio, per prima cosa il mittente avvolgeva attorno al cilindro una sottile striscia di pergamena. Quindi scriveva il messaggio sulla pergamena seguendo la lunghezza dello scitale. Quando si srotolava la pergamena, il testo del messaggio appariva senza senso. Riacquistava la sua forma originale solo quando veniva arrotolata attorno allo scitale identico posseduto dal destinatario. Da allora le forme crittografiche si sono evolute, inventando metodi sempre più sofisticati. L’ultimo e più raffinato congegno meccanico per la cifratura di messaggi fu Enigma, la macchina usata dalle forze armate tedesche nel corso della seconda guerra mondiale. Con l’avvento dei computer e internet si è iniziato a comunicare con luoghi sempre più lontani e in tempi brevissimi. Le informazioni che passano per la rete, però, non sono affatto sicure. Per questo si sono dovuti ideare nuovi sistemi di sicurezza elettronici.

Sistemi di sicurezza moderni: crittosistemi a chiave privata

«Propongo di considerare la questione: “Le macchine possono pensare”». Alan Turing

Tutti i sistemi di codice moderni si servono di calcolatori. Se si inviano delle informazioni segrete attraverso i moderni sistemi di comunicazione si deve presumere che il nemico possegga potenti mezzi elettronici per analizzare il messaggio. L’obiettivo di un sistema di sicurezza è resistere ai potenziali nemici facendo in modo che le informazioni siano cifrate (rese segrete) nella maniera più robusta possibile. Come nel caso di una cassaforte che protegge il suo contenuto, i sistemi di sicurezza elettronici devono basarsi su un programma di crittografia che non possa essere facilmente “scassinato”. L’unico modo per entrare in possesso del messaggio originale deve prevedere di essere a conoscenza della chiave di accesso al programma allo stesso modo in cui per poter acceder al contenuto di una cassaforte bisogna conoscerne la combinazione (fig. 1.1).

Immagine2Figura 1.1: Un tipico sistema di codice moderno. I sistemi tradizionali impiegano la stessa chiave sia per la codifica che per la decodifica.

Nei crittosistemi a chiave privata, il mittente e il destinatario si accordano preventivamente sulla chiave segreta che verrà usata poi per codificare e decodificare messaggi. Finché questa chiave rimane segreta il sistema, se ben strutturato, dovrebbe essere sicuro. A tal fine, la soluzione è usare numeri molto grandi in maniera tale da ridurre la probabilità che un potenziale nemico possa individuare la sequenza giusta. Ad esempio, il sistema DES (Data Encryption Standard), affermatosi all’inizio dell’era informatica, utilizzava come chiave un numero di 56 cifre in rappresentazione binaria (per intenderci una lista di 56 zeri e uno). Per poter trovare la combinazione giusta il “nemico” dovrebbe provare tutte le 256 potenziali chiavi, un numero tale da rendere l’impresa virtualmente impossibile.In realtà un numero del genere non è ancora sufficientemente grande da essere assolutamente sicuro, ma in qualunque sistema cifrato si deve accettare un compromesso tra la sicurezza e la convenienza per l’utente. Più grande è la chiave, più è ingombrante il processo.

Tutto okay, quindi? No. Perché, vi chiederete. Semplice. Il vero problema dei crittosistemi a chiave privata consiste nel fatto che il mittente e il destinatario si devono incontrare, oppure servirsi di un corriere fidato, per accordarsi sulla chiave da utilizzare. Un tale sistema quindi non è opportuno per comunicazioni fra individui che non si conoscano già. In particolare, non si presta per scambi internazionale in campo bancario o commerciale. Quest’ultimo limite. Particolarmente rilevante, viene aggirato con la nascita della crittografia a chiave pubblica, un nuovo sistema in codice che ha rivoluzionato il mondo dei sistemi elettronici di sicurezza.

La crittografia a chiave pubblica

«La “vera” matematica, dei “veri” matematici, quella di Fermat, di Eulero, di Gauss, di Abel e di Riemann, è quasi totalmente inutile» [Hardy G.H.]

Quante volte anche voi avete pensato quello che ha sempre sostenuto Hardy (uno dei più importanti matematici inglesi della storia). Dopotutto «non è possibile giustificare la vita di nessun vero matematico sulla base dell’utilità del suo lavoro». Eppure Hardy non avrebbe potuto sbagliarsi di più. La matematica di Fermat, di Gauss, la matematica di cui si occupava proprio lui, era destinata a diventare uno strumento fondamentale per il mondo del commercio. Oggi la sicurezza del villaggio elettronico dipende interamente dalla nostra comprensione dei numeri primi.

Tutto parte con la nascita della crittografia a chiave pubblica. La differenza fra questa e quella a chiave privata, sta nel fatto che nel nuovo sistema di sicurezza non è più richiesta un’unica chiave, ma bensì due: una per cifrare e l’altra per decifrare. La chiave di codifica sarà pubblica mentre quella di decodifica sarà detenuta solo dal destinatario. In questo modo, una volta codificato il messaggio neanche il mittente sarà più in grado di decifrarlo. La rivoluzione principale di questo metodo è nel permette scambi fra persone che non si conoscono, senza che prima si incontrino per accordarsi sulla chiave da utilizzare.

Tutto questo in teoria, ma come costruire, in pratica, un tale sistema? E cosa c’entrano, in tutto questo, i numeri primi? Beh, mettere in pratica un sistema del genere è molto difficile, per questo spiegherò solo i caratteri generali del funzionamento. Tutto si basa sulla constatazione che se da una parte è relativamente semplice trovare numeri primi grandi, diciamo nell’ordine delle 50 cifre, e di moltiplicarne due per ottenere un numero composto di un centinaio di cifre, dall’altra è assai complesso scomporre tale numero nei suoi fattori primi (si noti che un numero composto dalla moltiplicazione di due numeri primi può essere scomposto solo trovando quei due numeri primi). Ed ecco che si torna nel 1903, alla conferenza tenuta da Cole. Per trovare i fattori di 267-1 lui aveva impiegato tre anni. Scomporre un numero di 100 cifre invece è praticamente impossibile.
Questa è l’idea che sta alla base del sistema a chiave pubblica maggiormente diffuso oggi, il sistema RSA, dalle iniziali dei suoi ideatori Ronald Rivest, Adi Shamir e Leonard Adleman (fig.1.2).

 Immagine3Figura 1.2: Adi Shamir, RonRivest e Leonard Adleman

La chiave segreta di decodifica consiste in due grandi numeri primi scelti con l’aiuto del computer. La chiave pubblica di codifica invece è il prodotto di questi due numeri primi. Dato che non esiste un metodo veloce di scomposizione di grandi numeri risulta impossibile recuperare la chiave di decodifica dalla chiave pubblica di codifica.

In realtà, il sistema è un po’ più complesso di come è stato descritto. Per poterlo comprendere al meglio occorre un minino di conoscenze matematiche, tutte peraltro note già al tempo di Fermat. Eventualmente, di seguito si propone anche una lista di letture utili per chi volesse approfondire l’argomento.

Aldilà di questo, però, resta il punto di aver dimostrato (nella maniera meno criptica possibile, si spera) il ruolo che giocano la matematica e, in particolare, i numeri primi nel garantire la sicurezza delle grandi reti internazionali dei nostri giorni.

Per approfondire:

Marcus DuSautoy, “L’enigma dei numeri primi”, Rizzoli, Milano, 2004.

Simon Singh, “Codici e segreti”,Rizzoli, Milano, 1999.

Keith Devlin, “Dove va la matematica”, Universale Bollati Boringhieri, Torino, 2013.

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...