|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Historique des techniques
de cryptographie :
Depuis 3000 ans environ, les êtres humains ont tenu à garder secret certaines conversations. Pour cela, il y eût diverses techniques de cryptage reposant sur des principes méconnus des "espions" adverses.
L'écriture invisible, au jus de citron : Ecrire un message à l'aide d'une plume trempée dans du jus de citron permet de rendre le message invisible. Pour être en mesure de le lire, il faut connaître le truc : il faut approcher la feuille de papier, sur laquelle le message est écrit, d'une flamme et le message apparaît en transparence.
Le disque de Phaïstos : En 1908, sur une plaine crétoise de la Messara, une équipe d'archéologues italiens exhument au milieu des ruines millénaires du palais de Phaistos un disque d’argile recouvert sur ses deux faces de pictogrammes inconnus.
Le disque de Phaïstos est en argile cuite très fine, un peu irrégulier. Son diamètre varie de 15,8 cm à 16,5 cm, son épaisseur de 16 à 21 mm. Sur chaque face une ligne en spirale fait fonction de guide, comme les lignes d'un cahier d'écolier moderne. Cliquez sur les images pour les agrandir : Face A : Sur une face, 122 hiéroglyphes en 31 groupes séparés l'un de l'autre par un trait vertical. Sur l'autre 199 en 30 groupes pareillement séparés. Ces hiéroglyphes ont été, non pas tracés, mais estampillés (c'est le premier exemple connu). NB : L'estampillage est une forme de gravure. À quoi ressemblent ces hiéroglyphes? Pêle-mêle, on y voit une tête chauve, une autre coiffée comme un Mohican, une coquille Saint-Jacques (ou un gant de baseball), une mâchoire d'âne (ou une gondole vénitienne), un bouclier rond (ou un barillet de revolver), une équerre, une colombe avec une branche d'olivier, un chrysanthème (ou une marguerite), un pressoir (ou une ruche), ... En tout, 45 signes différents. Les traductions proposées vont de l'hymne à Poséïdon au récit de la disparition de l'Atlantide. C'est un fait bien connu des experts en cryptologie que, étant donné un texte chiffré suffisamment court, on peut en proposer à peu près n'importe quel déchiffrement sans qu'il soit possible de décider lequel est le vrai. Or, non seulement le texte du disque de Phaïstos est court, 241 hiéroglyphes, mais on n'en connaît pas la langue. On ne s'accorde même pas sur le sens de l'écriture: du centre à la périphérie, ou l'inverse. Et on ne risque pas de le savoir, car Shannon et Weaver ont prouvé que la mesure de la propriété mathématique fondamentale des textes, l'entropie, était la même qu'on les lise dans un sens ou dans l'autre.
La technique du rouleau assyrien : Le message est écrit sur une feuille enroulée autour d'un rouleau d'un certain diamètre. Durant le transport de la feuille, le message est illisible. Pour lire le message, on enroule la feuille autour d'un rouleau de même diamètre.
C'est une technique de transposition : elle consiste à modifier l'ordre des lettres, c'est-à-dire à faire des anagrammes. anagramme : n. fém. Mot composé avec les lettres d’un autre mot, placées dans un ordre différent: «écrit» est l’anagramme de «récit». © Dictionnaire Hachette 1998 Nous pouvons décrire très simplement cette méthode de chiffrement sous forme mathématique : par exemple, la permutation (2, 4, 1, 3) consiste à échanger la 1ère lettre avec la 2ème, la 2ème avec la 4ème, la 3ème avec la 1ère et la 4ème avec la 3ème, et ainsi de suite avec les groupes de quatre lettres suivants. NB : Il est bien évident que cette technique n'est valable que dans le cas de cryptages de messages assez longs. Un mot de 3 lettres présente 3! possibilités de transposition, soit 6. Il est aisé de toutes les essayer. En revanche, une phrase dont tous les mots sont collés sans espace présente n! phrases possibles, avec n le nombre de lettres composant la phrase. Par exemple, une phrase de 35 lettres peut être disposée de 35! façons possibles, soit de 10'333'147'966'386'144'929'666'651'337'523'200'000'000 manières différentes.
Le carré de Polybe : Polybe, écrivain grec, est à l'origine du premier procédé de chiffrement par substitution. C'est un système de transmission basé sur un carré de 25 cases.
Chaque lettre peut être ainsi représentée par un groupe de deux chiffres : celui de sa ligne et celui de sa colonne. Ainsi e=15, v=51,...
Polybe proposait de transmettre ces nombres au moyen de torches. Une dans la main droite et cinq dans la main gauche pour e par exemple. Cela permettait donc de transmettre des messages sur de longue distance. Les cryptologues modernes ont vu dans le "carré de 25" plusieurs caractéristiques extrêmement intéressantes : - la conversion de lettres en chiffres, - la réduction de nombres, de symboles, - la représentation de chaque lettre par deux éléments séparés.
Le chiffre Atbash : Le chiffre Atbash consiste simplement à inverser l'ordre des lettres de l'alphabet. Il est à remarquer que le mot "Atbash" dérive du système qu'il désigne, puisqu'il est composé à partir des lettres aleph, tau, beth et shin, les deux premières et les deux dernières de l'alphabet hébreux.
NB : En appliquant deux fois de suite ce chiffrement à un texte, on retrouve le texte clair.
Le décalage de César :
Cette technique cryptographique repose sur un principe très simple : on décale d'un certain nombre de crans dans l'alphabet chaque lettre constituant le message à transmettre. Par exemple, décalons les lettres du message suivant de 3 crans vers la droite, comme le faisait Jules César :
Ave Caesar morituri te salutant devient DYHFD HVDUP RULWX ULWHV DOXWD QW Chaque lettre est remplacée par une même lettre : c'est un chiffrement à substitution monoalphabétique.
Principe clairement énoncé : A chaque caractère du texte clair correspond un caractère du texte crypté. M = ( x1 x2 … xi … xn ) avec xi, le ième caractère du message clair après codage (il s’agit donc d’un nombre). On associé à chaque caractère un nombre, représentant sa place dans l'alphabet à 26 lettres. Le message codé est C = « c(x1) c(x2) … c(xi) … c(xn) » avec c la fonction de cryptage. Le nombre de lettres, ici noté n, est conservé. Pour la méthode de César : c(xi) = (xi + k) [26] Pour décoder : xi = (c(xi) - k) [26] avec k, le nombre de crans de décalage. exemple : A => x = 1 c(x) = (x+3) [26] = (1+3) [26] = 4 [26] A devient D. x = c(x) - 3 [26] = (4-3) [26]= 1 [26] D redevient A.
autre exemple : Z => x = 26 c(x) = (x+3) [26] = (26+3) [26] = 3 [26] Z devient C. x = c(x) - 3 [26] = (3-3) [26] = 0 [26] = 26 [26] C devient Z.
Une curiosité amusante à essayer : chiffrez le mot "oui" avec un décalage de 10 crans vers la droite. Voilà un drôle de dictionnaire français-anglais... Fiabilité :
Le message codé est cependant déchiffrable par une analyse statistique de la fréquence d'apparition de chaque lettre et par une comparaison avec une analyse faite sur un texte connu de la même langue. En effet, cette méthode conserve la fréquence d’apparition des lettres. Par ailleurs, si un espion parvient à se procurer la position d’un caractère donné dans le texte clair, il est en mesure de décrypter le message immédiatement. Plus simplement, il n’y a que 26 valeurs distinctes possibles pour k ; compte tenu de la puissance des machines actuelles, il ne pose aucun problème d’essayer toutes les clés (et même à la main, l’opération n’est pas très longue). Cette méthode a bien fonctionné, car sa technique demeurait secrète à l'époque.
On trouve une description du chiffre de César dans les Vies des douze Césars de Suétone : (Suétone - Vies des douze Césars, Livre premier, César, LVI)
Léonard de Vinci :
Etant ambidextre, Léonard de Vinci avait l'habitude d'écrire à l'envers de la main gauche pour que personne ne puisse relire ses découvertes dans son dos.
Le chiffre de Trithème : Jean Trithème (Ioannis Trithemius en latin), abbé de son état, est considéré comme un des pères de la cryptographie. C'est lui qui le premier publia un ouvrage imprimé, en latin, traitant de cryptographie : «Polygraphiae libri sex, Ioannis Trithemii abbatis Peapolitani, quondam Spanheimensis, ad Maximilianum Ceasarem» (Polygraphie en six livres, par Jean Trithème, abbé à Würzburg, précédemment à Spanheim, dédiée à l'empereur Maximilien). L'impression fut achevée en juillet 1518 par Johannes Haselberg et l'ouvrage fut réimprimé en 1550, 1571, 1600 et 1613. La litanie ci-dessous est basée sur l'un des 14 alphabets du système de chiffre de Trithème. Ainsi, chaque lettre est remplacée par un mot ou petit groupe de mots; des mots inutiles sont rajoutés pour articuler le texte.
Décodez cette litanie:
Retenez-les bien !
Le code de Vigenere : D'une bonne utilisation de cette grille d'alphabets décalés, Vigenere a tiré le premier codage à substitution polyalphabétique de l'histoire : le chiffre de Vigenère est une amélioration décisive du chiffre de César. Sa force réside dans l'utilisation non pas d'un, mais de 26 alphabets décalés pour chiffrer un message. On peut résumer ces décalages avec un carré de Vigenère (voir ci-dessous). Ce chiffre utilise une clef qui définit le décalage pour chaque lettre du message (A: décalage de 0 cran, B: 1 cran, C: 2 crans, ..., Z: 25 crans). Si la clef est aussi longue que le texte clair, et moyennant quelques précautions d'utilisation, le système est appelé masque jetable.
Pour coder : Pour décoder :
Principe mathématique : En faisant varier la valeur de k, on casse la fréquence d’apparition des lettres et on améliore grandement la difficulté de décryptage.
Substitution simple Chiffre de Vigenere
c(xi) = (xi + ki) [N] avec ki, la clé k utilisée avec le caractère x à la position i C’est le regroupement de plusieurs substitutions simples qui sont appliquées successivement suivant la place du caractère dans le message. La valeur de ki est donc donnée par la position i du caractère à chiffrer ainsi que par la clé. Si la clé est "key", alors k1 = position de k dans l'alphabet = 11 donc k1=11 k2 = 5 k3 = 25
Fiabilité : Dans l'exemple ci-dessous, le mot "thé" est chiffré "DPP" 2 fois et "BSS" 1 fois. Charles Babbage comprit que des répétitions de cette sorte lui offraient la prise dont il avait besoin pour attaquer Vigenère. Il va d'abord chercher des séquences de lettres qui apparaissent plus d'une fois dans le texte : - soit la même séquence de lettres du texte clair a été cryptée avec la même partie de la clef - soit deux suites de lettres différentes dans le texte clair auraient (possibilité faible) par pure coïncidence engendré la même suite dans le texte chiffré. Le 1er cas étant le plus probable, il en déduit le nombre de facteurs de la clef puis par une méthode de fréquence de distribution des lettres cryptées, il en déduit les lettres du texte clair. Exemple :
Dans cet exemple, THE est chiffré en DPP la première et la deuxième fois, et en BSS la troisième. C'est pourtant la faiblesse du chiffre de Vigenère: ces répétitions apparaissent parce que dans l'original, les mêmes séquences de lettres sont chiffrées avec la même partie de la clef. Résumons : Le premier pas consiste à deviner la longueur de la clef. Cela est possible si la clef est courte et le texte long. Dans ce cas des séquences de lettres peuvent apparaître plusieurs fois. On cherche pour cela des séquences de plusieurs lettres consécutives (par exemple 3 ou plus) apparaissant plusieurs fois. D'après l'emplacement de ces groupes, on déduit la longueur de la clef. Ce renseignement est capital. Si, par exemple, la longueur de la clef est 3, cela signifie que les caractères de rang 1, 4, 7, 10, ..., 3k+1, sont simplement décalés à la manière du chiffre de César. On peut donc appliquer maintenant l'analyse de fréquences à ces caractères et trouver la première lettre de la clef. Pour la deuxième lettre de la clef, on analysera les fréquences des caractères de rang 3k+2 et pour le dernière lettre les fréquences des caractères de rang 3k.
L'alphabet bilitère : La cryptographie consiste à chiffrer les messages pour les rendre incompréhensibles, alors que la stéganographie cache les images dans un support (une image ou un texte qui passeront inaperçus). La stéganographie est donc l'art de dissimuler les messages. Francis Bacon (1561-1626) est l'inventeur d'un système stéganographique qu'il mentionna d'abord en termes vagues dans un ouvrage paru en 1605 et intitulé Of the proficience and advancement of Learning, divine and humane (De la valeur de l'avancement de la science divine et humaine). Il l'exposa plus clairement en 1623 dans De dignitate et augmentis scientiarum. Il commençait par remplacer les vingt-quatre lettres de l'alphabet de son temps (i se confondait avec j et u avec v) par des arrangements des deux lettres A et B en groupes de cinq:
NB : Cet alphabet, que son inventeur appelait alphabet bilitère, est très semblable dans son principe au codage binaire de l'information dans nos ordinateurs actuels. A et B pour 0 et 1. Cette conversion est la première étape du procédé. Il faut ensuite un "texte de couverture" qui peut être absolument quelconque. Ce texte est imprimé au moyen de deux types différents de caractères, que l'on pourra appeler le type A et le type B. Ainsi, du texte apparent, on pourra déduire une séquence composée exclusivement de A et de B. Décomposée en groupes de cinq lettres, celle-ci permettra, en utilisant l'alphabet décrit dans notre tableau, de rétablir le texte secret. Dans l'exemple ci-dessous, le type A est représenté par les caractères romains, le type B par les italiques:
Le texte secret, "fuyez", est entièrement indépendant du texte apparent. Bien entendu, la différence entre les deux types de caractères doit être très discrète, afin qu'elle échappe au lecteur non averti.
Le mécanisme de Jefferson :
Cette machine permet un décalage des lettres automatiques. Sur une ligne, nous réglons le message, puis nous lisons sur une autre ligne le message codé. Le destinataire doit posséder la même machine avec les mêmes rouleaux, connaitre le message codé et le nombre de lignes le séparant du bon message.
Enigma :
Durant la Seconde Guerre Mondiale, les communications devaient rester secrètes. Pour cela, les Allemands avaient inventé une machine automatisant le cryptage par des procédés mécaniques. Le cryptage repose ici sur cinq éléments : - un tableau de connexions, - trois rotors, - un réflecteur. Le tableau de
connexions attribue à chaque lettre de l'alphabet une autre lettre de
l'alphabet. Les rotors établissent des connexions entre différentes lettres de l'alphabet et effectue des rotations (d'où le problème du décryptage si on ne connaît pas leur position d'origine). En effet, dès qu'une lettre a été codée, le premier rotor tourne d'un cran; le second rotor tourne d'un cran chaque fois que le premier a fait un tour et le troisième rotor avance d'un cran quand le deuxième a fait un tour. Le réflecteur, quant à lui effectue des permutations entre les lettres et renvoie la lettre à coder une nouvelle fois à travers les 3 rotors. Le principeLe principe de base des machines Enigma conçues par Scherbius repose sur l'utilisation de rotors qui transforment l'alphabet clair (noté en minuscules) en alphabet chiffré (en majuscules). Pour mieux l'illustrer, nous nous limiterons à un alphabet de six lettres. Voici la représentation de l'un de ces fameux rotors, ainsi que le schéma équivalent qui permet de mieux suivre l'opération "avec les doigts".
Schéma 1 Si on frappe la lettre b sur le clavier, un courant électrique est envoyé dans le rotor, suit la câblage interne, puis ressort à droite pour allumer la lettre A sur le tableau lumineux. b est donc codé en A. Idem pour les cinq autres lettres: a devient B, b devient A, c devient D, d devient F, e devient E et f devient C. Autre principe de base: chaque fois qu'une lettre est tapée au clavier, le rotor tourne d'un cran. Ainsi, b devient A la première fois, mais b devient C la deuxième fois (voir schéma 2, à droite), puis b devient E, etc.
Schéma 2 Dans notre exemple le mot bac est codé ADD (et non ABD si le rotor était resté immobile). Pour augmenter le nombre de combinaisons possibles - et déjouer les tentatives des cryptanalystes -, Scherbius a associé plusieurs dispositifs, comme indiqué sur le schéma 3.
Schéma 3 Le tableau de connexions permet de brouiller les pistes en reliant deux lettres du clavier entre elles (ici a et b). Ainsi, quand on tape b, le courant prend en fait le circuit prévu pour a. Les trois brouilleurs associés multiplient ainsi le nombre de combinaisons. Le deuxième et le troisième avancent respectivement d'un cran quand le premier et le deuxième ont fait un tour complet. Quant au réflecteur, il renvoie le courant dans le dispositif jusqu'au panneau lumineux où la lettre cryptée s'affiche. Son rôle n'est pas d'augmenter le nombre de combinaisons possibles, mais de faciliter considérablement la tâche du destinataire. En effet, si b devient C dans notre exemple (en rouge), on a aussi c devient B. Et c'est valable pour toutes les paires de lettres claire/cryptée. Conséquence: si le mot efface est codé ACBFEB par l'émetteur, il suffira à l'opérateur qui reçoit le message crypté de taper acbfeb sur son clavier pour voir les lettres E, F, F, A, C, E s'allumer. Seule condition: les deux opérateurs distants doivent avoir réglé leur machine Enigma de la même façon. Au final, si l'on revient aux machines Enigma équipées pour 26 lettres, on a énormément de possibilités, rendant le décryptage sans connaissance de la "clé" initiale quasiment impossible.
Nous avons donc rapidement passé en revue les principales techniques historiques de codage astucieux, physique, ou mécanique.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
