Da Wikipedia, l'enciclopedia libera.

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. L'algoritmo fu proposto da Merkle nell'ottobre del 1974.

Supponiamo che Bob e Alice 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. Bob 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). Alice riceve questi puzzle, diciamo qualche milione, e ne sceglie uno a caso. Lo risolve, ovvero forza la cifratura. A questo punto Alice legge il messaggio contenuto nel puzzle che dice qualcosa del genere: "Sono il puzzle numero x, la chiave numero x è y". A questo punto Alice comunica a Bob 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.