Chiffre affine

Le chiffre affine est une méthode de cryptographie basée sur un chiffrement par substitution. Il s'agit d'un code simple à appréhender mais aussi un des plus faciles à casser.

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) :

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 ax + b (soit ax + bmod 26).

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.

Déchiffrement

Pour déchiffrer le message, il faut être capable de trouver l'antécédent de y par l'application qui, à un entier x compris entre 0 et 25, associe le reste de ax + b dans la division par 26. Il est facile d'ôter b mais il n'est pas toujours réalisable de simplifier par a. La simplification ne peut s'effectuer que s'il existe un entier a' tel que aa' a pour reste 1 dans la division par 26. C'est-à-dire s'il existe un entier k tel que

aa' = 1 + k26 soit encore a'a − 26k = 1

Le théorème de Bachet-Bézout affirme que l'on ne peut trouver k et a' que lorsque a est premier avec 26. La clef de code doit donc être un couple d'entiers (a, b) dans lequel a est premier avec 26.

C'est le cas, dans l'exemple choisi, l'entier a' 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 128^e 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 ax + bmod 95.

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 · ADFGVX • Alberti • Beale • Carré de Polybe • César • Delastelle • Hill • Marie Stuart • Pigpen • Playfair • Polyalphabétique • Scytale • Substitution • Templiers • Transposition • Trithémius • Vigenère
Cryptanalyse	Analyse fréquentielle • Indice de coïncidence • Cryptanalyse du chiffre de Vigenère
Autre	Histoire de la cryptologie

• Portail de la cryptologie