les dossiers de l’ afis44
DOSSIER : MATHEMATIQUES
document : une invitation au voyage au pays du chiffre
cryptographie et cryptanalyse
Une Introduction élémentaire et,
pourquoi pas, distrayante, au monde du Chiffre …
"On
a inventé l'art d'écrire avec des chiffres ou avec des caractères inconnus pour
dérober la connaissance de ce qu'on écrit à ceux qui interceptent des lettres,
mais l'industrie des hommes, qui s'est raffinée par la nécessité & l'intérest, a trouvé des règles pour déchiffrer ces lettres
& pour pénétrer par ce moyen dans les secrets d'autruy." François de Callières (
1645 - 1717 ) De la manière de négocier avec les souverains
Cette citation, que
l'on trouve en exergue du livre "La guerre des codes secrets" de
David KAHN ( Interéditions,
1980) mérite qu'on s'y attarde car elle illustre bien ce qui a été toute
l'histoire de la cryptographie ( et de la cryptanalyse ) jusqu'aux
développements de la deuxième moitié du 20ème siècle en matière de
transport et traitement de l'information ( en langage clair : les
télécommunications et l'informatique ).
Tout d'abord elle
illustre clairement que le problème posé à la cryptographie (
= écriture cachée ) est celui de la confidentialité. DUPONT veut
transmettre un message à DURAND, message qu'ils (ou elles) veulent cacher à un
troisième personnage, DUBOIS, en sachant ( ou
supposant ) que DUBOIS s'intéresse au contenu de ce message et essaiera donc de
l'intercepter et d'appréhender son contenu. DUBOIS peut aussi envisager de parasiter
le circuit en arrêtant le message de DUPONT et en y substituant un autre
message qu'il (ou elle) enverrait à DURAND en se faisant passer pour DUPONT.
DURAND doit donc pouvoir s'assurer que c'est bien DUPONT qui lui a adressé le
message et que le message reçu est bien tout le message mais rien que le
message envoyé par DUPONT.
Les raffinements que
l'on peut trouver, pour reprendre l'expression de François de Callières,
peuvent être extrêmes et, comme il le note très bien, c'est bien "la
nécessité et l'intérêt" qui sont à la base de tous les progrès qui seront
réalisés, progrès accompagnant, cosignant même, les progrès de la civilisation.
Il est ainsi facile
d'appréhender les différentes dimensions du problème global. Il y a bien une
dimension "transport" de l'information ( fonction justificatrice
de l'arme des transmissions, en tant qu'arme distincte, au sein des forces
armées des différentes nations ) et une dimension "traitement" de
l'information ( fonction justificatrice de ce qu'on a souvent appelé
"Le Chiffre" ) afin d'obtenir une transmission sûre, à savoir une
information arrivant intègre ( authentifiée - être sûr de l'émetteur -,
à l'intégrité vérifiée - être sûr qu'en chemin l'information n'a pas été
altérée, et surtout pas volontairement - ) sans qu'un intermédiaire
indésirable ait pu l'intercepter, la comprendre voire la manipuler.
Autant il est des
fragments du problème qui sont purement de l'ordre du "transport" ou
purement "traitement", autant on comprendra que le mode de traitement
dépend du mode de transport. On pourrait ainsi dire que, comme toujours, en
dernier ressort, ce sont bien les conditions matérielles qui sont
déterminantes.
La confidentialité du
message proprement dite sera obtenue[1]
par l'opération de chiffrement à l'aide d'une "clef", ( ce chiffrement peut, suivant les cas, être réalisé par le
rédacteur du message, par le transmetteur ou par une tierce personne ),
chiffrement rendant le message a priori incompréhensible par quiconque aurait
accès à ce message chiffré. Pour pouvoir restaurer le texte clair il faut
utiliser la "clef" de déchiffrement.
Message |
|
chiffrement |
|
|
|
|
|
déchiffrement |
|
Message |
Clair |
|
du message |
|
|
|
|
|
du message |
|
Clair |
|
|
Clef chiffrante |
|
|
Transmission par canal peu sûr |
|
|
Clef déchiffrante |
|
|
Le tiers intéressé, le plus
souvent avec des intentions inamicales, s'investira dans l'interception de la
communication (voire dans le démantèlement - ou le retournement - du
réseau de transmission quand il est immergé chez les "méchants") puis
le décryptage ( c'est là l'objet des cryptanalystes ) du message.
On pense immédiatement
à un usage militaire mais on ne saurait oublier les usages commerciaux,
politiques, voire galants … même si ces derniers ne mobilisent pas les
dernières ressources mathématiques.
QUELQUES PRINCIPES DE
CRYPTOGRAPHIE
LE PRINCIPE DE TRANSPOSITION
Le premier principe est
celui de la transposition. Les lettres se retrouvent mélangées ( elles conservent leur identité, un E reste un E, mais
changent de position )
Une illustration simple
( de ce qu'on appelle d'ailleurs la transposition
simple à tableau, procédé le plus utilisé ) consisterait à écrire un texte
ligne par ligne dans un tableau à 10 colonnes puis à transmettre le message par
colonne.
Prenons
comme exemple le message :
"CE MESSAGE EST UNE ILLUSTRATION SIMPLE DU PROCEDE DE
TRANSPOSITION"
Ecrivons
ce message dans le tableau à 10 colonnes, en supprimant les espaces et la
ponctuation ( ici inexistante ) :
C |
E |
M |
E |
S |
S |
A |
G |
E |
E |
S |
T |
U |
N |
E |
I |
L |
L |
U |
S |
T |
R |
A |
T |
I |
O |
N |
S |
I |
M |
P |
L |
E |
D |
U |
P |
R |
O |
C |
E |
D |
E |
D |
E |
T |
R |
A |
N |
S |
P |
O |
S |
I |
T |
I |
O |
N |
|
|
|
L'émetteur émet le message
par colonne; cela donne la suite de caractère suivante :
CSTPDOETRLESMUAEDIENTDETSEIUTISIOPROALNRANGLSONEUICSESMEP
Il ne reste plus au
destinataire qu'à déchiffrer.
Il sait que le tableau
à 10 colonnes. Il va donc reconstituer le tableau mais pour cela il faut
d'abord qu'il trouve le nombre de lignes. Cela ne présente guère de difficulté
à celui qui sait qu'il s'agit d'un tableau de 10 colonnes; il lui suffit de
diviser le nombre de caractères par 10 : comme il a reçu 57 caractères, il en
déduit qu'il y a 5 lignes de 10 caractères et 1 ligne incomplète de 7
caractères. Il va donc considérer 7 groupes de 6 caractères puis 3 groupes de 5
qu'il va ranger dans son tableau.
La connaissance de la langue
lui permettra simplement ensuite de replacer les espaces et la ponctuation.
D'un point de vue
pratique, il conviendrait d'ajouter le "conditionnement" du message
permettant par exemple d'identifier l'émetteur ou d'identifier la ou les clefs
de transposition car, fréquemment, plusieurs grilles sont en service en même
temps.
On peut augmenter la
sécurité des messages en "améliorant" ( par
exemple en insérant des "nulles" dans le message - lettres inutiles -
suivant une convention connue du déchiffreur … ) la transposition simple ou en
réalisant des transpositions successives ( avec le même tableau ou un autre
tableau ).
LE PRINCIPE DE SUBSTITUTION
Le
second principe élémentaire est celui de substitution. Les lettres sont
remplacées par d'autres lettres, des symboles, ou des chiffres. Ainsi, elles
conservent leur position mais perdent leur identité ( un
E n'est, peut-être, plus un E )
Un
procédé de substitution alphabétique très ancien est le procédé hébreu "Atbash" (
aleph, tau, beth, shin )
consiste à remplacer la première lettre de l'alphabet ( en hébreu, aleph ) par
la dernière ( en hébreu, tau ), la seconde lettre de l'alphabet ( en hébreu, beth ) par l'avant-dernière ( en hébreu, shin ), et ainsi de suite. Le principe s'applique bien sûr
à n'importe quel alphabet et, pour l'alphabet français cela donne :
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 |
Z |
Y |
X |
W |
V |
U |
T |
S |
R |
Q |
P |
O |
N |
M |
L |
K |
J |
I |
H |
G |
F |
E |
D |
C |
B |
A |
Le chiffrement et le
déchiffrement sont un enfantillage, certes prenant du temps.
Prenons le message :
VOICI UN
EXEMPLE DE SUBSTITUTION
En
prenant cet alphabet de substitution "Atbash"
après avoir enlevé, là encore, les intervalles et ponctuation ( ici inexistante ), nous trouvons :
ELRXRFMVCVNKOVWVHFYHGRGFGRLM
On notera que la particularité
amusante de cette substitution est que la grille de déchiffrement est la même
que la grille de chiffrement. Tout comme pour l'exemple pris en transposition,
la connaissance de la langue permettra au destinataire de replacer les espaces
et la ponctuation.
Pour passer à des
substitutions numériques il faut se poser quelques questions supplémentaires
relatives aux modes de transmission car il faut toujours penser au mode de
déchiffrement.
Imaginons que de façon
élémentaire nous ayons envisagé de remplacer chaque lettre de l'alphabet par sa
position dans l'alphabet : le 1 pour la lettre A, le 2 pour la lettre B, …, le
25 pour la lettre Y et le 26 pour la lettre Z. Cela donnerait la grille :
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 |
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 |
Le chiffrement du
message
VOICI UN
EXEMPLE DE SUBSTITUTION
ne présente pas plus de difficulté que dans la
substitution alphabétique :
22 15 9 3 9 21
14 5 24 5 13 16 12 5 4 5 19 21 2 19 20 9 20 21 20 9 15 14
Imaginons simplement
que la transmission conduise à supprimer les intervalles entre les chiffres; le
destinataire reçoit alors :
221593921145245131612545192121920920212091514
Ainsi, même en
connaissant la grille de chiffrement, le destinataire ne saura pas d'une façon
ne présentant aucune ambiguïté si le message commence par 2 = B ou par 22 = V.
De déchiffreur il devient décrypteur ( ou cryptanalyste ).
Ceci illustre qu'un
système de chiffrement se conçoit nécessairement aussi bien en fonction des
contraintes du chiffrement que de celles du déchiffrement, sans oublier bien entendu,
car c'est la base matérielle de la construction, le mode technique de
transmission de l'information cryptée.
Dans le cas d'une
substitution littérale on veillera ainsi à ce que chaque élément transmis ait
la même longueur, ce pour permettre le déchiffrement.
Ainsi, comme nous le
verrons, le chiffre des nihilistes russes est basé sur une substitution
numérique avec des nombres à deux chiffres.
De même, on peut
considérer, par exemple, un codage en octets du système binaire ( système
binaire : n'utilisant que deux chiffres, et, en l'occurrence, n'utilisant
que les chiffres 0 et 1; octet : ensemble ordonné de 8 caractères; octet
du système binaire : ensemble ordonné de 8 chiffres 0 ou 1, par exemple :
10100101; il y a deux possibilités différentes pour un singleton binaire - 0 ou
1 -, quatre possibilités pour un couple - 00, 01 ,10 ou 11 -, huit pour un
triplet - 000, 001, 010, 011, 100, 101, 110, 111 -, … 256 possibilités pour un
octet - je vous laisse le soin de vérifier, on dit aussi 28 que l'on
énonce "2 puissance 8" ) . La codification en binaire est la base
du chiffre de Gilbert VERNAM utilisé notamment pour la liaison du
"téléphone rouge".
Avant d'entrer
davantage dans l'univers des clefs numériques, nous pouvons, par le souci d'une
exactitude minimale, mais aussi pour le plaisir évoquer plusieurs autres
éléments.
Il convient de noter ( ce qui est toujours d'usage, en particulier pour les
transmissions en radio phonique ) qu'il n'y a pas que les substitutions
littérales ( dans lesquelles on substitue lettre à lettre ) mais il y a les
substitutions codiques dans lesquelles on remplace des mots par d'autres mots (
le plus élémentaire consiste à prendre des pseudonymes pour les noms propres,
de personnes ou de lieux ) ou des groupes de caractères ( lettres ou (et)
chiffres ).
On arrive ainsi à de
véritables dictionnaires.
Ces codes ( puisque là on parle de code ) ont beaucoup été utilisés
dans les relations commerciales, depuis 1400 environ, mais, avec le
développement de la radiotélégraphie, n'ont pas été utilisés que pour assurer
un minimum de secret mais tout simplement pour gagner du temps de transmission
( et donc de l'argent ); ainsi certains codes ( dictionnaires ) étaient en
vente libre.
Exemple de code :
Partie chiffrante |
|
Partie déchiffrante |
||
les |
5110 |
|
5108 |
réponse
à votre lettre |
les
a |
3927 |
|
5109 |
insurrection |
les
ont |
4139 |
|
5110 |
les |
léser |
2154 |
|
5111 |
lesquels |
lesquels |
5111 |
|
5112 |
camisole |
lest |
3277 |
|
5113 |
dollar
américain |
lester |
7354 |
|
5114 |
il
est recommandé que |
La façon de l'utiliser
se passe de commentaire.
Un autre procédé de
substitution est associé au nom de Francis BACON. Par delà l'intérêt littéraire
et historique de ce procédé ( par exemple pour essayer
de décrypter le message peut-être caché dans la curieuse épitaphe de la tombe
de Skakespeare
: Good Frend for Iesus
SAKE forbeare To diGG TE
Dust Enclo-Ased HE.RE. Blese be
TE Man TY spares Tes Stones Ans curst be He
TY moves my Bones. ), c'est par la façon dont il combine un procédé cryptographique à un procédé stéganographique.
La base du chiffrement
est un alphabet dit bilitère ( avec deux lettres, en
l'occurence nous prenons A et B ). Chaque caractère à
chiffrer est donc représenté par un ensemble de 5 caractères A ou B. On peut,
par exemple établir cette grille élémentaire :
A |
AAAAA |
|
G |
AABBA |
|
N |
ABBAA |
|
T |
BAABA |
B |
AAAAB |
|
H |
AABBB |
|
O |
ABBAB |
|
U - V |
BAABB |
C |
AAABA |
|
I - J |
ABAAA |
|
P |
ABBBA |
|
W |
BABAA |
D |
AAABB |
|
K |
ABAAB |
|
Q |
ABBBB |
|
X |
BABAB |
E |
AABAA |
|
L |
ABABA |
|
R |
BAAAA |
|
Y |
BABBA |
F |
AABAB |
|
M |
ABABB |
|
S |
BAAAB |
|
Z |
BABBB |
La représentation du
mot Exemple serait ainsi :
AABAA BABAB AABAA ABABB
ABBBA ABABA AABAA
On peut se poser la
question de l'intérêt d'un procédé en l'apparence si long; cet intérêt réside
dans le procédé sténographique que représente la convention de représentation
de ces lettres.
Supposons que l'on dise
: A représente une lettre en minuscule, B représente une lettre en majuscule. aiNsi Le TeXte
CrypTé ESt CAChé DaNs la Typographie d'un
texte sans rapport quelconque avec le message qu'il véhicule.
Il peut certes être dit
que ce n'est pas discret mais il
suffit de convenir de choses beaucoup plus discrètes telles que par exemple écriture droite ou italique, écriture en caractères
normaux ou gras, ou, encore
plus difficile, en mélangeant deux polices de caractère qui seraient
proches mais détectables par l'œil averti. C'est ainsi que chacun aura reconnu
trois fois le mot exemple écrit de trois façons différentes (
plus une fois en clair ) dans ce paragraphe.
Ce procédé stéganographique mobilisant une substitution a deux
caractères peut être facilement interprété comme un procédé de substitution
numérique utilisant le système binaire ( en posant A =
0 et B = 1 par exemple ) et nous replongeons dans l'univers numérique.
Disons néanmoins, pour
conclure cette partie posant les principes qu'au stade ou nous en sommes nous
avons déjà beaucoup de moyens de compliquer le chiffrement d'un message.
Nous pouvons ainsi
concevoir des systèmes de substitutions composés ( à double clef par opposition
à la substitution simple ) en considérant, par exemple, pour un procédé
littéral, qu'une lettre sur deux est substituée au moyen d'une clef et une
lettre sur deux au moyen d'une autre.
Nous pouvons concevoir
également que l'on combine substitution et transposition.
Cette recherche de
complexité vise à se prémunir d'être lu par un tiers mais elle a aussi son
inconvénient ( en supposant des procédés manuels ou
peu mécanisés ) c'est d'être souvent d'autant plus longue et pénible à mettre
en œuvre que l'on essaye de combiner entre eux des procédés aussi nombreux que
"bestiaux".
C'est donc ici qu'il
convient de gravir un degré de plus dans la conceptualisation pour pouvoir
simplifier en allant à l'essentiel. Les mathématiciens commenceront à trouver
cela "beau".
Pour concevoir une
cryptographie efficace ( mise en œuvre aisée alliée
avec un haut degré de sûreté ) il faut d'abord comprendre comment on
"casse" un chiffre : c'est l'objet de la cryptanalyse.
La base technique de la cryptanalyse c'est l'analyse de fréquence.
Une langue donnée se
signe par la fréquence d'apparition de
ses lettres et caractères.
Ainsi, au stade où nous
en étions à ce début de paragraphe, et avant toute modification ultérieure, ce
texte comptait 12022 caractères autres que des espaces et des changements de
ligne ( mais y compris la ponctuation ).
Sur ces 12022
caractères 1631 étaient des e non accentués, 243
des é, et 46 des è. C'est la lettre la plus
fréquente du français ( ici de l'ordre de 16 % ). Il faut
diviser par de l'ordre de deux pour trouver des lettres de fréquence plus
faible : ici le a ( 859
), le i ( 787 ),
le n ( 835 ), le r ( 773 ), le s ( 907 ), le t ( 851 ). Dans les basses fréquences nous allons trouver
des lettres rares ( qui sont pourtant ici avec des
fréquences augmentées ne serait ce que parce qu'elles figurent automatiquement
dans chaque grille de chiffrement ) : le k n'est
apparu que 9 fois alors que le w est apparu 5 fois. La
lettre y, favorisée par les références à la cryptologie ou à la cryptanalyse, a réussi à apparaître 56
fois. Il est clair, pareillement, que si nous faisions une conférence sur les W.C. dans les wagons wallons le w s'en sortirait mieux.
Il est possible
d'améliorer considérablement l'analyse de fréquence car, dans une langue
donnée, sont également connues en tant que "signatures" de la langue
:
·
les
fréquences d'apparitions des lettres doublées : ainsi, le ll apparaît par exemple 43 fois représentant ainsi 86 l sur les 595 du texte, ce qui n'est
pas négligeable, etc.
·
les
fréquences d'apparitions d'associations usuelles : le le apparaît 257 fois
( ce qui veut dire que près d'une fois sur deux, quand le l apparaît c'est pour
être suivi d'un e ), le st apparaît 113 fois, le qu
apparaît 132 fois ( ce qui veut dire que sur les
136 apparitions de la lettre q dans ce texte, elle est apparue 132 fois
immédiatement suivie de la lettre u; en réalité, les autres fois elle est
apparue isolée dans les grilles de chiffrement … ), etc.
La méthode qu'il
conviendra d'appliquer a priori s'apparente ainsi à celle de quelqu'un,
marchant la nuit par ciel clair, ne sait pas où il se trouve mais connaît la
cartographie ciel et cherche ainsi à se repérer. Il repérera facilement
l'hémisphère dans lequel il se trouve tout d'abord en repérant les
constellations spécifiques (il est vrai qu'il faut vraiment être perdu pour
commencer à se poser la question de son hémisphère …). Dans l'hémisphère
nord il repère immédiatement la grande ourse, qui lui donne l'étoile polaire,
qui lui donne etc. … d'une façon logique dès qu'il aura réussi à attraper un
fil de la pelote il déroulera tout.
Ici, la méthode de
recherche typique consiste toujours à commencer par compter pour chercher - on
suppose, pour les besoins de la cause, que la langue est le français - la
lettre e et en partant du e, si il ne s'agit que
d'une substitution simple, sans transposition et sans procédés que nous allons
aborder maintenant, on raccrochera progressivement le reste grâce aux
mathématiques ( ici élémentaires ) et avec ce que les mathématiciens appellent
de l'intuition, qui est en fait surtout un paquet d'expérience digérée avec un
bon paquet d'entraînement, mais avec un brin de talent quand même … ( mais
qu'est-ce que le talent ? ). De plus quand on sait ce qu'on cherche, on
trouve toujours plus facilement ( on a
toujours dans un coin de la tête, qu'il ne serait pas improbable de trouver tel
nom, ou tel mot, ou telle expression et ainsi, telle disposition fera
"tilt" et nous incitera à essayer quelque chose puis quelque chose
d'autre : ainsi avec de la méthode, de l'intuition, quelques raccourcis, … on y
arrive toujours ).
Récréation : Pour ceux qui sont outillés d'un ordinateur, un "jeu" très
facile à mettre en œuvre pour vous entraîner à ces pratiques consiste à prendre
un texte au hasard que, surtout, vous ne lisez pas ( c'est le plus dur à faire;
sinon vous auriez le point de départ, à moins d'avoir la précaution de
supprimer la première page écran avant de commencer à décoder; vous pouvez
aussi demander à un(e) ami(e) de le faire pour vous ). Par l'instruction de
format de votre ordinateur vous demander de changer la police pour passer d'une
police latine à une police non latine ( hébreu,
cyrillique, symbolique, …, cela dépend de ce que vous avez en stock ). Vous
avez réalisé une substitution simple. Reste à la décrypter. Même avec les
logiciels de traitement de textes simples, vous pouvez, par les fonctions
statistiques de votre ordinateur ou les fonctions "rechercher /
remplacer" ( en gérant correctement vos
sauvegardes ), réussir, beaucoup plus vite qu'avec un papier et un crayon,
résoudre ce problème élémentaire.
La même méthode nous
montrera rapidement qu'il y a un "hic" éventuel et quelle est ( quelles sont ) la (les ) nature(s) probable(s) du
"hic". Et c'est là que cela commencera à vraiment devenir intéressant
: nous sommes conduits par la logique usuelle de l'épée et du bouclier, de la
mesure et de la contre mesure, …
Celui qui construit un
chiffre sait comment un chiffre se casse et ce n'est que parce qu'il sait
casser un chiffre qu'il peut essayer d'en concevoir qu'il essaye de rendre
incassable …
L'intuition dira
peut-être d'utiliser une transposition. La transposition, même double, se
cassera sans trop de difficultés car la clef de transposition est nécessairement
périodique, avec une longueur praticable, et on retrouvera sans trop de
difficulté sa signature, même si il y a une transposition multiple ( qui n'augmente que la longueur de la clef résiduelle ). Il
ne faut pas s'interdire l'usage des transpositions, elles représenteront la
cerise sur le gâteau d'un chiffre élémentaire mais les chiffres modernes ( du 20ème siècle ) basés sur l'exploitation de
la substitution sont beaucoup plus efficaces, à la fois plus simples
d'utilisation ( au chiffrement, au déchiffrement, à la transmission ) et
donnant une protection telle qu'une transposition devient inutile. Nous
resterons donc exclusivement sur les substitutions.
Dès que le concepteur
du chiffre aura compris que le cryptanalyste
commencera pas chercher les fréquences il essaiera de les masquer.
Prenons comme exemple
un chiffre qui a donné ( en tant que concept ) de
grands développements, à savoir celui dit des "nihilistes russes".
Ce chiffre a été développé
au départ par les prisonniers politiques, qui ne manquaient pas dans les
prisons du tsar tout au long du 19ème
siècle.
Pour communiquer entre
eux sur des sujets politiques il ont conçu un chiffre
élémentaire entrant les 35 lettres de l'alphabet russe ancien dans un tableau
carré de 6 lignes et 6 colonnes.
Pour comprendre, nous
franciserons ce tableau en prenant en compte notre alphabet réduit à 25
caractères par la fusion usuelle du I et du J. Cela donne donc un tableau de 5
lignes et 5 colonnes structuré comme celui-ci :
|
1 |
2 |
3 |
4 |
5 |
1 |
A |
B |
C |
D |
E |
2 |
F |
G |
H |
I - J |
K |
3 |
L |
M |
N |
O |
P |
4 |
Q |
R |
S |
T |
U |
5 |
V |
W |
X |
Y |
Z |
Le chiffrement de base
est facile. Ainsi, le message
VOICI UN EXEMPLE
DE SUBSTITUTION
se chiffre par
:
51 34 24 13 24
45 33 15 53 15 32 35 31 15 14 15 43 45 12 43 44 24 44 45 44 24 34 33
Ce chiffre présente en
outre l'avantage de se mémoriser très facilement.
L'addition d'une
transposition très simple permet de lui donner une précaution symbolique
protégeant la lecture des simples curieux en convenant d'un mot clef en tête de
tableau. En prenant par exemple le mot clef "ZEPHIR"
on obtient, en l'inscrivant en premier puis en finissant de compléter
l'alphabet :
|
1 |
2 |
3 |
4 |
5 |
1 |
Z |
E |
P |
H |
I - J |
2 |
R |
A |
B |
C |
D |
3 |
F |
G |
K |
L |
M |
4 |
N |
O |
Q |
S |
T |
5 |
U |
V |
W |
X |
Y |
On comprend bien que
face à quelqu'un qui examine le chiffre méthodiquement cette précaution ne ralentit
nullement l'analyse. Néanmoins, une liste définie de clefs, liste détenue par
l'émetteur et le destinataire, établissant la fréquence de changement de ces
clefs ( à la fois chiffrante
et déchiffrante ) perturbera le cryptanalyste
qui s'en sortira néanmoins toujours si il a des messages suffisamment longs.
Quelles idées ont dont été successivement mises en œuvre pour faire barrage aux
efforts des casseurs de chiffre ?
L'objectif est de
masquer autant que possible ces fréquences.
Le premier procédé
s'appelle homophonie : à une lettre ( ou un mot, ou une locution ) de fréquence naturellement
élevée correspondra plusieurs équivalents dans le chiffre, équivalents utilisés
à tour de rôle ou de façon aléatoire.
Il a été remarqué que
la fréquence d'apparition de la lettre e était,
en français, de l'ordre de 16 % dans un texte
français alors que les lettres a, i, n, r, s et t apparaissaient de l'ordre de deux fois moins
souvent. Avec un tableau de chiffrement comptant, non plus 5 colonnes et 5
lignes mais 10 colonnes et 10 lignes (numérotées de 0 à 9) l'ensemble image
compte désormais 100 caractères chiffrés disponibles. Une façon triviale de masquer les fréquences
d'apparition peut donc être d'attribuer 17 paires de chiffres à la lettre e, 8 paires de chiffres à la lettre s, 7 paires de chiffres aux lettres a, i, n, r et t, et ainsi de suite en ajustant pour que chaque
lettre apparaisse au moins une fois tout en ayant 100 caractères au total,
comme dans le tableau ci-dessous :
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
0 |
O1 |
C1 |
S1 |
U1 |
N1 |
I1 |
I2 |
G |
T1 |
Q |
1 |
A1 |
E1 |
A2 |
R1 |
N2 |
L1 |
T2 |
P1 |
T3 |
V |
2 |
M1 |
S2 |
N3 |
E2 |
E3 |
U2 |
I3 |
T4 |
C2 |
R2 |
3 |
S3 |
L2 |
N4 |
A3 |
N5 |
S4 |
I4 |
U3 |
M2 |
T5 |
4 |
O2 |
O3 |
L3 |
N6 |
E4 |
S5 |
E5 |
E6 |
C3 |
R3 |
5 |
E7 |
P2 |
E8 |
L4 |
E9 |
E10 |
O4 |
E11 |
R4 |
T6 |
6 |
M3 |
E12 |
S6 |
E13 |
A4 |
I5 |
O5 |
D1 |
R5 |
R6 |
7 |
T7 |
S7 |
N7 |
E14 |
I6 |
A5 |
E15 |
E16 |
D2 |
D3 |
8 |
S8 |
U4 |
U5 |
L5 |
I7 |
E17 |
P3 |
R7 |
A6 |
A7 |
9 |
W |
B1 |
F |
X |
J |
K |
Z |
B2 |
H |
Y |
Il peut bien entendu
être conçu des substitutions un peu plus complexes que des substitutions
alphabétiques; en effet certaines paires de chiffres de l'ensemble image peuvent
être attribuées à des associations de lettres; ainsi, par exemple, un groupe
peut être réservé à l'ensemble "st" ou à l'ensemble "le",
voire à un mot complet lorsque les objets prévus des messages peuvent permettre
de prédire un usage fréquent de tel ou tel mot ( ou
locution complète ). Ceci revient à mélanger des procédés de chiffrement par
substitution ( avec homophonie ) et des procédés de
codage.
Il convient de noter
que ce plus haut degré de protection conduit à rendre l'opération de chiffrement
moins aisée. Ceci présente des inconvénients qui, dans certains cas
historiques, se sont retournés contre les concepteurs. En effet le niveau de
protection dépend largement de la bonne volonté du chiffreur; le moindre
relâchement dans peut conduire (et a conduit ) à
baisser momentanément sa garde et à permettre au cryptanalyste
qui a judicieusement mis en lumière cette faiblesse d'obtenir le premier fil
qui lui permettra alors de façon inéluctable de dérouler toute la pelote.
Il en est ainsi de
cette histoire drôle ( mais vraie ) : pendant la 1ère
guerre mondiale, les allemands transmettent des messages codés et, à un certain
moment, comme c'est normal, changent leur code. Les cryptanalistes
alliés avaient cassé l'ancien code; il fallait repartir à un zéro lorsqu'un
message en réponse d'un correspondant attire l'attention car semble, par
l'utilisation d'une abréviation, chiffré en ancien code; en réalité, le
correspondant n'arrive pas à déchiffrer le nouveau code et demande la
retransmission du message en ancien code … les transmetteurs commettent alors
l'erreur inimaginable de réexpédier le message en ancien code … ne reste plus
aux cryptanalistes de déduire le nouveau code en
ayant le texte et sa version codée …
Il en est en effet dans
le chiffre comme dans la plupart des activités humaines : tôt ou tard la loi du
moindre effort l'emporte; si le degré de protection du chiffre dépend d'une
gêne qu'un opérateur peut contourner, un opérateur finira un jour ou l'autre
par la contourner illustrant ainsi que le degré de protection qui était attendu
n'était, dans la pratique, qu'illusoire.
Une meilleure voie
consiste donc à réfléchir sur la façon d'augmenter le degré de protection sans
que cela soit aux dépends de la facilité de mise en œuvre. Un résultat de ces
recherches est le surchiffrement.
Le principe du surchiffrement
Reprenons l' exemple élémentaire d'illustration du Chiffre des
nihilistes :
|
1 |
2 |
3 |
4 |
5 |
1 |
A |
B |
C |
D |
E |
2 |
F |
G |
H |
I - J |
K |
3 |
L |
M |
N |
O |
P |
4 |
Q |
R |
S |
T |
U |
5 |
V |
W |
X |
Y |
Z |
le message
"VOICI UN EXEMPLE DE SUBSTITUTION" se chiffrait :
51 34 24 13 24 45 33 15 53
15 32 35 31 15 14 15 43 45 12 43 44 24 44 45 44 24 34 33
Le principe du surchiffrement est de considérer une clef numérique ( qui
peut être tout simplement un mot, une locution, une phrase, un texte, etc. qui
aura été préalablement chiffré suivant la même grille de chiffrement) que l'on
additionnera au message ci-dessus.
Par exemple considérons
la clef : "JE SUIS LA CLEF".
Au moyen du tableau
ci-dessus, cette clef se chiffre :
24 15 43 45 24
43 31 11 13 31 15 21
Superposons donc la clef
au message ( en reproduisant la clef autant de fois
que nécessaire pour obtenir la longueur du message ) et additionnons les
ensemble :
Message chiffré
51 34 24 13 24 45 33 15 53
15 32 35 31 15 14 15 43 45 12 43 44 24 44 45 44 24 34 33
+ clef de surchiffrement
24 15 43 45 24
43 31 11 13 31 15 21/24 15 43 45 24 43 31 11 13 31 15 21/24 15 43 45
= Message surchiffré
75 49 67 58 48 88 64 26 66
46 47 56 55 30 57 60 67 88 43 54 57 55 59 66 68 39 77 78
Le transmetteur envoie
donc le message surchiffré; à la réception, les
opérations symétriques pour le déchiffrage sont bien entendu réalisées :
Message surchiffré
75 49 67 58 48 88 64 26 66
46 47 56 55 30 57 60 67 88 43 54 57 55 59 66 68 39 77 78
- clef de surchiffrement
24 15 43 45 24 43 31 11 13
31 15 21/24 15 43 45 24 43 31 11 13 31 15 21/24 15 43 45
= Message chiffré
51 34 24 13 24 45 33 15 53
15 32 35 31 15 14 15 43 45 12 43 44 24 44 45 44 24 34 33
Ce procédé permet de
gravir un échelon significatif dans l'échelon de protection du message. En
effet, le E, qui apparaît ( n'apparaît que ) 4 fois dans le message, et qui
apparaîtrait systématiquement masqué derrière le nombre 15 dans le cas d'un
chiffrement simple, apparaît dans le message surchiffré
caché derrière les nombres : 26 ( = 15 + 11 ), 46 ( = 15 + 31 ), 30 ( = 15 + 15
) et 60 ( = 15 + 45 ). L'objectif initial qui est de masquer les fréquences
d'apparition est donc apparemment atteint.
Dans le cas de notre
exemple : un message court avec une clef longue (
comparativement à la longueur du message : le message ne représente que
deux fois et demi la longueur de la clef ), le cassage du chiffre est d'ores et
déjà quasiment impossible.
Néanmoins, nous pouvons
essayer de généraliser.
Il était d'ores et déjà
clair que, dans le cas du chiffrement par substitution simple, plus la longueur
du message chiffré sera importante plus les chances de succès rapide du
décrypteur seront grandes. Cela rejoint d'ailleurs l'aspect plus technologique
de la transmission (en raisonnant dans un cadre militaire ou assimilé) : plus une
transmission est longue plus il est facile de l'intercepter (voire de repérer
l'émetteur par triangulation dans le cas d'émission radio). (
Nota Bene à ce stade :
décrivant le B.A.BA de la cryptographie, des
remarques comme celles ci dessus, qui seraient parfaitement adaptées au temps
de la seconde guerre mondiale ou de la guerre froide, ne le sont plus
réellement avec les technologies d'aujourd'hui et la facilité de leurs
diffusions; remonter aux principes de la cryptographie, c'est aussi remonter
dans l'histoire ).
Dans le cas d'une
substitution simple surchiffrée c'est la longueur de
la clef de surchiffrement comparativement au message
qui déterminera le degré d'efficacité de la protection ajoutée par le surchiffrement.
En effet il est facile
d'imaginer que le profil de la clef, s'ajoutant de façon continue sur la
longueur du message, finira par être trouvé.
En reprenant l'exemple
ci dessus la clef numérique était :
24 15 43 45 24 43 31 11 13
31 15 21
Les éléments les plus repérables
de cette clef seront le 11 ( qui plus est
immédiatement suivi du 13 ) et le 45 ( qui plus est suivant immédiatement un 43
).
En effet, en supposant ( ce qui n'est, nous l'avons vu, pas le cas ) que les
différents caractères apparaissant dans le message soient équiprobables ( =
aient la même probabilité d'apparaître ), nous aurions ainsi autant de chance
de voir apparaître un 11 qu'un 33 ou un 55 ou l'un quelconque des 25 nombres de
la grille de chiffrement.
Le fait de réaliser une
opération de surchiffrement modifie cette structure.
Il y a 625 combinaisons message + clef théoriquement possibles ( 25 positions possibles pour un caractère du message et 25
positions possibles pour un caractère de la clef ) mais elles ne sont
évidemment pas équivalentes. Il n'y a qu'une seule façon d'obtenir le nombre 22
c'est d'additionner 11 + 11, alors qu'il y a 25 façons différentes d'obtenir le
nombre 66 ( message+clef = 11+55, 12+54, 13+53, …, 32+34, 33+33, 34+32,
…,53+13, 54+12, 55+11).
Ainsi, le 11 de la clef
que nous avons choisi explique nécessairement les apparitions éventuelles d'un
22 dans le message surchiffré ( et
signale automatiquement un 11 dans le message chiffré; NB: notre
apprentissage présente évidemment un biais puisque nous connaissons la grille …
); de même il pourrait être susceptible d'être à l'origine d'une apparition de
23 sur deux, … etc.
Dans la pratique, avec
cette clef, toutes les apparitions d'un 23, mais aussi d'un 24, mais aussi d'un
25, signeraient la présence du 11 de la clef car le plus petit nombre
immédiatement supérieur à 11 dans la clef de notre exemple se troupe être 15.
Ces commentaires, dont
on ne voit peut-être pas immédiatement l'utilité visent à faire sentir la
méthode qu'utilisera le décrypteur devant sa salade de chiffres …
La recherche d'une
complexité croissante de la substitution, complexité qui est recherchée sans
compliquer pour autant les tâches tant du chiffreur que du déchiffreur, a amené
dans un premier temps à se poser la question en termes de fréquences moyennes
pour masquer les fréquences d'apparition de tel ou tel caractère; l'utilisation
du procédé de surchiffrement fournit une réponse
tendant à être satisfaisante à cette recherche.
Néanmoins, la recherche
de figures périodiques fournira des éléments au casseur de chiffre : en notant
dans un message suffisamment long ( par rapport à la
longueur de la clef ) les apparitions des nombres les plus bas ( ou/et les plus
élevés ) et en traitant correctement ces informations, il est relativement
facile de trouver la longueur de la clef. Une fois cette longueur trouvée, le cryptanalyste se retrouve dans une situation à peine plus
compliquée que dans le cas d'une substitution simple si il a un message assez
long …
Toutes ces remarques
sur la longueur de la clef doivent conduire logiquement à dire que si on
pouvait avoir une clef de surchiffrement aussi longue
que le message la tâche du cryptanalyste serait
impossible …
C'est effectivement le
cas : c'est ce qu'on appelle "la clef aléatoire une fois". L'appel au
mot aléatoire illustre bien, qui plus est, que l'ennemie de l'émetteur ( l'amie du cryptanalyste ) c'est
la régularité qui ouvre la voie à l'usage des outils mathématiques. De plus le
qualificatif "une fois" ne traduit aucune origine belge de
l'expression mais le fait qu'il s'agit de clefs "jetables" : non
seulement elle est de même longueur que le message mais elle ne sera utilisée
pour aucun autre message.
Encore faut-il, bien
sûr, que chiffreur et déchiffreur ( émetteur et
récepteur du message ) aient la même clef …
Là encore ce sont les
Russes (soviétiques cette fois ci) qui ont apporté une réponse pratique à cette
question à l'occasion de la seconde guerre mondiale. En effet les réseaux
TREPPER ( l'Orchestre rouge), SORGE ainsi que le
réseau suisse ont utilisé ces principes. Emetteur et récepteur conviennent
ensemble d'un livre code ( par exemple quelque chose du genre " l'édition
1927 de La Bête Humaine de Zola aux éditions Hachette" ) et des
procédures d'identification; ensuite, pour tel message, on partira par exemple
du haut à gauche de la page 43 comme clef de surchiffrement
jusqu'à la fin du message.; au message suivant, on partira peut-être de la page
127, et ce jusqu'à épuisement du livre code …
Ce procédé est
incassable et n'a effectivement jamais été cassé sauf quand l'émetteur a été
pris la main dans le sac … avec son livre code. Rétroactivement tous les
messages préalablement stockés peuvent alors être lus et l'émetteur retourné.
Ceci est arrivé quelquefois; la sécurité des transmissions en milieu hostile
commence évidemment par la sécurité des transmetteurs.
Néanmoins, même cet
aspect est désormais minimisé par les développements de la technologie mais
nous entrerions dans les dimensions contemporaines de la cryptographie et qui nous
entraîneraient beaucoup trop loin dans ce qui ne se voulait qu'une introduction
à la cryptographie.
(conférence
réalisée par Michel NAUD)
afis, Science et pseudo-sciences, 14 rue de l'école polytechnique, 75005
PARIS.
[1] On ne traitera pas des procédés dits "stéganographiques" visant à masquer l'existence même d'un message. Par exemple, l'usage de l' "encre sympathique" est un procédé de cette nature. Le jeu - car souvent pratiqué comme tel - consistant à ce que chaque lettre d'un message soit utilisée comme première lettre d'un ver dans ce qui a l'apparence d'une poésie procède d'un procédé de même nature. Certains procédés peuvent être à la limite entre les deux tels ceux inspirés du code de Francis BACON que nous évoquerons par curiosité.