{ "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": [ "\n", "# chiffrement affine \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": [ "## 1. Coder et décoder un message" ] }, { "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", "\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" ] }, { "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", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\;\\;\\;\\;\\;\\;$__b. Balthazar parviendra-t-il facilement à décoder ce message ? Pourquoi ?__
\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" ] }, { "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", "$\\;\\;\\;\\;\\;\\;$__b. Justifier que si on choisit $a$ premier avec $26$, alors le décodage de tout message est 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 ?__" ] }, { "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" ] }, { "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 chiffrage 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": [ "*(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.6.4" } }, "nbformat": 4, "nbformat_minor": 2 }