Chiffrer avec une fonction affine : tout se joue sur l’inverse modulaire

Numérotons les lettres de l’alphabet de 0 pour A à 25 pour Z, et chiffrons un message en remplaçant chaque lettre de rang x par ax + b, calculé modulo 26. Le procédé s’appelle le chiffrement affine. Il est élémentaire, et il pose une question qui ne l’est pas : quels couples de coefficients produisent un chiffrement déchiffrable ?

La réponse mobilise tout ce fil d’arithmétique : le PGCD de l’algorithme d’Euclide, et surtout l’identité de Bézout, qui fournit la clé de déchiffrement au sens propre.

1. Un chiffrement qui perd de l’information

Essayons $a=13$ et $b=4$ , c’est-à-dire $f(x)=13x+4$ . La lettre A, de rang $0$ , devient $4$ , soit E. La lettre C, de rang $2$ , devient $30$ , soit $4$ modulo $26$ : E encore. Et E, de rang $4$ , donne $56=2\times 26+4$ : E toujours.

Toutes les lettres de rang pair sont chiffrées en E, toutes celles de rang impair en R. Le message chiffré ne contient plus que deux lettres : il est illisible pour son destinataire légitime autant que pour un tiers. Le chiffrement a détruit le message.

Ce qui a échoué n’est pas le secret, c’est l’injectivité. Pour que le destinataire retrouve le texte clair, l’application

$\displaystyle f:\mathbb{Z}/26\mathbb{Z}\rightarrow\mathbb{Z}/26\mathbb{Z},\quad x\mapsto ax+b$

doit être une bijection. L’ensemble de départ et l’ensemble d’arrivée étant finis et de même cardinal, il revient au même d’exiger l’injectivité ou la surjectivité.

2. La condition

Proposition. L’application $x\mapsto ax+b$ de $\mathbb{Z}/26\mathbb{Z}$ dans lui-même est une bijection si et seulement si $\mathrm{pgcd}(a,26)=1$ .

Le paramètre $b$ n’intervient pas : une translation est toujours bijective. Tout se joue sur $a$ .

Preuve. Supposons d’abord $\mathrm{pgcd}(a,26)=1$ . D’après l’identité de Bézout, il existe deux entiers $u$ et $v$ tels que $au+26v=1$ , donc $au\equiv 1\,[\mathrm{mod}\,26]$ . Posons alors

$\displaystyle g(y)=u(y-b).$

On vérifie $g(f(x))=u(ax+b-b)=uax\equiv x$ , et de même $f(g(y))\equiv y$ . L’application $f$ admet donc une réciproque : elle est bijective.

Réciproquement, supposons $d=\mathrm{pgcd}(a,26)>1$ . Posons $k=\dfrac{26}{d}$ , qui est un entier vérifiant $0<k<26$ . Alors

$\displaystyle ak=\frac{a}{d}\times 26\equiv 0\,[\mathrm{mod}\,26],$

puisque $\dfrac{a}{d}$ est entier. Par conséquent $f(k)=ak+b\equiv b=f(0)$ , avec $k\neq 0$ : deux lettres distinctes ont la même image, et $f$ n’est pas injective. $\quad\Box$

Comme $26=2\times 13$ , les valeurs interdites de $a$ sont les multiples de $2$ et ceux de $13$ . Il reste douze valeurs licites : $1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25$ . Avec vingt-six choix pour $b$ , cela fait $12\times 26=312$ clés — assez peu pour qu’un ordinateur les épuise instantanément, ce qui situe la solidité du procédé.

3. Déchiffrer, c’est inverser $a$

La preuve a livré la méthode : la clé de déchiffrement est l’entier $u$ de l’identité de Bézout, appelé inverse de $a$ modulo $26$ . Prenons $a=7$ et $b=3$ , et déroulons l’algorithme d’Euclide étendu sur $26$ et $7$ :

$\displaystyle 26=3\times 7+5, \qquad 7=1\times 5+2, \qquad 5=2\times 2+1.$

Le dernier reste non nul vaut $1$ : les deux nombres sont bien premiers entre eux. En remontant les égalités :

$\displaystyle 1=5-2\times 2=5-2\times(7-5)=3\times 5-2\times 7=3\times(26-3\times 7)-2\times 7,$

soit $1=3\times 26-11\times 7$ . Ainsi $-11\times 7\equiv 1\,[\mathrm{mod}\,26]$ , et l’inverse de $7$ est $-11$ , c’est-à-dire $15$ modulo $26$ . Vérification : $7\times 15=105=4\times 26+1$ .

Les deux fonctions sont donc

$\displaystyle f(x)=7x+3$

$g(y)=15(y-3)=15y-45\equiv 15y+7\,[\mathrm{mod}\,26].$

À l’essai : M a pour rang $12$ , et $f(12)=87=3\times 26+9$ , soit la lettre de rang $9$ , J. Dans l’autre sens, $g(9)=15\times 9+7=142=5\times 26+12$ : on retrouve $12$ , donc M. La fonction de déchiffrement est elle aussi affine — c’est ce qui rend le procédé symétrique et commode.

4. Ce que l’exemple enseigne au-delà du chiffrement

La condition $\mathrm{pgcd}(a,26)=1$ ne concerne pas la cryptographie : elle dit quels éléments de $\mathbb{Z}/26\mathbb{Z}$ sont inversibles pour la multiplication. Le chiffrement affine n’est qu’une mise en scène de cette question.

Le raisonnement vaut pour tout module $n$ : les inversibles de $\mathbb{Z}/n\mathbb{Z}$ sont exactement les classes des entiers premiers avec $n$ , et leur nombre est noté $\varphi(n)$ , l’indicatrice d’Euler. Deux conséquences immédiates. Lorsque $n$ est premier, tout élément non nul est inversible : $\mathbb{Z}/n\mathbb{Z}$ est alors un corps. Lorsque $n$ ne l’est pas, il existe des diviseurs de zéro — dans $\mathbb{Z}/26\mathbb{Z}$ , $2\times 13=26\equiv 0$ sans qu’aucun des deux facteurs soit nul.

Un alphabet de vingt-cinq lettres, ou de vingt-neuf, se comporterait tout autrement : $29$ étant premier, les vingt-huit valeurs non nulles de $a$ conviendraient. Le nombre de clés d’un chiffrement affine dépend donc de l’arithmétique de la taille de l’alphabet, ce qui est une façon inattendue de rencontrer les nombres premiers.

C’est aussi le mécanisme sur lequel repose le chiffrement RSA, à ceci près que le module y est le produit de deux très grands nombres premiers, et que l’inverse modulaire s’y calcule par le même algorithme d’Euclide étendu, sur des nombres de plusieurs centaines de chiffres.

Ce fil d’arithmétique s’achève ici. Parti d’un calcul de PGCD sans factorisation, il aboutit à la structure multiplicative des anneaux $\mathbb{Z}/n\mathbb{Z}$ — sans avoir jamais eu besoin d’autre chose que de la division euclidienne.

Les congruences, l’inverse modulaire et leurs applications au chiffrement sont traités au chapitre 4 de Mathématiques en terminales scientifiques, Tome 2.

Formalis Mathematica

Rigueur et formalisme au cœur de l’apprentissage et de l’enseignement des mathématiques

Chiffrer avec une fonction affine : tout se joue sur l’inverse modulaire

1. Un chiffrement qui perd de l’information

2. La condition

3. Déchiffrer, c’est inverser $a$

4. Ce que l’exemple enseigne au-delà du chiffrement

Votre commentaire Annuler la réponse.

1. Un chiffrement qui perd de l’information

2. La condition

3. Déchiffrer, c’est inverser

4. Ce que l’exemple enseigne au-delà du chiffrement

Partagez :

Similaire

Votre commentaire Annuler la réponse.

3. Déchiffrer, c’est inverser $a$