Invitation à la cryptanalyse
par Desmaretz Gérard
vendredi 13 décembre 2019
Les collégiens et lycéens ont jusqu'au 21 décembre 2019 pour s'inscrire au jeu-concours Al-Kindi. Cette initiative lancée lundi 9 décembre 2019 rentre dans le cadre de la Stratégie mathématiques et du plan École numérique du Ministère de l’Éducation nationale. (...) Ainsi, chaque participant·e peut s’amuser à résoudre des défis adaptés à son niveau et découvrir les principes de base de la cryptographie. (...) Nous souhaitons faire découvrir aux élèves cette application très concrète des mathématiques qui joue un rôle fondamental dans leur vie quotidienne. Nous voulons les faire réfléchir, de façon ludique, aux fondements mathématiques, informatiques et logiques de la cryptanalyse (NdA : La cryptanalyse consiste à déchiffrer un message dont on ne possède pas la clé). Enfin, nous souhaitons les sensibiliser à la question importante de la sécurité de l’information.
Il est en général possible de lire un texte truffé de fautes : « Sleon une édtue de l'Uvinertisé de Cmabrigde, l'odrre des ltteers dnas les mtos n'a pas d'ipmrotncae, la suele coshe ipmrotnate est que la pmeirère et la drenèire soit à la bnnoe pclae. Le rsete peut êrte dnas un dsérorde ttoal et vuos puoevz tujoruos lrie snas porlblème. C'est prace que le creaveu hmauin ne lit pas chuaqe ltetre elle-mmêe, mias le mot cmome un tuot » (Cela n'est pas le cas avec les chiffres lorsqu'il s'agit de reconstituer un nombre). « Jusqu'à 50 % des lettres du Français sont inutiles, toutefois au-delà de 25 % d'élimination, la reconstitution du sens original devient difficile »
Si le texte ne comporte que quelques lignes, les occurrences respectives des lettres pourront s'écarter de la loi de distribution « normale ». Au tableau des fréquences unitaires viennent s'ajouter les digrammes. La lettre Q par exemple est suivi à 99 % par U - E à 18 % par S et 10 % par R, approche des cruciverbistes cherchant à deviner deux ou trois lettres manquantes (les dictionnaires de mots croisés et du scrabble pourront se révéler des plus utiles). Le décrypteur doit procéder par tâtonnements jusqu'à obtenir un ensemble de mots ayant un sens. L'usage d'une forme phonétique contribue à raccourcir le texte : KC (cassé), KCHE (caché), AQZE (accusé), KSK (casque), et une langue étrangère fausse les fréquences établies, l'islandais : A 10% - N 7,7% - I 7,6% - E 6,5% - S 5,6%, et le taux de conformité pour la traduction du swahili atteint 90 % d'erreurs !
Voici un exemple didactique : FCPU NGU NCPIWGU CPEKGPPGU NC HTGGWGPEG FGU NGVVTGU RGWV GVTG NGIGTGOGPV FKHHGT GPVG. En hiérarchisant les fréquences d'apparition, vous voyez rapidement que chaque lettre de l'alphabet a été décalée de 2 rangs vers la droite (substitution simple ou code de Jules César). Dans la pratique les lettres sont regroupées par blocs de 5 lettres : FCPUN-GUNCP-IWGUC-PEKGP-PGUNC-HTGGW-GPEGF-GUNGV-VTGUR-GWVGV-TGNGI-TGOGP-VFKHH-GTGPV-Gxxxx (la fin est complétée par des lettres nulles). Il est possible de compliquer le décryptage en plaçant les blocs de façon à former un carré ou un rectangle puis de procéder au relevage par lignes, colonnes, en spirale (dextrogyre, senestrogyre) ou suivant un mot clé.
Selon la fréquence d'apparition des lettres ou signes, le cryptanalyste sait s'il est confronté à une méthode par substitution ou à une transposition. Dans ce dernier cas il constate la présence d'une séquence de plusieurs lettres (le test de Friedman permet de différencier un chiffre mono-alphabétique d'un chiffre poly-alphabétique). La substitution poly-alphabétique la plus connue est la méthode imaginée par Blaise de Vigenère (1587). L'alphabet de A à Z est écrit sur la première ligne d'un carré de 26 cases, puis de B à A sur la deuxième, C à B sur la troisième et ainsi de suite. Chaque lettre d'un texte clair peut donc être désignée par 26 digrammes. S'il est impossible d'appliquer la règle des fréquences, la méthode de Kasiski permet de le « casser », une amélioration consiste à adopter des alphabets désordonnés et à en brouiller le relevage.
Voyons un autre exemple de substitution dans laquelle chaque lettre du texte « clair » est chiffrée différemment suivant sa position par rapport à la clé utilisée.
clair : DEMAIN SOIR A NEUF HEURES
clé : 125341 2534 1 2534 125341
crypto : EGRDMO UTLV B ELXS IGZU I T
La lettre A sera chiffrée par A, B, C, D, E ou F suivant qu'elle correspond aux chiffres 1, 2, 3, 4, ou 5. Si le décrypteur connaît la longueur de la clé, il peut répartir le texte en groupes de lettres correspondant à la longueur de la clé, dans notre exemple : ERGDM - OUTLV - BPLXS - IGZUI - T, la règle des fréquences devient applicable à l'ensemble des premières lettres de chaque groupe : 1°, 6°, 11°, puis à l'ensemble des deuxièmes lettres : 2°, 7°, 12° et ainsi de suite pour les troisièmes, quatrièmes et cinquièmes lettres. Pour découvrir la longueur de la clé utilisée, on applique les principes de Kerckhoffs et Kasiski qui reposent sur les polygrammes. Digrammes : ES - LE - EN - DE - NT - ON - OU - RE - NE - SE - EL - AI - TE - LA. Trigrammes : ENT - LES - QUE - EDE - MEN - LLE - DES - TRE - ELE - EME -NDE. Les capacités de calculs des ordinateurs actuels permettent d'analyser les fréquences des tétragrammes (4 lettres consécutives).
Première règle : « deux polygrammes semblables du texte chiffré sont l'un et l'autre, le produit de deux polygrammes semblables du texte clair par deux polygrammes semblables de la clé », exemple :
RECHERCHEZ DANS LA CHEMINÉE DE CHEZ CHEVALET
63 12631 263 1263 12 63126312 63 1263 12631263
XHDJKUDJKC ECTV MC IKFOOQFG I L DJKC DJKYBNKW
Les 4 polygrammes semblables DJK du texte chiffré sont bien l'un et l'autre le produit de deux polygrammes semblables au texte clair CHE par des trigrammes semblables correspondant à la clé additive 126 (exemples empruntés au professeur Loccard).
« La longueur de la clé est égale au produit des facteurs premiers les plus fréquents des nombres représentant l'écartement des polygrammes semblables ». Disposons la phrase en groupe de 5 lettres, clé choisie, 3421.
RECHE RCHEZ DANSL ACHEM INEED ECHEZ CHEVA LET
34 213 21342 21342 13421 34213 42134 21342 134
UI EIH VEIHD FBQWN BFLGN LRGFG IE IHD E IHZC MHX
Nous constatons que le polygramme EIH se retrouve bien 4 fois et en 3e, 7e, 27 e et 31 rangs. Les écarts de ce polygramme sont donc 4, 20, et 4, les polygrammes semblables du texte chiffré correspondent bien aux polygrammes semblables de la clé. Nous repérons chaque fois le groupe codique 213 au-dessus de EIH. Si la clé se retrouve égale à elle même au-dessus des polygrammes semblables, c'est qu'elle est répétée un nombre entier de fois, et que l'écart des polygrammes semblables est un multiple entier de la longueur de la clé. Dans notre exemple, les écarts étant 4, 20 et 4, la longueur de la clé doit être un diviseur de ces trois nombres, soit 4.
Cette règle comporte des exceptions, des polygrammes semblables du texte chiffré peuvent n'être que de simples coïncidences. Par exemple, si l'on chiffre AB par 42, on obtient ED, mais il en va de même si on chiffre BC par 31. Il est évident que la mesure de l'écart entre ces deux groupes ne saurait donner aucune indication sur la longueur de la clé. Il faut donc prendre les facteurs premiers les plus fréquents et non les facteurs premiers communs. La longueur de la clé déterminée, on tronçonne le texte en groupes et on effectue le pointage des fréquences non plus sur l'ensemble du texte, mais sur l'ensemble des premières lettres de chaque groupe. L'opération est reportée sur les deuxièmes puis troisièmes et ainsi de suite, il devient alors possible, à condition que le texte offre une certaine longueur, d'attribuer à chaque lettre sa valeur réelle.
Un nombre ou un mot peut déterminer la procédure à suivre. Dans la transposition avec clé, il suffit d'impartir à la première lettre de l'alphabet rencontrée le chiffre 1, à la deuxième le chiffre 2, etc.
clé littérale : T - R - A - N - S - P - O - S - I - T - I - O - N
clé numérique : 12 - 9 - 1 - 4 -10 - 8 - 6 -11 - 2 -13 - 3 - 7 - 5
Il suffit ensuite d'écrire le texte en dessous de ces clés. Le relèvement des lettres se fait dans l'ordre numérique des colonnes (pour être ensuite disposées en blocs de cinq ou six lettres. Pour rendre la méthode plus sûre, on peut introduire une nouvelle clé (double transposition).
Pour un message chiffré par transposition de longueur n lettres, le nombre de permutations est factorielle n (n !). Si n égal 10 on obtient déjà 3.628.800 (1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9) messages différents ! On peut aboutir, par-contre, à des significations très différentes d'un même message. PACLSEPOESSARTREUEZRVAPEZTDERTEPSNEAR peut aboutir à : PARTEZ CAR VOUS ÊTES REPÉRÉ NE TARDEZ PAS, ou RESTEZ EN PLACE ET PRÉPAREZ VOS PÉTARDS ! Pour casser un chiffre, le décrypteur peut supposer qu'une séquence de lettres correspond à un mot probable contenu dans le cryptogramme (date, destinataire, émetteur, matériel, etc.).
Comme le titre l'indique, je me suis cantonné à l'essentiel, les procédés sont nombreux et certains principes combinés pourront se révéler bien plus sûrs que la chaîne informatique (portes dérobées, spywares). Souvenez-vous l'affaire Snowden, les services ont ressorti leurs machines à écrire (ne pas oublier d'en détruire le ruban après usage). Une méthode de chiffrement se doit de répondre à un besoin clairement identifié : conservation du secret, gymnastique cérébrale, jeux de logique, longueur du texte, temps de chiffrement, risque d'erreur, durée du secret souhaitée, moyen de transmission (matériel, immatériel), capacité du service adverse, etc.
Le chiffre trifide de Delastelle dans lequel chaque lettre est remplacée par trois lettres extraites d'un cube de 3 x 3 x 3 reste difficile à décrypter manuellement. Che Guevara codait ses messages destinés à Fidel Castro en utilisant une substitution simple dont il groupait les chiffres par cinq et de les additionner avec une clé composée d'une suite de chiffres aléatoires à usage unique (la clé, ou masque jetable, est aussi longue que le message et détruite après usage). Le procédé One pad time créé par Vernam en 1917 fut utilisé par les agents du SOE durant la Seconde Guerre mondiale et mis en place le 30 août 1963 sur les téléscripteurs (téléphone rouge) entre les USA et l'URSS.
« Posséder à fond la technique des procédés de chiffrement et bien connaître les méthodes de décryptement qui leur correspondent ne suffit pas à faire un cryptologue. Il faut y ajouter l'enseignement pratique et concret que peut seule donner une longue habitude de la recherche spéculative, s'exerçant régulièrement sur des problèmes infiniment variés et faisant appel tour à tour à la logique et à l'imagination dans ce qu'elles ont de plus subtil et de plus délié » Cdt Baudouin. Vous souhaitez vous initier, entraîner vos neurones ou exercer votre sagacité ? www.clubalkindi.com.
°°°°°°°°°°°°°°°°°°°°°°