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é.