Chiffre affine
Le chiffre affine est une méthode de cryptographie basée sur un chiffrement par substitution mono-alphabétique, c'est-à-dire que la lettre d'origine n'est remplacée que par une unique autre lettre, contrairement au chiffre de Hill. Il s'agit d'un code simple à appréhender mais aussi un des plus faciles à casser. Le créateur du chiffre affine est inconnu.
Principe
Chiffrement
On commence par remplacer chaque lettre par son rang dans l'alphabet en commençant au rang 0 (certaines variantes commencent au rang 1) :
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 |
0 | 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 |
Deux entiers a et b sont choisis comme clef. Chaque lettre claire est d'abord remplacée par son équivalent numérique x puis chiffrée par le calcul du reste de la division euclidienne par 26 de l'expression affine (soit ).
Ainsi pour chiffrer le mot CODE grâce au chiffre affine de clef (17,3), il faut d'abord le transcrire en série de nombres
- C O D E → 2 ; 14 ; 3 ; 4
appliquer ensuite la fonction affine
- 2 ; 14 ; 3 ; 4 → 37 ; 241 ; 54 ; 71
prendre les restes dans la division par 26
- 37 ; 241 ; 54 ; 71 → 11 ; 7 ; 2 ; 19
puis retranscrire en lettres
- 11 ; 7 ; 2 ; 19 → L H C T
Note
Si le coefficient a vaut 1, alors le codage affine correspond au chiffre de César.
De plus, le coefficient a doit toujours être premier avec le nombre total de lettres de l'alphabet utilisé. Par exemple, pour l'alphabet latin de 26 lettres, les possibilités sont : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 ou 25. Dans le cas contraire, les autres coefficients donnent dans la table plusieurs fois la même lettre. (La fréquence d'apparition de la lettre vaut alors le coefficient) Si celui-ci vaut 4, la lettre "N", si elle est présente, remplacera 4 lettres différentes à elle seule. Par ailleurs, si le coefficient a vaut le nombre de lettres présentes dans la table, la lettre dont le rang est égal à 0 remplacera toutes les autres. Les coefficients supérieurs au nombre de lettres comprises dans la table ont la même valeur que ceux qui y sont compris. Par exemple, si notre nombre de lettres est égal à 26, alors les clefs (1 ; 0), (27 ; 0) et (53 ; 0) coderont exactement les mêmes lettres.
Déchiffrement
Pour déchiffrer le message, il faut être capable de trouver l'antécédent de par l'application qui, à un entier compris entre 0 et 25, associe le reste de dans la division par 26. Il est facile d'ôter mais il n'est pas toujours réalisable de simplifier par . La simplification ne peut s'effectuer que s'il existe un entier tel que a pour reste 1 dans la division par 26. C'est-à-dire s'il existe un entier tel que
- soit encore
Le théorème de Bachet-Bézout affirme que l'on ne peut trouver et que lorsque est premier avec 26. La clef de code doit donc être un couple d'entiers dans lequel est premier avec 26.
C'est le cas, dans l'exemple choisi, l'entier est 23. Pour déchiffrer le message, il faut donc ôter 3 à chaque nombre, les multiplier par 23 puis en chercher les restes dans la division par 26
- L H C T → 11 ; 7 ; 2 ; 19
- 11 ; 7 ; 2 ; 19 → 8 ; 4 ; -1 ; 16
- 8 ; 4 ; -1 ; 16 → 184 ; 92 ; -23 ; 368
- 184 ; 92 ; -23 ; 368 - > 2 ; 14 ; 3 ; 4
- 2 ; 14 ; 3 ; 4 - > C O D E
Cryptanalyse
Il n'existe que 12 entiers compris entre 0 et 26 et premiers avec 26 (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 et 25). Il n'existe donc que clés de chiffrement possible. Si l'on sait qu'un code affine a été utilisé, on peut casser le code par force brute en essayant les 312 clés.
À la lumière du principe de Kerckhoffs, ce manque de variété rend ce système très peu sécurisé.
Si le message est plus long, on peut tenter d'identifier les lettres selon leur fréquence d'apparition dans les messages. En effet une lettre est, par cette méthode, toujours remplacée par la même lettre. La lettre E, par exemple, étant en français très fréquente, si, dans le message chiffré, la lettre T est très fréquente, on peut supposer que E est remplacé par T et ne rechercher que les codages affines permettant cette substitution.
Variantes
Le système de codage précédemment décrit ne code que les 26 lettres de l'alphabet et aucun signe typographique. On peut élargir le champ des caractères à coder en prenant leur code ASCII. Ce qui fournit, si on exclut le 32 premiers nombres et 128e qui ne correspondent pas à des caractères affichables, 95 caractères à coder. À chaque caractère, on associe donc son code ASCII diminuée de 32. Le chiffre affine utilise alors une clé (a, b) où a et b sont choisis entre 0 et 94, l'entier a étant premier avec 95. le nombre x est remplacé par le reste de .
Cette variante offre l'avantage, d'une part d'offrir une plus grande variété dans les caractères utilisables (95) d'autre part de rendre le cassage par force brute un peu plus long car il faut essayer 6840 clefs. Ce système est en outre très facile à programmer. Mais le cassage par observation des fréquences de chaque caractère reste encore possible.
L'autre système consiste à grouper les lettres par paire et d'effectuer une transformation affine sur chaque paire de nombre. C'est le chiffre de Hill.
Utilisation
Le chiffre affine regroupe plusieurs systèmes de chiffrement simples comme le chiffrement par décalage, de clé (1,n) dont les plus connus sont le code de César de clé (1,3) et le ROT13 de clé (1,13) ou des chiffrements par symétrie comme le code Atbash de clé (-1;25).
Le chiffrement affine dans sa généralité n'offre pas de sécurité suffisante pour chiffrer des messages. Il est en outre plus difficile à mettre en place qu'un code de César. il est donc dans les faits assez rarement utilisé sauf dans le cadre d'énigme à résoudre. Il est principalement un exemple pédagogique montrant la place de l'arithmétique dans la cryptologie.
Source
- Arithmétique en TS, Arithmétique et cryptographie, CRDP d'Auvergne
Voir aussi
Articles connexes
- Chiffrement par substitution
- Chiffre de César
- Cryptanalyse
Lien externe
- Applet de chiffrement et de déchiffrement en ligne
v · m Cryptologie historique | |
---|---|
Substitution monoalphabétique | |
Substitution polyalphabétique |
|
Transposition | |
Substitution et transposition | |
Autres chiffrements | |
Cryptanalyse | |
Histoire |
Portail de la cryptologie