Chiffrement par décalage

Vous lisez un « bon article ».

Le chiffre de César fonctionne par décalage des lettres de l'alphabet. Par exemple dans l'image ci-dessus, il y a une distance de 3 caractères, donc B devient E dans le texte codé.

En cryptographie, le chiffrement par décalage, aussi connu comme le chiffre de César ou le code de César (voir les différents noms), est une méthode de chiffrement très simple utilisée par Jules César dans ses correspondances secrètes (ce qui explique le nom « chiffre de César »).

Le texte chiffré s'obtient en remplaçant chaque lettre du texte clair original par une lettre à distance fixe, toujours du même côté, dans l'ordre de l'alphabet. Pour les dernières lettres (dans le cas d'un décalage à droite), on reprend au début. Par exemple avec un décalage de 3 vers la droite, A est remplacé par D, B devient E, et ainsi jusqu'à W qui devient Z, puis X devient A etc. Il s'agit d'une permutation circulaire de l'alphabet. La longueur du décalage, 3 dans l'exemple évoqué, constitue la clé du chiffrement qu'il suffit de transmettre au destinataire — s'il sait déjà qu'il s'agit d'un chiffrement de César — pour que celui-ci puisse déchiffrer le message. Dans le cas de l'alphabet latin, le chiffre de César n'a que 26 clés possibles (y compris la clé nulle, qui ne modifie pas le texte).

Il s'agit d'un cas particulier de chiffrement par substitution monoalphabétique : ces substitutions reposent sur un principe analogue, mais sont obtenues par des permutations quelconques des lettres de l'alphabet. Dans le cas général, la clé est donnée par la permutation, et le nombre de clés possibles est alors sans commune mesure avec celui des chiffrements de César.

Le chiffrement de César a pu être utilisé comme élément d'une méthode plus complexe, comme le chiffre de Vigenère. Seul, il n'offre aucune sécurité de communication, à cause du très faible nombre de clés, ce qui permet d'essayer systématiquement celles-ci quand la méthode de chiffrement est connue, mais aussi parce que, comme tout encodage par substitution monoalphabétique, il peut être très rapidement « cassé » par analyse de fréquences (certaines lettres apparaissent beaucoup plus souvent que les autres dans une langue naturelle).

Exemple

Le chiffrement peut être représenté par la superposition de deux alphabets, l'alphabet clair présenté dans l'ordre normal et l'alphabet chiffré décalé, à gauche ou à droite, du nombre de lettres voulu. Nous avons ci-dessous l'exemple d'un encodage de 3 lettres vers la droite. Le paramètre de décalage (ici 3) est la clé de chiffrement :

clair   : ABCDEFGHIJKLMNOPQRSTUVWXYZ
chiffré : DEFGHIJKLMNOPQRSTUVWXYZABC

Pour encoder un message, il suffit de regarder chaque lettre du message clair, et d'écrire la lettre encodée correspondante. Pour déchiffrer, on fait tout simplement l'inverse.

original : Wikipedia l'encyclopedie libre
encodé   : ZLNLSHGLD O'HQFBFORSHGLH OLEUH

Le chiffrement peut aussi être représenté en utilisant les congruences sur les entiers. En commençant par transformer chaque lettre en un nombre (A = 0, B = 1,..., Z = 25)^[1], pour encoder une lettre $x$ avec une clé n il suffit d'appliquer la formule^[2] :

$E_n(x) {{=}} (x + n) \ [26]$

Le déchiffrement consiste à utiliser la clé opposée ( $-n$ à la place de $n$ ) :

$D_n(x) {{=}} (x - n) \ [26]$

On peut s'arranger pour que le résultat soit toujours représenté par un entier de 0 à 25 : si $x + n$ (respectivement $x - n$ ) n'est pas dans l'intervalle $[0,25]$ , il suffit de soustraire (respectivement ajouter) 26.

Le décalage demeurant toujours le même pour un même message, cette méthode est une substitution monoalphabétique, contrairement au chiffre de Vigenère qui constitue une substitution polyalphabétique.

Dénominations

Le chiffrement par décalage possède plusieurs synonymes :

le chiffre de César. César utilisait pour ses correspondances un chiffrement par décalage de 3 vers la droite. Selon David Kahn, ce n'est que récemment que l'expression « chiffre de César » désigne les chiffrements par décalage ayant un décalage différent de 3^[3] ;
la substitution de César ;
le terme code de César est un abus de langage : en cryptologie, le chiffre est un procédé systématique, alors qu'un code utilise le symbolisme des mots. À ce sujet, se reporter au chapitre Différence entre chiffre et code de l'article « Chiffre ».

Historique

Chiffre de César ainsi appelé car Jules César l'utilisa.

César

Postérieur et plus simple que la scytale^[4], le chiffre de César doit son nom à Jules César qui, selon Suétone l'utilisait avec l'alphabet grec (inintelligible pour la plupart des Gaulois mais langue maîtrisée par les élites dirigeantes romaines^[5]) et un décalage de trois sur la droite pour certaines de ses correspondances secrètes, notamment militaires :

« Il y employait, pour les choses tout à fait secrètes, une espèce de chiffre qui en rendait le sens inintelligible (les lettres étant disposées de manière à ne pouvoir jamais former un mot), et qui consistait, je le dis pour ceux qui voudront les déchiffrer, à changer le rang des lettres dans l'alphabet, en écrivant la quatrième pour la première, c'est-à-dire le d pour le a, et ainsi de suite^[6]. »

— Suétone, Vie des douze Césars, Livre I, paragraphe 56.

Aulu-Gelle confirme l'usage par Jules César de méthodes de chiffrement par substitution :

« Nous avons un recueil des lettres de J. César à C. Oppius et Balbus Cornelius, chargés du soin de ses affaires en son absence. Dans ces lettres, on trouve, en certains endroits, des fragments de syllabes sans liaison, caractères isolés, qu'on croirait jetés au hasard : il est impossible d'en former aucun mot. C'était un stratagème dont ils étaient convenus entre eux : sur le papier une lettre prenait la place et le nom d'une autre ; mais le lecteur restituait à chacune son nom et sa signification »

— Aulu-Gelle, Nuits attiques, livre XVII, 9

Bien que César soit le premier personnage connu à utiliser cette technique, on sait que d'autres chiffres par substitution, éventuellement plus complexes, ont été utilisés avant lui, et il n'est donc pas certain qu'il soit le premier à l'avoir conçu, même s'il a pu le réinventer^[7].

Auguste, son neveu, utilisait aussi un chiffre, consistant en un décalage de un sans boucler à la fin de l'alphabet :

« Lorsqu'il écrivait en chiffres, il employait le b pour a, le c pour le b, et ainsi de suite pour les autres lettres. Au lieu du z il mettait deux a. »

— Suétone, Vie d'Auguste, 88

Toujours suivant les écrits d'Aulu-Gelle, on peut penser que Jules César utilisait d'autres clés, et même d'autres techniques de chiffrement plus complexes^[8]. En particulier Aulu-Gelle fait référence à un traité (aujourd’hui perdu) consacré aux chiffres utilisés par César^[9].

On ignore quelle était l'efficacité du chiffre de César à son époque. La première trace de techniques de cryptanalyse date du IX^e siècle avec le développement dans le monde arabe de l'analyse fréquentielle^[10].

Utilisations

Un chiffre de César, avec un décalage de un, apparaît au dos du Mezuzah^[11].

Au XIX^e siècle, les pages d'annonces personnelles des journaux étaient parfois utilisées pour la transmission de messages chiffrés à l'aide de codes simples. David Kahn donne des exemples d'amants communiquant de manière confidentielle en chiffrant leurs messages à l'aide du chiffre de César dans le quotidien britannique The Times^[12]. Le chiffre de César fut encore employé en 1915 : l'armée russe le préférait à d'autres codes plus élaborés mais qui s'étaient révélés trop difficiles d'utilisation pour leurs troupes ; les analystes allemands et autrichiens eurent peu de mal à déchiffrer leurs messages^[13]. Le codage utilisé par Enigma se base aussi sur la substitution des lettres, mais en suivant une méthode beaucoup plus complexe.

Utilisations modernes

Aujourd'hui, on peut trouver le chiffre de César dans des jouets promotionnels pour enfants. Les livres-jeu emploient souvent cette méthode, avec un décalage de un ou deux dans un sens ou dans l'autre, pour donner des indications sans rendre le jeu trop facile.

Plusieurs cas particuliers ont été nommés par jeux de mots : « avocat » (A vaut K), « cassis » (K 6) et « cassette » (K 7). Typiquement, un jeu pour enfant peut impliquer de décoder un message, en donnant un indice contenant le mot « avocat ».

Un tel code avec un décalage de 13 caractères est aussi employé dans l'algorithme ROT13 : cette méthode très simple est utilisée dans certains forums sur Internet pour brouiller tout ou partie d'un texte (comme la chute d'une blague, ou un spoiler), mais pas comme méthode de chiffrement en tant que tel^[14].

En avril 2006, le chef en fuite de la mafia Bernardo Provenzano a été capturé en Sicile grâce notamment au déchiffrement d'une partie de sa correspondance qui utilisait une variante du chiffrement de César basée sur les nombres : A s'écrivait 4, B 5, etc^[15].

Attaques

Décalage du déchiffrement	Texte de test
0	`GVCTX SKVEQ QI`
1	`FUBSW RJUDP PH`
2	`ETARV QITCO OG`
3	`DSZQU PHSBN NF`
4	`CRYPT OGRAM ME`
5	`BQXOS NFQZL LD`
6	`APWNR MEPYK KC`
…
23	`JYFWA VNYHT TL`
24	`IXEVZ UMXGS SK`
25	`HWDUY TLWFR RJ`

Le chiffre de César peut être cassé très facilement, même à l'aide du seul texte chiffré. On peut distinguer deux cas :

le cryptanalyste a connaissance du fait qu'un simple chiffrement par substitution a été employé, mais ignore qu'il s'agit du chiffre de César en particulier ;
le cryptanalyste sait que le chiffre de César a été utilisé, mais ignore la valeur du décalage.

Par recherche de la méthode de chiffrement

Dans le premier cas, il est possible de casser le chiffre de César à l'aide des mêmes techniques que dans le cas général d'un chiffrement par substitution, à savoir l'analyse fréquentielle ou la recherche de mots probables^[16]. Lors de la résolution, le cryptanalyste ne sera pas sans remarquer une certaine régularité dans les décalages, et en déduira que l'algorithme employé est le chiffre de César.

Par recherche de la valeur du décalage

Dans le deuxième cas, comme il n'y a qu'un nombre limité de décalages (vingt-six dont un inutile), il suffit de tester tous les chiffrements possibles jusqu'à trouver le bon. C'est ce qu'on appelle une attaque par force brute, technique de test de toutes les combinaisons possibles^[17]. Une méthode simple pour mener l'attaque est de prendre un fragment du texte chiffré et d'écrire dans un tableau tous les décalages possibles (voir le tableau ci-contre)^[18]. Dans ce tableau, on a pris le fragment GVCTX SKVEQ QI ; le texte en clair apparaît ainsi facilement à la quatrième ligne. Une autre façon de procéder serait d'écrire toutes les lettres de l'alphabet, en dessous de chaque lettre du fragment, et en commençant par celle-ci. Ce genre d'attaque peut être accélérée en utilisant des bandes avec l'alphabet écrit dessus ; les bandes étant placées en colonne sur le texte chiffré (lettre sur lettre : par exemple, le « E » de la bande doit être placé au-dessus du « E » du texte chiffré), la phrase en clair doit apparaître sur une des lignes.

Analyse fréquentielle

Analyse de la fréquence d'apparition de lettres dans un texte en français. Un chiffrement de César ne fait que décaler cette distribution, ce qui rend son cassage aisé par analyse fréquentielle.

Une autre attaque possible est de faire une analyse de fréquence d'apparition des lettres : on génère un graphique sur la fréquence d'apparition de chaque lettre dans le texte chiffré et un autre avec un texte de référence, dans la langue du message d'origine, et on explore par décalages successifs toutes les possibilités. En les comparant, un humain peut facilement voir la valeur du décalage entre ces deux graphiques, et trouver la clé de chiffrement. Cette technique s'appelle l'analyse fréquentielle. Par exemple, en anglais, les lettres E et T sont les plus fréquentes et les lettres Q et Z, les moins fréquentes^[19]. Des ordinateurs peuvent aussi faire ce travail de reconnaissance en évaluant la concordance de distribution des deux textes (le texte chiffré et celui de référence) en utilisant, par exemple, une fonction test du χ² de Pearson^[20].

Avec des textes longs, il est très probable qu'il n'y ait qu'une seule possibilité de déchiffrement. Mais pour de courts textes, il peut y avoir plusieurs possibilités de déchiffrement. Par exemple, « NYHCL » peut être déchiffré en « grave » (par un décalage de 19) ou en « tenir » (6) (pour un texte en français) ; ou alors « DQODG » peut donner « bombe » (24) ou « recru » (14) (voir aussi : distance d'unicité).

Composition de chiffrements

Enchaîner les chiffrements (et les déchiffrements) ne donne pas de protection supplémentaire car chiffrer un texte avec un décalage de trois sur la gauche, puis le chiffrer de nouveau avec un décalage de sept sur la droite revient exactement au même que de coder le texte de départ avec un décalage de quatre sur la droite ( $3 - 7 = -4$ ). En termes mathématiques, l'ensemble des vingt-six opérations de chiffrement (en comprenant le décalage nul c'est-à-dire le texte chiffré identique au texte clair) est stable par composition. Il forme même un groupe^[21], puisque, de plus, une opération de déchiffrement est identique à une opération de chiffrement.

Le chiffre de Vigenère

Article détaillé : chiffre de Vigenère.

Le chiffre de Vigenère utilise le chiffre de César mais avec un décalage différent suivant la position de la lettre décalée dans le texte ; la valeur de ce décalage est définie à l'aide d'un mot-clé, chaque lettre du mot-clé désigne le décalage correspondant à sa position dans l'alphabet (0 pour A, 1 pour B etc.). Si la longueur du mot clé est n, toutes les lettres du texte clair en position un multiple de n sont décalées suivant le même entier, de même pour celles en position un multiple de n plus 1, etc. L'utilisation de plusieurs décalages différents rend inopérante l'analyse fréquentielle classique, du moins directement. Des méthodes statistiques plus avancées, utilisant l'indice de coïncidence, permettent cependant de casser le code (voir aussi cryptanalyse du chiffre de Vigenère).

On peut voir le chiffrement de Vernam (ou « masque jetable ») comme un chiffre de Vigenère où le mot-clé est de même longueur que le texte à chiffrer, choisi de façon complètement aléatoire, et utilisé une seule fois. Il est alors théoriquement incassable, mais difficile à utiliser en pratique.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Caesar cipher » (voir la liste des auteurs).

↑ (en) Dennis Luciano et Gordon Prichett, « Cryptology: From Caesar Ciphers to Public-Key Cryptosystems », The College Mathematics Journal, vol. 18, n^o 1,‎ janvier 1987, p. 3 (DOI 10.2307/2686311)
↑ R. Wobst, op. cit. Cryptology Unlocked p. 19
↑ « To this day, any cipher alphabet that consists of the standard sequence, like Caesar's, is called a Caesar alphabet, even if it begins with a letter other than D. » dans The Codebreakers
↑ Charles-François Vesin, La cryptographie dévoilée : ou, Art de traduire ou de déchiffrer toutes les écritures en quelque caractère et en quelque langue que ce soit ... appliqué aux langues française, allemande, anglaise, latine, italienne, espagnole, suivi d'un précis analytique des écrites ...,‎ 1857, 259 p. (lire en ligne)
↑ Rémy Kauffer, Histoire mondiale des services secrets, Perrin,‎ 2015, p. 23
↑ (en) Texte en anglais
↑ (en) Edgar C. Reinke, « Classical Cryptography », The Classical Journal, vol. 58, n^o 3,‎ décembre 1962, p. 115
↑ (en) Edgar C. Reinke, « Classical Cryptography », The Classical Journal, vol. 58, n^o 3,‎ décembre 1962, p. 114 et note 6 p 121
↑
« On trouve même un traité assez bien écrit du grammairien Probus au sujet de la signification cachée des lettres dans la correspondance de César. »
— Aulus Gellius, 17.9.1–5
, cité par Reinke, voir note précédente.
↑ S. Singh, op. cit. The Code Book pp. 14-20
↑ (en) Alexander Poltorak, « Mezuzah and Astrology - The Mysterious Name », sur http://www.chabad.org/ (consulté en 30 août 2009)
↑ D. Kahn, op. cit. The Codebreakers — The Story of Secret Writing pp. 775-776
↑ D. Kahn, op. cit. The Codebreakers — The Story of Secret Writing pp. 631-632
↑ R. Wobst, op. cit. Cryptology Unlocked p. 20
↑ (en) John Leyden, « Mafia boss undone by clumsy crypto », The Register,‎ avril 2006 (consulté en 30 août 2009)
↑ A. Beutelspacher, op. cit. Cryptology pp. 9-11
↑ A. Beutelspacher, op. cit. Cryptology pp. 8-9
↑ (en) Albert C. Leighton, « Secret Communication among the Greeks and Romans », Technology and Culture, vol. 10, n^o 2,‎ avril 1969, p. 153 (DOI 10.2307/3101474)
↑ S. Singh, op. cit. The Code Book pp. 72-77
↑ (en) Chris Savarese et Brian Hart, « The Caesar Cipher » (consulté en 30 août 2009)
↑ R. Wobst, op. cit. Cryptology Unlocked p. 31

Voir aussi

Bibliographie

(en) Friedrich L. Bauer, Decrypted Secrets, Springer,‎ 2000 (ISBN 3-540-66871-3)
(en) Albrecht Beutelspacher, Cryptology, Mathematical Association of America,‎ 1994 (ISBN 0-88385-504-6)
(en) David Kahn, The Codebreakers — The Story of Secret Writing,‎ 1967 (ISBN 0-684-83130-9)
(en) Josef Pieprzyk, Thomas Hardjono et Jennifer Seberry, Fundamentals of Computer Security, Springer,‎ 2003 (ISBN 3540431012)
(en) Simon Singh, The Code Book, Anchor,‎ 2000 (ISBN 0385495323). Édition française sous le tite Histoire des codes secrets. De l'Égypte des pharaons à l'ordinateur quantique, Livre de Poche, 2001, (ISBN 2253150975).
(en) Abraham Sinkov et Paul L. Irwin, Elementary Cryptanalysis: A Mathematical Approach, Mathematical Association of America,‎ 1966 (ISBN 0883856220)
(en) Reinhard Wobst, Cryptology Unlocked, Wiley,‎ 2001 (ISBN 978-0470060643)

Articles connexes

Distance d'unicité
Chiffre affine

Portail de la cryptologie
Portail de la Rome antique

This article is issued from Wikipédia - version of the Wednesday, October 28, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.