Sicurezza informatica: Funzioni one way trapdoor
Introduzione
Whitfield Diffie e Martin Hellman nel 1976 introdussero un nuovo concetto di crittografia in un articolo che è diventato storico. Praticamente la loro intuizione andava contro tutti i canoni della crittografia stessa: cifrare con una chiave conosciuta da tutti. La loro intuizione si basava sulla Teoria della complessità e sulle funzioni one way trapdoor.
Teoria della complessità
La teoria della complessità classifica come problemi intrattabili, quelli per i quali gli algoritmi risolutivi richiedono un tempo di calcolo che cresce rapidamente.
In particolare, se è d la dimensione di un problema intrattabile, il numero delle operazioni necessarie a risolvelo cresce come 2d. Diffie-Hellman suggerirono di impiegare cifrari in linea di principio decifrabili, ma solo da programmi di calcolo che operino su calcolatori per milioni di anni. Tutto si riduce nel legare il sistema crittografico a un problema intrattabile.
Funzioni one way trapdoor
Definizione: Una funzione f si dice one way se per ogni x il calcolo computazionale di
y=f(x)
è semplice, mentre il calcolo di
x=f-1(y)
è computazionalmente difficile (richiede una quantità enorme di tempo).
Definizione: Una funzione one-way è detta trapdoor se il calcolo di x=f-1(y) può essere reso facile qualora si conoscano delle informazioni aggiuntive (private).
Allo stato attuale delle cose non c’e’ molta chiarezza su quale possa essere una possibile funzione che garantisca quanto detto sin’ora, cioè:
- FACILITA’ COMPUTAZIONALE
- IRREVERSIBILITA’ IMPOSSIBILE
- EFFICENZA
Volendo vedere la cosa da un punto di vista matematico, non esiste nessuna dimostrazione, che un tale tipo di funzione esista, e che sia computabile. Comunque, esistono molte funzioni, che assomigliano e si avvicinano ad una funzione one-way. Possiamo computarle facilmente e non riusciamo ad invertirle. Ad esempio x2, è molto facile da implementare, la stessa cosa non si può dire per √x.
Ad ogni modo, comunque la si vuole intendere, la funzione one-way trapdoor gioca un ruolo chiave in tutta la moderna crittografia.
