Funzione botola

Una funzione botola (dall'inglese: trapdoor function) è una funzione facile da computare in una direzione, ma difficile da calcolare nella direzione opposta (ossia trovarne l'inversa) se non si conoscono determinate informazioni, chiamate appunto botole. Queste funzioni sono largamente utilizzate nell'ambito della crittografia.

In termini matematici, sia $F$ una funzione botola, allora esiste una qualche informazione segreta $y$ tale che date $F(x)$ e $y$ risulti facile calcolare $x$ . Si consideri ad esempio un lucchetto e la relativa chiave. È banale cambiare il lucchetto da aperto a chiuso senza utilizzare la chiave, è sufficiente far scattare la serratura. Tutt'altra cosa invece è aprire il lucchetto, in questo caso l'ausilio della chiave risulta indispensabile. La chiave è la botola.

Le funzioni botola hanno fatto la loro comparsa nell'ambito della crittografia intorno alla metà del 1970 con la pubblicazione di Tecniche di crittografia asimmetrica (o a chiave pubblica) da parte di Diffie, Hellman, and Merkle. Di fatto il termine botola venne proprio coniato da Diffie e Hellman (Diffie e Hellman, 1976). Inizialmente vennero proposte diverse classi di funzioni, ma fu subito chiaro che delle funzioni botola vere e proprie sono molto più difficili da trovare di quanto si pensasse. Fino al 2004 i candidati migliori per svolgere il ruolo di funzioni botola erano l'RSA e le funzioni della famiglia Rabin. Entrambi sono scritti come elevamento a potenza modulo di un numero complesso ed entrambi sono legati al problema della fattorizzazione dei numeri primi.

Esempi[modifica | modifica wikitesto]

Un esempio di una semplice botola matematica può essere: 6895601 è il prodotto di due numeri primi, quali sono questi numeri? Una tipica soluzione (forza bruta) potrebbe essere quella di dividere il numero per diversi numeri primi fino a trovare la risposta. Tuttavia se qualcuno rendesse noto che 1931 è parte della risposta, diverrebbe semplice, con l'aiuto di una calcolatrice, trovare la soluzione completa (6895601 ÷ 1931). Questo esempio non rappresenta una robusta funzione botola dal momento che un computer moderno può facilmente elaborare tutte le possibili soluzioni in un arco di tempo molto breve, ma lo stesso esempio può essere irrobustito semplicemente ricorrendo al prodotto di due numeri primi molto più grandi.