Chiffre de César
Un article de Wikipédia, l'encyclopédie libre.
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 de chiffrement des plus simples et une des plus connues. 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 ; on parle alors de décalage circulaire. 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 code 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 |
[modifier] 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é 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
Le chiffrement 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 :
Le déchiffrement est semblable mais en utilisant la clé inverse (avec − n à la place de n) :
(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) n'est 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 (exemple : Chiffre de Vigenère).
[modifier] Histoire et utilisation
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, principalement 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 l'a, et ainsi de suite.[1] »
— Suétone, Vie des douze Césars, Livre I, paragraphe 56
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 :
« 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
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, ou dans le cas où l'opposant savait lire, aurait tout simplement cru que le message était écrit dans un langage étranger. 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 IXe 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[2].
Au XIXe 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 chiffrement 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 4, B 5, etc.[3]
[modifier] Cassage du code
| 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 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.
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 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. 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 test du chi2 de Pearson.
Avec de grands textes, il n'y a fort probablement qu'une seul possibilité de déchiffrement ; mais pour de petits 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é).
Enchaîner les chiffrement 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 des termes mathématiques, l'ensemble des opérations de chiffrement, muni de la loi de composition des applications, forme un groupe fini car il n'existe que vingt six méthodes de chiffrement différentes.
[modifier] Noms de cas particuliers
- Décalage de 10 rangs : avocat (A vaut K)
- Décalage de -5 rangs : cassis (K 6)
- Décalage de -4 rangs : cassette (K 7)
- Décalage de 13 rangs : ROT13 (le seul pour lequel les fonctions de codage et décodage sont identiques)
[modifier] Notes et références de l'article
- ↑ (en) Texte en anglais
- ↑ (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, 2e édition, 2000, Springer (ISBN 3-540-66871-3).
- (en) Chris Savarese et Brian Hart, The Caesar Cipher, 1999 [1].
- (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Caesar cipher ».
[modifier] Voir aussi
[modifier] Articles connexes
[modifier] Liens et documents externes
- (en) A Caesar shift decoder in Excel format allowing you to see all 25 possibilities simultaneously
- Chiffrement en ligne
- (en) Code Cracker ; outil de chiffrement en ligne avec plusieurs algorithmes de chiffrement.
