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 una funzione botola, allora esiste una qualche informazione segreta tale che date e risulti facile calcolare . 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.