Vous l'aurez peut-être compris, le post suivant parle de cryptographie. La cryptographie est une science passionnante et très concrète en terme d'applications. Il existe une multitude de méthodes visant à crypter un message, plus ou moins difficiles à casser, et plus ou moins difficiles à mettre en oeuvre. Un des systèmes de cryptographie les plus faciles à réaliser, mais aussi à casser, sont les systèmes affines. L'idée est d'abord d'associer à chaque lettre de l'alphabet une valeur numérique, sous forme d'un tableau :
Ensuite, nous allons modifier cette valeur à l'aide d'une application mathématique. Cela correspond à la phase de codage. On vient transformer la valeur de la lettre initiale à coder pour obtenir une nouvelle valeur. Dans le cas d'un chiffrement affine, l'application en question est du type ax+b=y, avec x la valeur de la lettre à coder, et y la nouvelle valeur modifiée, transformée, correspondant à la lettre codée. On dit que la couple choisi (a,b) est la clef de chiffrement. Pour être certain que y soit bien compris entre 0 et 25, autrement dit que la lettre codée soit bien une lettre de notre tableau, nous devons travailler modulo 26. Cela signifie que lorsqu'on arrive à 25, on reprend à 0 (comme si les nombres s'organisaient sur un cercle).
De cette manière, à une lettre du message d'origine correspond une unique lettre codée. C'est un des inconvénients de cette méthode : elle est très sensible au cassage par fréquence. Le cassage par fréquence consiste à analyser la fréquence d'apparition d'une lettre codée et de la comparer aux fréquences d'apparition des lettres de la langue du message initial (par exemple, en français, un code avec beaucoup de fois la lettre "D" peut sous-entendre que "D" est la lettre codée de "E", très fréquent dans notre langue).
Une autre méthode de chiffrement a été développée par Lester S. Hill. Concrètement, elle correspond à une "amélioration" du chiffrement affine. Le chiffrement de Hill consiste dans un premier temps à découper le message initial en plusieurs morceaux de même longueur. Par exemple, avec des morceaux de longueur 2, le message "chiffrements" se découpe en "ch if fr em en ts", donc en six paquets de deux lettres. Ensuite ces paquets de deux lettres sont associés à un vecteur de longueur 2. Par exemple, le premier paquet "ch" est associé au vecteur [2, 7], correspondant respectivement aux valeurs de "c" et "h" . On procède de cette manière sur tout le message. Si le message contient un nombre impair de lettres, on peut ajouter ou enlever une lettre au message initial. Par exemple, "chiffrementdehill" devient "chiffrementdehilla". Maintenant, comme pour le chiffrement affine, nous allons modifier, transformer ce vecteur pour en obtenir un nouveau. Ici, la transformation est du type :
où A est une matrice 2x2 (c'est la clef de chiffrement), [x1, x2] le vecteur initial (non codé) et [y1, y2] le vecteur codé. Comme on travail toujours modulo 26, les valeurs de [y1, y2] sont bien des lettres de l'alphabet, et on peut associer ce nouveau vecteur au couple de lettres codées.
Maintenant, comment faire pour décoder un message connaissant la clef de chiffrement A ? Tout simplement en inversant la matrice A ! Si A est inversible, alors :
et on retrouve le couple [x1, x2], et par suite le couple de lettres initial. Petit point technique : l'inversion d'une matrice implique de calculer l'inverse de son déterminant. Or, ce nombre est à priori fractionnaire et non entier. Il faut donc, lorsque l'on choisi la clef de chiffrement A, vérifier que det (A) est inversible mod 26, c'est-à-dire qu'il existe k un entier tel que k×det A=1 [26].
L'intérêt d'une telle méthode est que, pour une même lettre du message initial, il peut y avoir plusieurs lettres codées correspondantes. Par exemple, un "e" peut être codé en "y" à un endroit du texte, mais aussi en "u" à un autre endroit. Le chiffrement de chaque lettre n'est plus fait au cas par cas, individuellement, mais est influencé par les lettres voisines. Le cassage d'un tel système ne se fait donc plus par analyse de fréquence de lettre, mais de couple de lettres.
Avec un ami, nous nous sommes mis au défi de mettre en pratique ces notions en créant un script "Matlab" (version R2019b) proposant :
-une génération aléatoire de clés de chiffrement de Hill valides d’ordre N ≥ 2
-le chiffrement et/ou déchiffrement d’un message écrit en caractères ASCII
-une interface utilisateur basique
La syntaxe du code est détaillée ci-dessous, et le fichier complet est accessible à l'adresse suivante (nécessite Matlab pour exécution) : https://we.tl/t-MOrwy3rfYU
Défi : en utilisant Matlab, essayez de déchiffrer le titre avec la clef disponible en téléchargement.