Terminale › Arithmétique › Condition de déchiffrement

Condition de déchiffrement : énoncé (Maths expertes)

Propriété

Condition de déchiffrement

Le chiffrement affine de clé $(a, b)$ permet de retrouver chaque lettre (deux lettres distinctes sont codées différemment) si et seulement si $a$ et $26$ sont premiers entre eux.

Dans ce cas, si $a'$ est un inverse de $a$ modulo $26$, le déchiffrement est donné par $$x \equiv a'(y - b) \;[26].$$

Démonstration : Condition de déchiffrement

Démonstration

Preuve

Si $\mathrm{PGCD}(a, 26) = 1$, il existe $a'$ tel que $aa' \equiv 1 \;[26]$. Si $y \equiv ax + b \;[26]$, alors $a'(y - b) \equiv a'ax \equiv x \;[26]$. Comme $0 \leqslant x \leqslant 25$, $x$ est le reste de $a'(y-b)$ modulo $26$ : il est entièrement déterminé par $y$.
Si $d = \mathrm{PGCD}(a, 26) \geqslant 2$, posons $x_1 = 26/d$, avec $1 \leqslant x_1 \leqslant 13$. Alors $ax_1 = 26 \times \frac{a}{d} \equiv 0 \;[26]$, donc les lettres de rangs $0$ et $x_1$ sont toutes deux codées par la lettre de rang $b$ modulo $26$ : le déchiffrement est impossible.

Exemple

Chiffrer et déchiffrer avec la clé (5 ; 3)

$\mathrm{PGCD}(5, 26) = 1$, la clé est valable. On chiffre le mot MATH avec $y \equiv 5x + 3 \;[26]$ :

Lettre	M	A	T	H
$x$	12	0	19	7
$5x + 3$	63	3	98	38
$y$	11	3	20	12
Lettre codée	L	D	U	M

MATH est codé LDUM.

Pour déchiffrer : $5 \times 21 = 105 = 4 \times 26 + 1$, donc $21$ est un inverse de $5$ modulo $26$. On utilise $x \equiv 21(y - 3) \;[26]$. Pour L ($y = 11$) : $21 \times 8 = 168 = 6 \times 26 + 12$, donc $x = 12$, soit M. Pour U ($y = 20$) : $21 \times 17 = 357 = 13 \times 26 + 19$, donc $x = 19$, soit T.

S’entraîner

Dans le cours

Arithmétique : Condition de déchiffrement