(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/
Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.
Archibald et Balthazar, deux détectives maladroits, souhaitent coder les messages qu'ils doivent échanger afin qu'ils ne soient pas déchiffrables s'ils tombaient en de mauvaises mains.
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 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Ils décident ensuite de coder leurs messages avec le chiffrement affine suivant :
Si la lettre à coder correspond à $x$ (avec $0 \leqslant x \leqslant 25$), alors on calcule le reste de la division euclidienne de $11x+8$ par $26$, noté $y$.
Comme $0 \leqslant y \leqslant 25$ , on peut associer une lettre à cette valeur $y$ : Cette lettre est le codage de la lettre initiale.
Le couple $(11;8)$ est la clé de chiffrement.
1.1. Archibald souhaite envoyer le message suivant à Balthazar : "C EST FACILE CE CODE". Quel message va-t-il lui envoyer?
1.2. On donne ci-dessous la fonction Python codage_affine, qui permet d'effectuer un chiffrement affine.
$\;\;\;\;\;\;$Effectuer un appel à cette fonction permettant de vérifier la réponse à la question précédente.
#Mise en mémoire de l'alphabet
Alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def codage_affine(a,b,message):
"""
Fonction effectuant le codage affine du message
avec la clé de chiffrement (a,b)
"""
code=""
for caractere in message: # pour chaque caractère du message
if caractere in Alphabet: # si ce caractère est dans l'alphabet, alors:
x = Alphabet.index(caractere) # on récupère l'entier correspondant à cette lettre
y = (a*x+b)%26 # on calcule y
code += Alphabet[y] # on complète le code avec la lettre correspondant à y
else: # sinon:
code += " " # on complète le code avec un espace
return code # on renvoie le message codé
# Effectuer ici l'appel à la fonction codage_affine
1.3. Archibald reçoit la réponse de Balthazar: "DA VA EGKRNAVPY RIY".
$\;\;\;\;\;\;$Il se rend alors compte qu'ils n'ont pas convenu de méthode pour le déchiffrement... et se demande comment il va décoder ce message.
$\;\;\;\;\;\;$On cherche donc à déterminer $x$ connaissant $y$.
$\;\;\;$a. Démontrer que s'il existe $u$ tel que $0 \leqslant u \leqslant 25$ et $11u \equiv 1[26]$ , alors $x \equiv u(y-8)[26]$.
$\;\;\;\;\;\;$Ainsi, une telle valeur de $u$ permettrait de décoder le message.
$\;\;\;$b. L'équation $11u+26v=1$ d'inconnues entières $u$ et $v$ a-t-elle des solutions ?
$\;\;\;\;\;\;$Si oui, déterminer une de ces solutions.
$\;\;\;$c. En déduire que $x \equiv 19y+4[26]$, puis déchiffrer le message que Balthazar a envoyé à Archibald
$\;\;\;\;\;\;$Ainsi, le couple $(19;4)$ est la clé de déchiffrement.
$\;\;\;$d. A l'aide d'un appel à la fonction Python codage_affine, vérifier le décodage du message, réalisé dans la question précédente.
# Effectuer ici l'appel à la fonction codage_affine
2.1. Rassurés de voir que leur méthode fonctionne, Archibald et Balthazar décident à présent d'utiliser la clé de chiffrement $(4;3)$.
$\;\;\;\;\;\;$Archibald souhaite envoyer le message "CA NE MARCHE PAS" à Balthazar.
$\;\;\;\;\;\;$a. A l'aide de la fonction Python codage_affine, déterminer le message qu'Archibald va envoyer.
# Effectuer ici l'appel à la fonction codage_affine
$\;\;\;\;\;\;$b. Balthazar parviendra-t-il facilement à décoder ce message ? Pourquoi ?
2.2. Démontrer que si $(a_1;b_1)$ et $(a_2;b_2)$ sont tels que $a_1 \equiv a_2[26]$ et $b_1 \equiv b_2[26]$ , alors les codes obtenus avec ces deux clés sont les mêmes.
$\;\;\;\;\;\;$On peut donc choisir des entiers naturels $a$ et $b$ tels que $1 \leqslant a \leqslant 25$ et $0 \leqslant b \leqslant 25$.
2.3. On se place dans le cas d’une clé de chiffrement $(a;b)$ vérifiant $1 \leqslant a \leqslant 25$ et $0 \leqslant b \leqslant 25$.
$\;\;\;\;\;\;$On note $x$ et $x'$ deux entiers compris entre $0$ et $25$, et on note $y$ et $y'$ leurs codes avec la clé $(a;b)$.
$\;\;\;\;\;\;$b. Justifier que si on choisit $a$ premier avec $26$, alors le décodage de tout message est unique.
$\;\;\;\;\;\;$Pour la suite, on admet que la réciproque est vraie :
$\;\;\;\;\;\;$Le décodage de n'importe quel message se fait de façon unique si et seulement si $a$ est premier avec $26$.
2.4. On dit qu'une clé de chiffrement est valide s'il y a unicité du décodage de n'importe quel message.
$\;\;\;\;\;\;$Combien de clés de chiffrements peut-on créer au maximum ?
$\;\;\;\;\;\;$Que peut-on en conclure concernant la sûreté de la technique de chiffrement affine ?
2.5. Dans cette question, on souhaite automatiser la recherche de la clé de déchiffrement associée à une clé de chiffrement initiale valide $(a;b)$.
$\;\;\;\;\;$(c'est à dire telle que $a$ est premier avec $26$).
$\;\;\;\;\;\;$a. On suppose qu'on a déterminé $u$ qui vérifie $1 \leqslant u \leqslant 25$ et $au \equiv 1[26]$.
$\;\;\;\;\;\;\;\;\;$On pose alors $v$ le reste de la division euclidienne de $-bu$ par $26$.
$\;\;\;\;\;\;\;\;\;$Vérifier que $(u;v)$ est la clé de déchiffrement cherchée.
$\;\;\;\;\;\;$b. Ecrire une fonction Python inverse_cle qui reçoit une clé de chiffrement $(a;b)$ et renvoie la clé de déchiffrement associée $(u;v)$.
$\;\;\;\;\;\;\;\;\;$On pourra, à l'aide d'une boucle, tester les candidats pour $u$ en partant de $1$ afin d'obtenir une valeur vérifiant
$au \equiv 1[26]$.
# Ecrire ici la fonction inverse_cle
$\;\;\;\;\;\;$c. Convenir avec une autre personne d'une clé de chiffrage valide.
$\;\;\;\;\;\;\;\;\;$Chacun code alors un message à l'aide de la fonction Python codage_affine en utilisant cette clé, et le donne à l'autre.
$\;\;\;\;\;\;\;\;\;$Enfin, chacun décode le message reçu (on peut à nouveau utiliser la fonction Python codage_affine).
#Utiliser cette zone pour coder le message à envoyer
#Utiliser cette zone pour déterminer la clé de déchiffrement
#Utiliser cette zone pour décoder le message reçu
(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/