| ★ APPLICATIONS ★ DIVERS ★ CR.A.O: CRYPTOGRAPHIE ASSISTÉE PAR ORDINATEUR / CRYPTO (CPCINFOS) ★ |
| CRYPTOGRAPHIE ASSISTEE PAR ORDINATEUR (1/2) | CRYPTOGRAPHIE ASSISTEE PAR ORDINATEUR (2/2) |
«Cryptographie» signifie «écriture cachée». C'est l'art de dissimuler le contenu d'un message initial (dit message en clair) au moyen d'un algorithme de codage, souvent appelé CLE, CHIFFRE ou CODE. Un algorithme, pour ceux qui ne connaissent pas encore ce terme, c'est simplement une marche à suivre, une séquence d'actions élémentaires. Le même algorithme sert au destinataire légitime du message à reconstituer, à décoder ce dernier. Si le message codé est intercepté par quelqu'un qui n'en possède pas la clé, celui-ci peut tenter de le décrypter (on dit aussi de le casser), parfois avec succès s'il connait suffisamment les diverses méthodes de codage.Dans AMSTAR & CPC N° 40 (décembre 89), H. MONCHATRE vous présentait un utilitaire de codage de fichiers binaires. Pour ma part, je vous exposerai d'abord les règles de la cryptographie, ainsi que quelques algorithmes classiques; ceci devrait vous permettre de développer éventuellement vos propres méthodes. Le mois prochain, vous trouverez un programme de codage de fichiers ASCII, quels qu'ils soient et quelle que soit leur longueur. Les heureux possesseurs d'un serveur pourront jouer à l'agent secret avec leurs correspondants. Pour les autres, l'échange de messages se fera sur disquette ou tout simplement sur papier, Outre un fichier texte, vous pourrez rendre confidentiel un fichier de fiches, ou même un programme BASIC sauvegardé en ASCII. Dernière possibilité, et pas la moins amusante : échanger des messages codés, et tenter de les décrypter sans en connaitre la clé; c'est un jeu de logique assez fascinant, parfois pratiqué par les cryptographes professionnels, et pour lequel des amateurs doués, tels Edgar POE, se sont passionnés. Je le recommande aux mordus des mots croisés. VOUS AVEZ DIT CRYPTOGRAPHIE ? Pour rendre un message incompréhensible au non-initié, il existe plusieurs moyens. Tout d'abord, on peut remplacer des mots, locutions ou phrases par des mots convenus ; il s'agit alors d'un CODE au sens strict. Ce système, qui nécessite l'emploi d'un dictionnaire-code, a été essentiellement utilisé par les marines de guerre. Bien que non destinés à un usage cryptographique, les langages informatiques sont dans ce sens des codes. On peut aussi brouiller l'ordre normal des caractères du mes- INITIATION.A.LA.CRYPTOGRAPHIE.SUR.AMSTRAD.CPC
SUBSTITUTION Pour coder le texte, superposons un alphabet en clair (normal) à un alphabet codé. Ce dernier correspondra dans cet exemple à un DECALAGE des lettres de 3 rangs dans l'ordre croissant (figure 1). Pour coder la première lettre, cherchons la lettre se trouvant sous le I : c'est le L. La lettre correspondant à N sera le Q, et ainsi de suite. Nous obtenons le texte codé suivant : LQLWLDWLRQ.D.OD.FUBSWRJUDSKLH. VXU.DPVWUDG.FSF La longueur naturelle des mots du texte en clair a été respectée, et nous avons ce qu'on appelle un CODE IRREGULIER. Pour rendre l'algorithme de codage moins transparent, opérons un COMPACTAGE (suppression des espaces), puis un REGROUPEMENT des lettres en blocs réguliers (de 3, ou plus généralement de 5 lettres) suivi d'une EXPANSION (insertion d'espaces pour séparer es blocs). Notre texte, ainsi transformé en un CODE REGULIER, est déjà moins facile à décrypter : LQLWL.DWLRQ.DODFU.BSWRJ.UDSKL. HVXUD.PVWUD.GFSFE Pour compléter le dernier bloc, nous avons ajouté une lettre aléatoire, choisie de préférence parmi celles qui présentent une fréquence élevée dans un texte normal. Cette lettre, sans valeur dans la signification du texte, est dite LETTRE NULLE. Afin de dérouter encore plus le décrypteur, on peu aussi découper le texte codé en blocs de 4 lettres séparés par des espaces, et ajouter à chaque bloc une 5ème lettre nulle (aléatoire), comme ceci : LQWC.LDWLI.RQDOA.DFUBZ.SWRJO. UDSKY.LHVXD.UDPVH.WUDGJ.FSFEG Au lieu d'utiliser un décalage constant pour le codage, nous aurions pu faire varier ce décalage. Pour cela, le moyen le plus commode est d'exprimer cette variation dans un MOT-CLE ou une EXPRESSION-CLE. Comment utiliser un mot-clé? Il y a essentiellement deux manières. Dans la première, le mot-clé peut comporter plusieurs fois la même lettre, alors que dans la seconde, chaque lettre ne doit y figurer qu'une fois. 1 - Première manière Soit le mot-clé AMSTRAD. Dans la pratique, pour être efficace, un mot-clé doit autant que possible comporter au moins 5 lettres. On utilise pour les lettres codées un alphabet disposé en ordre croissant ou décroissant, ou dans un savant désordre. Choisissons le cas d'un alphabet en ordre croissant (donc tout à fait normal) et écrivons-le 2 fois de suite. Plaçons au-dessus l'alphabet normal pour les lettres en clair, en imaginant que ce dernier peut glisser latéralement sur l'autre, ce qui permet un décalage variable (figure 2).
Le mot-clé commence par un A. Faisons glisser l'alphabet du dessus jusqu'à ce que sa première lettre soit au dessus du A de l'alphabet codé. Le message commence par un I ; en dessous du I se trouve un I, ce sera la première lettre du message codé (figure 3). La 2e lettre du mot-clé est M. Faisons à nouveau glisser l'alphabet du dessus pour que son A se trouve au-dessus du M. La 2e lettre du message (N) sera donc codée par Z (figure 4).
Même chose jusqu'à la 7e et dernière lettre du mot-clé, D, qui fixe le décalage pour coder la 7ème lettre du message, T, en W. Pour continuer, il suffit de prendre à nouveau la première lettre du mot-clé, qui permet de coder la 8ème lettre du message, et ainsi de suite jusqu'à la fin. Cette méthode est appelée CHIFFRE DE SAINT-CYR, du nom de l'Ecole Militaire où elle fut élaborée. Voici le résultat : IZAMZAWIAF.T.CA.FRKHMFGUABZBV.SXR.MELKRDD.OHV L'Intérêt de cette méthode est de rendre beaucoup moins perceptible pour le décrypteur la présence d'une périodicité dans le codage (égale à 1 dans le tout premier exemple, à la longueur du mot- clé sinon). La périodicité est nulle (et la fiabilité maximale) lorsque la longueur de l'expression-clé est égale à celle du message : pour chaque lettre codée, le décalage est différent, et aucun schéma régulier n'apparaît ; il s'agit cependant là d'un cas plus théorique que pratique. Deux remarques : d'abord, comme le mot-clé contient la lettre A, certaines lettres du message codé (la le et la 6èm®, par exemple) seront identiques aux lettres correspondantes du message en clair ; aucune importance, au contraire : dans l'ignorance de ce détail, un décrypteur pourra chercher longtemps l'équivalent de ces lettres... Ensuite, grâce au décalage variable, des lettres identiques dans le message en clair seront représentées par des lettres différentes dans le message codé : par exemple, la le, la 3e et la 5e. Mais, comme le mot-clé est de 7 lettres, on retrouvera toutes les 8 lettres Un décalage de même valeur (d'où l'intérêt d'un mot-clé suffisamment long). Dans cet exemple, comme l'alphabet utilisé ne comprenait que les lettres majuscules, les espaces (figurés par des points) n'ont pas été codés et sont demeurés inchangés. Si cela apparaît comme un inconvénient, on peut les supprimer d'abord par compactage, puis opérer sur le texte codé un regroupement en blocs réguliers séparés par des espaces (expansion). On peut aussi utiliser comme «alphabet» un jeu de caractères étendu comprenant les espaces, et coder également ceux-ci. 2 - Seconde manière C'est l'ALPHABET DOUBLE PARALLELE. Utilisons un autre mot- clé, HABITUDE par exemple. Cette fois, le mot-clé fait partie intégrante de l'alphabet-code. Pour écrire celui-ci, commençons par écrire le mot-clé, puis le reste de l'alphabet dans l'ordre croissant (c'est-à-dire les lettres qui ne figurent pas dans le mot-clé). Puis, comme d'habitude, plaçons au-dessus l'alphabet normal (figure 5).
A chaque lettre du message en clair, figurant dans l'alphabet du dessus, correspond la lettre codée juste en dessous. I devient C, N devient L, etc. Voici le texte codé: CLCRCHRCML.H.JH.BPYNRMDPHNECT.QSP.HKQRPHI.BNB Les espaces n'ont pas été codés. Il serait souhaitable d'effectuer un compactage suivi d'un regroupement et d'une expansion. Le décalage est différent pour la plupart des lettres (périodicité nulle). Les dernières sont inchangées ; ce n'est pas grave dans la mesure où. il s'agit de lettres peu fréquentes d'une part, et où quelques lettres codant sur elles-mêmes ne constituent pas un inconvénient d'autre part. Par contre, il y a ici une faiblesse par rapport à la méthode précédente, c'est que chaque lettre en clair correspond toujours à la même lettre codée ; c'est la faille par laquelle un cryptographe averti peut pénétrer le code. La SUPPRESSION DES FREQUENCES est un moyen de lui compliquer la tâche. Dans ce cas, les lettres très fréquentes (comme le E) sont représentées par plusieurs lettres ou chiffres : par exemple (et au hasard) par 1, 2 ou 3, ou par X, Y ou Z. Reprenons notre tout premier exemple : LQLWLDWLRQ.D.OD.FUBSWRJUDSKLH.VXU.DPVWUDG.FSF Au lieu de coder le A par D, codons-le par A, B ou C ; pour une meilleure clarté, ces lettres seront soulignées ici : LQLWLBWLRQ.C.OA.FUBSWRJUASKLH.VXU.CPVWUBG.FSF il pourrait y avoir confusion avec les A, B et C qui codent respectivement le X, le Y et le Z. Mais le destinataire du message, connaissant la règle, n'aura aucun mal à le décoder correctement. TRANSPOSITION Ici, les lettres seront exactement les mêmes dans le message en clair et dans le message codé, mais se présenteront dans un désordre savamment étudié. La première possibilité, la plus simpliste, consiste à permuter les caractères suivant des règles précises. Divisons, par exemple, notre message en blocs de 6, puis échangeons les caractères 1 et 6, 2 et 5, et 3 et 4. Notre message faisant 45 caractères, vous me direz que le compte n'est pas rond. Qu'à cela ne tienne, ajoutons 3 espaces à la fin, figurés par 3 points. La figure 6 montre le résultat.
Sans qu'il s'agisse vraiment d'un code régulier, la longueur des mots d'origine a quand même été bousculée. L'ensemble a un aspect suffisamment éloigné du texte initial, sauf à la fin. Je vous al prévenu que c'était une méthode simpliste ; en fait, elle ne s'emploie guère qu'en complément d'une autre. Mais au rayon du brouillage des lettres, il y a mieux. Reprenons nos 8 blocs de 6 caractères, et disposons-les verticalement côte à côte, du haut vers le bas, selon une matrice 6x8.
Si on considère l'alignement horizontal des lettres, on voit qu'il est possible de les regrouper en 6 nouveaux blocs (figure 7). Alignons ces blocs en séquence, et nous obtenons ceci IT.YASSCNILPPUTPIOATHRRCTN.OI.A.I.CGEAD.AARR.M. Intéressant, non ? Mais il y a des variantes encore plus performantes, qu'on peut combiner entre elles ; elles font appel à certaines des techniques que nous venons de voir, et qui prennent alors tout leur Intérêt. Dans le texte initial, supprimons d'abord tous les espaces (compactage) ; choisissons le nombre de lignes et de colonnes de la matrice (c'est-à-dire le nombre de caractères par bloc, et le nombre de blocs du texte en clair, tout simplement) en fonction de la longueur du message, éventuellement complété par des lettres nulles (mais pas des espaces). A l'aide de la matrice, extrayons les nouveaux blocs et alignons-les en séquence. Découpons maintenant cette séquence en blocs de 5 lettres, par exemple, et séparons-les par des espaces (expansion). Avec une matrice de 5 lignes x 8 colonnes (40 lettres, dont un E nul ajouté à la fin), nous obtenons finalement ceci (vérifiez, ce sera un bon exercice) : IAAYR.EMDNT.LPASS.CIIAT.PUTPT.OCOHR.RCINR.GIAAE Nous avons écrit le texte dans la matrice du haut vers le bas, toujours dans le même sens,à partir du coin haut et gauche et en alignant les blocs de gauche à droite. Nous aurions pu aussi bien partir du coin haut et droit, et aligner les blocs initiaux de droite à gauche, ou partir du coin bas et gauche en écrivant de bas en haut et de gauche à droite, ou enfin partir d'un angle quelconque et écrire alternativement le texte dans un sens, puis dans l'autre (figure 8).
Une variante simple et intéressante, nommée «verticale parallèle», consiste à diviser le message en 2 moitiés, après suppression des espaces. La première moitié est écrite sur une colonne, en partant du bas ou du haut ; la seconde moitié est écrite sur une seconde colonne, dans le même sens ou en sens inverse. Les lettres sont reprises horizontalement 2 par 2 et regroupées en blocs (de 5 lettres, par exemple) séparés par des espaces. Si le nombre de lettres du message compacté d'origine est impair, on rajoute une lettre nulle à la fin. En écrivant de bas en haut, puis de haut en bas, de la droite vers la gauche, voici ce que l'on obtient : RGAOP.THPIY.ERSCU.ARLAA.MNSOT.IRTAA.DICTP.ICNXI Plus le nombre de variantes possibles est élevé, plus cela complique le travail du décrypteur, et plus II lui faudra de temps pour casser le code ; c'est ce que l'on appelle le FACTEUR TRAVAIL. Dernière possibilité de brouillage de la matrice, avant d'en extraire les blocs horizontaux et de les réassembler (avec ou sans compactage/ expansion) : PERMUTER les lignes, les colonnes, ou les deux à la fois. De même que dans le premier exemple de transposition examiné plus haut, l'algorithme de permutation sera commodément exprimé par un code numérique, séquence de nombres dont la valeur de chacun représente l'ANCIEN emplacement, et le rang le NOUVEL emplacement de chaque élément du bloc. Dans ce premier exemple, l'ordre avant permutation était 123456, et après 654321 ; pour éviter ce schéma trop régulier, on aurait pu échanger 1 /5, 2/4 et 3/6, le code devenant alors 546213. Au lieu de permuter les blocs ou leurs éléments, on peut les DEPLACER, ce qui augmente le nombre de combinaisons possibles : notre bloc de 6 éléments peut ainsi être codé selon 614352. Si le nombre de lignes et/ou de colonnes de la matrice dépasse 9, alors on sépare les nombres par des points ou des tirets, pour supprimer toute ambiguïté (exemple : 9-6-5-12-3-2-10-11-1-7-8-4). Si on désire effectuer une permutation ou un déplacement double sur une matrice, celle-ci doit être une matrice carrée, le même code numérique servant de guide pour le déplacement des colonnes et celui des lignes. Si la matrice est rectangulaire, alors il faudra 2 codes différents, ce qui complique le codage et le décodage, mais peut tout à fait s'envisager. SURCODAGE Vous venez de voir qu'il est possible de combiner plusieurs des outils de codage disponibles. Pour accroitre encore l'efficacité du brouillage du texte, on peut aussi utiliser successivement la substitution, puis la transposition (ou l'inverse). DECODAGE Je ne l'ai pas encore dit ouvertement, mais II est évident que le décodage du message se fera en appliquant à l'envers l'algorithme qui a servi au codage. S'il y a eu compactage puis expansion portant sur les espaces, il faut d'abord supprimer les espaces, appliquer l'algorithme inverse, puis restituer l'espacement normal des mots en clair. Seule cette dernière étape ne pourra pas être automatisée, à moins de disposer d'un vérificateur orthographique avec dictionnaire en mémoire (impensable eu égard à la capacité du CPC). SUBSTITUTION OU TRANSPOSITION ? Le choix n'est pas indifférent. Si la fiabilité de ces 2 méthodes est comparable, la transposition ne s'applique facilement qu'à des messages relativement courts (une chaine ASCII de 255 caractères maxi), alors que la substitution s'accommode de fichiers ASCII de longueur quelconque. UN PEU D'HISTOIRE (MAIS PAS TROP) La cryptographie est un art fort ancien, associé dès son origine aux Intrigues politiques, à l'espionnage et aux tumultes guerriers. Le premier procédé connu est la SCYTALE, utilisée par LYSANDRE, roi de SPARTE, vers l'an 400 avant notre ère. Une longue bande de parchemin, ou la ceinture du messager, était enroulée autour d'un bâton de diamètre déterminé. La première ligne du message était alors écrite dans le sens de la longueur du bâton, une lettre par spire. Après avoir légèrement fait tourner l'ensemble, on écrivait la 2è ligne, et ainsi de suite. La bande une fois déroulée ne montrait qu'une suite de lettres apparemment dépourvue de sens. Mais le destinataire, disposant d'un bâton de même diamètre, pouvait facilement reconstituer le message. C'est le premier procédé de codage par transposition, Jules CESAR, pour sa part, avait inventé un code rudimentaire par substitution, qui n'est autre que le premier exemple présenté dans cet article. Au Moyen-Age apparurent des alphabets à symboles (notamment astrologiques). Mais c'est à partir de la Renaissance que la cryptographie trouva dans les complots tortueux de l'époque un terrain éminemment favorable à son développement. Dans la seconde moitié du XVIe siècle, Giovanni Battista délia PORTA et Biaise de VIGENERE établirent les premières méthodes modernes par substitution, au moyen de tables d'usage simple et rapide, utilisant un mot-clé. La TABLE DE VIGENERE n'est rien d'autre qu'une manière particulière d'utiliser l'algorithme mis en œuvre dans le CHIFFRE DE SAINT-CYR, créé 3 siècles plus tard... Du XVIIe au XIXe siècle, vu l'ampleur croissante des campagnes militaires, le développement des communications entre corps d'armée stimula la créativité des cryptographes, mais aussi des décryp-teurs... Au début de ce siècle, les états-majors de chaque grande nation européenne étaient parvenus, soit à casser les codes des autres pays, soit à se les procurer par corruption ou espionnage. Avec la première guerre mondiale, et pour pallier ce problème, Il apparut nécessaire de trouver un algorithme de codage souple, rapide et fiable, où il suffirait de changer régulièrement de code. Papier et crayon étaient jusque là les outils simples et efficaces du cryptographe. Dans l'entre-deux guerres apparurent des machines électro-mécaniques permettant une augmentation considérable de la vitesse de codage/décodage. La première, en 1920, fut la machine allemande ENIGMA de l'ingénieur SCHERBIUS, qui l'avait conçue pour la correspondance confidentielle d'affaires. Aucun succès dans ce domaine et la machine et son inventeur tombèrent dans l'oubli. Elle fut néanmoins exhumée, quelque peu perfectionnée et utilisée à d'autres fins par les armées du llle Reich lorsqu'elles envahirent l'Europe. Autour d'une copie de la machine récupérée en Pologne en 1939, le gouvernement britannique rassembla une éauipe de brillants cerveaux (dont Alan TURING, qui s'illus-* tra 20 ans plus tard dans les premiers balbutiements de l'intelligence artificielle). Après adaptation de la machine, et en utilisant des méthodes d'analyse statistique pour déceler les schémas linguistiques permettant le décryptage, les anglais parvinrent à décoder en quelques heures une bonne partie des messages radio ennemis (malgré un changement de code 3 fols par jour). Les allemands répliquèrent par un modèle électro-mécanique beaucoup plus performant, le SCHLUS-SELZUSATZ (clé supplémentaire). Relevant le défi, les britanniques mirent en service COLOSSUS, un calculateur électronique à lampes (2400 !), en 1943 soit 2 ans avant l'ENIAC américain (le premier ordinateur électronique), Après la guerre, les ordinateurs furent bien sûr utilisés pour coder les messages secrets à usage diplomatique et militaire. Mais dans les années 70, avec le développement des réseaux informatiques utilisant les lignes téléphoniques et la banalisation des modems, il devint indispensable d'assurer la confidentialité de certaines des données échangées (passation d'ordres de virement entre banques, par exemple), pendant leur transfert. Deux premiers systèmes virent le jour aux Etats-Unis à la fin des années 70, l'un mis au point chez l'incontournable IBM, l'autre au MIT (Massachussets Institute of Technology). Dans les 2 cas, la protection des données reposait sur la confidentialité des clés, l'algorithme pouvant être rendu public. Le premier code et décode les données au moyen de la même clé, un jeu de 8 nombres compris entre 0 et 127 ; le message est divisé en blocs de 8 caractères, brouillés jusqu'à 16 fois par association de TOUS les procédés de base énoncés plus haut, portant sur les bits et non sur les signes. Par le biais d'un XOR logique, le codage de chaque bloc, à partir du 2e, dépend du précédent. Le second fait appel à 2 clés (des nombres premiers, jusqu'à 200 chiffres !) entretenant entre elles un rapport mathématique, et que chaque partenaire d'un réseau protégé possède : 1 clé dite publique servant à coder les messages émis, et 1 clé dite secrète connue de lui seul, pour décoder les messages reçus. Actuellement, la protection des données dans les réseaux autres que ceux d'organismes financiers, se fait surtout par divers systèmes d'accès sélectif et de reconnaissance des utilisateurs autorisés, utilisant notamment un mot de passe. FANTOMAS CONTRE FANTOMAS Nous venons de le voir, décrypteurs et cryptographes ont toujours rivalisé d'ingéniosité, les uns cherchant à dévoiler ce que les autres voulaient leur cacher. Le plus piquant est qu'ils appartenaient souvent au même monde, les meilleurs cryptographes faisant les meilleurs décrypteurs. Une question se pose alors, celle de la fiabilité des systèmes de codage. On peut même se demander si, face aux meilleurs décrypteurs disposant de temps et de moyens, il existe seulement un système infaillible. Pour Edgar POE, la réponse est non ; ce fan de cryptographie a d'ailleurs construit sa nouvelle «The Gold Bug» (oh le beau titre !) autour d'un message secret. Il avait proposé dans un article, en 1840, qu'on lui adresse des messages codés à casser, en imposant quelques contraintes : substitution seule, sans compactage ni expansion. Il reçut des centaines de messages, qu'il cassa tous ! Depuis, la cryptographie a fait quelques progrès, et on peut définir comme infaillible le système suivant : soit un ensemble de clés numériques ; chaque nombre de la clé représente le décalage à utiliser pour chaque lettre du message (autant de nombres que de lettres à coder) ; chaque clé ne sert que pour un seul message, puis est détruite. Ce système a été parait-il utilisé dans le cas du fameux téléphone rouge Washington-Moscou. Infaillible peut-être, mais d'un emploi certainement délicat. En fait, le problème est mal posé. Admettons que tous les autres systèmes soient théoriquement vulnérables, toutefois certains moins que d'autres, Le décryptage dépend essentiellement de la puissance de traitement disponible ; et si les ordinateurs ont permis d'augmenter considérablement ia vitesse et la complexité du codage/décodage, ils constituent aussi un outil précieux dans les mains des décrypteurs. Alors ? Eh bien un code est considéré comme parfaitement satisfaisant si le temps nécessaire à le percer à jour est tel que les informations qu'il cache seront sans aucun intérêt lorsqu'on sera parvenu à les décrypter ; c'est la notion de «facteur travail» exposée plus haut. Dans le cas des 2 systèmes américains de protection des transferts de données, le temps d'ordinateur nécessaire pour découvrir la clé se chiffre en milliers d'années... Pour revenir au sujet qui nous préoccupe, l'utilisation d'algorithmes de codage dans un cadre essentiellement ludique, le logiciel que je vous présenterai le mois prochain comporte des méthodes livrées «clés en main», plus quelques routines qui vous permettront de personnaliser vos codages, suivant les principes énoncés plus haut. Ces différents sous-programmes vous permettront également de tenter le décryptage de messages inconnus. N'attendez pas de moi une méthode pour casser les codes, il n'y en a malheureusement pas. il existe cependant des astuces pour vous guider :
A suivre... G. DUBUS, CPCINFOS n°25 |
|  |
|
