Puzles de Merkle

En criptografia, el método dels puzles de Merkle (del anglés, Merkle's puzles) constituïx un protocol d'intercanvi de claus, és dir, un protocol per a intercanviar claus criptográficas de manera segura. Es basa en l'elaboració de «puzles», problemes computacionals de complexitat moderada, que dificulten que un tercer que intercepte la comunicació obtinga la clau.

Els puzles de Merkle utilisen exclusivament criptografia simètrica, a diferència de la majoria de protocols d'intercanvi de claus actuals. No obstant són menys eficients que estos i no s'usen en la pràctica. El método de Merkle constituïx el primer protocol d'intercanvi de claus de l'història, i deu el seu nom a Ralph Merkle, qui ho va desenrollar en 1974.

Descripció

Partint de dos parts interessades en comunicar-se, Alicia i Bob, una d'elles, per eixemple Alicia, deu començar per elaborar una gran cantitat de «puzles» i enviar-li-les a l'atra part, Bernardo. Un puzle és un problema computacional que requerix una cantitat moderada d'esforç computacional per a resoldre's. Una volta resolt un puzle s'obté una possible clau llistaper a ser usada, aixina com un identificador que ho distinguix del restant de puzles.

Quan Bernardo rep tots estos puzles elegix un a l'encert, ho resol i posteriorment envia l'identificador de la clau seleccionada de regrés a Alicia per a que esta sàpia que clave es va a usar. D'esta manera acorden una clau secreta comuna, puix abdós coneixen la que correspon a dit identificador. Si un tercer, Trudy, intercepta les comunicacions entre Alicia i Bernardo i vol obtindre la clau, deu resoldre tots els puzles fins a trobar-se en l'identificador en qüestió. El método es considera segur en la mida en que l'esforç total necessari per a resoldre una gran cantitat de puzles siga molt gran.

Per a l'elaboració de cada puzle, segons l'idea original de Ralph Merkle, poden generar-se una clau i identificador aleatoris, per a despuix codificar-los per mig d'un sifrat simètric en una clau relativament curta. D'esta manera, el puzle pot resoldre's per mig d'una dosis moderada de força bruta.

Seguritat

L'intercanvi de la clau requerix l'elaboració dels puzles per Alicia, aixina com de la resolució d'un d'ells per Bernardo. Si el número de puzles és n, i cada u requerix fins a m intents per a ser resolt, el temps per a l'intercanvi de la clau és O(m + n). El temps mig que necessita Eva per a dessifrar puzles fins a trobar la clau és O(n · m). Si el número de puzles és similar a la complexitat dels mateixos, m ≈ n, la complexitat per a Eva és quadràtica, O(n²) comparada en la d'Alicia i Bernardo.

Esta complexitat polinomial no oferix tanta seguritat com atres sistemes de clau pública que apleguen a tindre complexitat exponencial, en els que l'esforç computacional que requerix l'atacant creix de forma exponencial respecte al que realisa l'usuari autorisat. Ademés, existixen resultats que sugerixen que els puzles de Merkle són òptims, en el sentit de que cap atre protocol d'intercanvi de claus basat en criptografia simètrica oferix més dificultat a un atacant.

Referències

• Barak; Mahmoody-Ghidary, Mohammad (2009). «Merkle Puzles Llaure Optimal — An O(n²)-Query Attack on Any Key Exchange from a Random Oracle», Shai Halevi (ed.). Advances in Cryptology - CRYPTO 2009 (en anglés). doi:10.1007/978-3-642-03356-8_22.

1. REDIRECCIÓN Plantilla:Cita video

• Garfinkel, Simson (1995). PGP: Pretty Good Privacy (en anglés), O'Reilly Mija, p. 69. ISBN 9781565920989.