CDH : Computational Diffie-Hellman
Cryptographie
CDH : Computational Diffie-Hellman. « Diffie-Hellman calculatoire », par analogie avec une recette dont on voit passer les deux ingrédients séparés sans jamais réussir à reproduire le plat. C'est une hypothèse de difficulté, pas un protocole : à partir de g, g^a et g^b, calculer g^ab doit être hors de portée.
Hypothèse, pas protocole : CDH ne s'exécute pas, on la suppose. C'est le socle sur lequel repose la sécurité d'un échange Diffie-Hellman face à un observateur passif qui voudrait reconstituer le secret partagé.
Lien avec le logarithme discret : Savoir calculer un logarithme discret suffit à résoudre CDH ; la réciproque n'est pas démontrée en général. CDH est donc une hypothèse au moins aussi forte que la difficulté du logarithme discret dans le même groupe.
Plus faible que DDH : Si DDH tient dans un groupe, CDH y tient aussi. Il existe même des groupes où CDH semble difficile alors que DDH est facile, typiquement ceux munis d'un couplage calculable.
Ce que CDH ne garantit pas : Rendre le secret incalculable ne le rend pas indiscernable du hasard : quelques bits peuvent fuiter sans violer CDH. D'où le passage systématique par une fonction de dérivation avant d'utiliser le secret comme clé, étape que les tutoriels de blog oublient avec une régularité de métronome.
Ce qui arrive si on s'en passe
Oublier ce que dit exactement l'hypothèse CDH conduit à lui prêter des vertus qu'elle n'a jamais revendiquées. Elle rend le secret partagé incalculable pour un observateur passif, pas indiscernable du hasard : employer directement g^ab comme clé de chiffrement, sans fonction de dérivation, laisse fuiter quelques bits et fonde la sécurité sur une propriété que personne n'a démontrée. Choisir un groupe où le logarithme discret est facile ruine en outre l'hypothèse elle-même, puisque le résoudre suffit à résoudre CDH. Une preuve de sécurité bâtie sur la mauvaise hypothèse reste une preuve : elle démontre simplement autre chose.
Explication de la marmotte
Deux personnes veulent fabriquer un secret commun en ne s'envoyant que des messages que tout le monde peut lire. Chacune garde un nombre caché, fait un calcul avec, et publie le résultat. En combinant son nombre caché avec le résultat publié par l'autre, chacune tombe sur le même secret. Un curieux voit passer les deux résultats publics. La question est : peut-il, avec ces seules informations, retrouver le secret ? On parie que non, parce que le calcul est facile dans un sens et extrêmement long à défaire. Ce pari, que les spécialistes étudient depuis des décennies sans l'avoir cassé dans les bons groupes, porte ce nom.
Où ce terme est utilisé
- Établir une clé : Diffie-Hellman, KEM et HPKE (1 occurrence)