vendredi 13 décembre 2019 - par Desmaretz Gérard

Invitation à la cryptanalyse

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.

Al-Kindi né au IX° siècle en Irak était connu pour décrypter les messages en utilisant l'analyse de fréquence des lettres d'un texte. Dans chaque langue, certaines lettres reviennent plus fréquemment et d'autres sont peu courantes à un endroit donné, « j » en finale par exemple. Si le message est suffisamment long, il suffit de les compter puis de les classer selon leur fréquence d'apparition, ensuite de substituer à celles qui reviennent le plus souvent les lettres classées par ordre de fréquence décroissante : ESARTINULOC (Gén Cartier), ESARINTULOC (Cdt Bazeries), ESAINTRULOC pour la langue française (Les radio-amateurs remarqueront qu'il s'agit, peu ou prou, des lettres les plus courtes et de leur inverse en code Morse : A ._ N_. E. T_).

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.

°°°°°°°°°°°°°°°°°°°°°°



11 réactions


  • Clark Kent Séraphin Lampion 13 décembre 2019 08:47

    « 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. »

    C’est pareil pour les proctologues : il ne suffit pas d’avoit le diplôme pour être capable de prédire l’avenir en regardant « par le petit bout de la lorgnette ».


  • eau-mission eau-pression 13 décembre 2019 12:18

    C’est très bien de proposer une occasion de remue-méninges aux élèves.

    Dans mon court passage devant eux, j’avais eu plaisir à voir une minorité non négligeable des jeunes accrocher au Kangourou des mathématiques.

    En attendant leur réaction, on peut se demander ce que la prise de conscience attendue va leur apporter.

    Nos vieux comploto-parano luttent-ils eux-même contre la toute-puissance calculatoire des machines ?

    Vous n’avez pas donné votre opinion sur la machine quantique, supposée cracker tous les codes. Lehning pense que c’est du flan.

    Il y aurait aussi la piste culturelle pour armer les jeunes contre le crackage de leur personnalité : augmenter leur vocabulaire, casser la dépendance à FB, orienter autrement que vers le mythe Greta leurs connivences.


    • xana 13 décembre 2019 12:46

      @eau-pression
      Une opération de remue-méninges pour les élèves ? Je n’y crois pas. C’est plutôt pour se faire de la mousse à peu de frais.
      Ca n’apportera absolument rien aux jeunes. Comme je le disais, c’est comme de leur apprendre à tailler du silex. Mais quand on ne sait absolument pas ce que c’est qu’un silex, il faut réinventer la culture générale pour des gosses qui n’en ont rien à faire parce que ca n’est pas sur fesse-Bouc.
      Pour la machine quantique, à part faire beaucoup plus de calculs dans le même intervalle de temps, je ne crois pas que ca changera grand chose. Les codes à clé devront décupler leur nombre d’octets et on reviendra à la situation actuelle. Tant que les concepteurs ne changeront pas leurs concepts, les chiffres « spéciaux » n’auront rien à craindre. Et donc tant qu’on enseignera les techniques actuelles, pas de souci...


    • eau-mission eau-pression 13 décembre 2019 13:17

      @xana

      Vous ne me guidez pas, moi le vieux parano, vers la bonne attitude : se battre techniquement, en allant chercher les bons outils, pour protéger ma vie privée, cela a-t-il un sens ou est-ce techniquement voué à l’échec ?

      Perso, j’éprouve une opposition viscérale au discours du copain de Macron, Laurent Alexandre.

      Viscérale veut bien dire que la justification de ce rejet ne m’est pas encore montée au cerveau (au secours, @exol !)

      Je peux ajouter mon expérience de prof de maths. Face à des élèves en délicatesse avec la matière (beaucoup pas doué donc entrés dans une spirale d’échec, d’autres surprenants) j’ai essayé de leur rendre goût à la résolution de problèmes en leur rendant l’usage des calculatrices et du calcul formel automatisé familier. Je n’ai pas la prétention d’établir un constat général de cette expérience. J’ai juste ressenti que quand on n’a pas le goût de la formalisation, c’est pas gagné.

      Et pourtant, si je suis d’accord avec Dowek sur un point, c’est sur l’utilisation de modèles de simulation.


    • xana 13 décembre 2019 14:06

      @eau-pression

      Mettre sa vie privée à l’abri des indiscrétions n’est pas voué à l’échec. Mais il faut bien autre chose qu’un simple logiciel.
      Ca veut dire d’abord qu’on est capable de différencier ce qui mérite d’être protégé (souvent peu de chose, mais il ne faut pas se tromper) et le reste. Ensuite cela signifie que l’on est capable de s’astreindre à un minimum de discipline pour protéger chaque jour ce qui mérite de l’être.

      Pour votre ami Alexandre, sachez que tous ces discours prétentieux ne recouvrent pas grand-chose. Si le phénomène de l’intelligence vous intéresse, il vaut mieux aller chercher comment elle peut se manifester chez d’autres espèces (« Are we smart enough to know how smart animals are », de Frans De Waal, par exemple), plutôt que céder à l’anthropocentrisme en ne considérant que l’IA parce qu’elle est à la mode, et qu’implicitement, on considère que nous et nos productions sommes évidemment « supérieurs ».


  • xana 13 décembre 2019 12:32

    Ces systèmes de chiffrement ne présentent plus qu’un intérêt historique. La substitution, la transposition étaient des techniques valables à l’époque où un message se transmettait sur du papier et où tout se faisait manuellement.

    Ce concours me fait penser à un concours de taille de silex pour se faire un outil. Ce n’est même plus pédagogique ! C’est de la bêtise.

    De nos jours, avec un ordinateur non spécialisé, quiconque le souhaite vraiment peut mettre au point un système beaucoup plus complexe, voire absolument indéchiffrable. Un programme de quelques lignes permet de « traiter » en quelques micro-secondes n’importe quel document, texte ou image, et le brouiller de manière inextricable. Et ici je ne parle pas des systèmes à clé symétrique ou non que tout le monde utilise (parce que c’est la mode) et qui pourraient être déchiffrés par des gens bénéficiant d’une puissance de calcul énorme. Il existe d’autres systèmes qui ne pourront jamais être décryptés, parce qu’ils utilisent d’autres concepts. Et il n’y a pas besoin d’être un as en programmation, il suffit d’un peu d’imagination !!!

    Juste un exemple : Vous avez entendu parler de stéganographie, qui consiste à cacher un texte dans les milliers d’octets d’une image quelconque. Vous pouvez aussi crypter votre texte en intercalant entre chaque octet du texte un nombre aléatoire d’octets aléatoires... ca rallongera un peu le texte, mais quelle importance ? Si vous avez préalablement modifié votre texte avec une clé même simple, il devient déjà à peu près impossible à déchiffrer, à moins de savoir quelle est la règle d’introduction des octets de masquage... Et ce n’est qu’une technique extrêmement simple !

    Pour ceux qui croient encore que tout peut toujours être déchiffré, apprenez qu’il existe encore des textes codés même anciens qui ont résisté et résistent encore aux efforts, simplement parce qu’ils utilisent d’autres concepts que la sacro-sainte substitution-transposition. Gageons que la plupart ne seront jamais décodés.


    • eau-mission eau-pression 13 décembre 2019 12:53

      @xana
      Effectivement, la stéganographie est mal connue. Pourriez éviter de la propager trop vite, quand même.

      En poussant votre raisonnement sur l’école (et il faut le faire) on en arrive à se demander s’il est raisonnable de garder ce vieux scénario prof-classes.
      Je suis en phase de digestion de cette conférence, où sont soulevés pas mal de lièvres d’actualité. En particulier, faut-il démontrer Pythagore ou insister sur la façon de se servir de cette propriété géométrique ? Pour faire savant, on pourrait parler du théorème des 4 couleurs.

      Si on veut qu’il reste un lieu de développement du libre-arbitre, il faut bien à un moment exposer concrètement le problème. A priori, cette initiative pédagogique peut leur faire comprendre que l’esprit humain crée ses propres outils.


    • xana 13 décembre 2019 13:43

      @eau-pression
      La stégano étant déjà connue, j’en ai juste fait un exemple pour indiquer qu’on peut cacher un texte crupté au sein d’un document lui-même composé de caractères aléatoires. Mais il existe une infinité de possibilités en dehors de cela, seulement limitée par notre manque d’imagination.
      J’ai été prof autrefois, mais j’ai perdu totalement la foi. Si dans nos classes il existe encore quelques élèves capables de faire mieux que boutonner leur téléphone, je n’aurai plus le courage de leur réapprendre la culture humaine depuis le début. Ils n’ont plus besoin de profs et ne les croient plus, les réseaux sociaux leur tenant lieu d’esprit. Peut-être si vous êtes assez jeune pour survivre quand Internet s’effondrera ?


    • eau-mission eau-pression 14 décembre 2019 10:53

      @xana

      Ils n’ont plus besoin de profs et ne les croient plus, les réseaux sociaux leur tenant lieu d’esprit.

      Votre constat est à fois juste et excessif. Je vous accorde sans difficulté le droit d’être désabusé, ayant moi-même baissé les bras devant la montagne à soulever : redonner son sens à l’école. Or, si je n’avais qu’une qualité, ce serait la ténacité.

      S’il nous reste le courage d’assumer notre statut d’ancien, il faut d’abord dire haut et fort que l’institution doit être rasée puis redéfinie. Votre phrase ci dessus, elle traduit un message que la jeunesse nous lance, car un individu en construction se projette plus aisément dans le monde futur que nous les anciens, dont le rôle est d’abord de leur expliquer le pourquoi du comment.

      Si on laisse faire, la jeunesse s’abandonne aux réponses googliennes et aux émoticones standardisés. A beaucoup, cela suffit, et vous ne les trouvez pas sur les rond-points. Ces instruments leur fournissent un cadre encore plus sécurisant que les murs de l’école et la palette des métiers de notre époque.

      Le goût de la vie, c’est d’affronter ce défi : l’élève doit dépasser le maître. Etre ambitieux dans la construction de l’individu, c’est l’orgueil qu’on peut partager entre générations. Au moins, ça relie l’individu aux structures existantes et à ceux qui les ont bâties.

      Imaginer l’effondrement d’internet ? Vous m’en demandez beaucoup, vu comme l’arrivée de l’électronique a alimenté mes rêves de jeunesse. Electronique balbutiante, pour vous donner une idée de mon âge.

      On en revient au sujet de l’auteur, désespérément absent : développer la conscientisation de cette toile (connaissance de sa réalité physique et algorithmique) peut éviter l’uniformisation des comportements et les dérives totalitaires.

      Encore un mot en réponse à ce que vous dites sur l’autre post. On peut débattre sur la prétention de l’homme à se croire supérieur (mon âme de paysan vous rejoindrait sans doute), mais on doit surtout prendre conscience de la puissance destructrice de la technique. Malheureusement, Macron comme les auditeurs de L.Alexandre ont la capacité de développer les moyens de détruire notre environnement, notre humanité, et bien peu remettent en cause cette tendance suicidaire.


  • Ruut Ruut 14 décembre 2019 06:12

    Pour crypter il n’y a pas que les math :)


    • eau-mission eau-pression 14 décembre 2019 10:56

      @Ruut
      Oui, les matheux cryptent en plein jour.
      Cependant, ils ne disent rien de leurs pratiques souterraines (faudra que je retrouve mon ancien avatar).


Réagir