{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "![En tête general](img/En_tete_general.png)\n", "\n", "\n", "*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*\n", "\n", " Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Chiffrement affine et chiffrement de Vigenère \n", "\n", "### Activité sur le chiffrement n°1\n", "##### (prérecquis: congruences, théorème de Bézout, théorème de Gauss, équations diophantiennes)\n", "\n", "![Illustration_detectives](img/Chiffrement_affine.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Sommaire\n", "\n", "1. Principe du chiffrement affine
\n", "2. Choisir une clé de chiffrement affine
\n", "3. Chiffrement de Vigenère
\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Principe du chiffrement affine" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.
\n", "
\n", "Ils commencent par associer chaque lettre de l'alphabet à un nombre entier comme l'indique le tableau ci-dessous.\n", "
\n", "\n", "| 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 | \n", "|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|\n", "| 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|\n", "\n", "Ils décident ensuite de coder leurs messages avec le chiffrement affine suivant :
\n", "\n", "

\n", "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$.
\n", "Comme $0 \\leqslant y \\leqslant 25$ , on peut associer une lettre à cette valeur $y$ : Cette lettre est le codage de la lettre initiale.
\n", "Le couple $(11;8)$ est la clé de chiffrement.\n", "

\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__1.1. Archibald souhaite envoyer le message suivant à Balthazar : \"C EST FACILE CE CODE\". Quel message va-t-il lui envoyer?__\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__1.2. On donne ci-dessous la fonction Python codage_affine, qui permet d'effectuer un chiffrement affine.__
\n", "$\\;\\;\\;\\;\\;\\;$__Effectuer un appel à cette fonction permettant de vérifier la réponse à la question précédente.__" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Mise en mémoire de l'alphabet\n", "Alphabet=\"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n", "\n", "def codage_affine(a,b,message):\n", " \"\"\"\n", " Fonction effectuant le codage affine du message\n", " avec la clé de chiffrement (a,b)\n", " \"\"\"\n", " code=\"\" \n", " for caractere in message: # pour chaque caractère du message\n", " if caractere in Alphabet: # si ce caractère est dans l'alphabet, alors:\n", " x = Alphabet.index(caractere) # on récupère l'entier correspondant à cette lettre\n", " y = (a*x+b)%26 # on calcule y\n", " code += Alphabet[y] # on complète le code avec la lettre correspondant à y\n", " else: # sinon: \n", " code += \" \" # on complète le code avec un espace\n", " return code # on renvoie le message codé\n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Effectuer ici l'appel à la fonction codage_affine\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__1.3. Archibald reçoit la réponse de Balthazar: \"DA VA EGKRNAVPY RIY\".__
\n", "$\\;\\;\\;\\;\\;\\;$__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.__
\n", "$\\;\\;\\;\\;\\;\\;$__On cherche donc à déterminer $x$ connaissant $y$.__" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;$__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]$.__
\n", "$\\;\\;\\;\\;\\;\\;$Ainsi, une telle valeur de $u$ permettrait de décoder le message.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;$__b. L'équation $11u+26v=1$ d'inconnues entières $u$ et $v$ a-t-elle des solutions ?__
\n", "$\\;\\;\\;\\;\\;\\;$__Si oui, déterminer une de ces solutions.__\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;$__c. En déduire que $x \\equiv 19y+4[26]$, puis déchiffrer le message que Balthazar a envoyé à Archibald__
\n", "$\\;\\;\\;\\;\\;\\;$Ainsi, le couple $(19;4)$ est la clé de déchiffrement.
\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;$__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.__" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Effectuer ici l'appel à la fonction codage_affine\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Choisir une clé de chiffrement affine" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__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)$.__
\n", "$\\;\\;\\;\\;\\;\\;$__Archibald souhaite envoyer le message \"CA NE MARCHE PAS\" à Balthazar.__
\n", "$\\;\\;\\;\\;\\;\\;$__a. A l'aide de la fonction Python codage_affine, déterminer le message qu'Archibald va envoyer.__\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Effectuer ici l'appel à la fonction codage_affine\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;\\;\\;\\;$__b. Balthazar parviendra-t-il facilement à décoder ce message ? Pourquoi ?__
\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__2.2. \tDé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.__
\n", "$\\;\\;\\;\\;\\;\\;$On peut donc choisir des entiers naturels $a$ et $b$ tels que $1 \\leqslant a \\leqslant 25$ et $0 \\leqslant b \\leqslant 25$.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__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$.__
\n", "$\\;\\;\\;\\;\\;\\;$__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)$.__
\n", "
\n", "$\\;\\;\\;\\;\\;\\;$__a. Démontrer que si $y=y'$ alors $a(x-x') \\equiv 0[26]$.__\n", "\n", "\n", "$\\;\\;\\;\\;\\;\\;$__b. Justifier que si on choisit $a$ premier avec $26$, alors le décodage de tout message est unique.__\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;\\;\\;\\;$Pour la suite, on admet que la réciproque est vraie :
\n", "$\\;\\;\\;\\;\\;\\;$Le décodage de n'importe quel message se fait de façon unique si et seulement si $a$ est premier avec $26$.
\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__2.4. On dit qu'une clé de chiffrement est valide s'il y a unicité du décodage de n'importe quel message.__
\n", "$\\;\\;\\;\\;\\;\\;$__Combien de clés de chiffrements peut-on créer au maximum ?__
\n", "$\\;\\;\\;\\;\\;\\;$__Que peut-on en conclure concernant la sûreté de la technique de chiffrement affine ?__\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__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)$.__
\n", "$\\;\\;\\;\\;\\;$__(c'est à dire telle que $a$ est premier avec $26$).__\n", "\n", "$\\;\\;\\;\\;\\;\\;$__a. On suppose qu'on a déterminé $u$ qui vérifie $1 \\leqslant u \\leqslant 25$ et $au \\equiv 1[26]$.__
\n", "$\\;\\;\\;\\;\\;\\;\\;\\;\\;$__On pose alors $v$ le reste de la division euclidienne de $-bu$ par $26$.__
\n", "$\\;\\;\\;\\;\\;\\;\\;\\;\\;$__Vérifier que $(u;v)$ est la clé de déchiffrement cherchée.__\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;\\;\\;\\;$__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)$.__
\n", "$\\;\\;\\;\\;\\;\\;\\;\\;\\;$On pourra, à l'aide d'une boucle, tester les candidats pour $u$ en partant de $1$ afin d'obtenir une valeur vérifiant \n", "$au \\equiv 1[26]$.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ecrire ici la fonction inverse_cle\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;\\;\\;\\;$__c. Convenir avec une autre personne d'une clé de chiffrement valide.__
\n", "$\\;\\;\\;\\;\\;\\;\\;\\;\\;$__Chacun code alors un message à l'aide de la fonction Python codage_affine en utilisant cette clé, et le donne à l'autre.__
\n", "$\\;\\;\\;\\;\\;\\;\\;\\;\\;$__Enfin, chacun décode le message reçu (on peut à nouveau utiliser la fonction Python codage_affine).__" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Utiliser cette zone pour coder le message à envoyer\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Utiliser cette zone pour déterminer la clé de déchiffrement\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Utiliser cette zone pour décoder le message reçu\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Chiffrement de Vigenère" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.
\n", "
\n", "On se munit de la table de Vigenère :\n", "
\n", "\n", "| | | __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__ | \n", "|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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__ | | 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 |\n", "| __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 |\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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "| __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 |\n", "\n", "
\n", "Les personnes qui doivent échanger les messages conviennent d'un mot, d'une phrase ou d'un texte (sans espace), qui constitue la clé du chiffrement de Vigenère.
\n", "Par exemple, si la clé est \"MOTUS\" et que le texte à coder est \"VIVE VIGENERE\", on inscrit en vis-à-vis les lettres de ce texte et les lettres de la clé, répétée si nécessaire. Ensuite on associe à la première lettre V, dont la clé est M, la lettre qui figure dans la colonne V et la ligne M de la table de Vigenère, c'est-à-dire un H.
\n", "\n", "\n", "| Texte à coder | | __V__ | I | V | E | | V | I | G | E | N | E | R | E |\n", "|:--------------|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|\n", "| Clé répétée | | __M__ | O | T | U | | S | M | O | T | U | S | M | O |\n", "| Texte codé | | __H__ | W | O | Y | | N | U | U | X | H |...|...|...|\n", "\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__3.1. Recopier et compléter le codage du texte \"VIVE VIGENERE\" à l'aide de la clé \"MOTUS\".__\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__3.2. Expliquer comment décoder un texte connaissant la clé, et appliquer la méthode pour décoder \"NFTPAEGBGG\" avec la clé \"MOTUS\".__\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__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]$.__
\n", "$\\;\\;\\;\\;\\;$__La fonction Python codage_Vigenere donnée ci-dessous utilise cette relation.__
\n", "$\\;\\;\\;\\;\\;$__Effectuer un appel à cette fonction pour vérifier le résultat de la question 3.1.__
\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Mise en mémoire de l'alphabet\n", "Alphabet=\"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n", "\n", "def codage_Vigenere(message,cle):\n", " \"\"\"\n", " Fonction effectuant le codage de Vigenere du message avec la cle\n", " \"\"\"\n", " l_cle=len(cle) # longueur de la clé\n", " j=0 # rang de la lettre de la clé utilisée\n", " code=\"\" \n", " \n", " for caractere in message: # on parcourt les caractères du message à coder\n", " if caractere in Alphabet: # si c'est une lettre de l'alphabet:\n", " x = Alphabet.index(caractere) # on stocke dans x le rang de cette lettre \n", " c = Alphabet.index(cle[j]) # on stocke dans c le rang de la lettre de la clé \n", " y = (x+c) %26 # on calcule le rang y de la lettre codée correspondante\n", " code += Alphabet[y] # on complète le code avec la lettre de rang y\n", " j = (j+1) %l_cle # on avance d'un rang dans la clé\n", " else: # sinon:\n", " code += \" \" # on complète le code avec un espace\n", " \n", " return code # on renvoie le message codé\n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Effectuer ici l'appel à la fonction codage_Vigenere\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__3.4. On reprend les notations de la question 3.3.__
\n", "$\\;\\;\\;\\;\\;$__a. Exprimer $x$ en fonction de $y$, modulo $26$.__
\n", "\n", "\n", "$\\;\\;\\;\\;\\;$__b. Adapter la fonction Python précédente pour écrire une fonction decodage_Vigenere.__
\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ecrire ici la fonction decodage_Vigenere\n", "\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;\\;\\;$__c. Effectuer un appel à cette fonction pour vérifier le résultat de la question 3.2.__
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Effectuer ici l'appel à la fonction decodage_Vigenere\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__3.5. Convenir avec une autre personne d'un mot clé.__
\n", "$\\;\\;\\;\\;\\;$__Chacun code alors un message à l'aide de la fonction Python codage_Vigenere en utilisant cette clé, et le donne à l'autre.__
\n", "$\\;\\;\\;\\;\\;$__Enfin, chacun décode le message reçu à l'aide de la fonction Python decodage_Vigenere.__" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Utiliser cette zone pour le codage du message\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Utiliser cette zone pour le décodage du message\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Vigenere](img/Vigenere.jpg)\n", "\n", "
Blaise de Vigenère (1523-1596)
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*\n" ] } ], "metadata": { "celltoolbar": "Raw Cell Format", "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.8" } }, "nbformat": 4, "nbformat_minor": 2 }