Chiffre de César

Un article de Wikipédia, l'encyclopédie libre.

90 %

Traduction -----

Caesar cipher →

Chiffre de César ---- (+ d’infos)

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 chiffre de César, est aussi connu comme code de César, substitution de César, chiffrement par décalage (de l'anglais shift cipher), est une des méthodes connues d'encryptage la plus simple et la plus connue. C'est une technique de chiffrement par substitution, c'est-à-dire que chaque lettre du texte en clair est remplacée par une autre lettre à distance fixe dans l'alphabet. Par exemple, si l'on utilise un décalage de 3, A serait remplacé par D, B deviendrait E, et ainsi de suite. Cette méthode doit son nom à Jules César, qui utilisait cette technique pour certaines de ses correspondances, notamment militaires.

L'étape de chiffrement du chiffre de César n'est souvent qu'une partie d'une méthode plus complexe, comme le chiffre de Vigenère. Encore aujourd'hui, il est utilisé dans l'algorithme de chiffrement ROT13. Comme n'importe quel encodage par substitution monoalphabétique, le chiffre de César est facilement décrypté et n'offre qu'une très faible sécurité de communication.

Sommaire

1 Exemple
2 Histoire et utilisation
3 Cassage du code
4 Notes et références de l'article
5 Voir aussi
- 5.1 Articles connexes
- 5.2 Liens et documents externes
6 Source

[modifier] Exemple

L'encryptage peut être représenté par la superposition de deux alphabets, l'alphabet clair présenté dans l'ordre normal et l'alphabet chiffré qui est 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

L'encryptage peut aussi être représenté en utilisant l'arithmétique modulaire. En commençant par transformer chaque lettre en un nombre (A = 0, B = 1,..., Z = 25), pour encoder une lettre $x$ avec une clé n il suffit d'appliquer la formule:

$E_n(x) = (x + n) \mod {26}.$

Le décryptage est semblable mais en utilisant la clé inverse ( avec $- n$ à la place de $n$ ):

$D_n(x) = (x - n) \mod {26}.$

(NB: il y a plusieurs définitions pour l'opérateur modulo en mathématique, voir notamment le modulo en informatique. Ci-dessus, le résultat doit être dans l'intervalle $[0,25]$ ; c'est-à-dire que si $x + n$ (resp. $x - n$ ) ne sont pas dans l'intervalle $[0,25]$ , il faut soustraire (resp. ajouter) 26).

Le décalage demeurant toujours le même pour un même message, cette méthode est classée comme une substitution monoalphabétique, contrairement à une substitution polyalphabétique (ex: Chiffre de Vigenère).

[modifier] Histoire et utilisation

Code de César ainsi nommé car Jules César l'utilisa.

Le code de César doit son nom à Jules César qui, selon Suétone (dans Vie des douze Césars), l'utilisait, avec un décalage de trois sur la gauche, pour certaines de ses correspondances secrètes (notamment militaire) :

…et pour ce qu'il voulait particulièrement cacher, il modifiait les lettres de façon à ce qu'elles ne forment plus de mot intelligible. Et pour celui qui s'aviserait à les déchiffrer, j'indique qu'il s'agissait de substituer les lettres une à une : à la première lettre de l'alphabet on substitue la quatrième, soit D pour A, et ainsi de suite. — Suétone, Vie des douze Césars, Livre I, paragraphe 56 [1].

Ce que confirme Aulu-Gelle :

Nous avons un recueil des lettres du C. César à C. Oppius et Balbus Cornélius, 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 à substitution ont été utilisés avant lui. Augustus, son neveu, utilisait aussi un chiffre, mais utilisait un décalage de un sans boucler à la fin de l'alphabet :

Chaque fois qu'il écrivait de manière chiffrée, il écrivait un B pour un A, un C pour un B, ainsi de suite pour le reste de l'alphabet, utilisant AA pour X. — Suétone, Vie d'Auguste, 88.

Des preuves montrent que Jules César utilisait d'autres techniques de chiffrement plus complexes, et Aulu-Gelle fait référence à un piège (aujourd’hui perdu) de son chiffrement :

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.

On ignore quelle était l'efficacité du code de César à cette époque, mais il est probable qu'il ait été relativement sûr, principalement parce que la plupart des ennemis de César étaient illettrés, et n'étaient donc pas à même d'envisager la cryptanalyse du texte. Même en supposant qu'un opposant ait pu lire le message, il n'y a pas de trace à cette époque des techniques permettant de casser un simple chiffrement par substitution. La première trace de leur apparition date du IX^e siècle, avec la découverte dans le monde arabe de l'analyse fréquentielle.

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

Au XIX^e siècle, les pages d'annonces personnelles des journaux étaient parfois utilisées pour la transmission de messages cryptés à l'aide de codes simples. David Kahn (1967) donne des exemples d'amants communiquant en secret en chiffrant leurs messages à l'aide du chiffre de César dans le journal britannique The Times. Le code de César fut employé pas plus tard qu'en 1915 quand l'armée russe s'en servit en remplacement de codes plus élaborés, 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.

Aujourd'hui, on peut trouver le chiffre de César dans des jouets promotionnels pour enfants. 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 cryptage en tant que tel.

Le chiffre de Vigenère est une variante du chiffre de César qui utilise un décalage différent pour chaque lettre du texte ; la valeur de ce décalage est défini à l'aide d'un mot-clé. Si ce dernier est choisi de façon parfaitement aléatoire, et qu'il est aussi long que le message à chiffrer (afin d'éviter les répétitions), le résultat est alors théoriquement incassable - et donc aussi efficace que le masque jetable.

En avril 2006, le chef en fuite de la Mafia Bernardo Provenzano a été capturé en Sicile en partie parce qu'une partie de sa correspondance fut déchiffrée. Elle était écrite dans une variante du chiffrement de César ; Provenzano utilisait les nombres: A s'écrivait 5, B 6, etc.^[2]

[modifier] Cassage du code

Décalage du décryptage	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 code de César a été utilisé, mais ignore la valeur du décalage.

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

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'à avoir trouvé le bon. C'est ce qu'on appel une attaque par force brute qui est une technique peu subtile. Un méthode simple pour faire cela est de prendre un fragment du texte crypté et d'écrire dans un tableau tous les décalages possibles (voir le tableau ci-contre). 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 présenter serait d'écrire toutes les lettres de l'alphabet à l'envers, 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 à l'envers écrit dessus ; les bandes étant placés 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 de la fréquence d'apparition de lettres dans un texte en anglais. Un chiffrement de César ne fait que décaler cette distribution, ce qui rend son cassage par analyse fréquentielle aisé.

Une autre attaque par force brute 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 crypté et un autre avec un texte de référence, dans la langue du message d'origine - 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 par là même la clé de cryptage. 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. Des ordinateurs peuvent aussi faire ce travail de reconnaissance en évaluant la concordance de distribution de deux textes (le texte chiffré et celui de référence) (en utilisant, par exemple, une fonction Pearson's chi-square test (en)).

Avec de grand texte, il n'y a aura fort probablement qu'une seul possibilité de décryptage ; mais pour de petits textes, il peut y avoir plusieurs possibilités de décryptage.

Enchaîner les cryptage et les décryptages ne donne pas de protection supplémentaire car crypter un texte avec un décalage de trois sur la gauche, puis le crypter 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 d'autres termes, le cryptage sous n'importe quelle clé forme un groupe.

[modifier] Notes et références de l'article

↑ (en) Alexander Poltorak, « Mezuzah and Astrology - The Mysterious Name » sur http://www.chabad.org/. Consulté le 30 janvier 2008
↑ (en)John Leyden, « Mafia boss undone by clumsy crypto » sur http://www.theregister.co.uk/. Mis en ligne le 19 avril 2006, consulté le 30 janvier 2008

(en) David Kahn, The Codebreakers — The Story of Secret Writing, 1967. ISBN 0-684-83130-9.
(en) F.L. Bauer, Decrypted Secrets, 2nd edition, 2000, Springer. ISBN 3-540-66871-3.
(en) Chris Savarese and Brian Hart, The Caesar Cipher, 1999 [2].