Algoritmo del puzzle

Questa voce o sezione sull'argomento crittografia non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

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

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.

Supponiamo che Alice mandi ${\displaystyle 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: ${\displaystyle 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 è considerato sufficientemente sicuro perché il tempo che ci metterà Eva a trovare la chiave cresce quadraticamente rispetto a quello impiegato da Bob. I moderni protocolli di crittografia asimmetrica e di scambio di chiave richiedono algoritmi di attacco e legittimi con complessità computazionali che divergono esponenzialmente.

Portale Crittografia

Portale Sicurezza informatica