Le code de VIGENERE (1586) ____________________________________________________
TABLE DES MATIERES DE LA
PAGE :
2. Quelques remarques importantes sur
cet algorithme
3. Cassage de l’algorithme de
VIGENERE : technique de BABBAGE- KASISKI (1854)
5. Cassage de l’algorithme de MAUBORGNE
Définissons
d’abord ce que l’on appelle le carré de Vigenère :
|
Texte
en clair 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
A B
C D E F G
H I J K L
M N O P Q
R S T U V
W X Y Z B C
D E F G H
I J K L M
N O P Q R
S T U V W
X Y Z A C D
E F G H I
J K L M N
O P Q R S
T U V W X
Y Z A B D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z A B C E F
G H I J K
L M N O P
Q R S T U
V W X Y Z
A B C D F G
H I J K L
M N O P Q
R S T U V
W X Y Z A
B C D E G H
I J K L M
N O P Q R
S T U V W
X Y Z A B
C D E F H I
J K L M N
O P Q R S
T U V W X
Y Z A B C
D E F G I J
K L M N O
P Q R S T
U V W X Y
Z A B C D
E F G H J K
L M N O P
Q R S T U
V W X Y Z
A B C D E
F G H I K L
M N O P Q
R S T U V
W X Y Z A
B C D E F
G H I J L M
N O P Q R
S T U V W
X Y Z A B
C D E F G
H I J K M N
O P Q R S
T U V W X
Y Z A B C
D E F G H
I J K L N O
P Q R S T
U V W X Y
Z A B C D
E F G H I
J K L M O P
Q R S T U
V W X Y Z
A B C D E
F G H I J
K L M N P Q
R S T U V
W X Y Z A
B C D E F
G H I J K
L M N O Q R
S T U V W
X Y Z A B
C D E F G
H I J K L
M N O P R S
T U V W X
Y Z A B C
D E F G H
I J K L M
N O P Q S T
U V W X Y Z
A B
C D E F G
H I J K L
M N O P Q
R T U
V W X Y Z
A B C D E
F G H I J
K L M N O
P Q R S U V
W X Y Z A
B C D E F
G H I J K
L M N O P
Q R S T V W
X Y Z A B
C D E F G
H I J K L
M N O P Q
R S T U W X
Y Z A B C
D E F G H
I J K L M
N O P Q R
S T U V X Y
Z A B C D
E F G H I
J K L M N
O P Q R S
T U V W Y Z
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Z A
B C D E F
G H I J K
L M N O P
Q R S T U
V W X Y A B
C D E F G
H I J K L
M N O P Q
R S T U V
W X Y Z |
Je pense que c’est assez clair,
chaque ligne est fabriquée en décalant la ligne précédente de une lettre.
1.
Il
faut un mot clé ou une phrase clé,
prenons par exemple : "ceci est la phrase clé"
2.
Il
faut un texte à coder, prenons par exemple : "je dois coder le texte
que je suis en train d’écrire"
3.
Ensuite…codons comme suit :
Pour
chaque lettre du texte à coder, la lettre correspondante du texte chiffré se
trouve à l’intersection de la colonne correspondant à la lettre du texte en
clair et de la ligne correspondant à la lettre de la phrase clé correspondante.
Ainsi,
par exemple pour coder "j", on regarde la colonne "j" et la
ligne "c", d’où le cryptage de "j" en "l".
Ou
encore, pour coder "e", on regarde la colonne "e" et la
ligne "e" (ceci n’est qu’un hasard), d’où le cryptage de
"e" en "".
Texte
en clair : J E D O I S C O D
E R L E T E X T E Q U E J E S U I S E N T R A I N D E C R I R E…
Phrase clef : C E C I E S T L A P H R A S E C L E C
E C I E S T L A P H R A S E C L E C E C I E S T L A …
Texte
chiffré : L I F W J…
Avantages
:
-
Résiste à
l’analyse des fréquences (forme de cryptage assez développée) : en effet, ce code utilise une ligne
différente pour chiffrer chaque lettre. De cette façon, un "e" va
être chiffré suivant les cas par un "i" ou un "t" ou même
un "f". Et réciproquement, si un cracker regarde la lettre la plus
utilisée dans le texte chiffré, celle-ci peut être mise pour plusieurs autres
lettres "originales". De la même manière un mot entier peut être codé
suivant différentes manières suivant sa position par rapport à la partie de la
phrase clé qui lui est en regard.
-
Il possède
un nombre immense de clefs : l’utilisateur et le destinataire peuvent
forger la suite de mots qui leur plait, que ce soit au chapitre 3, page 45 du
livre sur la reproduction des volatiles an Soudan, ou tout simplement une suite
sans sens particulier, toute suite de lettres est susceptible d’être la phrase
clé. Pour une phrase de longueur de 18
lettres comme ici, le nombre de possibilités sera de 2618, soit
environ 325 possibilités, ce qui est pas mal ! Mais ce calcul
est le plus général possible, c’est à dire qu’il suppose que les mots
constituants la clé sont aléatoires (comme on le verra dans le 4.), alors que
dans ce cas-ci, les mots sont des mots connus, ce qui diminue énormément le
nombre de possibilités.
-
Plus on
augmente la longueur de la phrase clé, plus le niveau de sécurité va augmenter
de façon exponentielle.
Inconvénient
:
-
Le problème
de transmission de la phrase clé : l’idéal serait de trouver un moyen de
transmettre la clé sans pour autant que les deux personnes se rencontrent. Ceci
ne sera réalisé que grâce aux travaux conjugués de Martin HELLMAN, Ralph MERKLE
et Whitfield DIFFIE.
-
La
répétition de la phrase clé, qui, comme on va le voir ci-dessous, va être la
seule faille réelle à ce cryptage.
Vu
que la longueur de la phrase clé ici est strictement inférieure à la longueur
du texte à chiffrer, les différentes traductions d’un même mot sont relativement
limitées à cause de la répétition du mot clé. Evidemment, plus celui-ci est
long, plus il sera difficile de le trouver. La technique de BABBAGE se
base donc sur la recherche de séquences de lettres qui vont apparaître plus
d’une fois dans le texte chiffré. Par exemple, pour un texte de 1000 lettres
crypté suivant le code de Vigenère avec une clé de 5 lettres, son déchiffrement
se "limiterait" à l’analyse de 5 ensembles de 200 lettres, puisque
toutes les 5 lettres successives, on recode avec la même clé (ou, ce qui
revient au même, avec la "même ligne" dans le carré de VIGENERE). Ces
répétitions peuvent venir soit d’une même séquence de lettres cryptée par la
même partie de la phrase clé comme nous venons de le dire, soit de deux suites
différentes chiffrées par deux parties indépendantes, mais cette dernière
possibilité apparaît comme extrêmement improbable. A partir de la, on peut
espérer que le même mot n’apparaisse pas deux fois dans la phrase clé, et par
conséquent on peut entrevoir les endroits où se répètent la phrase clé (dans un
voisinage autour ce chaque mot clé). Il ne "suffit plus qu’à" essayer
toutes les combinaisons possibles pour les clés (on essaye une clé, on essaye
de décrypter avec, et si on tombe sur des mots incompréhensibles, on va à la
clé suivante), en attribuant une longueur croissante à la phrase clé. Cette
technique s’avère d’autant plus payante et rapide que les mots utilisés dans la
phrase clé sont courts, ce qui augmente la répétition de la phrase clé, et diminuer donc le nombre de phrases qui
peuvent être formés par rapport au début de phrase clé. Et aussi d’autant plus rapide que les mots
utilisés pour la phrase clé sont des
mots connus, que l’on peut trouver dans le dictionnaire.
Comme
nous l’avons vu, l’attaque de Babbage n’est vraiment possible que s’il existe
un certain nombre de répétitions de la phrase clé. Alors que la Grande Guerre
touchait à son terme, le major Joseph MAUBORGNE qui dirigeait la
recherche cryptographique de l’armée US eut l’idée de constituer des phrases
clés formées par des lettres de manière complètement aléatoires. Dans ce cas,
vu que en plus chaque code n’était en plus valable que pour un seul chiffrement
(chiffre à usage unique), cela faisait effectivement un
chiffrement…indéchiffrable. On peut en effet prouver mathématiquement qu’il est
impossible de déchiffrer un message traité avec un chiffre à usage unique. Car
en plus du nombre extrêmement élevé de possibilités, on se heurte aussi au fait
que pour un même message crypté, on puisse obtenir plus de deux messages
apparemment décryptés et cohérents…comment choisir le bon dans ce cas ?
Mais
cet algorithme infaillible se heurtait aux difficultés suivantes :
-
Le problème
de la transmission de la clé (comme le code de Vigenère d’ailleurs),
-
La quantité
immense de clés à transmettre, en des temps restreints.
-
La manière
de trouver une clé…vraiment aléatoire. Rappelons que nous nous situions à une
époque qui commençait vaguement à voir l’apparition de semblants d’ordinateurs,
on était bien loin des PC actuels qui donnent des suites aléatoires avec une
simple fonction random !
Le cassage de ce code est basé sur le fait
que dans un texte cohérent, il existera toujours des mots tels que
"les", "le", "des", …Par conséquent, une attaque serait de mettre ces
mots à tous les endroits possibles dans le texte chiffré, et de trouver par là
les phrases clé correspondantes.
Il semble alors évident que :
-
Plus on a de
"mots clés", plus on augmente nos chances qu’au moins un de ceux-ci
soit effectivement utilisé…mais on augmente aussi la puissance de calcul et/ou
le temps de calcul nécessaire(s).
-
Cette
attaque ne peut être valable que d’après la supposition faite que certains mots
se trouvent dans le texte…avec de la malchance, on tombe sur un texte du genre
"attaquez à 12H" où aucun mot "devinable" à priori
n’apparaît.
-
Plus on
dispose de messages codés de la même manière ou plus le message intercepté est
long, plus on a de chances de trouver les mots cherchés dedans et donc plus on
a de chances de casser le code.
-
Si la clé
n’est pas faite de mots que l’on trouve dans le dictionnaire (i.e. des suites
de lettres complètement aléatoires comme dans le cas du code de Mauborgne), ce
sera d’autant plus difficile à casser car on ne pourra pas alors
"vérifier" la validité de la clef trouvée car elle ne sera plus
formée de mots connus et on devra alors tout décrypter pour voir si le message
obtenu peut être correct ou pas. Ceci augmente évidemment considérablement le
nombre de possibilités !