Algoritmo del puzzle: differenze tra le versioni

Versione delle 15:11, 8 mar 2007

Versione attuale delle 02:22, 9 mag 2023

(19 versioni intermedie di 14 utenti non mostrate)

Riga 1:

{{F|crittografia|ottobre 2018}}

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 [[Ralph Merkle|Merkle]] nell'ottobre del [[1974]] e pubblicato nel [[1978]]

== Funzionamento ==

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 [[scambio della chiave|scambiarsi la chiave]], ma non hanno un canale sicuro per farlo. BobAlice 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). AliceBob riceve questi ''puzzle'' (la [[chiave pubblica]]), diciamo qualche milione, e ne sceglie uno a caso. Lo risolve, ovvero forza la cifratura. A questo punto AliceBob legge il messaggio contenuto nel puzzle che dice qualcosa del genere: "Sono il puzzle numero ''x'', la chiave numero ''x'' è ''y''". A questo punto AliceBob comunica aad BobAlice 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 ==

[[Categoria:crittografia]]

Supponiamo che Alice mandi <math>2^{20}</math> (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: <math>2^{19}</math>. 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.

[[en:Merkle's puzzle]]

{{Portale|Crittografia|Sicurezza informatica}}

[[fr:Puzzles de Merkle]]

[[Categoria:Crittosistemi asimmetrici]]

[[Categoria:Protocolli di scambio della chiave]]