(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 chiffrement 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
On a vu dans la question 2.4 que le chiffrement affine présente une faille de sécurité, liée au peu de clés de chiffrement valides existantes. Archibald et Balthazar décident d'appliquer une variante permettant de contourner cet écueil en appliquant le chiffrement de Vigenère, où le codage d'une lettre dépend de sa place dans le texte.
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 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
A | 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 | |
B | 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 | A | |
C | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | |
D | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | |
E | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | |
F | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | |
G | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | |
H | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | |
I | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | |
J | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | |
K | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | |
L | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | |
M | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | |
N | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | |
O | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | |
P | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | |
Q | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | |
R | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | |
S | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | |
T | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | |
U | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | |
V | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | |
W | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | |
X | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | |
Y | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | |
Z | Z | 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 |
Texte à coder | V | I | V | E | V | I | G | E | N | E | R | E | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Clé répétée | M | O | T | U | S | M | O | T | U | S | M | O | ||
Texte codé | H | W | O | Y | N | U | U | X | H | ... | ... | ... |
3.1. Recopier et compléter le codage du texte "VIVE VIGENERE" à l'aide de la clé "MOTUS".
3.2. Expliquer comment décoder un texte connaissant la clé, et appliquer la méthode pour décoder "NFTPAEGBGG" avec la clé "MOTUS".
3.3. Si on note $x$ le rang de la lettre à coder, $c$ le rang de la lettre de la clé à utiliser et $y$ le rang de la lettre codée, on a $y \equiv x+c[26]$.
$\;\;\;\;\;$La fonction Python codage_Vigenere donnée ci-dessous utilise cette relation.
$\;\;\;\;\;$Effectuer un appel à cette fonction pour vérifier le résultat de la question 3.1.
#Mise en mémoire de l'alphabet
Alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def codage_Vigenere(message,cle):
"""
Fonction effectuant le codage de Vigenere du message avec la cle
"""
l_cle=len(cle) # longueur de la clé
j=0 # rang de la lettre de la clé utilisée
code=""
for caractere in message: # on parcourt les caractères du message à coder
if caractere in Alphabet: # si c'est une lettre de l'alphabet:
x = Alphabet.index(caractere) # on stocke dans x le rang de cette lettre
c = Alphabet.index(cle[j]) # on stocke dans c le rang de la lettre de la clé
y = (x+c) %26 # on calcule le rang y de la lettre codée correspondante
code += Alphabet[y] # on complète le code avec la lettre de rang y
j = (j+1) %l_cle # on avance d'un rang dans la clé
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_Vigenere
3.4. On reprend les notations de la question 3.3.
$\;\;\;\;\;$a. Exprimer $x$ en fonction de $y$, modulo $26$.
$\;\;\;\;\;$b. Adapter la fonction Python précédente pour écrire une fonction decodage_Vigenere.
# Ecrire ici la fonction decodage_Vigenere
$\;\;\;\;\;$c. Effectuer un appel à cette fonction pour vérifier le résultat de la question 3.2.
# Effectuer ici l'appel à la fonction decodage_Vigenere
3.5. Convenir avec une autre personne d'un mot clé.
$\;\;\;\;\;$Chacun code alors un message à l'aide de la fonction Python codage_Vigenere en utilisant cette clé, et le donne à l'autre.
$\;\;\;\;\;$Enfin, chacun décode le message reçu à l'aide de la fonction Python decodage_Vigenere.
# Utiliser cette zone pour le codage du message
# Utiliser cette zone pour le décodage du message
(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/