Exercice 7 / 9Facile
Chiffrement de César
À toi
Les lettres sont numérotées de A = 0 à Z = 25.
- Chiffre le mot SERVEUR avec la clé k = 5.
- Déchiffre ZSXQ, chiffré avec la clé k = 10.
- Dans un message chiffré par César, la lettre E est devenue R. Quelle est la clé ?
Arithmétique modulaire et chiffrement
La division euclidienne
Pour a entier naturel et b entier naturel non nul, il existe un unique couple (q, r) tel que a = b × q + r avec 0 ≤ r < b. À la calculatrice, q est la partie entière de a ÷ b, et r = a − b × q (jamais la partie décimale). Exemple : 2 026 = 7 × 289 + 3, avec 0 ≤ 3 < 7. En Python : 2026 // 7 donne 289, 2026 % 7 donne 3.
Nombres premiers et décomposition
Pour savoir si n est premier, on teste les nombres premiers jusqu'à √n. Pour décomposer n, on le divise par le plus petit nombre premier possible, et on recommence avec le quotient jusqu'à 1 :
| Nombre | 360 | 180 | 90 | 45 | 15 | 5 | 1 |
|---|---|---|---|---|---|---|---|
| Divisé par | 2 | 2 | 2 | 3 | 3 | 5 |
360 = 2³ × 3² × 5. Un diviseur de 360 s'écrit 2ᵃ × 3ᵇ × 5ᶜ avec a de 0 à 3, b de 0 à 2, c de 0 à 1 : 360 a 4 × 3 × 2 = 24 diviseurs.
Le PGCD par l'algorithme d'Euclide
Si a = b × q + r, alors PGCD(a, b) = PGCD(b, r). On divise, puis le diviseur devient le dividende et le reste devient le diviseur, jusqu'à un reste nul. Le PGCD est le dernier reste non nul.
| a | b | Division euclidienne | Reste |
|---|---|---|---|
| 252 | 180 | 252 = 180 × 1 + 72 | 72 |
| 180 | 72 | 180 = 72 × 2 + 36 | 36 |
| 72 | 36 | 72 = 36 × 2 + 0 | 0 |
PGCD(252, 180) = 36. Deux entiers sont premiers entre eux quand leur PGCD vaut 1.
Les congruences
a ≡ b [n] (« a est congru à b modulo n ») si a − b est un multiple de n, c'est-à-dire si a et b ont le même reste dans la division par n. On peut additionner, multiplier et élever à une puissance des congruences : remplace chaque nombre par son reste le plus tôt possible.
Pour une grande puissance, on cherche une puissance qui vaut 1. Modulo 5 : 2¹ ≡ 2, 2² ≡ 4, 2³ ≡ 3, 2⁴ ≡ 1. Comme 2 026 = 4 × 506 + 2, 2²⁰²⁶ = (2⁴)⁵⁰⁶ × 2² ≡ 4 [5]. Les jours de la semaine reviennent tous les 7 jours : ils se comptent modulo 7.
L'inverse modulo n
a' est l'inverse de a modulo n si a × a' ≡ 1 [n]. Il existe si et seulement si PGCD(a, n) = 1. Pour le trouver modulo 26, cherche parmi 27, 53, 79, 105… (les nombres 1 + 26k) le premier divisible par a : pour a = 7, 105 = 7 × 15, l'inverse de 7 est 15.
Pour résoudre 7x ≡ 3 [26], on multiplie par l'inverse : x ≡ 15 × 3 = 45 ≡ 19 [26]. On ne divise jamais une congruence.
César et chiffrement affine
| A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
- César de clé k : y ≡ x + k [26] ; on déchiffre avec x ≡ y − k [26]. Après Z, on revient à A.
- Affine de clé (a, b) : y ≡ ax + b [26], avec PGCD(a, 26) = 1. On déchiffre avec x ≡ a'(y − b) [26], où a' est l'inverse de a.
Exemple avec la clé (7, 3) : R (17) donne 7 × 17 + 3 = 122 = 4 × 26 + 18, soit S. Pour déchiffrer, x ≡ 15(y − 3) = 15y − 45 ≡ 15y + 7 [26].
Casser un chiffrement affine : deux lettres devinées donnent deux congruences. Si E (4) est codé F (5) et T (19) est codé G (6) : 4a + b ≡ 5 et 19a + b ≡ 6. En soustrayant, 15a ≡ 1 [26], donc a = 7 (l'inverse de 15), puis b ≡ 5 − 28 = −23 ≡ 3 [26].
Tu es bloqué ?
Ouvre les indices un par un, le corrigé en dernier.
Indice 1
Numérote les lettres de A = 0 à Z = 25 (le tableau est dans le rappel).
Indice 2
Chiffrer : y ≡ x + k [26]. Déchiffrer : x ≡ y − k [26]. Après Z, on revient à A.
Indice 3
V vaut 21 : 21 + 5 = 26 ≡ 0, c'est A.
Voir le corrigé
Connecte-toi pour voir le corrigé
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données
Pour revoir la notion : chapitre 8 du cours Arithmétique, Congruences modulo n : définition et calculs.
Tes réponses
Connecte-toi pour faire cet exercice
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données