Accueilretour

Systèmes historiques

1. transpositions et substitutions

Généralités

Stéganographie

Cryptanalyse

Littérature

Transpositions

chiffrage

exemple

analyse

conclusion

Subs. monoα

Subs. polyα 1 - 2

One-time pad

DES 1 - 2

Clef publique

Knapsack

Diffie-Hellman

RSA 1 - 2

Grands noms

Références


 Il est question ici de systèmes agissant sur un texte littéral [1].

Le texte clair peut essentiellement être modifié de deux manières [2] :
  • transposition : on réordonne les lettres du texte clair sans les modifier. le texte chiffré est ainsi une anagramme du clair. 
  • substitution : on modifie les lettres du texte clair sans en changer l'ordre. Dans cette substitution, chaque lettre du clair peut être remplacée
    • soit toujours par la même lettre (substitution monoalphabétique) ;
    • soit par une lettre variable en fonction de la position de la lettre d'origine du clair (substitution polyalphabétique).
Nous présentons ici le procédé de transposition (et son analyse). Le message dans "Voyage au centre de la Terre" en constitue un exemple.

retour

Chiffrage par transposition

Afin que le chiffrage et le déchiffrage soient efficaces, il faut adopter une règle de permutation commode à appliquer, à mémoriser et à transmettre.

À cet effet :
  1. on choisit un mot-clef de n lettres (p. ex. CODE -- n = 4), en prenant n suffisamment petit pour que la longueur ℓ du message M le contienne pluieurs fois ;
  2. on écrit le clair sur n colonnes, en passant donc à la ligne toutes les n lettres. On obtient un tableau à n colonnes (la dernière ligne peut être incomplète, lorsque ℓ n'est pas multiple de n).
  3. on transpose ces colonnes en les rangeant dans l'ordre des lettres du mot clef. Dans notre exemple :

    C
    		 O
    		 D
    		 E
    (1)
    		 (4)
    		 (2)
    		 (3)

    les colonnes sont réordonnées selon : 1ère, 3ème, 4ème, 2ème. Le mot-clef ne sert qu'à mémoriser cet ordre !
  4. on réécrit le message chiffré sur une seule ligne en effectuant l'opération inverse de celle du 2.
Le déchiffreur, qui connaît le mot-clef, n'a aucun mal à découper le chiffré en n colonnes et remettre celles-ci dans l'ordre initial.

un système ancien

C'est là un des plus anciens systèmes de cryptage connus. Son utilisation est attestée dans l'antiquité grecque plus de 4 siècles avant notre ère. La transposition était alors réalisée "mécaniquement" au moyen de la scytale, un bâton épais sur lequel était enroulé en spirale un ruban.

Le texte clair était tracé selon l'axe du bâton, une lettre par spire. Le ruban était ensuite déroulé et transmis au destinataire. Le "déchiffrage" se bornait à enrouler le ruban sur un bâton de même diamètre...

Exemple

Chiffrons le clair "Élémentaire, mon cher Watson !" :

elementairemoncherwatson

... à l'aide de la clef de codage DOYLE. Le clair est donc découpé en 5 colonnes :

D
 O
 Y
 L
 E
(1)
 (4)
 (5)
 (3)
 (2)
e
 l
 e
 m
 e
n
 t
 a
 i
 r
e
 m
 o
 n
 c
h
 e
 r
 w
 a
t
 s
 o
 n

Ces colonnes sont ensuite redisposées dans l'ordre des lettres de la clef, soit 1 - 4 - 5 - 3 - 2 :

D
 E
 L
 O
 Y
(1)
 (2)
 (3)
 (4)
 (5)
e
 e
 m
 l
 e
n
 r
 i
 t
 a
e
 c
 n
 m
 o
h
 a
 w
 e
 r
t
n
 s
 o

et on relève enfin le chiffré correspondant en lisant en lignes :

EEMLENRITAECNMOHAWERTNSO

retour

Analyse

L'abondance des choix possibles pour les clefs ne doit pas faire illusion. Ce chiffrage est très faible : toutes les lettres du clair sont présentes dans le chiffré. Comme l'a écrit Bazeries :

    "En un mot, les méthodes par transposition sont une salade de lettres du texte clair."

Livrons-nous à un petit exemple de cryptanalyse sur le chiffré suivant :

SECTLEDAUADBIWENWODS

Il faut deviner, non pas la clef, mais sa longueur n. En séparant le chiffré en groupes de n lettres, convenablement réordonnés, des mots doivent apparaître. On essaie...
  • n = 2 (pour mémoire) : SE CT LE DA UA... Une seule permutation est possible, qui conduit à : ES TC EL AD AU BA... (qui n'a pas de sens).

  • n = 3 : SEC TLE DAU ADB... SEC peut être permuté (pour donner le début d'un mot [3]) en
    • CES (3 - 2 - 1) qui donne CES ETL UDA... ça ne va pas ;
    • ESC ("escamoter...") (2 - 1 - 3) qui conduit à ESC LTE... qui échoue aussi ;
    • SCE ("scène...") (1 - 3 - 2) qui correspond à SCE TEL... encore un échec. n = 3 ne convient pas.

  • n = 4 : SECT LEDA UADB IWEN... et parmi les 4!−1 = 23 permutations non triviales possibles, nous pouvons considérer
    • ESTC ("est-ce...") (2 - 1 - 4 - 3) qui donne ESTC ELAD AUIB -- encore un échec ;
    • CEST (3 - 2 - 1 - 4), va s'avérer l'essai gagnant : CEST DELA DAUB EWIN DOWS, autrement dit :

cestdeladaubewindows

(C'est de la daube, Windows.)

Avouons que ce message n'était pas un tel secret qu'il nécessite un chiffrage puissant ! Le mot-clef était UNIX (mais nous n'en avons même pas eu besoin).

retour

Conclusion

Inutile d'insister sur la faiblesse de ce chiffre. Son principal talon d'Achille est qu'il contient tous les caractères du message clair. Des essais systématiques -- tenant compte du lexique -- ne peuvent manquer de conduire au décryptage.

Même si l'on ne connaît pas la langue du clair (cas peu probable en pratique), les essais ne sont pas multipliés. Car il n'est pas facile de permuter des lettres pour former des mots : vérifiez pour vous-même que dans l'exemple ci-dessus, les essais n'auraient pas été beaucoup plus nombreux en supposant le clair rédigé en anglais.

Pourtant, jusqu'en 1880, c'est selon un système de ce type qu'étaient cryptés les messages militaires français !

Notes

[1]  et non numérique, par opposition aux méthodes arithmétiques modernes

[2]  non exclusives

[3]  ECS et CSE ne vont pas.