La lecture de Codes, la grande aventure m'a fait repenser à un problème des plus intéressants concernant la cryptographie. Il s'agit de la problématique de l'échange des clefs.
Première constatation : avec une clef aléatoire et unique de la longueur du message, on peut réaliser un chiffrement absolument incassable. Il suffit par exemple de faire une addition modulo entre la clef et le message, et on obtient un message crypté sans risque de répétition et sans faille. La taille des clefs rend cette méthode inapplicable en pratique.
Deuxième constatation : la sécurité des solutions actuelles permettant l'échange de clef ou l'existence de clefs de chiffrement publiques (comme RSA ou Diffie-Hellman-Merkle) ne reposent que sur la limite des moyens de calcul. Avec un ordinateur infiniment puissant (mettons un ordinateur quantique...), casser de tels code est un jeu d'enfant. La sécurité ne repose donc pas sur un aspect théorique, mais sur un aspect pratique (1).
Ce qui est fascinant, c'est que dans la réalité, cet échange est possible. Il suffit à A de mettre son message dans un coffre m (on assimile le message et le coffre), et de le fermer grâce à un cadenas X. Il envoie la boite à B, qui pose son cadenas Y, et la renvoie à A. A reçoit la boîte avec les deux cadenas, enlève son cadenas X, et la renvoie à B. Il ne reste alors plus qu'à B de retirer son cadenas Y et de lire le message.
Ceci est possible, car les cadenas sont commutatifs. On peut appliquer l'un ou l'autre dans n'importe quel ordre, et les enlever dans n'importe quel ordre. Autrement dit, les applications X() et Y() sont commutatives : X(Y(m)) = Y(X(m)) (2). Dans ce cas, on peut appliquer X-1() à Y(X(m)) pour obtenir Y(m), et l'opération peut (en simplifiant certaines étapes) s'écrire ainsi :
m => X(m) => Y(X(m)) => X-1(Y(X(m))) => Y(m) => m
La transposition mathématique est plus délicate, car une fois que A a appliqué son chiffrement X(), il n'existe pas, comme dans la réalité, deux objets distincts (le coffre m et le cadenas X()) mais un seul objet, un coffre fermé X(m). On peut l'imaginer comme un coffre enfermé dans un autre coffre. Il n'est possible à B d'agir sur le coffre m à l'intérieur de X(m) que dans deux cas : soit il connaît X() ; soit X() et Y() sont commutatives.
Malheureusement, dans ce cas les opérations X() et Y() sont transparentes pour un observateur extérieur, et donc la sécurité (théorique) est compromise. (Connaissant Y(X(m)) et X(m) un observateur peut définir Y() et comme il connait Y(m), il en déduit m.)
Du point de vue du raisonnement, cet échange de clef peut être vu comme l'échange d'un système d'équations, avec plusieurs paramètres bien définis et connus seulement de A et B. La sécurité repose sur le fait que ce système ne doit pas pouvoir être résolu (3) sans la connaissance des paramètres - l'impossibilité pouvant être d'ordre pratique, ou d'ordre théorique.
(1) Ce qui n'est guère rassurant, car dans l'histoire du chiffrement et du déchiffrement, les briseurs de code se sont toujours évidemment gardés de se vanter qu'ils ont trouvé la faille d'un système. Si des ordinateurs (ou des réseaux) permettant de casser ces codes existaient, nul ne le saurait.
On pourrait imaginer par exemple que la CIA a développé des vers transformant les machines infectées en machines-zombies (c'est un phénomène bien connu, et utilisé de manière légale ou non). Les PC formeraient alors un réseau suffisamment puissant pour briser un chiffre.
(2) Ce qui marche très bien avec des applications linéaires... mais question sécurité, ce n'est pas génial.
(3) Dans le cas de RSA, comme c'est exposé ici, connaissant p, q et d, la clef privée, on arrive à générer deux clefs publiques n et e à partir desquelles il n'est pas possible de remonter à p, q, d. L'astuce (géniale) vient ensuite du fait que n et e permettent uniquement de chiffrer, mais que pour déchiffrer, il faut connaître p, q et d.