Algoritmo del puzzle

Da Wikipedia, l'enciclopedia libera.

In crittografia l'algoritmo del puzzle è un esempio istruttivo di algoritmo di crittografia a chiave pubblica. Sebbene sia praticamente irrealizzabile contiene molte delle idee di base di algoritmi più complessi, in particolare risolve il problema dello scambio della chiave, cioè consente a due persone di scambiare messaggi segreti anche se non si sono mai scambiate un segreto prima di allora (la chiave). L'algoritmo fu proposto da Merkle nell'ottobre del 1974 e pubblicato nel 1978

Funzionamento[modifica | modifica wikitesto]

Supponiamo che Alice e Bob vogliano comunicare in modo sicuro, al riparo di Eva che ha accesso al canale di comunicazione e quindi potrebbe intercettare i loro scambi di informazione. Bob e Alice devono scambiarsi la chiave, ma non hanno un canale sicuro per farlo. Alice crea dei puzzle ovvero crea tanti messaggi codificati con un algoritmo facile da forzare (il puzzle è una metafora, è abbastanza facile da risolvere come è abbastanza facile forzare il messaggio cifrato). Bob riceve questi puzzle (la chiave pubblica), diciamo qualche milione, e ne sceglie uno a caso. Lo risolve, ovvero forza la cifratura. A questo punto Bob legge il messaggio contenuto nel puzzle che dice qualcosa del genere: "Sono il puzzle numero x, la chiave numero x è y". A questo punto Bob comunica ad Alice il numero del puzzle: x. In questo modo Alice e Bob hanno una chiave in comune: y. Eva avendo intercettato lo scambio dei puzzle ha anche lei la chiave y, ma è mischiata tra un milione di altre chiavi; inoltre conosce il numero della chiave. A questo punto potrebbe provare a risolvere tutti i puzzle fino a trovare il puzzle numero x, ma il numero dei puzzle è scelto in modo che questa operazione sia computazionalmente troppo lunga.

Sicurezza[modifica | modifica wikitesto]

Supponiamo che Alice mandi 2^{20} (circa un milione) di puzzle a Bob. Mediamente Eva per trovare il puzzle che contiene la chiave usata tra Bob e Alice dovrà risolvere la metà dei puzzle: 2^{19}. Se per risolvere un puzzle Bob ci mette un minuto, Eva impiegherà un anno a risolverne la metà. Quindi in media Eva ha bisogno di un anno per decifrare il messaggio intercettato.

Il metodo non è sicuro perché il tempo che ci metterà Eva a trovare la chiave non è limitato inferiormente, cioè potrebbe essere fortunata e trovarla al primo tentativo.