{
 "metadata": {
  "name": "Cryptographie"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Cryptographie"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Principes g\u00e9n\u00e9raux"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Deux personnes $A$ et $B$ veulent \u00e9changer des donn\u00e9es confidentielles. Comment transmettre ce message sans qu'une tierce personne $C$ puisse intercepter ces donn\u00e9es, ou en cas d'interception, ne puisse les d\u00e9chiffrer ?\n",
      "\n",
      "La cryptographie est le domaine de la cryptologie d\u00e9volue \u00e0 la protection des donn\u00e9es transmises.\n",
      "\n",
      "Le principe g\u00e9n\u00e9ral est donc le suivant :\n",
      "\n",
      "$\\bullet$ la personne $A$ veut transmettre un message que l'on nomme **message en clair**\n",
      "\n",
      "$\\bullet$ la personne $A$ va **chiffrer** ou **coder** son message afin de le rendre inintelligible. Ce message crypt\u00e9 s'appelle le **cryptogramme**.\n",
      "\n",
      "L'outil permettant ce **chiffrement** ou ce **codage** s'appelle la **cl\u00e9 de chiffrement**\n",
      "\n",
      "$\\bullet$ le message crypt\u00e9 est transmis vers la personne $B$\n",
      "\n",
      "$\\bullet$ la personne $B$ re\u00e7oit le message crypt\u00e9, puis le d\u00e9crypt\u00e9 via une **cl\u00e9 de d\u00e9chiffrement**\n",
      "\n",
      "En g\u00e9n\u00e9ral, la cl\u00e9 de chiffrement et de d\u00e9chiffrement ont \u00e9t\u00e9 confectionn\u00e9es de mani\u00e8re \u00e0 ce que si une personne $C$ intercepte le cryptagramme sans disposer de la cl\u00e9 de d\u00e9chiffrement, alors elle ne pourra que difficilement d\u00e9chiffrer le message d'origine."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Nous pr\u00e9sentons dans ce chapitre deux types de cryptages :\n",
      "\n",
      "$\\rhd$ le chiffrement de Vigenera\n",
      "\n",
      "$\\rhd$ le codage RSA"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Le chiffrement de Vigenere"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Principe du chiffrement"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Il s'agit d'un syst\u00e8me de chiffrement polyalphab\u00e9tique reposant essentiellement sur une translation portant sur l'alphabet latin. Ce syst\u00e8me a \u00e9t\u00e9 mis au point par le diplomate Blaise de Vigenere au $XVI^{\\grave{e}me}$ si\u00e8cle.\n",
      "\n",
      "Le principe est :\n",
      "\n",
      "$\\bullet$ la personne $A$ dispose de son message en clair et d'une cl\u00e9 de chiffrement qui est une cha\u00eene de caract\u00e8res compos\u00e9e uniquement de lettres de l'alphabet latin :"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alphabet=\"abcdefghijklmnopqrstuvwxyz\"\n",
      "\n",
      "print(' '.join(alphabet))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "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"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Le premier travail de la personne $A$ consiste \u00e0 calibrer la cl\u00e9 de chiffrement en fonction de son message d'origine : on dispose d'abord le message d'origine, puis en dessous la cl\u00e9 de chiffrement."
     ]
    },
    {
     "cell_type": "raw",
     "metadata": {},
     "source": [
      "message en clair =\"Les probl\u00e8mes du mill\u00e9naire sont r\u00e9put\u00e9s insurmontables.\"\n",
      "cle=\"maclef\"\n",
      "cle recalibr\u00e9e en fonction du message d'origine :\n",
      "\n",
      "Les probl\u00e8mes du mill\u00e9naire sont r\u00e9put\u00e9s insurmontables.\n",
      "mac lefma cle fm acle fmacl efma c lef m aclefmaclefmac "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "En dessous de chaque lettre de l'*alphabet* (les lettres majuscules sont transform\u00e9es en minuscules) figure une lettre de la cl\u00e9 de chiffrement et en dessous de chaque autre symbole figure un espace.\n",
      "\n",
      "Le message d'origine et la cl\u00e9 recalibr\u00e9e consituent d\u00e9sormais deux cha\u00eenes de caract\u00e8res de taille identique.\n",
      "\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\bullet$ Le deuxi\u00e8me travail de la personne $A$ consiste \u00e0 remplacer chaque symbole de son message d'origine gr\u00e2ce \u00e0 cette cl\u00e9 recalibr\u00e9e : le symbole (lettre ou espace) figurant en dessous du message \u00e0 transmettre indique la substitution \u00e0 effectuer : la lettre *\"m\"* est la $13^{\\grave{e}me}$ lettre de l'alphabet. La lettre *\"L\"* du message est la $12^{\\grave{e}me}$ lettre de l'alphabet : la lettre *\"L\"* sera remplac\u00e9e par la $25^{\\grave{e}me}$ lettre de l'alphabet qui le *\"y\"*, \u00e9tant entendu que si l'on obtient un nombre sup\u00e9rieur \u00e0 $26$, on reboucle l'alphabet (la lettre qui vient apr\u00e8s le *\"z\"* est le *\"a\"*, etc.)\n",
      "\n",
      "Tout symbole du message d'origine est au-dessus d'un espace dans la cl\u00e9 recalibr\u00e9e : ce symbole reste identique dans le cryptogramme.\n",
      "\n",
      "On obtient ainsi un message chiffr\u00e9. \n",
      "\n",
      "La personne $A$ n'a plus qu'\u00e0 l'envoyer \u00e0 la personne $B$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\rhd$ Le premier travail de la personne $B$ qui dispose de la m\u00eame cl\u00e9 de chiffrement que la personne $A$ recalibre cette cl\u00e9 de chiffrement en fonction du message re\u00e7u : cette cl\u00e9 recalibr\u00e9e est identique \u00e0 celle trouv\u00e9e par la personne $A$, car le cryptogramme ou le message d'origine ont la m\u00eame longueur et les places des symboles de l'*alphabet* sont identiques.\n",
      "\n",
      "$\\rhd$ Le second travail de la personne $B$ consiste \u00e0 effectuer les substitutions dans l'e sens contraire : au lieu d'ajouter les rangs des lettres de la cl\u00e9 recalibr\u00e9e, elle les retranchera, pour finalement obtenir le message d'origine o\u00f9 les majuscules seront remplac\u00e9es par des minuscules, ce qui rend tout \u00e0 fait compr\u00e9hensible le texte."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Impl\u00e9mentation en Python"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alphabet=\"abcdefghijklmnopqrstuvwxyz\"\n",
      "\n",
      "print(' '.join(alphabet))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "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"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\n",
      "def Trouve_Place(symbole) :\n",
      "    symbole_temp=symbole.lower()\n",
      "    k=0\n",
      "    while k<26 and alphabet[k]!=symbole_temp :\n",
      "        k+=1\n",
      "    return k\n",
      "for lettre in \"Hypoth\u00e8se de Riemann : probl\u00e8me difficile !!!\" :    \n",
      "    print(lettre,\" a pour place : \",Trouve_Place(lettre))\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "H  a pour place :  7\n",
        "y  a pour place :  24\n",
        "p  a pour place :  15\n",
        "o  a pour place :  14\n",
        "t  a pour place :  19\n",
        "h  a pour place :  7\n",
        "\u00e8  a pour place :  26\n",
        "s  a pour place :  18\n",
        "e  a pour place :  4\n",
        "   a pour place :  26\n",
        "d  a pour place :  3\n",
        "e  a pour place :  4\n",
        "   a pour place :  26\n",
        "R  a pour place :  17\n",
        "i  a pour place :  8\n",
        "e  a pour place :  4\n",
        "m  a pour place :  12\n",
        "a  a pour place :  0\n",
        "n  a pour place :  13\n",
        "n  a pour place :  13\n",
        "   a pour place :  26\n",
        ":  a pour place :  26\n",
        "   a pour place :  26\n",
        "p  a pour place :  15\n",
        "r  a pour place :  17\n",
        "o  a pour place :  14\n",
        "b  a pour place :  1\n",
        "l  a pour place :  11\n",
        "\u00e8  a pour place :  26\n",
        "m  a pour place :  12\n",
        "e  a pour place :  4\n",
        "   a pour place :  26\n",
        "d  a pour place :  3\n",
        "i  a pour place :  8\n",
        "f  a pour place :  5\n",
        "f  a pour place :  5\n",
        "i  a pour place :  8\n",
        "c  a pour place :  2\n",
        "i  a pour place :  8\n",
        "l  a pour place :  11\n",
        "e  a pour place :  4\n",
        "   a pour place :  26\n",
        "!  a pour place :  26\n",
        "!  a pour place :  26\n",
        "!  a pour place :  26\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "On d\u00e9cide pour la suite d'octroyer la place $26$ pour les symboles hors de l'*alphabet*."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\n",
      "def Trouve_Symbole(place) :\n",
      "    return alphabet[place%26]\n",
      "\n",
      "for k in range(20,30) :\n",
      "    print(\"A la place \",k,\" se trouve le symbole :\",Trouve_Symbole(k))\n",
      "\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "A la place  20  se trouve le symbole : u\n",
        "A la place  21  se trouve le symbole : v\n",
        "A la place  22  se trouve le symbole : w\n",
        "A la place  23  se trouve le symbole : x\n",
        "A la place  24  se trouve le symbole : y\n",
        "A la place  25  se trouve le symbole : z\n",
        "A la place  26  se trouve le symbole : a\n",
        "A la place  27  se trouve le symbole : b\n",
        "A la place  28  se trouve le symbole : c\n",
        "A la place  29  se trouve le symbole : d\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "C'est la d\u00e9marche inverse : \u00e0 partir de la place, on trouve la lettre associ\u00e9e dans l'*alphabet* boucl\u00e9."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Calibrage(cle,message_en_clair) :\n",
      "    message_temp=message_en_clair.lower()\n",
      "    cle_calibree=\"\"\n",
      "    k_cle,l_mess=0,0\n",
      "    while l_mess<len(message_en_clair) :\n",
      "        if Trouve_Place(message_en_clair[l_mess])!=26 :\n",
      "            cle_calibree=cle_calibree+cle[k_cle%len(cle)]\n",
      "            k_cle+=1\n",
      "        else :\n",
      "            cle_calibree=cle_calibree+\" \"\n",
      "        l_mess+=1\n",
      "        \n",
      "        \n",
      "    return cle_calibree\n",
      "mess=\"Les probl\u00e8mes du mill\u00e9naire sont r\u00e9put\u00e9s insurmontables.\"\n",
      "print(mess)    \n",
      "print(Calibrage(\"maclef\",mess))\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Les probl\u00e8mes du mill\u00e9naire sont r\u00e9put\u00e9s insurmontables.\n",
        "mac lefma cle fm acle fmacl efma c lef m aclefmaclefmac \n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Voici la fonction de cryptage proprement dite :"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Crypte(message_en_clair,cle) :\n",
      "    message_crypte=\"\"\n",
      "    cle_Calibree=Calibrage(cle,message_en_clair)\n",
      "    for k in range(len(message_en_clair)) :\n",
      "        symbole=message_en_clair[k]\n",
      "        if Trouve_Place(symbole)==26 :\n",
      "            message_crypte=message_crypte+symbole\n",
      "        else :\n",
      "            message_crypte=message_crypte+Trouve_Symbole(Trouve_Place(symbole)+Trouve_Place(cle_Calibree[k]))\n",
      "    return message_crypte\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "message_en_clair=\"Dieu ne joue pas aux d\u00e9s. [citation d'Albert Einstein]\"\n",
      "cle=\"einstein\"\n",
      "print(Crypte(message_en_clair,cle))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "hqrm gi rbym csl eck h\u00e9a. [pamebvsv q'sefmex mvflxmvr]\n"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Decrypte(message_crypte,cle) :\n",
      "    message_decrypte=\"\"\n",
      "    cle_Calibree=Calibrage(cle,message_crypte)\n",
      "    for k in range(len(message_crypte)) :\n",
      "        symbole=message_crypte[k]\n",
      "        if Trouve_Place(symbole)==26 :\n",
      "            message_decrypte=message_decrypte+symbole\n",
      "        else :\n",
      "            message_decrypte=message_decrypte+Trouve_Symbole(Trouve_Place(symbole)-Trouve_Place(cle_Calibree[k]))\n",
      "    return message_decrypte\n",
      "    "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "message_en_clair=\"L'imagination est plus importante que le savoir !! [1 citation d'Albert Einstein]\"\n",
      "cle=\"einstein\"\n",
      "cryptogramme=Crypte(message_en_clair,cle)\n",
      "message_decrypte=Decrypte(cryptogramme,cle)\n",
      "print(\"message en clair :\\n\",message_en_clair)\n",
      "print(\"cryptogramme :\\n\",cryptogramme)\n",
      "print(\"message d\u00e9crypt\u00e9:\\n\",message_decrypte)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "message en clair :\n",
        " L'imagination est plus importante que le savoir !! [1 citation d'Albert Einstein]\n",
        "cryptogramme :\n",
        " p'qzszmvnxqbf xwb cpcf aftwexialx ucr pm fsosqe !! [1 gqgsmmwa h'iytxvb rmvflxmv]\n",
        "message d\u00e9crypt\u00e9:\n",
        " l'imagination est plus importante que le savoir !! [1 citation d'albert einstein]\n"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Cryptanalyse du Vigenere"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "La **cryptanalyse** est la science qui consiste \u00e0 d\u00e9chiffrer un message cod\u00e9, avec ou sans la cl\u00e9 de d\u00e9chiffrement. \n",
      "\n",
      "Dans l'exemple du codage de Vigenere, si la personne $C$ intercepte le cryptogramme sans la cl\u00e9 de chiffrement, il lui est assez difficile de le d\u00e9crypter. La m\u00e9thode de codage r\u00e9siste \u00e0 l'**analyse de fr\u00e9quences** qui consisterait \u00e0 retrouver certaines lettres par rapport \u00e0 leur fr\u00e9quence d'usage (la lettre *e* \u00e9tant la plus utilis\u00e9e en fran\u00e7ais). En effet, deux symboles identiques dans le message d'origine peuvent \u00eatre crypt\u00e9s selon deux symboles diff\u00e9rents par la cl\u00e9.\n",
      "\n",
      "Cependant, le tr\u00e8s gros inconv\u00e9nient de cette m\u00e9thode est que les personnes $A$ et $B$ doivent confectionner la cl\u00e9 ensemble, ce qui impose une mise en commun de plusieurs informations, cette mise en commun devant \u00eatre secr\u00e8te, car si la personne $C$ intercepte \u00e0 la fois le cryptogramme et la cl\u00e9, alors il lui est tr\u00e8s facile de d\u00e9crypter le message, comme le fait d'ailleurs le destinataire $B$.\n",
      "\n",
      "Existe-t-il un moyen d'assuer un bon cryptage sans que les personnes $A$ et $B$ ne se rencontrent ?"
     ]
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Le codage RSA"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Principe du codage"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Le codage RSA a \u00e9t\u00e9 cr\u00e9\u00e9 en 1977 par Ronald **Rivest**, Adi **Shimar** et Leonard **Adleman** puis brevet\u00e9 en 1983 par le Massachussetts Institute of Technology (MIT).\n",
      "\n",
      "Ce syst\u00e8me utilise tr\u00e8s fortement les congruences. \n",
      "\n",
      "Voici le principe :\n",
      "\n",
      "$\\rhd$ la personne $B$ choisit deux nombres premiers $p$ et $q$ diff\u00e9rents et assez grands (on verra plus tard ce que signifie ce *grand*)\n",
      "\n",
      "$\\rhd$ la personne $B$ calcule $n=p~q$\n",
      "\n",
      "$\\rhd$ la personne $B$ calcule l'indicateur d'Euler :\n",
      "\n",
      "$\\varphi(n)=(p-1)~(q-1)={\\rm Card}((\\mathbb{Z}/n\\mathbb{Z})^*)$\n",
      "\n",
      "$\\rhd$ la personne $B$ choisit un \u00e9l\u00e9ment $e$ dans $(\\mathbb{Z}/\\varphi(n)\\mathbb{Z})^*$\n",
      "\n",
      "$\\rhd$ la personne $B$ calcule alors $d=e^{-1}$ dans $\\mathbb{Z}/\\varphi(n)\\mathbb{Z}$\n",
      "\n",
      "La personne $B$ est donc en mesure de fournir deux cl\u00e9s :\n",
      "\n",
      "$\\longrightarrow$ la cl\u00e9 de chiffrement encore appel\u00e9e **cl\u00e9 publique** qui est le couple $(n,e)$\n",
      "\n",
      "$\\longrightarrow$ la cl\u00e9 de d\u00e9chiffrement encore appel\u00e9e **cl\u00e9 priv\u00e9e** qui est le couple $(n,d)$\n",
      "\n",
      "$\\rhd$ la personne $B$ garde secr\u00e8tement la cl\u00e9 priv\u00e9e et publie la cl\u00e9 publique  : la personne $A$ a donc acc\u00e8s au couple $(n,e)$.\n",
      "\n",
      "La premi\u00e8re phase est termin\u00e9e."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\rhd$ la personne $A$ veut alors transmettre son message. Elle utilise par exemple le code ASCII (pour **American Standard Code for Information Interchange**) qui est une norme de codage des caract\u00e8res.\n",
      "\n",
      "Habituellement, ce codage a lieu sur un octet, permettant ainsi de coder $256$ symboles.\n",
      "\n",
      "Les syntaxes **chr(k)** et **ord(\"symbole\")** permettent respectivement de calculer le caract\u00e8res dont le code ASCII vaut $k$ et de calculer le code de *\"symbole\"* : "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "L=[[chr(k),k] for k in range(2**8)]\n",
      "print(L)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[['\\x00', 0], ['\\x01', 1], ['\\x02', 2], ['\\x03', 3], ['\\x04', 4], ['\\x05', 5], ['\\x06', 6], ['\\x07', 7], ['\\x08', 8], ['\\t', 9], ['\\n', 10], ['\\x0b', 11], ['\\x0c', 12], ['\\r', 13], ['\\x0e', 14], ['\\x0f', 15], ['\\x10', 16], ['\\x11', 17], ['\\x12', 18], ['\\x13', 19], ['\\x14', 20], ['\\x15', 21], ['\\x16', 22], ['\\x17', 23], ['\\x18', 24], ['\\x19', 25], ['\\x1a', 26], ['\\x1b', 27], ['\\x1c', 28], ['\\x1d', 29], ['\\x1e', 30], ['\\x1f', 31], [' ', 32], ['!', 33], ['\"', 34], ['#', 35], ['$', 36], ['%', 37], ['&', 38], [\"'\", 39], ['(', 40], [')', 41], ['*', 42], ['+', 43], [',', 44], ['-', 45], ['.', 46], ['/', 47], ['0', 48], ['1', 49], ['2', 50], ['3', 51], ['4', 52], ['5', 53], ['6', 54], ['7', 55], ['8', 56], ['9', 57], [':', 58], [';', 59], ['<', 60], ['=', 61], ['>', 62], ['?', 63], ['@', 64], ['A', 65], ['B', 66], ['C', 67], ['D', 68], ['E', 69], ['F', 70], ['G', 71], ['H', 72], ['I', 73], ['J', 74], ['K', 75], ['L', 76], ['M', 77], ['N', 78], ['O', 79], ['P', 80], ['Q', 81], ['R', 82], ['S', 83], ['T', 84], ['U', 85], ['V', 86], ['W', 87], ['X', 88], ['Y', 89], ['Z', 90], ['[', 91], ['\\\\', 92], [']', 93], ['^', 94], ['_', 95], ['`', 96], ['a', 97], ['b', 98], ['c', 99], ['d', 100], ['e', 101], ['f', 102], ['g', 103], ['h', 104], ['i', 105], ['j', 106], ['k', 107], ['l', 108], ['m', 109], ['n', 110], ['o', 111], ['p', 112], ['q', 113], ['r', 114], ['s', 115], ['t', 116], ['u', 117], ['v', 118], ['w', 119], ['x', 120], ['y', 121], ['z', 122], ['{', 123], ['|', 124], ['}', 125], ['~', 126], ['\\x7f', 127], ['\\x80', 128], ['\\x81', 129], ['\\x82', 130], ['\\x83', 131], ['\\x84', 132], ['\\x85', 133], ['\\x86', 134], ['\\x87', 135], ['\\x88', 136], ['\\x89', 137], ['\\x8a', 138], ['\\x8b', 139], ['\\x8c', 140], ['\\x8d', 141], ['\\x8e', 142], ['\\x8f', 143], ['\\x90', 144], ['\\x91', 145], ['\\x92', 146], ['\\x93', 147], ['\\x94', 148], ['\\x95', 149], ['\\x96', 150], ['\\x97', 151], ['\\x98', 152], ['\\x99', 153], ['\\x9a', 154], ['\\x9b', 155], ['\\x9c', 156], ['\\x9d', 157], ['\\x9e', 158], ['\\x9f', 159], ['\\xa0', 160], ['\u00a1', 161], ['\u00a2', 162], ['\u00a3', 163], ['\u00a4', 164], ['\u00a5', 165], ['\u00a6', 166], ['\u00a7', 167], ['\u00a8', 168], ['\u00a9', 169], ['\u00aa', 170], ['\u00ab', 171], ['\u00ac', 172], ['\\xad', 173], ['\u00ae', 174], ['\u00af', 175], ['\u00b0', 176], ['\u00b1', 177], ['\u00b2', 178], ['\u00b3', 179], ['\u00b4', 180], ['\u00b5', 181], ['\u00b6', 182], ['\u00b7', 183], ['\u00b8', 184], ['\u00b9', 185], ['\u00ba', 186], ['\u00bb', 187], ['\u00bc', 188], ['\u00bd', 189], ['\u00be', 190], ['\u00bf', 191], ['\u00c0', 192], ['\u00c1', 193], ['\u00c2', 194], ['\u00c3', 195], ['\u00c4', 196], ['\u00c5', 197], ['\u00c6', 198], ['\u00c7', 199], ['\u00c8', 200], ['\u00c9', 201], ['\u00ca', 202], ['\u00cb', 203], ['\u00cc', 204], ['\u00cd', 205], ['\u00ce', 206], ['\u00cf', 207], ['\u00d0', 208], ['\u00d1', 209], ['\u00d2', 210], ['\u00d3', 211], ['\u00d4', 212], ['\u00d5', 213], ['\u00d6', 214], ['\u00d7', 215], ['\u00d8', 216], ['\u00d9', 217], ['\u00da', 218], ['\u00db', 219], ['\u00dc', 220], ['\u00dd', 221], ['\u00de', 222], ['\u00df', 223], ['\u00e0', 224], ['\u00e1', 225], ['\u00e2', 226], ['\u00e3', 227], ['\u00e4', 228], ['\u00e5', 229], ['\u00e6', 230], ['\u00e7', 231], ['\u00e8', 232], ['\u00e9', 233], ['\u00ea', 234], ['\u00eb', 235], ['\u00ec', 236], ['\u00ed', 237], ['\u00ee', 238], ['\u00ef', 239], ['\u00f0', 240], ['\u00f1', 241], ['\u00f2', 242], ['\u00f3', 243], ['\u00f4', 244], ['\u00f5', 245], ['\u00f6', 246], ['\u00f7', 247], ['\u00f8', 248], ['\u00f9', 249], ['\u00fa', 250], ['\u00fb', 251], ['\u00fc', 252], ['\u00fd', 253], ['\u00fe', 254], ['\u00ff', 255]]\n"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "On constate que les premiers caract\u00e8res sont en fait r\u00e9serv\u00e9s aux s\u00e9parateurs et aux commandes de passage \u00e0 la ligne."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "message=\"Les probl\u00e8mes \\n du voyageur de commerce \\n ou \\n du sac \u00e0 dos\\n sont NP-complets.\"\n",
      "print(message)\n",
      "\n",
      "print(\"message par codes ASCII :\")\n",
      "print([ord(symbole) for symbole in message])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Les probl\u00e8mes \n",
        " du voyageur de commerce \n",
        " ou \n",
        " du sac \u00e0 dos\n",
        " sont NP-complets.\n",
        "message par codes ASCII :\n",
        "[76, 101, 115, 32, 112, 114, 111, 98, 108, 232, 109, 101, 115, 32, 10, 32, 100, 117, 32, 118, 111, 121, 97, 103, 101, 117, 114, 32, 100, 101, 32, 99, 111, 109, 109, 101, 114, 99, 101, 32, 10, 32, 111, 117, 32, 10, 32, 100, 117, 32, 115, 97, 99, 32, 224, 32, 100, 111, 115, 10, 32, 115, 111, 110, 116, 32, 78, 80, 45, 99, 111, 109, 112, 108, 101, 116, 115, 46]\n"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\rhd$ la personne $A$ transforme alors son message initial en codes ASCII\n",
      "\n",
      "$\\rhd$ ayant connaissance de la cl\u00e9 publique $(n,e)$, la personne $A$ compl\u00e8te les codes de $256$ \u00e0 $n$ en utilisant par exemple les symboles \\# $k$ : le symbole \\# $k$ correspond donc au nombre $256+k$ ; cela pr\u00e9suppose que l'entier $n=p~q$ soit sup\u00e9rieur \u00e0 $2**8=256$ afin de pouvoir coder au moins $256$ symboles diff\u00e9rents\n",
      "\n",
      "$\\rhd$ pour chaque symbole \"s\"  de son message initial, la personne $A$ calcule son code ASCII $s$, puis $s^e$ dans $\\mathbb{Z}/n\\mathbb{Z}$\n",
      "\n",
      "$\\rhd$ La personne $A$ remplace alors chaque symbole \"s\" de son message initial par le symbole correspondant au code ASCII extrapol\u00e9 $s^e$ (si $s^e$ d\u00e9passe $255$ dans $\\mathbb{Z}/n\\mathbb{Z}$, le symbole substitu\u00e9 vaut alors \\# $(s^e-256)$)\n",
      "\n",
      "$\\rhd$ apr\u00e8s chaque substitution, la personne $A$ a ainsi construit son message crypt\u00e9 qu'elle envoie \u00e0 la personne $B$\n",
      "\n",
      "\\n La seconde phase est termin\u00e9e."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\rhd$ La personne $B$ re\u00e7oit le cryptogramme.\n",
      "\n",
      "$\\rhd$ Pour chaque symbole du cryptogramme, la personne $B$ calcule son code ASCII extrapol\u00e9 \u00e0 $\\mathbb{Z}/n\\mathbb{Z}$\n",
      "\n",
      "$\\rhd$ pour chaque \u00e9l\u00e9ment $t$ ainsi obtenu, la personne $B$ calcule $t^d$ dans $\\mathbb{Z}/n\\mathbb{Z}$ : la personne $B$ dispose alors d'un message constitu\u00e9 de codes ASCII.\n",
      "\n",
      "$\\rhd$ Pour chaque code de ce message, la personne $B$ retrouve le symbole associ\u00e9 et la personne $B$ retrouve exactement le message initial de la personne $A$ !!"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "On d\u00e9montre maintenant cette m\u00e9thode.\n",
      "\n",
      "Cela revient \u00e0 d\u00e9montrer que chaque symbole transmis est correctement d\u00e9crypt\u00e9.\n",
      "\n",
      "Soit \"s\" un symbole du message initial, associ\u00e9 \u00e0 $s\\in \\mathbb{Z}/n\\mathbb{Z}$ en code ASCII.\n",
      "\n",
      "La personne $A$ transmet le symbole associ\u00e9 au code $s^e$.\n",
      "\n",
      "La personne $B$, apr\u00e8s d\u00e9cryptage, obtient le symbole associ\u00e9 au code $(s^e)^d=s^{e~d}$ dans $\\mathbb{Z}/n\\mathbb{Z}$.\n",
      "\n",
      "Il s'agit donc de montrer que $s^{e~d}=s$ dans $\\mathbb{Z}/n\\mathbb{Z}$.\n",
      "\n",
      "En effet, on distingue trois cas :\n",
      "\n",
      "$\\longrightarrow$ **<u>cas n$^o ~1$** : l'entier $s$ est premier avec $p$ et $q$</u> \n",
      "\n",
      "Dans ce cas, par le th\u00e9or\u00e8me de Gauss, l'entier $s$ est premier avec $n=p~q$, donc $s$ appartient au groupe $(\\mathbb{Z}/n\\mathbb{Z})^*$, qui est de cardinal $\\varphi(n)$. \n",
      "\n",
      "Une cons\u00e9quence du th\u00e9or\u00e8me de Lagrange donne : $s^{\\varphi(n)}=1$ dans $\\mathbb{Z}/n\\mathbb{Z}$.\n",
      "\n",
      "Or, $d=e^{-1}$ dans $\\mathbb{Z}/\\varphi(n)\\mathbb{Z}$ : il existe un entier $k\\in\\mathbb{Z}$ tel que : $e~d=1+k~\\varphi(n)$, de sorte que :\n",
      "\n",
      "$s^{e~d}=s\\times (s^{\\varphi(n)})^k=s$ dans $\\mathbb{Z}/n\\mathbb{Z}$.\n",
      "\n",
      "\n",
      "$\\longrightarrow$ **<u>cas n$^o ~2$** : l'entier $s$ est premier avec un seul des deux nombres $p$ ou $q$</u>\n",
      "\n",
      "Par exemple $p\\wedge s=1$, donc $q$ divise $s$.\n",
      "\n",
      "Il est \u00e9vident que l'entier $q$ divise $s^{e~d}-s$, car l'entier $e~d$ ne peut \u00eatre nul. Ensuite, en posant toujours $e~d=1+k~\\varphi(n)$, avec $k\\in\\mathbb{Z}$, on \u00e9crit, l'entier $s$ \u00e9tant premier avzec $q$ appartient donc \u00e0 $(\\mathbb{Z}/q\\mathbb{Z})^*$, de cardinal $(q-1)$. \n",
      "\n",
      "En utilisant le m\u00eame corollaire que le th\u00e9or\u00e8me de Lagrange, on obtient que $s^{q-1}=1$ dans $\\mathbb{Z}/q\\mathbb{Z}$, donc que l'entier $q$ divise $s^{q-1}-1$.\n",
      "\n",
      "L'entier $q$ divise donc l'entier $s^{e~d}-s=s\\times (s^{k\\varphi(n)}-1)=\n",
      "s\\times \\Bigl((s^{q-1})^{p-1}-1^{p-1}\\Bigr)$.\n",
      "\n",
      "En d\u00e9finitive, les entiers $p$ et $q$, donc l'entier $n$ divise $s^{ e~d}-s$.\n",
      "\n",
      "\n",
      "$\\longrightarrow$ **<u>cas n$^o ~3$** : l'entier $s$ est multiple de $p$ et de $q$, donc de $n$</u>\n",
      "\n",
      "Il est alors facile de voir que $n$ divise $s^{e~d}-s$.\n",
      "\n",
      "Dans tous les cas, le symbole d\u00e9crypt\u00e9 par la personne $B$ redonne exactement le m\u00eame symbole que la personne $A$.\n"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Impl\u00e9mentation en Python"
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Fonctions arithm\u00e9tiques"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Test_PGCD(a,b) :\n",
      "    \"\"\" teste si a et b sont premiers entre eux \"\"\"\n",
      "    u,v=a,b\n",
      "    while v!= 0:\n",
      "        u,v=v,u%v\n",
      "    return u==1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Inverse(a,n) : \n",
      "    \"\"\" calcule l'inverse de a dans Z/nZ \"\"\"\n",
      "    u,v=a,n\n",
      "    L=[]\n",
      "    while v!=0 :\n",
      "        L.append(u//v)\n",
      "        u,v=v,u%v\n",
      "        \n",
      "    Crochet=[0,1]\n",
      "    L.reverse() \n",
      "    for j in range(len(L)-1) :\n",
      "        Crochet=[Crochet[1],Crochet[0]-Crochet[1]*L[j+1]] # on parcourt la liste dans le sens droite->gauche en \u00e9vitant l'avant-dernier\n",
      "    return Crochet[0]%n\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\n",
      "n=11\n",
      "for k in range(1,11) :\n",
      "    print(\"inverse de \",k,\" modulo \",n,\" :\",Inverse(k,n))\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inverse de  1  modulo  11  : 1\n",
        "inverse de  2  modulo  11  : 6\n",
        "inverse de  3  modulo  11  : 4\n",
        "inverse de  4  modulo  11  : 3\n",
        "inverse de  5  modulo  11  : 9\n",
        "inverse de  6  modulo  11  : 2\n",
        "inverse de  7  modulo  11  : 8\n",
        "inverse de  8  modulo  11  : 7\n",
        "inverse de  9  modulo  11  : 5\n",
        "inverse de  10  modulo  11  : 10\n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Test_Premier(p) :\n",
      "    \"\"\" teste si p est premier \"\"\"\n",
      "    k=2 \n",
      "    while k<p and p%k != 0 :\n",
      "        k+=1\n",
      "    return k==p"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print([k for k in range(1,100) if Test_Premier(k)])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]\n"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Liste_Premiers(k) :\n",
      "    \"\"\" renvoie la liste des k premiers nombres premiers : en r\u00e9cursif \"\"\"\n",
      "    if k==1 :\n",
      "        return [2]\n",
      "    else :\n",
      "        L=Liste_Premiers(k-1)\n",
      "        N=L[-1]+1\n",
      "        while not(Test_Premier(N)) :\n",
      "            N+=1\n",
      "        L.append(N)\n",
      "        return L\n",
      "    "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 18
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(Liste_Premiers(30))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]\n"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Fonctions pour g\u00e9n\u00e9rer les deux cl\u00e9s"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from random import *\n",
      "\n",
      "\n",
      "def Generation_Deux_Premiers() :\n",
      "    \"\"\" renvoie deux premiers p<q entre le 20-\u00e8me et le 100-\u00e8me nombre premier \"\"\"\n",
      "    L=list(range(20,101))\n",
      "    p=randint(20,100)\n",
      "    L.remove(p)\n",
      "    q=L[randint(0,79)]\n",
      "    if p>q :\n",
      "        p,q=q,p\n",
      "    M=Liste_Premiers(q)\n",
      "    return [M[p-1],M[q-1]]\n",
      "    "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(Generation_Deux_Premiers())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[227, 337]\n"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Generation_Cles() :\n",
      "    L=Generation_Deux_Premiers()\n",
      "    n=L[0]*L[1]\n",
      "    phi=(L[0]-1)*(L[1]-1)\n",
      "    Inversibles=[k for k in range(1,phi) if Test_PGCD(k,phi)]\n",
      "    e=Inversibles[randint(0,len(Inversibles)-1)]\n",
      "    d=Inverse(e,phi)\n",
      "    return [[n,e],[n,d]]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 22
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(Generation_Cles())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[46357, 17953], [46357, 36517]]\n"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Le plus petit entier $p$ choisi est $p=71$ correspondant au $20^{\\grave{e}me}$ nombre premier, ce qui fait que l'entier $n$ minimal choisi est $n=71\\times 73=5183$ qui permet largement coder les 256 symboles du code ASCII."
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Fonction manipulant le code ASCII extrapol\u00e9 \u00e0 $\\mathbb{Z}/n\\mathbb{Z}$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Calibrage_Symboles(n) :\n",
      "    L=[]\n",
      "    for k in range(n) :\n",
      "        if k<256 :\n",
      "            L.append([chr(k),k])\n",
      "        else :\n",
      "            L.append([\"#\"+str(k-256),k])\n",
      "    return L"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 24
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(Calibrage_Symboles(300))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[['\\x00', 0], ['\\x01', 1], ['\\x02', 2], ['\\x03', 3], ['\\x04', 4], ['\\x05', 5], ['\\x06', 6], ['\\x07', 7], ['\\x08', 8], ['\\t', 9], ['\\n', 10], ['\\x0b', 11], ['\\x0c', 12], ['\\r', 13], ['\\x0e', 14], ['\\x0f', 15], ['\\x10', 16], ['\\x11', 17], ['\\x12', 18], ['\\x13', 19], ['\\x14', 20], ['\\x15', 21], ['\\x16', 22], ['\\x17', 23], ['\\x18', 24], ['\\x19', 25], ['\\x1a', 26], ['\\x1b', 27], ['\\x1c', 28], ['\\x1d', 29], ['\\x1e', 30], ['\\x1f', 31], [' ', 32], ['!', 33], ['\"', 34], ['#', 35], ['$', 36], ['%', 37], ['&', 38], [\"'\", 39], ['(', 40], [')', 41], ['*', 42], ['+', 43], [',', 44], ['-', 45], ['.', 46], ['/', 47], ['0', 48], ['1', 49], ['2', 50], ['3', 51], ['4', 52], ['5', 53], ['6', 54], ['7', 55], ['8', 56], ['9', 57], [':', 58], [';', 59], ['<', 60], ['=', 61], ['>', 62], ['?', 63], ['@', 64], ['A', 65], ['B', 66], ['C', 67], ['D', 68], ['E', 69], ['F', 70], ['G', 71], ['H', 72], ['I', 73], ['J', 74], ['K', 75], ['L', 76], ['M', 77], ['N', 78], ['O', 79], ['P', 80], ['Q', 81], ['R', 82], ['S', 83], ['T', 84], ['U', 85], ['V', 86], ['W', 87], ['X', 88], ['Y', 89], ['Z', 90], ['[', 91], ['\\\\', 92], [']', 93], ['^', 94], ['_', 95], ['`', 96], ['a', 97], ['b', 98], ['c', 99], ['d', 100], ['e', 101], ['f', 102], ['g', 103], ['h', 104], ['i', 105], ['j', 106], ['k', 107], ['l', 108], ['m', 109], ['n', 110], ['o', 111], ['p', 112], ['q', 113], ['r', 114], ['s', 115], ['t', 116], ['u', 117], ['v', 118], ['w', 119], ['x', 120], ['y', 121], ['z', 122], ['{', 123], ['|', 124], ['}', 125], ['~', 126], ['\\x7f', 127], ['\\x80', 128], ['\\x81', 129], ['\\x82', 130], ['\\x83', 131], ['\\x84', 132], ['\\x85', 133], ['\\x86', 134], ['\\x87', 135], ['\\x88', 136], ['\\x89', 137], ['\\x8a', 138], ['\\x8b', 139], ['\\x8c', 140], ['\\x8d', 141], ['\\x8e', 142], ['\\x8f', 143], ['\\x90', 144], ['\\x91', 145], ['\\x92', 146], ['\\x93', 147], ['\\x94', 148], ['\\x95', 149], ['\\x96', 150], ['\\x97', 151], ['\\x98', 152], ['\\x99', 153], ['\\x9a', 154], ['\\x9b', 155], ['\\x9c', 156], ['\\x9d', 157], ['\\x9e', 158], ['\\x9f', 159], ['\\xa0', 160], ['\u00a1', 161], ['\u00a2', 162], ['\u00a3', 163], ['\u00a4', 164], ['\u00a5', 165], ['\u00a6', 166], ['\u00a7', 167], ['\u00a8', 168], ['\u00a9', 169], ['\u00aa', 170], ['\u00ab', 171], ['\u00ac', 172], ['\\xad', 173], ['\u00ae', 174], ['\u00af', 175], ['\u00b0', 176], ['\u00b1', 177], ['\u00b2', 178], ['\u00b3', 179], ['\u00b4', 180], ['\u00b5', 181], ['\u00b6', 182], ['\u00b7', 183], ['\u00b8', 184], ['\u00b9', 185], ['\u00ba', 186], ['\u00bb', 187], ['\u00bc', 188], ['\u00bd', 189], ['\u00be', 190], ['\u00bf', 191], ['\u00c0', 192], ['\u00c1', 193], ['\u00c2', 194], ['\u00c3', 195], ['\u00c4', 196], ['\u00c5', 197], ['\u00c6', 198], ['\u00c7', 199], ['\u00c8', 200], ['\u00c9', 201], ['\u00ca', 202], ['\u00cb', 203], ['\u00cc', 204], ['\u00cd', 205], ['\u00ce', 206], ['\u00cf', 207], ['\u00d0', 208], ['\u00d1', 209], ['\u00d2', 210], ['\u00d3', 211], ['\u00d4', 212], ['\u00d5', 213], ['\u00d6', 214], ['\u00d7', 215], ['\u00d8', 216], ['\u00d9', 217], ['\u00da', 218], ['\u00db', 219], ['\u00dc', 220], ['\u00dd', 221], ['\u00de', 222], ['\u00df', 223], ['\u00e0', 224], ['\u00e1', 225], ['\u00e2', 226], ['\u00e3', 227], ['\u00e4', 228], ['\u00e5', 229], ['\u00e6', 230], ['\u00e7', 231], ['\u00e8', 232], ['\u00e9', 233], ['\u00ea', 234], ['\u00eb', 235], ['\u00ec', 236], ['\u00ed', 237], ['\u00ee', 238], ['\u00ef', 239], ['\u00f0', 240], ['\u00f1', 241], ['\u00f2', 242], ['\u00f3', 243], ['\u00f4', 244], ['\u00f5', 245], ['\u00f6', 246], ['\u00f7', 247], ['\u00f8', 248], ['\u00f9', 249], ['\u00fa', 250], ['\u00fb', 251], ['\u00fc', 252], ['\u00fd', 253], ['\u00fe', 254], ['\u00ff', 255], ['#0', 256], ['#1', 257], ['#2', 258], ['#3', 259], ['#4', 260], ['#5', 261], ['#6', 262], ['#7', 263], ['#8', 264], ['#9', 265], ['#10', 266], ['#11', 267], ['#12', 268], ['#13', 269], ['#14', 270], ['#15', 271], ['#16', 272], ['#17', 273], ['#18', 274], ['#19', 275], ['#20', 276], ['#21', 277], ['#22', 278], ['#23', 279], ['#24', 280], ['#25', 281], ['#26', 282], ['#27', 283], ['#28', 284], ['#29', 285], ['#30', 286], ['#31', 287], ['#32', 288], ['#33', 289], ['#34', 290], ['#35', 291], ['#36', 292], ['#37', 293], ['#38', 294], ['#39', 295], ['#40', 296], ['#41', 297], ['#42', 298], ['#43', 299]]\n"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A partir du code $256$ viennent les symboles \\# $k$."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\n",
      "def Trouve_ID(symbole,n) :\n",
      "    \"\"\" fonction trouvant le code de symbole \"\"\"\n",
      "    k=0\n",
      "    L=Calibrage_Symboles(n)\n",
      "    while k<n and L[k][0] != symbole   :\n",
      "        k+=1\n",
      "    return k\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 26
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(Trouve_ID(\"[\",300))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "91\n"
       ]
      }
     ],
     "prompt_number": 27
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Trouve_Symbole(Id,n) :\n",
      "    \"\"\" fonction trouvant le symbole associ\u00e9 \u00e0 un code modulo n \"\"\"\n",
      "    return Calibrage_Symboles(n)[Id%n][0]\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 28
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(Trouve_Symbole(400,300)) "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "d\n"
       ]
      }
     ],
     "prompt_number": 29
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Fonction d'exponentiation rapide r\u00e9cursive"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Afin de gagner en rapidit\u00e9 lors de calculs de puissances, on opte pour l'exponentiation rapide en ${\\cal O}(\\log p)$, o\u00f9 $p$ est la puissance, meilleure que la complexit\u00e9 lin\u00e9aire d'une exponentiation classique."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Expo(x,p,n) :\n",
      "    \"\"\" calcule x**p modulo n\"\"\"\n",
      "    if p==0 :\n",
      "        return 1\n",
      "    else :\n",
      "        if p%2==0 :\n",
      "            val_Temp=Expo(x,p//2,n)\n",
      "            return (val_Temp*val_Temp)%n\n",
      "        else :\n",
      "            val_Temp=Expo(x,(p-1)//2,n)\n",
      "            return (x*val_Temp*val_Temp)%n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 30
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for k in range(10) :\n",
      "    print(Expo(3,k,100))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n",
        "3\n",
        "9\n",
        "27\n",
        "81\n",
        "43\n",
        "29\n",
        "87\n",
        "61\n",
        "83\n"
       ]
      }
     ],
     "prompt_number": 31
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Cryptage proprement dit "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\n",
      "Cles=Generation_Cles()\n",
      "\n",
      "def Cryptage_RSA(message_en_clair) :\n",
      "    \"\"\" code selon RSA et la cl\u00e9 publique le message \"\"\"\n",
      "    global Cles # pour envisager le d\u00e9cryptage ...\n",
      "    message_Temp=[]\n",
      "     \n",
      "    n,e=Cles[0][0],Cles[0][1]\n",
      "    for symbole in message_en_clair :\n",
      "        message_Temp.append(Trouve_Symbole(Expo(Trouve_ID(symbole,n),e,n),n))\n",
      "    return message_Temp\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 32
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "On choisit de g\u00e9n\u00e9rer non pas une cha\u00eene de caract\u00e8res, mais une liste de symboles, pour ainsi d\u00e9limiter plus facilement le symboles les uns des autres. On affiche par contre la cha\u00eene de caract\u00e8res correspondant au cryptogramme :"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(''.join(Cryptage_RSA(\"message_en_clair\")))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "#12818#21896#12998#12998#30616#89#21896#11902#21896#30518#11902#18671#15173#30616#7030#23624\n"
       ]
      }
     ],
     "prompt_number": 33
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "D\u00e9cryptage"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Decryptage_RSA(message_crypte) :\n",
      "    global Cles\n",
      "    message_Temp=[]\n",
      "    n,d=Cles[1][0],Cles[1][1]\n",
      "    for symbole in message_crypte :\n",
      "        message_Temp.append(Trouve_Symbole(Expo(Trouve_ID(symbole,n),d,n),n))\n",
      "    return message_Temp"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 34
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "On essaie une transmission :"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "    \n",
      "message=\"Probl\u00e8me P=NP ... difficile !\"\n",
      "\n",
      "print(\"message initial :\\n\",message)\n",
      "Cles=Generation_Cles() # \u00e0 chaque ex\u00e9cution, une nouvelle cl\u00e9 est cr\u00e9\u00e9e\n",
      "print(\"Cl\u00e9 publique connue de tous :\\n \",Cles[0])\n",
      "\n",
      "message_crypte=Cryptage_RSA(message)\n",
      "print(\"message crypt\u00e9 : \\n\",''.join(message_crypte))\n",
      "\n",
      "print(\"message d\u00e9crypt\u00e9 :\\n\",''.join(Decryptage_RSA(message_crypte)))\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "message initial :\n",
        " Probl\u00e8me P=NP ... difficile !\n",
        "Cl\u00e9 publique connue de tous :\n",
        " "
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " [137843, 96265]\n",
        "message crypt\u00e9 : \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " #51908#35329#75065#128887#22349#84588#64677#96760#50380#51908#14066#82971#51908#50380#12377#12377#12377#50380#110098#70468#105160#105160#70468#29480#70468#22349#96760#50380#98631\n",
        "message d\u00e9crypt\u00e9 :\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " Probl\u00e8me P=NP ... difficile !\n"
       ]
      }
     ],
     "prompt_number": 35
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Cryptanalyse du RSA"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Le tr\u00e8s gros avantage du syst\u00e8me de codage RSA est que les deux interlocuteurs $A$ et $B$ peuvent \u00e9changer \u00e0 distance : la cl\u00e9 publique est connue de tous alors que seul $B$ est d\u00e9tenteur de la cl\u00e9 priv\u00e9e.\n",
      " \n",
      "Une personne $C$ qui tenterait d'intercepter la communication serait donc en possession des \u00e9l\u00e9ments suivants :\n",
      "\n",
      "$\\bullet$ le cryptogramme, donc chaque $s^e$\n",
      "\n",
      "$\\bullet$ la cl\u00e9 publique $(n,e)$.\n",
      "\n",
      "L'int\u00e9r\u00eat de choisir des nombres premiers $p$ et $q$ grands est double :\n",
      "\n",
      "$\\rhd$ permettre d'avoir un entier $n=p~q$ sup\u00e9rieur \u00e0 $256$, permettant de coder les $256$ codes ASCII usuels en le $256$ premiers \u00e9l\u00e9ments de $\\mathbb{Z}/n\\mathbb{Z}$\n",
      "\n",
      "$\\rhd$ rendre tr\u00e8s compliqu\u00e9 le calcul de $d=e^{-1}$ et de mani\u00e8re implicite, de rendre impossible en temps raisonnable la d\u00e9composition en facteurs premiers de l'entier $n$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Les nombres de Mersenne sont les nombres de la forme : $M_p=2^p-1$."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def Mersenne(p) :\n",
      "    return 2**p-1\n",
      "\n",
      "print([Mersenne(p) for p in range(2,7)])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[3, 7, 15, 31, 63]\n"
       ]
      }
     ],
     "prompt_number": 36
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Les nombres $M_2=3$ ou $M_3=7$ sont premiers, alors que les nombres $M_4$ ou $M_6$ ne le sont pas.\n",
      "\n",
      "Le **Great Internet Mersenne Prime Search**, ou **GIMPS** est un projet li\u00e9 \u00e0 la recherche de grands nombres premiers de Mersenne, lesquels peuvent justement servir pour un codage RSA efficace.\n",
      "\n",
      "Le test de primalit\u00e9 utilis\u00e9 par ce projet est le test de *Lucas-Lehmer*, dont voici le principe :\n",
      "\n",
      "$\\bullet$ si $M_p$ est premier, alors $p$ est premier : on ne teste que les nombres o\u00f9 $p$ est premier (que l'on teste avec un algorithme de base)\n",
      "\n",
      "$\\bullet$ on d\u00e9finit la suite r\u00e9currente : $s_0=4$ et $s_{i+1}={s_i}^2-1$. Alors on a l'\u00e9quivalence suivante :\n",
      "\n",
      "$M_p$ est premier $\\Longleftrightarrow$ $s_{p-1}=0~[M_p]$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "En f\u00e9vrier 2013, le $48^{\\grave{e}me}$ nombre premier de Mersenne a \u00e9t\u00e9 d\u00e9couvert.\n",
      "\n",
      "Il s'agit de : $M_{57 885 161}=2^{57 885 161}-1$.\n",
      "\n",
      "Ce nombre gigantesque compte plus de $17$ millions de chiffres. Il faudrait un fichier texte de 22 Mo pour stocker ces chiffres.\n",
      "\n",
      "A titre de comparaison, il n'existe seulement que moins de $10^{100}$ particules dans l'univers connu (neutrons, protons, \u00e9lectrons).\n",
      "\n",
      "En janvier 2016, le $49^{\\grave{e}me}$ nombre premier de Mersenne a \u00e9t\u00e9 d\u00e9couvert. Il s'agit de : $M_{74 207 281}=2^{74 207 281}-1$. Il comporte plus de $22$ millions de chiffres en base $10$.\n",
      "\n",
      "Actuellement, le syst\u00e8me de codage RSA est encore pleinement utilis\u00e9 pour coder des donn\u00e9es bancaires sur le net par exemple.\n",
      "\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 36
    }
   ],
   "metadata": {}
  }
 ]
}