Cryptographie!
Le plan de la partie : méthodes historiques de cryptographie >

Le chiffre affine

Principe

  Le chiffre affine est une variante du chiffre de César, très pratique à mettre en oeuvre sur un ordinateur car il se réduit à des calculs sur des nombres entiers. On commence par remplacer chaque lettre par son ordre dans l'alphabet, auquel, pour des raisons techniques, on enlève 1 : A devient 0, B devient 1,..., Z devient 25. On choisit ensuite deux nombres entiers $a$ et $b$ qui sont la clé de chiffrement. Le nombre $x$ est alors codé par $y=ax+b$. Ce nombre n'étant pas forcément compris entre 0 et 25, on prend son reste $r$ dans la division par 26. Et ce nombre $r$ est à son tour remplacé par la lettre qui lui correspond.

  Ainsi, dans le chiffre affine, une lettre est toujours remplacée par la même lettre : il s'agit bien d'un chiffrement par substitution mono-alphabétique.

Exemple

  On souhaite coder le mot ELECTION avec le choix a=3, b=5.

Message initial E L E C T I O N
Étape 1 : en nombres 4 11 4 2 19 8 14 13
Étape 2 : après chiffrement 17 38 17 11 62 29 47 44
Étape 3 : réduction modulo 26 17 12 17 11 10 3 21 18
Message chiffré R M R L K D V S

  • Étape 1 : On remplace les lettres par leur nombre associé : 4,11,4,2,19,8,14,13.
  • Étape 2 : On calcule pour chaque nombre $ax+b$ : Par exemple, pour le premier nombre x1=4, on obtient y1=17. De même, y2=38, y3=17, y4=11, y5=62, y6=29, y7=47, y8=44.
  • Étape 3 : On prend les restes dans la division par 26, et on trouve : z1=17, z2=12, z3=17, z4=11, z5=10, z6=3, z7=21, z8=18.
  • Étape 4 : On retranscrit en lettres, remplaçant 17 par R, etc… On trouve RMRLK DVS.
  Toutes les valeurs de $a$ ne sont pas autorisés pour le chiffrement affine. Imaginons en effet que $a=2$ et $b=3$. Alors,
  • la lettre A est remplacée par 0, chiffrée en 2*0+3=3, c'est-à-dire que A est chiffrée par D.
  • la lettre N est remplacée par 13, chiffrée en 2*13+3=29, dont le reste dans la division par 26 est 3 : N est également remplacé par D.
  Ainsi, la valeur a=2 ne convient pas, car deux lettres sont chiffrées de la même façon, et si on obtient un D dans le message chiffré, on ne pourra pas savoir s'il correspond à un A ou à un N.

  Avec un peu d'arithmétique, et notamment l'aide du théorème de Bezout, on peut prouver que a convient s'il n'est pas divisible par 2 ou par 13. On peut choisir en revanche pour b n'importe quelle valeur.
Déchiffrement
  Pour déchiffrer un message, il faut procéder de la même façon. On commence par transcrire le message en nombres. Pour chaque nombre, on doit inverser la relation $y=ax+b$ (ici, on connait $y$ et on doit retrouver $x$). On a envie de poser $x=\frac1a y-\frac ba$. C'est presque cela, sauf que l'on fait de l'arithmétique modulo 26. Ce qui remplace $\frac 1a$, c'est l'inverse de $a$ modulo 26, autrement dit un entier $a'$ tel que, lorsqu'on fait le produit $aa'$, on trouve un entier de la forme $1+26k$. On sait qu'un tel entier existe dès que la condition précédente (2 ne divise pas a, 13 ne divise pas a) est vérifiée. Par exemple, pour $a=3$, on peut choisir $a'=9$ car 9×3=1+26.

  Cette valeur de a déterminée, on a alors $x=a'y-a'b$, qu'on retranscrit en une lettre comme pour l'algorithme de chiffrement.
En pratique

  Chiffrons donc nos messages par le chiffre affine :

Message clair
Clé a= b=
     
Message codé

Consulter aussi