Chiffre affine

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 aux chiffre de Hill. Il s'agit d'un code simple à appréhender mais aussi un des plus faciles à casser.

Principe[modifier | modifier le code]

Chiffrement[modifier | modifier le code]

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 ax + b (soit (ax + b) \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[modifier | modifier le code]

Si le coefficient a vaut 1, alors le codage affine correspond au chiffre de César.

Déchiffrement[modifier | modifier le code]

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[modifier | modifier le code]

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 12 \times 26 = 312 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[modifier | modifier le code]

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 ax + b \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[modifier | modifier le code]

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[modifier | modifier le code]

  • Arithmétique en TS, Arithmétique et cryptographie, CRDP d'Auvergne

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]