La teoria della casualità potrebbe essere la chiave per la sicurezza di Internet

C’è un codice infrangibile? La domanda è stata fondamentale per la crittografia per migliaia di anni e costituisce il fulcro degli sforzi per proteggere le informazioni private su Internet. I ricercatori di Cornell Tech in un nuovo articolo, hanno identificato un problema che contiene la chiave per capire se tutta la crittografia può essere infranta, oltre a una sorprendente connessione a un concetto matematico che mira a definire e misurare la casualità.
Rafael Pass, professore di informatica alla Cornell Tech, coautore di “On One-Way Functions and Kolmogorov Complexity” (“Su funzioni unidirezionali e Complessità di Kolmogorov”), sarà presentato allo IEEE Symposium on Foundations of Computer Science, che si terrà dal 16 al 19 novembre 2020 a Durham, North Carolina, ha detto:
«Il nostro risultato non solo mostra che la crittografia ha un problema “madre” naturale, ma evidenzia anche una profonda connessione tra due aree piuttosto separate della matematica e dell’informatica, la crittografia e la teoria dell’informazione algoritmica. Il risultato è che un problema di calcolo naturale introdotto negli anni ’60 in Unione Sovietica caratterizza la fattibilità della crittografia di base, la crittografia a chiave privata, le firme digitali e l’autenticazione; ad esempio per millenni la crittografia è stata considerata un ciclo: qualcuno ha inventato un codice, il codice è stato efficace fino a quando qualcun altro alla fine l’ha decifrato, e il codice è diventato inefficace».
I ricercatori alla scoperta di una migliore teoria della crittografia negli anni ’70 hanno introdotto il concetto della funzione a senso unico, un compito facile in una direzione o un problema impossibile nell’altra: per esempio, è facile accendere un fiammifero ma impossibile riportare un fiammifero acceso allo stato spento senza riordinare i suoi atomi, un compito immensamente difficile.
Rafael Pass ha detto:
«L’idea era che, se abbiamo una tale funzione a senso unico, forse questo è un ottimo punto di partenza per capire la crittografia. Crittografare il messaggio è molto facile. E se hai la chiave, puoi anche decifrarlo, ma chi non conosce la chiave dovrebbe fare la stessa cosa del ripristino di un fiammifero acceso».
I ricercatori non sono stati in grado di dimostrare l’esistenza di una funzione a senso unico. Il candidato più noto, che è anche la base degli schemi di cifratura più comunemente usati su Internet, si basa sulla fattorizzazione integrale. È facile moltiplicare due numeri primi casuali, ad esempio 23 e 47, ma è molto più difficile trovare questi due fattori se si considera solo il loro prodotto, 1.081.
Rafael Pass spiega:
«Si ritiene che non esista un algoritmo di fattorizzazione efficiente per i grandi numeri, anche se i ricercatori potrebbero non aver ancora trovato gli algoritmi giusti. La domanda centrale che stiamo affrontando è, esiste? C’è qualche problema naturale che caratterizza l’esistenza di funzioni a senso unico? Se esiste, questa è la madre di tutti i problemi, e se si ha un modo per risolvere quel problema, si possono infrangere tutte le presunte funzioni a senso unico. E se non si sa come risolvere il problema, è possibile ottenere una crittografia sicura».
I matematici negli anni ’60 hanno identificato la cosiddetta “Complessità di Kolmogorov, si riferisce alla quantificazione della quantità di casualità o del modello di una stringa di numeri. La Complessità di Kolmogorov di una stringa di numeri è definita come la lunghezza del programma per computer più corto in grado di generare la stringa; per alcune stringhe, come 12121212121212121212121212121212121212121212121212, c’è un breve programma che lo genera: 1s e 2s; ma per stringhe di numeri più complicate e apparentemente casuali, come 3753901733282840393452954329, potrebbe non esistere un programma più corto della lunghezza della stessa stringa.
Il problema interessa da tempo matematici e informatici, tra cui Juris Hartmanis, professore emerito di informatica e ingegneria: poiché il programma informatico che tenta di generare il numero potrebbe richiedere milioni o addirittura miliardi di anni, i ricercatori dell’Unione Sovietica negli anni ’60, così come Juris Hartmanis e altri negli anni ’80, hanno sviluppato la Complessità di Kolmogorov, la lunghezza del programma più breve che può produrre una stringa di numeri in un certo lasso di tempo.
Yanyi Liu ha partecipato alla ricerca, nel documento ha dimostrato che se il calcolo della Complessità di Kolmogorov a tempo è difficile, allora esistono funzioni a senso unico. Ha evidenziato che la loro scoperta anche se è teorica, ha potenziali implicazioni attraverso la crittografia, compresa la sicurezza di Internet.
Rafael Pass in conclusione ha detto:
«Se si riesce a trovare un algoritmo per risolvere il problema della Complessità di Kolmogorov a tempo limitato, allora si possono infrangere tutte le crittografie, tutti gli schemi di crittografia, tutte le firme digitali. Tuttavia, se non esiste un algoritmo efficiente per risolvere questo problema, si può ottenere una funzione a senso unico, e quindi una crittografia sicura e firme digitali e così via».

Pino Silvestri

About Pino Silvestri

Pino Silvestri, blogger per diletto, fondatore, autore di Virtualblognews, presente su Facebook e Twitter.
View all posts by Pino Silvestri →