Un chiffrement affine modulo 26
On numérote les lettres de l'alphabet de à :
| A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
Une clé est un couple d'entiers tels que et . Pour chiffrer la lettre de numéro , on calcule le reste de dans la division par . La lettre chiffrée est celle de numéro .
- 1.
Chiffre le mot RESTE avec la clé .
- 2.
Montre que est inversible dans et détermine son inverse. Déduis-en une formule de déchiffrement : des entiers et , entre et , tels que, pour tous entiers et , équivaille à .
- 3.
On a reçu le message UJFWCP, chiffré avec la clé . Déchiffre-le.
- 4.
Avec la clé , montre que A et C sont chiffrées par la même lettre. Plus généralement, montre qu'avec une clé , deux lettres distinctes ont toujours des chiffrés distincts si et seulement si . Combien y a-t-il de telles clés ?

Pour chaque lettre, calcule , puis son reste dans la division par . Range les calculs dans un tableau.
Un couple de Bézout pour et donne l'inverse. Multiplie ensuite la congruence de chiffrement par cet inverse, sans oublier le sens réciproque.
Applique à chaque lettre reçue la formule de la question 2, puis réduis modulo .
Si , cherche un entier entre et tel que . Si , utilise l'inverse de , comme à la question 2.
| lettre | R | E | S | T | E |
|---|---|---|---|---|---|
| reste | |||||
| lettre chiffrée | C | P | R | G | P |
Par exemple, pour R : , avec , d'où la lettre C. Le mot chiffré est CPRGP. Les deux E donnent la même lettre P : un chiffrement lettre par lettre conserve les répétitions.
Algorithme d'Euclide, restes encadrés :
- , avec ;
- , avec ;
- , avec ;
- , avec ;
- .
Donc , et est inversible dans . En remontant : Vérification : et , donc . Ainsi : l'inverse de est .
Déchiffrement. Supposons . En multipliant par : . Or et , donc . Ainsi , et comme , .
Réciproquement, si , alors . Comme et , on obtient . La formule de déchiffrement est : et .
| lettre reçue | U | J | F | W | C | P |
|---|---|---|---|---|---|---|
| reste | ||||||
| lettre claire | N | O | M | B | R | E |
Le message clair est NOMBRE. Contrôle sur la troisième lettre : et , donc M est bien chiffrée en F.
Avec : A donne , et C donne , avec . Les deux lettres sont chiffrées en F.
Si . Posons , entier tel que . Comme , , donc . Les lettres de numéros et , distinctes, ont le même chiffré : le reste de .
Si . La classe a un inverse dans . Si deux lettres de numéros et ont le même chiffré, alors . En multipliant par , . Comme et , on a .
Dénombrement. Comme , les entiers de à premiers avec sont les impairs différents de : . Cela fait valeurs de , et valeurs de : il y a clés.
