On numérote les lettres de l'alphabet de $A = 0$ à $Z = 25$, comme dans le tableau du cours. On chiffre une lettre de rang $x$ par la lettre de rang $y$, où $y$ est le reste de la division euclidienne de $9x + 4$ par $26$.
-
Chiffrer le mot CODE.
-
a) À l'aide de l'algorithme d'Euclide appliqué à $26$ et $9$, déterminer deux entiers $u$ et $v$ tels que $9u + 26v = 1$. En déduire un inverse de $9$ modulo $26$.
b) Montrer que, pour tous entiers $x$ et $y$ : $y \equiv 9x + 4 \;[26] \iff x \equiv 3y + 14 \;[26]$.
c) Déchiffrer le message JBYIO.
-
On remplace la clé par $y \equiv 13x + 4 \;[26]$. Montrer que les lettres A et C sont codées par la même lettre. Que peut-on en conclure ?
-
Combien d'entiers $a$ compris entre $0$ et $25$ permettent-ils un chiffrement $y \equiv ax + 4 \;[26]$ déchiffrable ?
Pour chaque lettre, calculer $9x + 4$ puis son reste modulo $26$.
L'algorithme d'Euclide s'arrête après trois divisions ; remonter ensuite pour exprimer $1$.
Dans le sens direct, multiplier par l'inverse de $9$ ; dans le sens réciproque, multiplier par $9$. Penser à $-12 \equiv 14 \;[26]$.
Pour la question 4, utiliser la condition de déchiffrement du cours et la décomposition $26 = 2 \times 13$.
1. C, O, D, E ont pour rangs $2$, $14$, $3$, $4$.
- $9 \times 2 + 4 = 22$, donc $y = 22$ : W.
- $9 \times 14 + 4 = 130 = 5 \times 26$, donc $y = 0$ : A.
- $9 \times 3 + 4 = 31 = 26 + 5$, donc $y = 5$ : F.
- $9 \times 4 + 4 = 40 = 26 + 14$, donc $y = 14$ : O.
CODE est chiffré WAFO.
2. a) Algorithme d'Euclide : $$\begin{aligned} 26 &= 2 \times 9 + 8 \\ 9 &= 1 \times 8 + 1 \\ 8 &= 8 \times 1 + 0 \end{aligned}$$ Donc $\mathrm{PGCD}(26, 9) = 1$. On remonte : $1 = 9 - 8 = 9 - (26 - 2 \times 9) = 3 \times 9 - 26$. Ainsi $u = 3$ et $v = -1$. Vérification : $27 - 26 = 1$.
Par conséquent $9 \times 3 = 27 \equiv 1 \;[26]$ : $3$ est un inverse de $9$ modulo $26$.
b) Supposons $y \equiv 9x + 4 \;[26]$. En multipliant par $3$ : $3y \equiv 27x + 12 \equiv x + 12 \;[26]$, donc $x \equiv 3y - 12 \;[26]$. Comme $-12 = 14 - 26$, $x \equiv 3y + 14 \;[26]$.
Réciproquement, supposons $x \equiv 3y + 14 \;[26]$. En multipliant par $9$ : $9x \equiv 27y + 126 \;[26]$. Or $27 \equiv 1$ et $126 = 4 \times 26 + 22 \equiv 22 \;[26]$, donc $9x \equiv y + 22 \;[26]$, soit $y \equiv 9x - 22 \equiv 9x + 4 \;[26]$.
L'équivalence est démontrée.
c) On calcule le reste de $3y + 14$ modulo $26$ pour chaque lettre :
| Lettre codée | J | B | Y | I | O |
|---|---|---|---|---|---|
| $y$ | 9 | 1 | 24 | 8 | 14 |
| $3y + 14$ | 41 | 17 | 86 | 38 | 56 |
| $x$ | 15 | 17 | 8 | 12 | 4 |
| Lettre claire | P | R | I | M | E |
(En effet $41 = 26 + 15$, $86 = 3 \times 26 + 8$, $38 = 26 + 12$, $56 = 2 \times 26 + 4$.) Le message déchiffré est PRIME.
3. A : $13 \times 0 + 4 = 4$, codé E. C : $13 \times 2 + 4 = 30 = 26 + 4$, codé E aussi. Deux lettres distinctes ont le même code : à la réception de E, on ne peut pas savoir s'il s'agit de A ou de C. Ce chiffrement n'est pas déchiffrable, ce qui est cohérent avec $\mathrm{PGCD}(13, 26) = 13 \neq 1$.
4. D'après le cours, le chiffrement est déchiffrable si et seulement si $\mathrm{PGCD}(a, 26) = 1$. Comme $26 = 2 \times 13$ avec $2$ et $13$ premiers, cela équivaut à : $a$ impair et $a \neq 13$. Les valeurs sont $1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25$ : il y en a $12$.
WAFO ; 3 × 9 − 26 = 1, inverse 3 ; message PRIME ; clé 13 non déchiffrable ; 12 valeurs de a