Le funzioni one-way e trapdoor: il cuore della crittografia moderna

Introduzione

Una funzione one-way (in italiano, funzione unidirezionale) è, per definizione, una funzione matematica facile da calcolare ma computazionalmente difficile da invertire. In altre parole, invertire una funzione one-way è equivalente a risolvere un problema matematico intrattabile, ovvero per il quale non è noto alcun algoritmo risolutivo computazionalmente efficiente.

Le funzioni one-way rappresentano le fondamenta della crittografia asimmetrica (o a chiave pubblica) moderna. Infatti, la totalità delle tecniche crittografiche asimmetriche utilizzate per proteggere dati e comunicazioni basa la propria sicurezza sulla difficoltà di invertire questi oggetti.

Si noti, però, che tale difficoltà, è solo presunta. Infatti, dal punto di vista teorico, questo è ancora una congettura aperta, mai formalmente dimostrata. Una dimostrazione comporterebbe la risoluzione della principale questione non risolta dell’informatica teorica, nonché uno dei sette quesiti del Millennio (Millennium problems), P vs NP.

Questi sono stati individuati dal Clay Mathematics Institute nel 2000 e consistono di sette problemi matematici mai risolti la cui soluzione avrebbe un impatto cruciale sia nelle implicazioni teoriche che nelle loro applicazioni pratiche. Per ognuno di questi è stato messo in palio un premio di un milione di dollari nel caso se ne fornisca una dimostrazione.

Tra i sette quesiti, si cita l’ipotesi di Riemann, la cui risoluzione porterebbe a conseguenze sulla distribuzione di numeri primi e avrebbe quindi profonde ripercussioni nella matematica pura e nella crittoanalisi. L’unico ad essere stato risolto è la congettura di Poincaré, i restanti rimangono ancora oggi problemi aperti.

Il fatto che l’esistenza di funzioni one-way sia ancora una congettura aperta significa che nessuna di queste funzioni sia dimostrabilmente difficile da invertire. È teoricamente possibile, quindi, che un giorno venga scoperto un algoritmo in grado di invertire efficientemente una di queste, rendendo inutile la protezione offerta dagli schemi crittografici che si basano su essa.

Sebbene non se ne abbia la certezza matematica, la comunità scientifica crede profondamente che ciò non accadrà, e ripone da sempre la sicurezza degli schemi crittografici su questa assunzione.

A rafforzare la fiducia nelle funzioni one-way contribuisce il fatto che diversi candidati hanno resistito a decenni di ricerca nel cercare un algoritmo di inversione. Alcuni esempi sono le funzioni hash, la moltiplicazione di due numeri primi e l’esponenziazione modulare.

In particolare, i problemi di inversione di queste ultime due sono meglio conosciuti come la fattorizzazione di numeri interi e il logaritmo discreto, problemi su cui ripongono la propria sicurezza la maggior parte degli schemi crittografici asimmetrici oggi in uso, ad esempio RSA e Diffie-Hellman.

Funzioni one-way nella crittografia a chiave pubblica

Per capire meglio il concetto di funzione one-way, si immagini che la funzione agisca come un frullatore. A partire dall’input, ottenere il risultato frullato è facile, mentre il viceversa è in un certo senso impossibile.

Più formalmente, sia f:A\rightarrow B una funzione, f è one-way se:

• dato a\in A è facile calcolare f(a)
• dato b\in Bè computazionalmente difficile trovare un a\in A tale che f(a)=b

Un esempio proveniente dalla crittografia a chiave pubblica, in particolare dallo scambio chiavi Diffie-Hellman, è la funzione di esponenziazione modulare. Dato un numero primo p ed un numero positivo g minore di p la seguente funzione è un forte candidato ad essere one-way
f(x) = g^x \mod p.
Possiamo osservare che calcolare la potenza x-esima di g modulo p è facile. Viceversa, dato un intero positivo h minore di p trovare l’elemento x per cui g^x=h \mod p è un problema assunto intrattabile. Quello appena descritto è il problema del logaritmo discreto ed è alla base di numerosi schemi crittografici come lo scambio di chiavi Diffie-Hellman e ECDH e la firma su curve ellittiche ECDSA.

Per comprendere come vengono usate nella crittografia a chiave pubblica, è opportuno conoscere come il concetto di funzione one-way sia legato alla coppia di chiavi pubblica/privata utilizzata in un algoritmo a chiave pubblica.
Solitamente, data una funzione one-way f si crea la coppia chiave privata/chiave pubblica come (x,f(x)).

La chiave privata è quindi un elemento arbitrario x mentre la relativa chiave pubblica risulta semplicemente essere l’applicazione di f alla chiave privata. Noto f(x) la segretezza di x risiede nella difficoltà di invertire f.
In Diffie-Hellman, la chiave privata è un intero x mentre la relativa chiave pubblica è f(x)=g^x \mod p.

Funzioni trapdoor nella crittografia a chiave pubblica

Un caso speciale di funzione one-way sono le funzioni dotate di trapdoor, dette anche più semplicemente funzioni trapdoor (in italiano, funzioni botola). Queste hanno la particolarità di essere facili da invertire a patto che si conoscano alcune informazioni segrete (la trapdoor), mentre, in caso contrario, agiscono come delle normali funzioni one-way.

A titolo esplicativo, si immagini che la funzione trapdoor agisca come il meccanismo di chiusura di un lucchetto; chiunque è in grado di chiudere il lucchetto e soltanto chi possiede la chiave (trapdoor) del lucchetto è in grado di aprirlo facilmente.

Formalmente, una funzione trapdoor è una funzione one-way con la proprietà aggiuntiva che nel caso in cui siamo a conoscenza dell’informazione segreta k esiste una funzione f_k facile da calcolare per cui, dato b\in B abbiamo f(f_k(b))=b.

Un celebre esempio di funzione trapdoor è quello alla base dello schema crittografico a chiave pubblica RSA. Siano p e q due numeri primi e sia N il loro prodotto. Siano e e d due interi positivi coprimi con (p-1)(q-1) tali che
ed = 1 \mod (p-1)(q-1).
La chiave pubblica è data da (N,e) mentre quella privata è d La funzione one-way è data da
f(m) = m^e \mod N.
Anche in questo caso, calcolare f(m) a partire da m è facile, mentre estrarre una radice e-esima modulo N di un intero c=f(m) è un problema assunto difficile.

La funzione f è, una funzione one-way trapdoor, ove la trapdoor consiste proprio nella conoscenza della chiave privata d. Infatti, data la funzione
f_d(c) = c^d \mod N,
se ed = 1 \mod (p-1)(q-1) allora per ogni x si ha x^ed = x \mod N e si può provare che
f(f_d(c)) = f( c^d \mod N) = c^{ed} \mod N = c \mod N.
In altre parole, f_d(c) è proprio m ovvero il messaggio iniziale.

One-way vs trapdoor

La sostanziale differenza tra le funzioni one-way con e senza trapdoor è la presenza di un’informazione segreta che ne permetta l’inversione. Questo implica l‘esistenza di una “struttura” nascosta che potrebbe far trapelare informazioni sulla chiave segreta.

Pertanto, nello studio della sicurezza di questi schemi va presa in considerazione sia la difficoltà di invertire la funzione che quella di ricavare informazioni sulla trapdoor.

Nell’esempio di RSA, l’inversione di fconsiste nell’estrazione di una radice e-esima modulo N e la sicurezza della trapdoor è basata sulla difficoltà di trovare i fattori primi p e q tali che N=pq e calcolare quindi d.

Nella crittografia asimmetrica, le funzioni trapdoor sono utilizzate per camuffare il messaggio e renderlo disponibile solo a chi conosce la trapdoor, al contrario delle semplici funzioni one-way, che sono invece utilizzate per generare la coppia di chiavi privata/pubblica.

Come abbiamo visto negli articoli precedenti, un computer quantistico, grazie all’algoritmo di Shor, può invertire efficientemente sia la funzione di moltiplicazione di numeri primi che l’esponenziazione modulare, minando la sicurezza della totalità degli schemi asimmetrici moderni oggi utilizzati.

È di vitale importanza, pertanto, studiare e analizzare le funzioni one-way anche da un punto di vista quantistico per costruire schemi resistenti a questi attacchi.

La Crittografia Post-Quantum è una risposta alla minaccia del computer quantistico, e identifica nuovi problemi matematici, e quindi nuove funzioni one-way, non vulnerabili agli algoritmi quantistici.

Nel corso dei prossimi articoli di questa rubrica si approfondiranno alcuni esempi di queste costruzioni in ottica Post-Quantum.

Questo articolo appartiene ad una serie di contributi, a cura del Gruppo di Ricerca in Crittografia di Telsy, dedicata al calcolo quantistico e alle sue implicazioni sulla Crittografia. Per la consultazione di altri articoli si rimanda all’indice della rubrica.

Per altri articoli relativi ai temi Quantum e Crittografia si rimanda alle relative categorie nel blog.

Gli autori

Veronica Cristiano, laureata triennale in Matematica presso l’Università di Pisa e laureata magistrale in Matematica con specializzazione in Crittografia presso l’Università di Trento, entrata a far parte del gruppo di ricerca in Crittografia di Telsy a metà del 2021.

Giuseppe D’Alconzo, laureato in Matematica con specializzazione in Crittografia presso l’Università di Trento, ha svolto nel 2019 uno stage presso Telsy, occupandosi di Multi-party Computation e Attribute Based Encryption. Attualmente è studente di dottorato in Matematica Pura e Applicata presso il Politecnico di Torino, con una borsa a tema “Crittografia Post-Quantum” nell’ambito del programma UniversiTIM e in collaborazione con il Gruppo di Ricerca di Telsy.