Pensate al vostro ultimo acquisto online: avete visto un prodotto che vi piaceva, avete soppesato un po’ le recensioni, la possibilità di cercarlo in negozio, e alla fine avete cliccato sul pulsante “aggiungi al carrello”. Procedendo, vi siete trovati in una pagina in cui vi è stato chiesto di inserire i vostri dati (per i più, i dati della carta di credito), e, una volta confermati, avete autorizzato il pagamento utilizzando un’app sul vostro cellulare o inserendo un numero che avete ricevuto per messaggio. Ora, soddisfatti, state pregustando l’arrivo del pacco con un nuovo libro, un nuovo elettrodomestico o un inutile set per giocare a minigolf dal gabinetto di casa.

A pensarci bene in quello che avete fatto c’è qualcosa di miracoloso. Le informazioni che permettono di accedere al vostro conto in banca viaggiano sulla rete da voi al venditore, passando per la vostra banca, e in qualche modo, a parte rare e sfortunate eccezioni, i pagamenti vanno a buon fine senza disagi per nessuna delle parti coinvolte. Se vi chiedessero di trasmettere le stesse informazioni a voce o per lettera, probabilmente vi sentireste meno sicuri.

Alla base dei protocolli che garantiscono la sicurezza di queste operazioni informatiche c’è la crittografia, la scienza dei messaggi nascosti, il cui obiettivo è comunicare informazioni riservate senza che queste possano essere lette da terzi non autorizzate. La storia della crittografia ha radici antiche, molto precedenti all’invenzione dei computer e la si può ritrovare nei cifrari usati dai Romani, nella celebre Enigma utilizzata dai tedeschi durante la Seconda guerra mondiale, fino ai “pizzini” scambiati dai mafiosi e venuti alla luce nella cronaca contemporanea.

Tutto questo può fare apparire la crittografia come una costruzione solida e concreta: a suo favore ci sono millenni di storia umana e il sistema economico globale, che si affida in gran parte ai miliardi di transazioni online eseguite ogni giorno. Ciò che ai più non è noto è che per matematici e informatici la questione non è così semplice: l’esistenza stessa della crittografia, seppur ragionevole, non è una certezza, ma un’ipotesi. Il Black Friday, la digital finance, l’home banking e tutta una serie di nomi importati dall’inglese e popolarizzati negli ultimi vent’anni, si basano sull’assunzione che “P sia diverso da NP”. Peccato, che questa non sia mai stata provata.

In questo articolo, raccontiamo in cosa consiste questo problema, perché la crittografia si basa su di esso e quali scenari si aprirebbero se questo ammettesse una soluzione diversa da quella che ci aspettiamo. Ci sentiamo però di rassicurarvi: i matematici sono esseri puntigliosi, che senza una dimostrazione formale non danno niente per vero. Anche loro però ammettono che tutto sembra puntare verso la conferma dell’esistenza della crittografia. Alla luce di ciò, unito a qualche migliaio di anni di esperienza umana in questa disciplina, ci sentiamo di dire che potete continuare a fare acquisti online in tutta tranquillità!

Problemi speciali

La crittografia che oggi usiamo per gli acquisti online prende il nome di “crittografia a chiave pubblica”. Non si tratta di un semplice nascondere un messaggio con un codice concordato tra noi e un destinatario, ma un meccanismo leggermente più sofisticato. Possiamo immaginare che il destinatario, per esempio il venditore online, possieda due chiavi, una pubblica e una privata. Quella pubblica è visibile a tutti, e una volta criptate (cioè, nascoste) delle informazioni usando la chiave pubblica, l’unico modo per leggerle è usando la chiave privata, accessibile solo al venditore. In questo modo i nostri dati di pagamento, una volta criptati dalla chiave pubblica, saranno visibili solo a chi è in possesso della chiave privata.

Perché questo meccanismo sia sicuro, la chiave privata deve godere di particolari proprietà matematiche che possono essere riassunte dicendo che “la chiave privata dev’essere la soluzione di un problema difficile da risolvere, ma facile da verificare”.

Per spiegare cosa questo voglia dire immaginate di avere un grafo, ovvero un insieme di punti collegati da segmenti, e di voler trovare un percorso che passi da tutti i punti esattamente una volta. Trovare una soluzione per questo problema, specialmente se i punti e i segmenti sono tanti, è molto difficile: provare per credere. Se però vi viene dato un percorso, è relativamente facile verificare se questo risolve il problema: basta seguirlo e vedere se passa per ogni punto esattamente una volta. Per questo, il problema del Cammino Hamiltoniano è considerato di difficile soluzione ma facile verifica, proprio come quelli usati per generare le chiavi private in crittografia.

Questo problema evidenzia due aspetti interessanti. Il primo è il fatto che i concetti di “facile” e “difficile” sono legati in qualche modo alle dimensioni del problema, cioè, nel nostro caso, al numero di punti e segmenti con cui abbiamo a che fare. Trovare il percorso può sembrare “facile” se si considerano pochi punti uniti da pochi segmenti, ma al crescere di questi numeri diventa velocemente “difficile”. In un certo senso, consideriamo il problema difficile, non perché sia sempre difficile risolverlo, ma perché la sua difficoltà cresce molto velocemente al crescere della dimensione del problema.

Un secondo aspetto su cui soffermarsi è il fatto che consideriamo il problema difficile perché non conosciamo un modo per risolverlo velocemente. Esistono tanti problemi per cui trovare una soluzione è apparentemente difficile e richiede molto tempo, ma per cui, usando qualche trucco particolarmente furbo, la soluzione diventa facilmente accessibile. Se chiedessimo a uno studente che non sa fare le divisioni “Qual è il numero che moltiplicato per 7 dà 147?” questo dovrebbe provare a moltiplicare tutti i numeri per 7 finché non ne trova uno corretto. Se però impara a fare le divisioni è immediato rispondere che la risposta è 147/7=21. Allo stesso modo chi ci dice che non esiste un’operazione “furba” che ci consenta di trovare il cammino rapidamente? Magari gli informatici fino ad oggi sono solo stati troppo pigri o troppo poco furbi per trovarla.

In realtà la situazione è molto più complessa di così, e per capire in cosa consistono questi problemi speciali da cui la crittografia dipende in maniera vitale dobbiamo immergerci in una branca dell’informatica che prende il suggestivo nome di teoria della complessità computazionale.

Quanto sei complesso?

La teoria della complessità computazionale nasce per rispondere alla domanda: quanto è difficile risolvere un problema? Come potete immaginare, rispondere non è per niente semplice, e ce lo confermano anche i teorici della teoria della meta-complessità, che si pongono la domanda di quanto sia difficile rispondere alla domanda su quanto sia difficile risolvere un problema, ma questo ulteriore gradino di astrazione lo lasceremo per un altro articolo.

I problemi a cui ci rivolgiamo sono i problemi computazionali, cioè quelli per cui esiste un algoritmo, ovvero una lista finita di istruzioni, che permette di giungere a una soluzione, quindi problemi per cui sappiamo che una soluzione esiste, e sappiamo come arrivarci.

Se prima, parlando del problema del Cammino Hamiltoniano ci siamo concentrati sugli aggettivi “facile” e “difficile”, adesso possiamo tradurre questi aggettivi in algoritmi “veloci” e “lenti”. Un problema facile avrà un algoritmo veloce per la sua soluzione, un problema difficile avrà un algoritmo lento. Parlare di velocità dell’algoritmo ci consente di essere più precisi, perché è una quantità che possiamo calcolare direttamente, a differenza della difficoltà di un problema.

In questo modo, possiamo distinguere due famiglie di problemi particolarmente importanti. Da un lato, i problemi facili, cioè per cui esiste un algoritmo che li risolve velocemente, che chiameremo problemi P; dall’altro, la nostra classe di problemi speciali: i problemi di difficile soluzione ma di facile verifica, cioè problemi per cui non esiste un algoritmo che li risolve velocemente, ma per cui esiste un algoritmo che verifica velocemente se la soluzione è corretta. Questi problemi si chiamano NP, e di questa classe fanno parte il problema del Cammino Hamiltoniano e i problemi usati per generare le chiavi private nella crittografia a chiave pubblica. Esistono anche problemi che non sono né P né NP ma non ne parleremo in questo articolo.

Come avevamo osservato prima non è scontato dire che un problema sia difficile, o equivalentemente, che non esista un algoritmo veloce che lo risolve. In fondo nuovi algoritmi vengono continuamente scoperti, a volte dopo che per decine di anni ne è stato usato uno più lento. Se però sappiamo che esiste un algoritmo veloce per risolvere un problema, questo è sicuramente un problema P. Inoltre, per alcuni problemi si può dimostrare che per questi non esiste nessun algoritmo veloce né per verificare se una soluzione è corretta, e questi problemi non sono né P né NP. Per molti problemi però non abbiamo certezze: magari abbiamo un algoritmo lento per risolverli e uno veloce per verificarne la correttezza, ma non riusciamo a dimostrare che non esiste un algoritmo veloce per la loro soluzione. Questi problemi potrebbero essere un problema sia P che NP.

Il dilemma crittografico

Riepilogando: per la crittografia servono problemi di difficile soluzione ma facile verifica, cioè problemi NP. Ma ora, allacciatevi le cinture, perché arriva il colpo di scena: i problemi NP potrebbero non esistere! La crittografia dietro tutte le transazioni online che avvengono ogni giorno si basa sulla fiducia nel fatto che nessun hacker sia abbastanza bravo da risolvere un problema NP con un algoritmo veloce. Tuttavia, il fatto che sia impossibile trovare un tale algoritmo veloce, non è mai stato dimostrato, per nessun problema NP.

Questo problema, noto come P ≠ NP (P diverso da NP), tiene matematici e informatici impiegati dal 1971. Per quanto ne sappiamo ogni problema NP che conosciamo, potrebbe essere un problema P, semplicemente non siamo abbastanza bravi da trovare il modo per risolverlo velocemente.

Ma c’è di più: per una larga classe di problemi NP, detti NP-completi, se venisse mostrato che questi sono in realtà P, si potrebbe mostrare che tutti i problemi NP sono in realtà P. In questo caso P e NP sarebbero la stessa famiglia di problemi, cioè P=NP, e la crittografia così come la utilizziamo oggi, non sarebbe più utilizzabile. In pratica, un hacker che vuole fare collassare la finanza digitale non deve necessariamente cercare di risolvere i problemi specifici dietro le chiavi private, basta che risolva un problema NP completo, per mostrare che qualunque problema NP utilizzabile dalla crittografia è in realtà un problema P. Collasso totale e nessuna possibilità di riscatto, al prezzo di un singolo problema da risolvere!

La vita a Cryptomania

In realtà se dimostrare che P=NP distruggerebbe ogni possibilità di esistenza della crittografia è anche vero che dimostrare P≠NP non risolverebbe del tutto il problema. Un modo divertente di sintetizzare la situazione è stato proposto da Russell Impagliazzo, un informatico americano, nel 1995. Esistono 5 mondi possibili: in uno di essi, Algoritmica, P è uguale a NP e la crittografia così come la conosciamo, non esiste. In altri tre, Heuristica, Pessiland e Minicrypt, P è diverso da NP, ma la crittografia a chiave pubblica continua a non esistere. Solo nel quinto mondo, Cryptomania, P è diverso da NP ed esiste la crittografia a chiave pubblica.

Se vi state già muovendo per rimuovere i vostri dati di pagamento da tutti i servizi online, vi preghiamo di fermarvi. In realtà, matematici e informatici sono abbastanza convinti che NP sia diverso da P, solo che questo stesso è un problema molto difficile da risolvere (ecco che si inciampa di nuovo nella meta-complessità). Se questo fosse confermato, potremmo considerarci definitivamente fuori da Algoritmica. Ma sviluppi recenti portano a pensare che anche Heuristica e Pessiland potranno essere eliminate dalla lista dei mondi possibili. Rimarrebbero Minicrypt, in cui almeno una parte della crittografia esisterebbe, e Cryptomania, il mondo così come lo conosciamo.

Insomma, anche se non ne abbiamo la certezza matematica, abbiamo ottime ragioni per credere di vivere a Cryptomania. Dunque, benvenuti nel mondo della crittografia possibile, speriamo che il vostro set da minigolf arrivi al più presto!