{ "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 (corrigé)\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", "\n", "\n", "\n", "La première lettre du message est C, qui correspond à $x=2$. On a $11x+8=30$ dont le reste par la division euclidienne par $26$ vaut $y=4$. Ainsi, cette lettre C sera codée par la lettre E.
\n", "En procédant de même pour les lettres suivantes, on obtient le message codé : E AYJ LIESZA EA EGPA.\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": 1, "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": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'E AYJ LIESZA EA EGPA'" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Effectuer ici l'appel à la fonction codage_affine\n", "codage_affine(11,8,\"C EST FACILE CE CODE\")\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", "\n", "Supposons qu'il existe $u$ tel que $0 \\leqslant u \\leqslant 25$ et $11u \\equiv 1[26]$.
\n", "Par construction de $y$, on a $y \\equiv 11x+8 [26]$.
\n", "En multipliant par $u$, il vient:
\n", "$uy \\equiv u(11x+8)[26]$
\n", "$uy-8u \\equiv 11ux[26]$
\n", "et comme $11u \\equiv 1[26]$, on a finalement:
\n", "$u(y-8) \\equiv x[26]$
\n", "$x \\equiv u(y-8)[26]$\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", "\n", "\n", "$11$ et $26$ sont premiers entre eux, donc l'équation diophantienne $11u+26v=1$ admet des solutions.
\n", "L'algorithme d'Euclide permet de déterminer des coefficients de Bézout, qui donnent une solution particulière:
\n", "On note $a=26$ et $b=11$.
\n", "\n", "
\n", "\n", "|Divisions euclidiennes |Recherche des coefficients de Bézout $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;$ | \n", "|:-----------------------|:-----------------------------------------------------------------------------------|\n", "| $\\color{red}{26=11 \\times 2+4}$ | $\\color{red}{4=26-11 \\times 2=a-2b}$ |\n", "| $\\color{red}{11=4 \\times 2+3}$ | $\\color{red}{3=11-4 \\times 2=b-(a-2b) \\times 2=-2a+5b}$ | \n", "| $\\color{red}{4=3 \\times 1+1}$ | $\\color{red}{1=4-3 \\times 1=a-2b-(-2a+5b)=3a-7b}$ | \n", "| $\\color{red}{3=1 \\times 3+0}$ | |\n", "\n", "
\n", " \n", "On en déduit donc que le couple $(u;v)=(-7;3)$ est solution de $11u+26v=1$. \n", "\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", "\n", " \n", "D'après la question b, $u=-7$ vérifie $11u+26 \\times2=1$ donc $11u \\equiv 1[26]$.
\n", "D'après la question a, on en déduit que:
\n", "$x \\equiv u(y-8)[26]$
\n", "$x \\equiv -7(y-8)[26]$
\n", "$x \\equiv -7y+56[26]$
\n", "$x \\equiv 19y+4[26]$ car $-7 \\equiv 19[26]$ et $56 \\equiv 4[26]$
\n", "
\n", "On peut maintenant décoder le message. La première lettre du message codé est D, qui correspond à $y=3$. On a $19y+4=61$ dont le reste par la division euclidienne par $26$ vaut $x=9$. Ainsi, le décodage de la lettre D donne la lettre J.
\n", "En procédant de même pour les lettres suivantes, on obtient le message décodé : JE NE COMPRENDS PAS.\n", "\n", "\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": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'JE NE COMPRENDS PAS'" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Effectuer ici l'appel à la fonction codage_affine\n", "codage_affine(19,4,\"DA VA EGKRNAVPY RIY\")\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": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'LD DT ZDTLFT LDX'" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Effectuer ici l'appel à la fonction codage_affine\n", "codage_affine(4,3,\"CA NE MARCHE PAS\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;\\;\\;\\;$__b. Balthazar parviendra-t-il facilement à décoder ce message ? Pourquoi ?__
\n", "\n", " \n", "On peut constater sur l'exemple de la question a que deux lettres différentes peuvent être codées par la même lettre, d'où l'impossibilité de mettre en place une méthode de décodage.
\n", "Par exemple, les lettres C et P sont toutes deux codées L, et les lettres A et N sont toutes deux codées D.\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", " \n", "Soit $x$ la valeur à coder. Les valeurs obtenues avec les clés $(a_1;b_1)$ et $(a_2;b_2)$ vérifient respectivement $y_1 \\equiv a_1x+b_1[26]$ et $y_2 \\equiv a_2x+b_2[26]$. Comme $a_1 \\equiv a_2[26]$ et $b_1 \\equiv b_2[26]$, on en déduit que $y_1 \\equiv y_2[26]$. Finalement, comme $y_1$ et $y_2$ sont compris entre $0$ et $25$, ils sont égaux.\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", "Supposons que $y=y'$. On a alors:
\n", "$ax+b \\equiv ax'+b[26]$
\n", "$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", "\n", "Supposons que $a$ premier avec $26$.
\n", "Considérons $x$ et $x'$ dont le codage avec la clé $(a;b)$ donne une même valeur, c'est à dire $y=y'$.
\n", "La question précédente donne $a(x-x') \\equiv 0[26]$ , qui permet de déduire que $26$ divise le produit $a(x-x')$.
\n", "Comme $26$ est premier avec $a$, le théorème de Gauss permet d'affirmer que $26$ divise $(x-x')$.
\n", "Or $0 \\leqslant x \\leqslant 25$ et $0 \\leqslant x' \\leqslant 25$ permettent de déduire que $-25 \\leqslant x-x' \\leqslant 25$ et $0$ est le seul multiple de $26$ compris entre $-25$ et $25$.
\n", "Ainsi, $x-x'=0$ c'est à dire $x=x'$.
\n", "Ceci prouve que le décodage d'un message est bien unique.\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", "\n", "La clé de chiffrement choisie doit vérifier $1 \\leqslant a \\leqslant 25$ et $0 \\leqslant b \\leqslant 25$ avec $a$ premier avec $26$.
\n", "Il y a $26$ valeurs possibles pour $b$ et $12$ valeurs possibles pour $a$ , qui sont $1;3;5;7;9;11;15;17;19;21;23$ et $25$.
\n", "Ainsi, on peut créer $26 \\times 12 = 312$ clés $(a;b)$ valides distinctes.
\n", "
\n", "La sûreté d'un chiffrement affine est faible au vu du peu de clés valides distinctes existantes. Un traitement informatisé de test exhaustif des clés possibles permettrait facilement de trouver la clé de déchiffrement. \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", "\n", "\n", "Considérons $x$ et $y$ tels que $y$ est la valeur codée correspondant à $x$ :
\n", "$y \\equiv ax+b [26]$
\n", "En multipliant par $u$, on obtient:
\n", "$uy \\equiv u(ax+b) [26]$
\n", "$uy \\equiv aux+bu [26]$
\n", "et comme $au \\equiv 1[26]$ et $bu \\equiv -v[26]$ , on déduit:
\n", "$uy \\equiv x-v [26]$
\n", "$x \\equiv uy+v [26]$
\n", "Ainsi $(u;v)$ est bien la clé de déchiffrement associée à la clé de chiffrement $(a;b)$.\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": 5, "metadata": {}, "outputs": [], "source": [ "# Ecrire ici la fonction inverse_cle\n", "def inverse_cle(a,b):\n", " \"\"\"\n", " fonction qui renvoie la clé de déchiffrement associée à la clé de chiffement (a;b)\n", " \"\"\"\n", " for u in range(1,26):\n", " if (a*u)%26==1:\n", " return u,(-b*u)%26\n", " return None" ] }, { "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": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'LZLB ZTA HK DZTTXNZ SZ AZTA'" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#Utiliser cette zone pour coder le message à envoyer\n", "\n", "#clé de chiffrement choisie:\n", "a,b = 7,23\n", "\n", "#message choisi:\n", "message='CECI EST UN MESSAGE DE TEST'\n", "\n", "#codage du message:\n", "message_code=codage_affine(a,b,message)\n", "message_code" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(15, 19)" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#Utiliser cette zone pour déterminer la clé de déchiffrement\n", "\n", "u,v=inverse_cle(7,23)\n", "u,v" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'CECI EST UN MESSAGE DE TEST'" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#Utiliser cette zone pour décoder le message reçu\n", "\n", "#décodage du message codé:\n", "decodage=codage_affine(u,v,message_code)\n", "decodage" ] }, { "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", "\n", "\n", "Le codage de \"VIVE VIGENERE\" donne \"HWOY NUUXHWDS\".\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", "\n", "\n", "Pour le décodage, on applique la méthode à l'envers: on cherche dans la ligne de la clé la colonne pour laquelle l'intersection donne la lettre codée.
\n", "Le décodage de \"NFTPAEGBGG\" donne \"BRAVISSIMO\".\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.__
" ] }, { "cell_type": "code", "execution_count": 9, "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": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'HWOY NUUXHWDS'" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#Effectuer ici l'appel à la fonction codage_Vigenere\n", "codage_Vigenere(\"VIVE VIGENERE\",\"MOTUS\")\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", "$y \\equiv x+c[26]$ est équivalent à $x \\equiv y-c[26]$\n", "\n", "\n", "$\\;\\;\\;\\;\\;$__b. Adapter la fonction Python précédente pour écrire une fonction decodage_Vigenere.__
\n" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "# Ecrire ici la fonction decodage_Vigenere\n", "\n", "def decodage_Vigenere(code,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", " message=\"\" \n", " \n", " for caractere in code: # on parcourt les caractères du message à décoder\n", " if caractere in Alphabet: # si c'est une lettre du dictionnaire:\n", " y = Alphabet.index(caractere) # x contient le rang de cette lettre \n", " c = Alphabet.index(cle[j]) # c contient le rang de la lettre de la clé \n", " x = (y-c) %26 # on calcule le rang de la lettre décodée correspondante\n", " message += Alphabet[x] # on complète le message avec cette lettre\n", " j = (j+1) %l_cle # on avance d'un rang dans la clé\n", " else: # sinon:\n", " message += \" \" # on complète le message avec un espace\n", " \n", " return message # on renvoie le message décodé\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": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'BRAVISSIMO'" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Effectuer ici l'appel à la fonction decodage_Vigenere\n", "decodage_Vigenere(\"NFTPAEGBGG\",\"MOTUS\")\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": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'DSGKMJTXG R NGHEXQ PAMPJVFSF IWIFHU GHD ZR LGIC'" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Utiliser cette zone pour le codage du message\n", "\n", "message = \"RETROUVEZ D AUTRES ACTIVITES PYTHON SUR LE SITE\"\n", "cle = \"MONTYPYTHON\"\n", "code=codage_Vigenere(message,cle)\n", "code" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'RETROUVEZ D AUTRES ACTIVITES PYTHON SUR LE SITE'" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Utiliser cette zone pour le décodage du message\n", "\n", "decode=decodage_Vigenere(code,cle)\n", "decode" ] }, { "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.6" } }, "nbformat": 4, "nbformat_minor": 2 }