Puzzles de Merkle

En cryptographie, les puzzles de Merkle ou énigme de Merkle de Ralph Merkle constituent la première construction à clé asymétrique, à l'exception possible d'études top secrètes par le GCHQ. Cette construction a été réalisée en 1974, mais n'a été publiée qu'en 1978. Elle permet à deux parties de se mettre d'accord sur un secret en commun par l'échange de messages, et sans que ces partis n'aient préalablement de secret commun.

Technique

Supposons qu'Alice et Bob veulent communiquer en utilisant une clé secrète commune. Pour établir cette clé, Bob envoie à Alice un message qui consiste en un grand nombre de puzzles, chacun assez petit pour qu'Alice puisse le résoudre par attaque par force brute. Les puzzles sont de la forme d'un message chiffré avec une clé inconnue, donc la clé est assez courte.

Bob envoie tous les messages à Alice. Elle en sélectionne un au hasard et le résout par force brute. Le message déchiffré contient un identificateur (du choix d'Alice) et une clé secrète, dite clé de session. Alice renvoie l'identificateur à Bob, qui sait alors également quelle est la clé de session.

Le tiers parti Ève, l'adversaire, a la tâche plus difficile. Elle ne sait pas quel puzzle a été résolu. La meilleure stratégie pour Ève est de résoudre tous les puzzles, ce qui est beaucoup plus coûteux pour elle que pour Alice.

Références

• (en) R. C. Merkle, "Secure Communications over Insecure Channels" Communications of the ACM 21(4), p. 294--299 (April 1978).

Liens externes

• (en) Ralph Merkle, Secure Communications over Insecure Channels (1974) : histoire et l'idée et de sa publication