Come criptare un messaggio: l’esempio del problema dei due re e i numeri primi

La situazione è questa: ci sono due re alleati che si trovano in guerra contro un nemico dotato di spie abilissime: come possono fare per scambiarsi messaggi segreti senza che questi cadano nelle mani del nemico? I grandi protagonisti della risposta a questa domanda sono i numeri primi, cioè quei numeri interi positivi che non hanno altri divisori se non l'1 e se stessi. Ma che cosa c'entrano i numeri primi con due re che vogliono comunicare tra loro in modo sicuro? Risolvendo questo problema scopriremo l’idea chiave alla base di molti protocolli di comunicazione sicura, basata sul fatto che la moltiplicazione di numeri primi molto grandi è un'operazione facile che può essere utilizzata per rendere un messaggio illeggibile, mentre scomporre un numero in fattori primi, cioè cercare di recuperare il messaggio iniziale, può richiedere molto tempo.
Ma in che modo? Lo vediamo in questo articolo.

Il problema dei due re che vogliono comunicare in segreto

Per capire che cosa significa criptare (o cifrare) un messaggio in modo da renderlo illeggibile a qualsiasi persona sconosciuta che lo trovi tra le mani, consideriamo questa situazione di fantasia.

Re Gino deve inviare a Re Pino,  senza che venga intercettato dalle abilissime spie nemiche, un messaggio vitale per le sorti dei due regni. I fabbri dei due Re sanno realizzare bauli e lucchetti indistruttibili, impossibili da aprire senza chiave. Re Gino mette il messaggio in un baule, lo chiude con un lucchetto e lo invia a Re Pino. Se durante il viaggio il baule venisse intercettato da una spia non potrebbe essere aperto, ma neppure Re Pino potrebbe aprirlo senza chiave. Re Gino potrebbe allora inviare a Re Pino la chiave separatamente dal baule, ma una spia potrebbe intercettare sia chiave che baule e così aprirlo: la chiave non può viaggiare, è troppo pericoloso! E quindi, come rendere il baule non apribile per le spie, ma apribile da Re Pino?

Per trovare una risposta a questa domanda, dobbiamo pensare a una chiave particolare, cioè i numeri primi.

Il lungo viaggio del messaggio: come renderlo segreto per tutti ma non per i due Re?

I due Re si rendono conto che inviarsi una chiave fisica è rischioso, e così ideano lo stratagemma dei due lucchetti:

1. Re Gino mette il messaggio nel baule, lo chiude con un lucchetto rosso di cui solo lui ha la chiave e invia il baule così serrato a Re Pino
2. Re Pino riceve il baule e rafforza la sua chiusura con un secondo lucchetto blu di cui solo lui ha la chiave, e lo rinvia a Re Gino ben chiuso con i due lucchetti
3. Re Gino a questo punto toglie il lucchetto rosso dal baule usando la sua chiave e lo rinvia a Pino. A questo punto il baule è ancora chiuso con il lucchetto blu, di cui Re Pino ha la chiave!
4. Re Pino riceve il baule e, avendo la chiave giusta, toglie il lucchetto blu, riuscendo così ad aprire il baule e leggere il messaggio segreto.

Il messaggio parte da Re Gino ed arriva e Re Pino ben nascosto dentro il baule senza che nessuna spia possa leggerlo, perché le due chiavi necessarie per la lettura del baule sono sempre rimaste al sicuro nelle mani dei due Re!
Possiamo dire che il messaggio è stato infatti cifrato, come direbbe chi si occupa di crittografia, la disciplina che studia come trasformare un messaggio in chiaro – cioè chiaramente leggibile – in un altro messaggio cifrato – cioè contraffatto – così che risulti incomprensibile a chi non conosce i dettagli della tecnica usata per la trasformazione.

A questo punto viene da chiedersi: ma cosa c'entrano i numeri primi?

I numeri primi sono un'ottima chiave segreta per nascondere un messaggio

Quello che abbiamo appena visto era, chiaramente, un esempio di fantasia in cui per "serrare" un messaggio abbiamo utilizzato dei lucchetti. Nella pratica come facciamo ad allucchettare un messaggio, considerato che i canali che utilizziamo per comunicare sono digitali e non fisici? Un baule e due lucchetti non sono sufficienti.
Lo scambio di messaggi digitali – come sms o WhatsApp – avviene sostanzialmente sotto forma di sequenze di numeri. Ad esempio la parola “ciao” potrebbe viaggiare come “39115”, dove ogni lettera è stata sostituita dalla sua posizione nell’alfabeto. È chiaro però che una cifratura del genere è molto facile da decifrare: abbinando a ogni numero della sequenza la lettera dell'alfabeto corrispondente, abbiamo tre ipotesi possibili: 3-9-1-1-5 che corrisponde a ciaae, 3-9-1-15 che corrisponde a ciao,  oppure 3-9-11-5 cioè cike. Non è difficile intuire che la parola inviata sia la seconda ipotesi, cioè ciao.

Va pensato quindi qualcosa di più complesso: non solo quindi abbinare numeri a lettere, ma fare determinate operazioni su questi numeri. Cerchiamo di capirlo con un esempio.

Supponiamo che il nostro messaggio segreto sia il numero sia la lettera F a cui abbiniamo il numero 6. Per camuffare il messaggio, possiamo moltiplicarlo per un numero segreto che decidiamo – detto chiave – così da ottenere un ulteriore numero. Scegliamo per esempio il numero 5, che moltiplicato per il nostro messaggio 6 dà come risultato il numero 30, che sarà il nostro messaggio cifrato. Se una spia intercettasse il numero 30, non conoscendo la chiave, avrebbe difficoltà a riconoscere il messaggio segreto perché non sa di dover dividere per 5 ottenendo così 6 e infine la lettera F. Tuttavia potrebbe immaginare che abbiamo ottenuto il numero tramite un'operazione semplice e dopo qualche tentativo arriverebbe con ogni probabilità a intuire che si tratti di una moltiplicazione e, scrivendo tutti i prodotti che danno 30 come risultato, otterrebbe: 6×5, 2×15, 3×10, 2x3x5, 30×1. La spia a questo punto non saprebbe quale è esattamente il messaggio, ma avrebbe sicuramente ristretto le possibilità: sa che si tratta di un numero tra 1, 2, 3, 5, 6, 10, 15, 30. Insomma, moltiplicare per 5 sembra non essere una tattica poi così impenetrabile. Come fare quindi?

È qui che entrano in gioco i numeri primi: scomporre un numero come prodotto di numeri è tanto più difficile quanto più grandi sono i numeri primi che lo compongono. Se invece del numero 5 usassimo come chiave un numero primo enorme, per la nostra spia scomporre il numero potrebbe diventare un compito talmente arduo e lungo da farla desistere.

Dal baule ai numeri primi: cosa avrebbero fatto dei Re digitali

Torniamo ora alla storia dei due Re e cerchiamo di capire meglio come i numeri possono sostituire i due lucchetti con due chiavi numeriche segrete, ognuna delle due nota solo al Re che la possiede. Immaginiamo che Re Gino e Re Pino vivano ai giorni nostri ed usino quindi il digitale. Cosa potrebbero fare per fregare le spie? Potrebbero ad esempio fare così:

1. Re Gino cifra il messaggio 6 moltiplicandolo per la prima chiave numerica, ad esempio 5 (utilizziamo per comodità un numero primo piccolo, ma come abbiamo accennato sopra la scelta migliore è quella di utilizzare un numero primo enorme!); una volta cifrato, invia 6×5=30 a Re Pino;
2. Re Pino moltiplica 30 per la seconda chiave personale, ad esempio 7, ed invia 30×7=210 a Re Gino;
3. Re Gino toglie il suo "lucchetto" dividendo 210 per la prima chiave, cioè 5, ed invia 42 a Re Pino;
4. A questo punto Re Pino può decifrare completamente il messaggio con la seconda chiave, dividendo 42 per 7  e ottiene il messaggio di partenza: 6.

Nell'immagine sopra si può vedere come il messaggio 6 parta da Re Gino ed arrivi a Re Pino senza mai essere visibile dato che viaggia sempre nascosto, prima dentro il numero 30, poi nel 210 ed infine nel 42.

Molti protocolli di comunicazione – cioè i processi che vengono utilizzati per rendere i messaggi che usiamo il più sicuri possibile – si basano su soluzioni simili a quella adottata dai due Re digitali e, anche se cifrano i messaggi con operazioni più complicate rispetto alla semplice moltiplicazione, utilizzano comunque il prodotto di numeri primi molto grandi. Uno dei più diffusi si chiama RSA e venne reso pubblico nel 1977 tramite una sfida che prevedeva la scomposizione in fattori primi di un numero di 129 cifre: solo nel 1994 una squadra di 600 volontari riuscì a completare la sfida, dopo ben 17 anni, un tempo che avrebbe fatto desistere qualsiasi spia!

non perderti questo video

Non è vero finché non viene dimostrato: cosa sono le verità matematiche