{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# M1 Cryptographie - Cryptographie asymétrique\n",
    "\n",
    "La cryptographie classique (symétrique) permet à deux utilisateurs A (Alice) et B (Bob) de communiquer confidentiellement\n",
    "en partageant une clef secrète $K$. Ainsi, Eve (eavesdropper) qui intercepte la communication ne peut pas la déchiffrer.\n",
    "\n",
    "Le problème qui s'est immédiatement posé avec l'apparition des réseaux informatiques est celui de la distribution des clefs.\n",
    "Avec un réseau de $N$ noeuds, tous susceptibles de communiquer entre eux ou d'intercepter le traffic, chaque utilisateur\n",
    "devrait posséder $\\frac{N(N-1)}{2}$ clefs, une pour chaque lien bidirectionnel, ce qui est évidemment impossible.\n",
    "\n",
    "En 1976, dans un [article historique](new_directions_in_cryptography.pdf), Diffie et Hellman ont proposé (sans savoir à l'époque comment la réaliser), l'idée de *cryptographie à clef publique*, avec laquelle chaque utilisateur du réseau posséderait deux clefs,\n",
    "une *publique* $K_P$, accessible à tous les autres, et une *secrète* $K_S$, connue de lui seul.\n",
    "\n",
    "On devrait pouvoir chiffrer un message destiné à un utilisateur en connaissant seulement sa clef publique, mais ne pouvoir déchiffrer le cryptogramme  qu'en connaissant en plus sa clef secrète.\n",
    "\n",
    "Plusieurs systèmes ont alors été proposés pour satisfaire ces contraintes, apparemment inconciliables. L'idée générale est d'utiliser des problèmes algorithmiquement difficiles, mais dont certaines instances sont faciles.\n",
    "\n",
    "## Le système de Merkle-Hellman\n",
    "\n",
    "Le [premier système proposé](https://fr.wikipedia.org/wiki/Cryptosyst%C3%A8me_de_Merkle-Hellman), dû à Merkle et Hellman, reposait sur le problème du sac-à-dos : il est généralement difficile de savoir si un grand nombre $N$ peut s'écrire comme somme d'une \n",
    "sous-liste d'une liste  de nombres donnée, mais le problème est trivial si la liste en question est par exemple \n",
    "$1,2,4,8,\\ldots,2^m$ : cela revient à écrire $N$ en binaire. Il existe d'autres instances faciles, les suites super-croissantes,\n",
    "c'est à dire, dans lesquelles chaque terme est strictement supérieur à la somme des précédents..\n",
    "On en choisit une qu'on garde secrète, $A=[a_0,a_1,\\ldots,a_{n-1}]$ et on publie $B=[b_0,b_1,\\ldots,b_{n-1}$ où $b_i=ka_i\\mod M$ où\n",
    "$M$ est un grand nombre $>a_0+a_1+\\cdots+a_n$, et $k$ un entier inversible modulo $M$. On pose $d=k^{-1}\\mod M$.\n",
    "\n",
    "La clef publique est $B$, la clef secrète est $(A,k,M)$. Les messages sont des blocs de $n$ bits. \n",
    "\n",
    "Le cryptogramme de\n",
    "$$m = (m_0,\\ldots,m_{n-1})\\in \\{0,1\\}^n$$ \n",
    "est \n",
    "$$c = \\sum_{i=0}^{n-1}m_i b_i$$\n",
    "Pour déchiffrer, le destinataire calcule\n",
    "$$ s = lc\\mod M = \\sum_{i=0}^{n-1}m_ia_i$$\n",
    "et retrouve les $m_i$ en résolvant le problème facile.\n",
    "\n",
    "Ce système a été rapidement [craqué](crack_merkle_hellman.pdf), et par conséquent abandonné.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## RSA\n",
    "\n",
    "Le premier système à résister sérieusement a été RSA, initiales de Rivest-Shamir-Adelman. Il est encore le plus utilisé.\n",
    "Il repose sur la difficulté de la factorisation des grands entiers. Si on multiplie deux grands nombres premiers $p$ et $q$,\n",
    "il est impossible en pratique de retrouver $p$ et $q$ à partir de $n=pq$.\n",
    "\n",
    "Pour construire une clef RSA, on tire au hasard deux nombres premiers $p<q$ de $N$ bits, et on calcule $n=pq$ (le *module*).\n",
    "On calcule aussi $\\varphi(n)=(p-1)(q-1)$ (indicatrice d'Euler).\n",
    "\n",
    "On choisit ensuite un *exposant public* $2\\lt e\\lt n-1$, qui doit être inversible modulo $\\varphi(n)$, et on calcule son inverse\n",
    "$d = e^{-1}\\mod \\varphi(n)$ (l'*exposant privé*). On a donc $ed=1+k\\varphi(n)$ pour un certain $k$.\n",
    "\n",
    "Dans la description originale, $d$ est choisi au hasard et $e$ calculé ensuite,\n",
    "mais pour des raisons pratiques on utilise souvent les valeurs $e=3,17,257$ ou $65537$.\n",
    "\n",
    "La clef publique est $(n,e)$, la clef secrète est $(p,q,d)$.\n",
    "\n",
    "Les messages à chiffrer sont des blocs de $2N$ bits, interprétés comme des entiers modulo $n$. Pour chiffrer un tel message $m$,\n",
    "on calcule\n",
    "$$ c= m^e \\mod n.$$\n",
    "Pour déchiffrer $c$, le destinataire calcule\n",
    "$$ c^d \\mod n = m^{ed} \\mod n = m^{1+k\\varphi(n)} \\mod n = m^1 (m^{\\varphi(n)})^k \\mod n = m$$\n",
    "au moins si $m$ est premier avec $\\varphi(n)$ d'après le théorème d'Euler, et en fait dans tous les cas, à cause\n",
    "de la forme spéciale de $n$.\n",
    "\n",
    "On a \n",
    "$$c^d = m(m^{k(q-1)})^{p-1}\\equiv m \\mod p$$\n",
    "$$c^d = m(m^{k(p-1)})^{q-1}\\equiv m \\mod q$$\n",
    "d'après le théorème de Fermat, et on peut donc retrouver $m$ à partir de $m_p = c^d\\mod p$ et $m_q=c^d\\mod q$ en appliquant le théorème des reste chinois.\n",
    "\n",
    "En pratique, on complète la clef secrète avec\n",
    "$$d_p = d\\mod (p-1)$$\n",
    "$$d_q = d\\mod (q-1)$$\n",
    "$$q_{inv} = q^{-1}\\mod p$$\n",
    "et le déchiffrement est obtenu en calculant\n",
    "$$m_1 = c^{d_p}\\mod p$$\n",
    "$$m_2 = c^{d_q}\\mod q$$\n",
    "$$h = (m_1-m_2)q_{inv} \\mod p$$\n",
    "$$ m = m_2+hq.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Construisons une clef RSA de 512 bits\n",
    "from random import randrange\n",
    "from ent3 import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "26500187408045894646773779047611999515297724476034815358742346965632430907347"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = randrange(2*255,2**256-1)\n",
    "if not a%2: a+=1\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "while not miller_rabin(a):a+=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "p=a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = randrange(p,2**256-1)\n",
    "if not b%2: b+=1\n",
    "while not miller_rabin(b):b+=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "q=b "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3a969315486e392c3dfbeb9046d7a25e2cefd3ed32fb68dd5f26ac5564e8204f\n",
      "d0c3fdec83717e5c79b926bb62a3dc585a5930cb147ba0f9aac225809073f587\n"
     ]
    }
   ],
   "source": [
    "print ('%x' % p)\n",
    "print ('%x' % q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2502342741777978305394161689835161800308635593678070233706745739850497379826016189955751135672383376951956116000952438972760111920886781584882452875289769\n"
     ]
    }
   ],
   "source": [
    "n = p*q\n",
    "print (n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1129462093565157523057286988408088594691835520881930533501877454562870412684061674861262502135092940232711653086400913818719717504109788414970713354381073\n"
     ]
    }
   ],
   "source": [
    "phi_n = (p-1)*(q-1)\n",
    "e = 257\n",
    "d = inversemod(e,phi_n)\n",
    "print (d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "d1, d2, q_inv  = d % (p-1), d % (q-1), inversemod(q,p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20519600366541373675906544865660653321183841131248748079337459323583088523683\n",
      "734843270047991781736235626626299541236651911309911826448204008511863643661\n",
      "16059359551391899448053333558918060785093890179516929488208050776761986861230\n"
     ]
    }
   ],
   "source": [
    "print (d1)\n",
    "print (d2)\n",
    "print (q_inv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from codecs import encode, decode\n",
    "def text2int(t):\n",
    "    assert len(t) <= 64 # 64*8 = 512 bits\n",
    "    if isinstance(t,str):\n",
    "        return int(encode(t.encode(),'hex'), 16) # t.encode() nécessaire en Python 3 pour avoir des bytes\n",
    "    elif isinstance(t,bytes):\n",
    "        return int(encode(t,'hex'), 16)\n",
    "    \n",
    "\n",
    "def int2text(m):\n",
    "    s = '%x' % m\n",
    "    if len(s)%2: s = '0'+s\n",
    "    return decode(s, 'hex')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2482049485033484295509148869034669333161266776700492625573073315249287942938347748044373827617\n"
     ]
    }
   ],
   "source": [
    "msg = \"L'arithmétique, c'est bien difficile !\"\n",
    "m = text2int(msg)\n",
    "print (m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b\"L'arithm\\xc3\\xa9tique, c'est bien difficile !\""
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "msg.encode() # l'encodage par défaut est celui du système "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b\"L'arithm\\xc3\\xa9tique, c'est bien difficile !\""
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "msg.encode('utf8')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1424921898341682605762331838499604971017849285555226544151583141753235703470686191844906762174964147363721712002777200150575835094876121346964116166603823\n"
     ]
    }
   ],
   "source": [
    "# Chiffrement\n",
    "c = pow(m,e,n)\n",
    "print (c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2482049485033484295509148869034669333161266776700492625573073315249287942938347748044373827617\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "b\"L'arithm\\xc3\\xa9tique, c'est bien difficile !\""
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Déchiffrement\n",
    "test = pow(c,d,n)\n",
    "print (test)\n",
    "int2text(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "L'arithmétique, c'est bien difficile !\n"
     ]
    }
   ],
   "source": [
    "print(_.decode('utf8'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2482049485033484295509148869034669333161266776700492625573073315249287942938347748044373827617\n",
      "L'arithmétique, c'est bien difficile !\n"
     ]
    }
   ],
   "source": [
    "# Déchiffrement accéléré avec les paramètres précalculés\n",
    "m1, m2 = pow(c,d1,p), pow(c,d2,q)\n",
    "h = (m1-m2)*q_inv % p\n",
    "test2 = m2 + h*q\n",
    "print (test2)\n",
    "print (int2text(test2).decode('utf8'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b'4c2761726974686dc3a974697175652c206327657374206269656e20646966666963696c652021'\n",
      "2fc732504450614349ff94bc8282afec9a4bd4d96ecaf31e0e32634c0e37f62fbd0a487f2196ac8df264720fe7b61e6be22857cf82cc9498960b138d50d1a4a9\n"
     ]
    }
   ],
   "source": [
    "print (encode(msg.encode(),'hex'))\n",
    "print ('%x'%n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notre message était sensiblement plus court que la clef. \n",
    "En pratique, pour éviter de chiffrer des blocs de zéros, qui risqueraient de révéler des indications sur la clef secrère, et pour éviter\n",
    "que deux messages identiques soient chiffrés de la même manière, on remplace les octets nuls par un bourrage aléatoire, respectant\n",
    "une norme telle que [PKCS #1](https://tools.ietf.org/html/rfc2313). \n",
    "\n",
    "Par exemple, avec un module de $k$ octets, on transmettra des entiers $D$ de moins de $k-11$ octets, sous forme de blocs\n",
    "de $k$ octets ayant la structure\n",
    "\n",
    "```00 02 ||bourrage||00||D```\n",
    "\n",
    "où le bourrage est consitué d'octets aléatoires non nuls.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b\"\\x00\\x02\\xab\\xd2\\xf7P\\xdf\\t\\x9eM\\xa5\\xf0\\xba\\xd6\\xf8\\xc7\\xb4\\xe9k\\xec\\xdbF\\xcf\\\\\\x00L'arithm\\xc3\\xa9tique, c'est bien difficile !\""
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def pad(D,k,random=True):\n",
    "    assert len(D)<k-11\n",
    "    m = k-3-len(D)\n",
    "    s = open('/dev/urandom','rb').read(m).replace(b'\\x00',b'\\xff')\n",
    "    res = b'\\x00\\x02'+s+b'\\x00'+D\n",
    "    return res\n",
    "\n",
    "D = msg.encode()\n",
    "\n",
    "P = pad(D,64); P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "39"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(D)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "546490073573023782919833310723505366415935528325926911697419548819970651491447084662782218655660251683607633278569570342040339125483138841796956987425"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = text2int(P)\n",
    "m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2295163261149511403305503728933624368514007681287606939863821243050574765579241828142902110121753137764180975920166834008405867299008418437194186758123539"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c = pow(m,e,n)\n",
    "c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b\"\\x02\\xab\\xd2\\xf7P\\xdf\\t\\x9eM\\xa5\\xf0\\xba\\xd6\\xf8\\xc7\\xb4\\xe9k\\xec\\xdbF\\xcf\\\\\\x00L'arithm\\xc3\\xa9tique, c'est bien difficile !\""
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test3 = pow(c,d,n)\n",
    "int2text(test3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## RSA en pratique\n",
    "\n",
    "Le premier endroit où observer des clefs RSA sur un système Unix est le répertoire `.ssh` d'un utilisateur.\n",
    "\n",
    "Avant un première utilisation, on crée les clefs par la commande\n",
    "\n",
    "```\n",
    "$ ssh-keygen\n",
    "Generating public/private rsa key pair.\n",
    "Enter file in which to save the key (/home/jyt/.ssh/id_rsa): ./.ssh/id_rsa\n",
    "Enter passphrase (empty for no passphrase): \n",
    "Enter same passphrase again: \n",
    "Your identification has been saved in ./.ssh/id_rsa.\n",
    "Your public key has been saved in ./.ssh/id_rsa.pub.\n",
    "The key fingerprint is:\n",
    "56:1d:12:06:7d:4d:96:52:1d:83:d5:de:c6:3b:39:f7 jyt@scriabine\n",
    "The key's randomart image is:\n",
    "+--[ RSA 2048]----+\n",
    "|        .o+..+**o|\n",
    "|         ..oo+o +|\n",
    "|          .... o.|\n",
    "|         .      =|\n",
    "|        S      .o|\n",
    "|       .       =.|\n",
    "|                =|\n",
    "|                E|\n",
    "|                 |\n",
    "+-----------------+\n",
    "$ ls .ssh\n",
    "id_rsa  id_rsa.pub\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On n'a pas précisé de paramètres, la commande a donc crée par défaut une clef RSA de 2048 bits.\n",
    "La clef secrète est dans `id_rsa`, la clef publique dans `id_rsa.pub`.\n",
    "\n",
    "Examinons ces fichiers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQC/rbeMXySUYh1A728Vocv9oaijeVOUF9sKzqUBVfAR6PNXtaMYqY49gFM/YvlYSDKwmurF1sVMts9DWS1ofAbu1TqqOScGex2bbVrCfhxWyEcT5PlYnPYBlaJ7/1USbeHWgeFHIArfOzeknEvjsecwoxjOgzRDCRD9q9Pa35PX9IDgGF5z2ojAG5p84sYtJaLvHiSDUxfjZ/0d2aNJ6vKQ7jJhNJxqGmFpwQ+XKSIZ/oS1OffCMvn/cQGXjc14Litl1hdQf8pky6r6TPdUYS62o1qjDsFs1BB9xFnRGDH9BkWaHdychICHsUy3nmBsYgxqMwAfg1olwYNs5Vrqca7x jyt@elzet\r\n"
     ]
    }
   ],
   "source": [
    "!cat .ssh/id_rsa.pub"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----BEGIN RSA PRIVATE KEY-----\r\n",
      "MIIEowIBAAKCAQEAv623jF8klGIdQO9vFaHL/aGoo3lTlBfbCs6lAVXwEejzV7Wj\r\n",
      "GKmOPYBTP2L5WEgysJrqxdbFTLbPQ1ktaHwG7tU6qjknBnsdm21awn4cVshHE+T5\r\n",
      "WJz2AZWie/9VEm3h1oHhRyAK3zs3pJxL47HnMKMYzoM0QwkQ/avT2t+T1/SA4Bhe\r\n",
      "c9qIwBuafOLGLSWi7x4kg1MX42f9HdmjSerykO4yYTScahphacEPlykiGf6EtTn3\r\n",
      "wjL5/3EBl43NeC4rZdYXUH/KZMuq+kz3VGEutqNaow7BbNQQfcRZ0Rgx/QZFmh3c\r\n",
      "nISAh7FMt55gbGIMajMAH4NaJcGDbOVa6nGu8QIDAQABAoIBAHgxLyJXWrGs4Fki\r\n",
      "io6O+UIeh4eSgaUgXFrnfzJaOAKTB1wdapsBX08TU6AwqNgB1b9GNSc/aFKVY1wA\r\n",
      "5GdbNmG21WV+FwmKU+Nta/b/azfDuEYyU2SMb/pIYS3NywOWYYHHyYJ3Bjo6gMa4\r\n",
      "tyGdIbIu41RDk5bhbYUTpPHfNm64LfTM/ZZUwfZGzPCv3VPDXLy2ws2NWWRcAyBH\r\n",
      "F6hMpS/ARTHKrssjz2MvvF0BmcvDRK1D//hmXbbK7LXJsjR63YCpFSAepXfrktyf\r\n",
      "8ILrnnatfmoO9DyEQQ56kceGALbyE/zy6frqw74MnTwoiLdiZxGeY4YIezWYL8SR\r\n",
      "HwwFOpECgYEA3aqnqAFbRLbzv5fU56gTO63EzOgCYN+2P0WrnH0BKK7AySxrtDgj\r\n",
      "4vhEoI5QpBZ42H9pza3WZNFZ1hCnIIH/EXR/ZIOX8N+TMus8d8d378JBlg36W8F8\r\n",
      "tEWjn6kW6kY8Yyjw7Hs+3jYqnDeIETeIQzzcm7pRViH8xw7NHbO3z+UCgYEA3V4A\r\n",
      "LMe9MOrVBT1YfFboQGuYGdO9qZRL4wH1oBe+9tbP3p5rLL7OsMid64A9aS4ebdGa\r\n",
      "CPlBUM3tr1NbHez9JbgpNLooCNLNV5iJn4iMt5yAyKpZ3DAwFgorTZ6iVdfAAUi1\r\n",
      "o02Qq407va7tjpd/9ded/I9U2wfT4Jy1L86ceh0CgYBbNfiM6hn7GWkNAlXqCL/5\r\n",
      "Q5SCWEl6QTOFr45g8xMCAX50iSG8Y4lowI3EnyrRiimptCv+JTTeAUL9EZcjijpB\r\n",
      "nXU6D+f6hpTUU/VquBpC/uTr8M5+6Qv+RdWBQhuaxNHeX59bP49r8k/wPe1wYDBi\r\n",
      "sm14at9DGPMhmZaPTT8qfQKBgQC+saNk8AvCgAlRoi7/rb4VAJreZNEVrHJS8/Us\r\n",
      "HEidSx92nvGkchqLn8aqgKZmXRxJbi5LXK0vdrYyOpRbizPnsmWMznB+aVoLA5RK\r\n",
      "oc7WvTMTqewPClPiKJB1JRqi6GC2unP+YWsm3VuBY5exJkFM/plSYAaxSGT1MQnE\r\n",
      "TS/u4QKBgHhygHlkyxpbcOGUAj/4puB1lLB6gzZfbDQVxi95VLBeR33+DUCi2FNR\r\n",
      "tmZoYJqsSO1G5DsEa7p4locjVjEMOGLmxm2vDlv6A6Rgip4l31OywMj/oMJVBpAM\r\n",
      "C3xh7uUSbfhMYRWWEcD+1X/7Nfmr2g7AswqLbzjDFU6o8POjV66m\r\n",
      "-----END RSA PRIVATE KEY-----\r\n"
     ]
    }
   ],
   "source": [
    "!cat .ssh/id_rsa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ils sont manifestement encodés en base64. Essayons de déchiffrer leur contenu, en commençant par la clef publique qui est plus simple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = open('.ssh/id_rsa.pub','rb').read()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'\\x00\\x00\\x00\\x07ssh-rsa\\x00\\x00\\x00\\x03\\x01\\x00\\x01\\x00\\x00\\x01\\x01\\x00\\xbf\\xad\\xb7\\x8c_$\\x94b\\x1d@\\xefo\\x15\\xa1\\xcb\\xfd\\xa1\\xa8\\xa3yS\\x94\\x17\\xdb\\n\\xce\\xa5\\x01U\\xf0\\x11\\xe8\\xf3W\\xb5\\xa3\\x18\\xa9\\x8e=\\x80S?b\\xf9XH2\\xb0\\x9a\\xea\\xc5\\xd6\\xc5L\\xb6\\xcfCY-h|\\x06\\xee\\xd5:\\xaa9\\'\\x06{\\x1d\\x9bmZ\\xc2~\\x1cV\\xc8G\\x13\\xe4\\xf9X\\x9c\\xf6\\x01\\x95\\xa2{\\xffU\\x12m\\xe1\\xd6\\x81\\xe1G \\n\\xdf;7\\xa4\\x9cK\\xe3\\xb1\\xe70\\xa3\\x18\\xce\\x834C\\t\\x10\\xfd\\xab\\xd3\\xda\\xdf\\x93\\xd7\\xf4\\x80\\xe0\\x18^s\\xda\\x88\\xc0\\x1b\\x9a|\\xe2\\xc6-%\\xa2\\xef\\x1e$\\x83S\\x17\\xe3g\\xfd\\x1d\\xd9\\xa3I\\xea\\xf2\\x90\\xee2a4\\x9cj\\x1aai\\xc1\\x0f\\x97)\"\\x19\\xfe\\x84\\xb59\\xf7\\xc22\\xf9\\xffq\\x01\\x97\\x8d\\xcdx.+e\\xd6\\x17P\\x7f\\xcad\\xcb\\xaa\\xfaL\\xf7Ta.\\xb6\\xa3Z\\xa3\\x0e\\xc1l\\xd4\\x10}\\xc4Y\\xd1\\x181\\xfd\\x06E\\x9a\\x1d\\xdc\\x9c\\x84\\x80\\x87\\xb1L\\xb7\\x9e`lb\\x0cj3\\x00\\x1f\\x83Z%\\xc1\\x83l\\xe5Z\\xeaq\\xae\\xf1'"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kp = decode(p[p.index(b'A'):p.index(b'jyt')], 'base64') # on découpe le morceau intéressant\n",
    "kp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On voit que la structure décodée se compose des 4 octets 0,0,0,7, de la chaîne « ssh-rsa ». Il y a ensuite un entier sur 32 bits en big-endian donnant la longueur de l'exposant public e (en octets, ici 3) , suivi de sa valeur, puis de la longueur de n (même système) et de sa valeur. On peut décoder avec le module struct sans trop de difficulté :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 0, 0, 7, b'ssh-rsa', 3, 1, 0, 1, 257, b'\\x00', b'\\xbf', b'\\xad', b'\\xb7', b'\\x8c', b'_', b'$', b'\\x94', b'b', b'\\x1d', b'@', b'\\xef', b'o', b'\\x15', b'\\xa1', b'\\xcb', b'\\xfd', b'\\xa1', b'\\xa8', b'\\xa3', b'y', b'S', b'\\x94', b'\\x17', b'\\xdb', b'\\n', b'\\xce', b'\\xa5', b'\\x01', b'U', b'\\xf0', b'\\x11', b'\\xe8', b'\\xf3', b'W', b'\\xb5', b'\\xa3', b'\\x18', b'\\xa9', b'\\x8e', b'=', b'\\x80', b'S', b'?', b'b', b'\\xf9', b'X', b'H', b'2', b'\\xb0', b'\\x9a', b'\\xea', b'\\xc5', b'\\xd6', b'\\xc5', b'L', b'\\xb6', b'\\xcf', b'C', b'Y', b'-', b'h', b'|', b'\\x06', b'\\xee', b'\\xd5', b':', b'\\xaa', b'9', b\"'\", b'\\x06', b'{', b'\\x1d', b'\\x9b', b'm', b'Z', b'\\xc2', b'~', b'\\x1c', b'V', b'\\xc8', b'G', b'\\x13', b'\\xe4', b'\\xf9', b'X', b'\\x9c', b'\\xf6', b'\\x01', b'\\x95', b'\\xa2', b'{', b'\\xff', b'U', b'\\x12', b'm', b'\\xe1', b'\\xd6', b'\\x81', b'\\xe1', b'G', b' ', b'\\n', b'\\xdf', b';', b'7', b'\\xa4', b'\\x9c', b'K', b'\\xe3', b'\\xb1', b'\\xe7', b'0', b'\\xa3', b'\\x18', b'\\xce', b'\\x83', b'4', b'C', b'\\t', b'\\x10', b'\\xfd', b'\\xab', b'\\xd3', b'\\xda', b'\\xdf', b'\\x93', b'\\xd7', b'\\xf4', b'\\x80', b'\\xe0', b'\\x18', b'^', b's', b'\\xda', b'\\x88', b'\\xc0', b'\\x1b', b'\\x9a', b'|', b'\\xe2', b'\\xc6', b'-', b'%', b'\\xa2', b'\\xef', b'\\x1e', b'$', b'\\x83', b'S', b'\\x17', b'\\xe3', b'g', b'\\xfd', b'\\x1d', b'\\xd9', b'\\xa3', b'I', b'\\xea', b'\\xf2', b'\\x90', b'\\xee', b'2', b'a', b'4', b'\\x9c', b'j', b'\\x1a', b'a', b'i', b'\\xc1', b'\\x0f', b'\\x97', b')', b'\"', b'\\x19', b'\\xfe', b'\\x84', b'\\xb5', b'9', b'\\xf7', b'\\xc2', b'2', b'\\xf9', b'\\xff', b'q', b'\\x01', b'\\x97', b'\\x8d', b'\\xcd', b'x', b'.', b'+', b'e', b'\\xd6', b'\\x17', b'P', b'\\x7f', b'\\xca', b'd', b'\\xcb', b'\\xaa', b'\\xfa', b'L', b'\\xf7', b'T', b'a', b'.', b'\\xb6', b'\\xa3', b'Z', b'\\xa3', b'\\x0e', b'\\xc1', b'l', b'\\xd4', b'\\x10', b'}', b'\\xc4', b'Y', b'\\xd1', b'\\x18', b'1', b'\\xfd', b'\\x06', b'E', b'\\x9a', b'\\x1d', b'\\xdc', b'\\x9c', b'\\x84', b'\\x80', b'\\x87', b'\\xb1', b'L', b'\\xb7', b'\\x9e', b'`', b'l', b'b', b'\\x0c', b'j', b'3', b'\\x00', b'\\x1f', b'\\x83', b'Z', b'%', b'\\xc1', b'\\x83', b'l', b'\\xe5', b'Z', b'\\xea', b'q', b'\\xae', b'\\xf1')\n"
     ]
    }
   ],
   "source": [
    "import struct\n",
    "ll = struct.unpack('!4B7sI3BI257c',kp)\n",
    "print (ll)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'exposant public est 0x010001 = 65537, et le module $n$ est obtenu à partir des 257 octets suivant la longueur 257 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24197179286847076751267479433531096843909808556802245716741850737709306610630209095849920785452573764685331100203869311911185589435045631598880460398180094783356081371040731411086573360175212809003571417615130967550083085172889965589447863323037820202564159411800029468070675092209232569824831755420473655291845994055252634351126006832264373276055321558278890539694434772450398306253177305863877630248829723619454994737708243342606106336309152591177066470311180531219923044630357544050235563465629102942455163945967779489025449096558359347845799748312800495268065956440209963378476890619202259560003463746530818764529\n"
     ]
    }
   ],
   "source": [
    "nn=ll[10:]\n",
    "N = int(''.join(map(lambda x: \"%02X\"%x, map(ord,nn))),16)\n",
    "print (N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " C'est donc $N$ qu'il faut factoriser si on veut craquer la clef.\n",
    "\n",
    "Le décodage de la clef privée est plus complexe. Elle est encodée avec le système [DER](http://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf) de l'Union Internationale des Télécommunications. Il existe un module Python, \n",
    "[pyasn1](http://snmplabs.com/pyasn1/index.html), qui peut décoder et réencoder."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Structure de la clef privée :\n",
    "\n",
    "<pre>\n",
    "-----BEGIN RSA PRIVATE KEY-----\n",
    "base64data\n",
    "-----END RSA PRIVATE KEY-----\n",
    "\n",
    "base64data DER structure:\n",
    "\n",
    "RSAPrivateKey ::= SEQUENCE {\n",
    "version Version,\n",
    "modulus INTEGER, -- n\n",
    "publicExponent INTEGER, -- e\n",
    "privateExponent INTEGER, -- d\n",
    "prime1 INTEGER, -- p\n",
    "prime2 INTEGER, -- q\n",
    "exponent1 INTEGER, -- d mod (p - 1)\n",
    "exponent2 INTEGER, -- d mod (q - 1)\n",
    "coefficient INTEGER -- q^-1 mod p\n",
    "}\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'-----BEGIN RSA PRIVATE KEY-----\\nMIIEowIBAAKCAQEAv623jF8klGIdQO9vFaHL/aGoo3lTlBfbCs6lAVXwEejzV7Wj\\nGKmOPYBTP2L5WEgysJrqxdbFTLbPQ1ktaHwG7tU6qjknBnsdm21awn4cVshHE+T5\\nWJz2AZWie/9VEm3h1oHhRyAK3zs3pJxL47HnMKMYzoM0QwkQ/avT2t+T1/SA4Bhe\\nc9qIwBuafOLGLSWi7x4kg1MX42f9HdmjSerykO4yYTScahphacEPlykiGf6EtTn3\\nwjL5/3EBl43NeC4rZdYXUH/KZMuq+kz3VGEutqNaow7BbNQQfcRZ0Rgx/QZFmh3c\\nnISAh7FMt55gbGIMajMAH4NaJcGDbOVa6nGu8QIDAQABAoIBAHgxLyJXWrGs4Fki\\nio6O+UIeh4eSgaUgXFrnfzJaOAKTB1wdapsBX08TU6AwqNgB1b9GNSc/aFKVY1wA\\n5GdbNmG21WV+FwmKU+Nta/b/azfDuEYyU2SMb/pIYS3NywOWYYHHyYJ3Bjo6gMa4\\ntyGdIbIu41RDk5bhbYUTpPHfNm64LfTM/ZZUwfZGzPCv3VPDXLy2ws2NWWRcAyBH\\nF6hMpS/ARTHKrssjz2MvvF0BmcvDRK1D//hmXbbK7LXJsjR63YCpFSAepXfrktyf\\n8ILrnnatfmoO9DyEQQ56kceGALbyE/zy6frqw74MnTwoiLdiZxGeY4YIezWYL8SR\\nHwwFOpECgYEA3aqnqAFbRLbzv5fU56gTO63EzOgCYN+2P0WrnH0BKK7AySxrtDgj\\n4vhEoI5QpBZ42H9pza3WZNFZ1hCnIIH/EXR/ZIOX8N+TMus8d8d378JBlg36W8F8\\ntEWjn6kW6kY8Yyjw7Hs+3jYqnDeIETeIQzzcm7pRViH8xw7NHbO3z+UCgYEA3V4A\\nLMe9MOrVBT1YfFboQGuYGdO9qZRL4wH1oBe+9tbP3p5rLL7OsMid64A9aS4ebdGa\\nCPlBUM3tr1NbHez9JbgpNLooCNLNV5iJn4iMt5yAyKpZ3DAwFgorTZ6iVdfAAUi1\\no02Qq407va7tjpd/9ded/I9U2wfT4Jy1L86ceh0CgYBbNfiM6hn7GWkNAlXqCL/5\\nQ5SCWEl6QTOFr45g8xMCAX50iSG8Y4lowI3EnyrRiimptCv+JTTeAUL9EZcjijpB\\nnXU6D+f6hpTUU/VquBpC/uTr8M5+6Qv+RdWBQhuaxNHeX59bP49r8k/wPe1wYDBi\\nsm14at9DGPMhmZaPTT8qfQKBgQC+saNk8AvCgAlRoi7/rb4VAJreZNEVrHJS8/Us\\nHEidSx92nvGkchqLn8aqgKZmXRxJbi5LXK0vdrYyOpRbizPnsmWMznB+aVoLA5RK\\noc7WvTMTqewPClPiKJB1JRqi6GC2unP+YWsm3VuBY5exJkFM/plSYAaxSGT1MQnE\\nTS/u4QKBgHhygHlkyxpbcOGUAj/4puB1lLB6gzZfbDQVxi95VLBeR33+DUCi2FNR\\ntmZoYJqsSO1G5DsEa7p4locjVjEMOGLmxm2vDlv6A6Rgip4l31OywMj/oMJVBpAM\\nC3xh7uUSbfhMYRWWEcD+1X/7Nfmr2g7AswqLbzjDFU6o8POjV66m\\n-----END RSA PRIVATE KEY-----\\n'"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = open('.ssh/id_rsa').read()\n",
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'0\\x82\\x04\\xa3\\x02\\x01\\x00\\x02\\x82\\x01\\x01\\x00\\xbf\\xad\\xb7\\x8c_$\\x94b\\x1d@\\xefo\\x15\\xa1\\xcb\\xfd\\xa1\\xa8\\xa3yS\\x94\\x17\\xdb\\n\\xce\\xa5\\x01U\\xf0\\x11\\xe8\\xf3W\\xb5\\xa3\\x18\\xa9\\x8e=\\x80S?b\\xf9XH2\\xb0\\x9a\\xea\\xc5\\xd6\\xc5L\\xb6\\xcfCY-h|\\x06\\xee\\xd5:\\xaa9\\'\\x06{\\x1d\\x9bmZ\\xc2~\\x1cV\\xc8G\\x13\\xe4\\xf9X\\x9c\\xf6\\x01\\x95\\xa2{\\xffU\\x12m\\xe1\\xd6\\x81\\xe1G \\n\\xdf;7\\xa4\\x9cK\\xe3\\xb1\\xe70\\xa3\\x18\\xce\\x834C\\t\\x10\\xfd\\xab\\xd3\\xda\\xdf\\x93\\xd7\\xf4\\x80\\xe0\\x18^s\\xda\\x88\\xc0\\x1b\\x9a|\\xe2\\xc6-%\\xa2\\xef\\x1e$\\x83S\\x17\\xe3g\\xfd\\x1d\\xd9\\xa3I\\xea\\xf2\\x90\\xee2a4\\x9cj\\x1aai\\xc1\\x0f\\x97)\"\\x19\\xfe\\x84\\xb59\\xf7\\xc22\\xf9\\xffq\\x01\\x97\\x8d\\xcdx.+e\\xd6\\x17P\\x7f\\xcad\\xcb\\xaa\\xfaL\\xf7Ta.\\xb6\\xa3Z\\xa3\\x0e\\xc1l\\xd4\\x10}\\xc4Y\\xd1\\x181\\xfd\\x06E\\x9a\\x1d\\xdc\\x9c\\x84\\x80\\x87\\xb1L\\xb7\\x9e`lb\\x0cj3\\x00\\x1f\\x83Z%\\xc1\\x83l\\xe5Z\\xeaq\\xae\\xf1\\x02\\x03\\x01\\x00\\x01\\x02\\x82\\x01\\x00x1/\"WZ\\xb1\\xac\\xe0Y\"\\x8a\\x8e\\x8e\\xf9B\\x1e\\x87\\x87\\x92\\x81\\xa5 \\\\Z\\xe7\\x7f2Z8\\x02\\x93\\x07\\\\\\x1dj\\x9b\\x01_O\\x13S\\xa00\\xa8\\xd8\\x01\\xd5\\xbfF5\\'?hR\\x95c\\\\\\x00\\xe4g[6a\\xb6\\xd5e~\\x17\\t\\x8aS\\xe3mk\\xf6\\xffk7\\xc3\\xb8F2Sd\\x8co\\xfaHa-\\xcd\\xcb\\x03\\x96a\\x81\\xc7\\xc9\\x82w\\x06::\\x80\\xc6\\xb8\\xb7!\\x9d!\\xb2.\\xe3TC\\x93\\x96\\xe1m\\x85\\x13\\xa4\\xf1\\xdf6n\\xb8-\\xf4\\xcc\\xfd\\x96T\\xc1\\xf6F\\xcc\\xf0\\xaf\\xddS\\xc3\\\\\\xbc\\xb6\\xc2\\xcd\\x8dYd\\\\\\x03 G\\x17\\xa8L\\xa5/\\xc0E1\\xca\\xae\\xcb#\\xcfc/\\xbc]\\x01\\x99\\xcb\\xc3D\\xadC\\xff\\xf8f]\\xb6\\xca\\xec\\xb5\\xc9\\xb24z\\xdd\\x80\\xa9\\x15 \\x1e\\xa5w\\xeb\\x92\\xdc\\x9f\\xf0\\x82\\xeb\\x9ev\\xad~j\\x0e\\xf4<\\x84A\\x0ez\\x91\\xc7\\x86\\x00\\xb6\\xf2\\x13\\xfc\\xf2\\xe9\\xfa\\xea\\xc3\\xbe\\x0c\\x9d<(\\x88\\xb7bg\\x11\\x9ec\\x86\\x08{5\\x98/\\xc4\\x91\\x1f\\x0c\\x05:\\x91\\x02\\x81\\x81\\x00\\xdd\\xaa\\xa7\\xa8\\x01[D\\xb6\\xf3\\xbf\\x97\\xd4\\xe7\\xa8\\x13;\\xad\\xc4\\xcc\\xe8\\x02`\\xdf\\xb6?E\\xab\\x9c}\\x01(\\xae\\xc0\\xc9,k\\xb48#\\xe2\\xf8D\\xa0\\x8eP\\xa4\\x16x\\xd8\\x7fi\\xcd\\xad\\xd6d\\xd1Y\\xd6\\x10\\xa7 \\x81\\xff\\x11t\\x7fd\\x83\\x97\\xf0\\xdf\\x932\\xeb<w\\xc7w\\xef\\xc2A\\x96\\r\\xfa[\\xc1|\\xb4E\\xa3\\x9f\\xa9\\x16\\xeaF<c(\\xf0\\xec{>\\xde6*\\x9c7\\x88\\x117\\x88C<\\xdc\\x9b\\xbaQV!\\xfc\\xc7\\x0e\\xcd\\x1d\\xb3\\xb7\\xcf\\xe5\\x02\\x81\\x81\\x00\\xdd^\\x00,\\xc7\\xbd0\\xea\\xd5\\x05=X|V\\xe8@k\\x98\\x19\\xd3\\xbd\\xa9\\x94K\\xe3\\x01\\xf5\\xa0\\x17\\xbe\\xf6\\xd6\\xcf\\xde\\x9ek,\\xbe\\xce\\xb0\\xc8\\x9d\\xeb\\x80=i.\\x1em\\xd1\\x9a\\x08\\xf9AP\\xcd\\xed\\xafS[\\x1d\\xec\\xfd%\\xb8)4\\xba(\\x08\\xd2\\xcdW\\x98\\x89\\x9f\\x88\\x8c\\xb7\\x9c\\x80\\xc8\\xaaY\\xdc00\\x16\\n+M\\x9e\\xa2U\\xd7\\xc0\\x01H\\xb5\\xa3M\\x90\\xab\\x8d;\\xbd\\xae\\xed\\x8e\\x97\\x7f\\xf5\\xd7\\x9d\\xfc\\x8fT\\xdb\\x07\\xd3\\xe0\\x9c\\xb5/\\xce\\x9cz\\x1d\\x02\\x81\\x80[5\\xf8\\x8c\\xea\\x19\\xfb\\x19i\\r\\x02U\\xea\\x08\\xbf\\xf9C\\x94\\x82XIzA3\\x85\\xaf\\x8e`\\xf3\\x13\\x02\\x01~t\\x89!\\xbcc\\x89h\\xc0\\x8d\\xc4\\x9f*\\xd1\\x8a)\\xa9\\xb4+\\xfe%4\\xde\\x01B\\xfd\\x11\\x97#\\x8a:A\\x9du:\\x0f\\xe7\\xfa\\x86\\x94\\xd4S\\xf5j\\xb8\\x1aB\\xfe\\xe4\\xeb\\xf0\\xce~\\xe9\\x0b\\xfeE\\xd5\\x81B\\x1b\\x9a\\xc4\\xd1\\xde_\\x9f[?\\x8fk\\xf2O\\xf0=\\xedp`0b\\xb2mxj\\xdfC\\x18\\xf3!\\x99\\x96\\x8fM?*}\\x02\\x81\\x81\\x00\\xbe\\xb1\\xa3d\\xf0\\x0b\\xc2\\x80\\tQ\\xa2.\\xff\\xad\\xbe\\x15\\x00\\x9a\\xded\\xd1\\x15\\xacrR\\xf3\\xf5,\\x1cH\\x9dK\\x1fv\\x9e\\xf1\\xa4r\\x1a\\x8b\\x9f\\xc6\\xaa\\x80\\xa6f]\\x1cIn.K\\\\\\xad/v\\xb62:\\x94[\\x8b3\\xe7\\xb2e\\x8c\\xcep~iZ\\x0b\\x03\\x94J\\xa1\\xce\\xd6\\xbd3\\x13\\xa9\\xec\\x0f\\nS\\xe2(\\x90u%\\x1a\\xa2\\xe8`\\xb6\\xbas\\xfeak&\\xdd[\\x81c\\x97\\xb1&AL\\xfe\\x99R`\\x06\\xb1Hd\\xf51\\t\\xc4M/\\xee\\xe1\\x02\\x81\\x80xr\\x80yd\\xcb\\x1a[p\\xe1\\x94\\x02?\\xf8\\xa6\\xe0u\\x94\\xb0z\\x836_l4\\x15\\xc6/yT\\xb0^G}\\xfe\\r@\\xa2\\xd8SQ\\xb6fh`\\x9a\\xacH\\xedF\\xe4;\\x04k\\xbax\\x96\\x87#V1\\x0c8b\\xe6\\xc6m\\xaf\\x0e[\\xfa\\x03\\xa4`\\x8a\\x9e%\\xdfS\\xb2\\xc0\\xc8\\xff\\xa0\\xc2U\\x06\\x90\\x0c\\x0b|a\\xee\\xe5\\x12m\\xf8La\\x15\\x96\\x11\\xc0\\xfe\\xd5\\x7f\\xfb5\\xf9\\xab\\xda\\x0e\\xc0\\xb3\\n\\x8bo8\\xc3\\x15N\\xa8\\xf0\\xf3\\xa3W\\xae\\xa6'"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = s[s.index('\\n')+1:]\n",
    "s = s.replace('\\n','')\n",
    "s = s[:s.index('-')]\n",
    "s=  decode(s.encode(), 'base64')\n",
    "s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C'est à ce stade qu'il vaut mieux faire appel au décodeur de pyasn1 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(<SequenceOf value object, tagSet=<TagSet object, tags 0:32:16>, subtypeSpec=<ConstraintsIntersection object>, componentType=None, sizeSpec=<ConstraintsIntersection object>, payload [<Integer value object, tagSet <TagSet object, tags 0:0:2>, payload [0]>, <Integer value object, tagSet <TagSet object, tags 0:0:2>, payload [2419717928684707...3746530818764529]>, <Integer value object, tagSet <TagSet object, tags 0:0:2>, payload [65537]>, <Integer value object, tagSet <TagSet object, tags 0:0:2>, payload [1517285018833606...3859940738022033]>, <Integer value object, tagSet <TagSet object, tags 0:0:2>, payload [1556595946552543...8997631767465957]>, <Integer value object, tagSet <TagSet object, tags 0:0:2>, payload [1554493273635817...9837865199303197]>, <Integer value object, tagSet <TagSet object, tags 0:0:2>, payload [6405041868056585...7513910247238269]>, <Integer value object, tagSet <TagSet object, tags 0:0:2>, payload [1339098101170082...5539413120708321]>, <Integer value object, tagSet <TagSet object, tags 0:0:2>, payload [8458095138064153...3543979375505062]>]>,\n",
       " b'')"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from pyasn1.codec.der import decoder\n",
    "der=decoder.decode(s)\n",
    "der"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "(version, n, e, d, p, q, e1, e2, c) = (int(x) for x in der[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "e = 65537\n",
      "0x10001\n",
      "d =  15172850188336063888999146548071477559248570771347304388810997696967574883864815948150701049455628406239890162242367050261534275261809363116346377161957535363565896576634860572479709663799080983047770990538074783884991140656116592701807527705879720176760824130306883302414886139346299227260195934952841369977350597441906754021159518664780005306118805594715343080488084374604059401335521866192949329558171222548434007661718013724887136902271039720597793760620351506991948830109271399986139475607937692536493513291795644092189491020024173088845020436085238851119034143510539946782308823105168030061480903859940738022033\n",
      "e*d mod (p-1)*(q-1) =  1\n",
      "p*q-n =  0\n",
      "N-n =  0\n"
     ]
    }
   ],
   "source": [
    "print (\"e = %d\" % e)\n",
    "print (hex(e))\n",
    "print (\"d = \",d)\n",
    "print (\"e*d mod (p-1)*(q-1) = \", e*d % ((p-1)*(q-1)))\n",
    "print (\"p*q-n = \", p*q-n)\n",
    "print (\"N-n = \",  N-n)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il existe un module [rsa](https://stuvel.eu/rsa) pour Python qui permet toutes ces manipulations de clefs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "import rsa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on package rsa:\n",
      "\n",
      "NAME\n",
      "    rsa - RSA module\n",
      "\n",
      "DESCRIPTION\n",
      "    Module for calculating large primes, and RSA encryption, decryption, signing\n",
      "    and verification. Includes generating public and private keys.\n",
      "    \n",
      "    WARNING: this implementation does not use compression of the cleartext input to\n",
      "    prevent repetitions, or other common security improvements. Use with care.\n",
      "\n",
      "PACKAGE CONTENTS\n",
      "    _compat\n",
      "    asn1\n",
      "    cli\n",
      "    common\n",
      "    core\n",
      "    key\n",
      "    parallel\n",
      "    pem\n",
      "    pkcs1\n",
      "    pkcs1_v2\n",
      "    prime\n",
      "    randnum\n",
      "    transform\n",
      "    util\n",
      "\n",
      "CLASSES\n",
      "    rsa.key.AbstractKey(builtins.object)\n",
      "        rsa.key.PrivateKey\n",
      "        rsa.key.PublicKey\n",
      "    rsa.pkcs1.CryptoError(builtins.Exception)\n",
      "        rsa.pkcs1.DecryptionError\n",
      "        rsa.pkcs1.VerificationError\n",
      "    \n",
      "    class DecryptionError(CryptoError)\n",
      "     |  Raised when decryption fails.\n",
      "     |  \n",
      "     |  Method resolution order:\n",
      "     |      DecryptionError\n",
      "     |      CryptoError\n",
      "     |      builtins.Exception\n",
      "     |      builtins.BaseException\n",
      "     |      builtins.object\n",
      "     |  \n",
      "     |  Data descriptors inherited from CryptoError:\n",
      "     |  \n",
      "     |  __weakref__\n",
      "     |      list of weak references to the object (if defined)\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Methods inherited from builtins.Exception:\n",
      "     |  \n",
      "     |  __init__(self, /, *args, **kwargs)\n",
      "     |      Initialize self.  See help(type(self)) for accurate signature.\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Static methods inherited from builtins.Exception:\n",
      "     |  \n",
      "     |  __new__(*args, **kwargs) from builtins.type\n",
      "     |      Create and return a new object.  See help(type) for accurate signature.\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Methods inherited from builtins.BaseException:\n",
      "     |  \n",
      "     |  __delattr__(self, name, /)\n",
      "     |      Implement delattr(self, name).\n",
      "     |  \n",
      "     |  __getattribute__(self, name, /)\n",
      "     |      Return getattr(self, name).\n",
      "     |  \n",
      "     |  __reduce__(...)\n",
      "     |      Helper for pickle.\n",
      "     |  \n",
      "     |  __repr__(self, /)\n",
      "     |      Return repr(self).\n",
      "     |  \n",
      "     |  __setattr__(self, name, value, /)\n",
      "     |      Implement setattr(self, name, value).\n",
      "     |  \n",
      "     |  __setstate__(...)\n",
      "     |  \n",
      "     |  __str__(self, /)\n",
      "     |      Return str(self).\n",
      "     |  \n",
      "     |  with_traceback(...)\n",
      "     |      Exception.with_traceback(tb) --\n",
      "     |      set self.__traceback__ to tb and return self.\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Data descriptors inherited from builtins.BaseException:\n",
      "     |  \n",
      "     |  __cause__\n",
      "     |      exception cause\n",
      "     |  \n",
      "     |  __context__\n",
      "     |      exception context\n",
      "     |  \n",
      "     |  __dict__\n",
      "     |  \n",
      "     |  __suppress_context__\n",
      "     |  \n",
      "     |  __traceback__\n",
      "     |  \n",
      "     |  args\n",
      "    \n",
      "    class PrivateKey(AbstractKey)\n",
      "     |  PrivateKey(n: int, e: int, d: int, p: int, q: int) -> None\n",
      "     |  \n",
      "     |  Represents a private RSA key.\n",
      "     |  \n",
      "     |  This key is also known as the 'decryption key'. It contains the 'n', 'e',\n",
      "     |  'd', 'p', 'q' and other values.\n",
      "     |  \n",
      "     |  Supports attributes as well as dictionary-like access. Attribute access is\n",
      "     |  faster, though.\n",
      "     |  \n",
      "     |  >>> PrivateKey(3247, 65537, 833, 191, 17)\n",
      "     |  PrivateKey(3247, 65537, 833, 191, 17)\n",
      "     |  \n",
      "     |  exp1, exp2 and coef will be calculated:\n",
      "     |  \n",
      "     |  >>> pk = PrivateKey(3727264081, 65537, 3349121513, 65063, 57287)\n",
      "     |  >>> pk.exp1\n",
      "     |  55063\n",
      "     |  >>> pk.exp2\n",
      "     |  10095\n",
      "     |  >>> pk.coef\n",
      "     |  50797\n",
      "     |  \n",
      "     |  Method resolution order:\n",
      "     |      PrivateKey\n",
      "     |      AbstractKey\n",
      "     |      builtins.object\n",
      "     |  \n",
      "     |  Methods defined here:\n",
      "     |  \n",
      "     |  __eq__(self, other: Any) -> bool\n",
      "     |      Return self==value.\n",
      "     |  \n",
      "     |  __getitem__(self, key: str) -> int\n",
      "     |  \n",
      "     |  __getstate__(self) -> Tuple[int, int, int, int, int, int, int, int]\n",
      "     |      Returns the key as tuple for pickling.\n",
      "     |  \n",
      "     |  __hash__(self) -> int\n",
      "     |      Return hash(self).\n",
      "     |  \n",
      "     |  __init__(self, n: int, e: int, d: int, p: int, q: int) -> None\n",
      "     |      Initialize self.  See help(type(self)) for accurate signature.\n",
      "     |  \n",
      "     |  __ne__(self, other: Any) -> bool\n",
      "     |      Return self!=value.\n",
      "     |  \n",
      "     |  __repr__(self) -> str\n",
      "     |      Return repr(self).\n",
      "     |  \n",
      "     |  __setstate__(self, state: Tuple[int, int, int, int, int, int, int, int]) -> None\n",
      "     |      Sets the key from tuple.\n",
      "     |  \n",
      "     |  blinded_decrypt(self, encrypted: int) -> int\n",
      "     |      Decrypts the message using blinding to prevent side-channel attacks.\n",
      "     |      \n",
      "     |      :param encrypted: the encrypted message\n",
      "     |      :type encrypted: int\n",
      "     |      \n",
      "     |      :returns: the decrypted message\n",
      "     |      :rtype: int\n",
      "     |  \n",
      "     |  blinded_encrypt(self, message: int) -> int\n",
      "     |      Encrypts the message using blinding to prevent side-channel attacks.\n",
      "     |      \n",
      "     |      :param message: the message to encrypt\n",
      "     |      :type message: int\n",
      "     |      \n",
      "     |      :returns: the encrypted message\n",
      "     |      :rtype: int\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Data descriptors defined here:\n",
      "     |  \n",
      "     |  coef\n",
      "     |  \n",
      "     |  d\n",
      "     |  \n",
      "     |  e\n",
      "     |  \n",
      "     |  exp1\n",
      "     |  \n",
      "     |  exp2\n",
      "     |  \n",
      "     |  n\n",
      "     |  \n",
      "     |  p\n",
      "     |  \n",
      "     |  q\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Methods inherited from AbstractKey:\n",
      "     |  \n",
      "     |  blind(self, message: int, r: int) -> int\n",
      "     |      Performs blinding on the message using random number 'r'.\n",
      "     |      \n",
      "     |      :param message: the message, as integer, to blind.\n",
      "     |      :type message: int\n",
      "     |      :param r: the random number to blind with.\n",
      "     |      :type r: int\n",
      "     |      :return: the blinded message.\n",
      "     |      :rtype: int\n",
      "     |      \n",
      "     |      The blinding is such that message = unblind(decrypt(blind(encrypt(message))).\n",
      "     |      \n",
      "     |      See https://en.wikipedia.org/wiki/Blinding_%28cryptography%29\n",
      "     |  \n",
      "     |  save_pkcs1(self, format: str = 'PEM') -> bytes\n",
      "     |      Saves the key in PKCS#1 DER or PEM format.\n",
      "     |      \n",
      "     |      :param format: the format to save; 'PEM' or 'DER'\n",
      "     |      :type format: str\n",
      "     |      :returns: the DER- or PEM-encoded key.\n",
      "     |      :rtype: bytes\n",
      "     |  \n",
      "     |  unblind(self, blinded: int, r: int) -> int\n",
      "     |      Performs blinding on the message using random number 'r'.\n",
      "     |      \n",
      "     |      :param blinded: the blinded message, as integer, to unblind.\n",
      "     |      :param r: the random number to unblind with.\n",
      "     |      :return: the original message.\n",
      "     |      \n",
      "     |      The blinding is such that message = unblind(decrypt(blind(encrypt(message))).\n",
      "     |      \n",
      "     |      See https://en.wikipedia.org/wiki/Blinding_%28cryptography%29\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Class methods inherited from AbstractKey:\n",
      "     |  \n",
      "     |  load_pkcs1(keyfile: bytes, format: str = 'PEM') -> 'AbstractKey' from builtins.type\n",
      "     |      Loads a key in PKCS#1 DER or PEM format.\n",
      "     |      \n",
      "     |      :param keyfile: contents of a DER- or PEM-encoded file that contains\n",
      "     |          the key.\n",
      "     |      :type keyfile: bytes\n",
      "     |      :param format: the format of the file to load; 'PEM' or 'DER'\n",
      "     |      :type format: str\n",
      "     |      \n",
      "     |      :return: the loaded key\n",
      "     |      :rtype: AbstractKey\n",
      "    \n",
      "    class PublicKey(AbstractKey)\n",
      "     |  PublicKey(n: int, e: int) -> None\n",
      "     |  \n",
      "     |  Represents a public RSA key.\n",
      "     |  \n",
      "     |  This key is also known as the 'encryption key'. It contains the 'n' and 'e'\n",
      "     |  values.\n",
      "     |  \n",
      "     |  Supports attributes as well as dictionary-like access. Attribute access is\n",
      "     |  faster, though.\n",
      "     |  \n",
      "     |  >>> PublicKey(5, 3)\n",
      "     |  PublicKey(5, 3)\n",
      "     |  \n",
      "     |  >>> key = PublicKey(5, 3)\n",
      "     |  >>> key.n\n",
      "     |  5\n",
      "     |  >>> key['n']\n",
      "     |  5\n",
      "     |  >>> key.e\n",
      "     |  3\n",
      "     |  >>> key['e']\n",
      "     |  3\n",
      "     |  \n",
      "     |  Method resolution order:\n",
      "     |      PublicKey\n",
      "     |      AbstractKey\n",
      "     |      builtins.object\n",
      "     |  \n",
      "     |  Methods defined here:\n",
      "     |  \n",
      "     |  __eq__(self, other: Any) -> bool\n",
      "     |      Return self==value.\n",
      "     |  \n",
      "     |  __getitem__(self, key: str) -> int\n",
      "     |  \n",
      "     |  __getstate__(self) -> Tuple[int, int]\n",
      "     |      Returns the key as tuple for pickling.\n",
      "     |  \n",
      "     |  __hash__(self) -> int\n",
      "     |      Return hash(self).\n",
      "     |  \n",
      "     |  __ne__(self, other: Any) -> bool\n",
      "     |      Return self!=value.\n",
      "     |  \n",
      "     |  __repr__(self) -> str\n",
      "     |      Return repr(self).\n",
      "     |  \n",
      "     |  __setstate__(self, state: Tuple[int, int]) -> None\n",
      "     |      Sets the key from tuple.\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Class methods defined here:\n",
      "     |  \n",
      "     |  load_pkcs1_openssl_der(keyfile: bytes) -> 'PublicKey' from builtins.type\n",
      "     |      Loads a PKCS#1 DER-encoded public key file from OpenSSL.\n",
      "     |      \n",
      "     |      :param keyfile: contents of a DER-encoded file that contains the public\n",
      "     |          key, from OpenSSL.\n",
      "     |      :return: a PublicKey object\n",
      "     |  \n",
      "     |  load_pkcs1_openssl_pem(keyfile: bytes) -> 'PublicKey' from builtins.type\n",
      "     |      Loads a PKCS#1.5 PEM-encoded public key file from OpenSSL.\n",
      "     |      \n",
      "     |      These files can be recognised in that they start with BEGIN PUBLIC KEY\n",
      "     |      rather than BEGIN RSA PUBLIC KEY.\n",
      "     |      \n",
      "     |      The contents of the file before the \"-----BEGIN PUBLIC KEY-----\" and\n",
      "     |      after the \"-----END PUBLIC KEY-----\" lines is ignored.\n",
      "     |      \n",
      "     |      :param keyfile: contents of a PEM-encoded file that contains the public\n",
      "     |          key, from OpenSSL.\n",
      "     |      :type keyfile: bytes\n",
      "     |      :return: a PublicKey object\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Data descriptors defined here:\n",
      "     |  \n",
      "     |  e\n",
      "     |  \n",
      "     |  n\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Methods inherited from AbstractKey:\n",
      "     |  \n",
      "     |  __init__(self, n: int, e: int) -> None\n",
      "     |      Initialize self.  See help(type(self)) for accurate signature.\n",
      "     |  \n",
      "     |  blind(self, message: int, r: int) -> int\n",
      "     |      Performs blinding on the message using random number 'r'.\n",
      "     |      \n",
      "     |      :param message: the message, as integer, to blind.\n",
      "     |      :type message: int\n",
      "     |      :param r: the random number to blind with.\n",
      "     |      :type r: int\n",
      "     |      :return: the blinded message.\n",
      "     |      :rtype: int\n",
      "     |      \n",
      "     |      The blinding is such that message = unblind(decrypt(blind(encrypt(message))).\n",
      "     |      \n",
      "     |      See https://en.wikipedia.org/wiki/Blinding_%28cryptography%29\n",
      "     |  \n",
      "     |  save_pkcs1(self, format: str = 'PEM') -> bytes\n",
      "     |      Saves the key in PKCS#1 DER or PEM format.\n",
      "     |      \n",
      "     |      :param format: the format to save; 'PEM' or 'DER'\n",
      "     |      :type format: str\n",
      "     |      :returns: the DER- or PEM-encoded key.\n",
      "     |      :rtype: bytes\n",
      "     |  \n",
      "     |  unblind(self, blinded: int, r: int) -> int\n",
      "     |      Performs blinding on the message using random number 'r'.\n",
      "     |      \n",
      "     |      :param blinded: the blinded message, as integer, to unblind.\n",
      "     |      :param r: the random number to unblind with.\n",
      "     |      :return: the original message.\n",
      "     |      \n",
      "     |      The blinding is such that message = unblind(decrypt(blind(encrypt(message))).\n",
      "     |      \n",
      "     |      See https://en.wikipedia.org/wiki/Blinding_%28cryptography%29\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Class methods inherited from AbstractKey:\n",
      "     |  \n",
      "     |  load_pkcs1(keyfile: bytes, format: str = 'PEM') -> 'AbstractKey' from builtins.type\n",
      "     |      Loads a key in PKCS#1 DER or PEM format.\n",
      "     |      \n",
      "     |      :param keyfile: contents of a DER- or PEM-encoded file that contains\n",
      "     |          the key.\n",
      "     |      :type keyfile: bytes\n",
      "     |      :param format: the format of the file to load; 'PEM' or 'DER'\n",
      "     |      :type format: str\n",
      "     |      \n",
      "     |      :return: the loaded key\n",
      "     |      :rtype: AbstractKey\n",
      "    \n",
      "    class VerificationError(CryptoError)\n",
      "     |  Raised when verification fails.\n",
      "     |  \n",
      "     |  Method resolution order:\n",
      "     |      VerificationError\n",
      "     |      CryptoError\n",
      "     |      builtins.Exception\n",
      "     |      builtins.BaseException\n",
      "     |      builtins.object\n",
      "     |  \n",
      "     |  Data descriptors inherited from CryptoError:\n",
      "     |  \n",
      "     |  __weakref__\n",
      "     |      list of weak references to the object (if defined)\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Methods inherited from builtins.Exception:\n",
      "     |  \n",
      "     |  __init__(self, /, *args, **kwargs)\n",
      "     |      Initialize self.  See help(type(self)) for accurate signature.\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Static methods inherited from builtins.Exception:\n",
      "     |  \n",
      "     |  __new__(*args, **kwargs) from builtins.type\n",
      "     |      Create and return a new object.  See help(type) for accurate signature.\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Methods inherited from builtins.BaseException:\n",
      "     |  \n",
      "     |  __delattr__(self, name, /)\n",
      "     |      Implement delattr(self, name).\n",
      "     |  \n",
      "     |  __getattribute__(self, name, /)\n",
      "     |      Return getattr(self, name).\n",
      "     |  \n",
      "     |  __reduce__(...)\n",
      "     |      Helper for pickle.\n",
      "     |  \n",
      "     |  __repr__(self, /)\n",
      "     |      Return repr(self).\n",
      "     |  \n",
      "     |  __setattr__(self, name, value, /)\n",
      "     |      Implement setattr(self, name, value).\n",
      "     |  \n",
      "     |  __setstate__(...)\n",
      "     |  \n",
      "     |  __str__(self, /)\n",
      "     |      Return str(self).\n",
      "     |  \n",
      "     |  with_traceback(...)\n",
      "     |      Exception.with_traceback(tb) --\n",
      "     |      set self.__traceback__ to tb and return self.\n",
      "     |  \n",
      "     |  ----------------------------------------------------------------------\n",
      "     |  Data descriptors inherited from builtins.BaseException:\n",
      "     |  \n",
      "     |  __cause__\n",
      "     |      exception cause\n",
      "     |  \n",
      "     |  __context__\n",
      "     |      exception context\n",
      "     |  \n",
      "     |  __dict__\n",
      "     |  \n",
      "     |  __suppress_context__\n",
      "     |  \n",
      "     |  __traceback__\n",
      "     |  \n",
      "     |  args\n",
      "\n",
      "FUNCTIONS\n",
      "    compute_hash(message: Union[bytes, BinaryIO], method_name: str) -> bytes\n",
      "        Returns the message digest.\n",
      "        \n",
      "        :param message: the signed message. Can be an 8-bit string or a file-like\n",
      "            object. If ``message`` has a ``read()`` method, it is assumed to be a\n",
      "            file-like object.\n",
      "        :param method_name: the hash method, must be a key of\n",
      "            :py:const:`HASH_METHODS`.\n",
      "    \n",
      "    decrypt(crypto: bytes, priv_key: rsa.key.PrivateKey) -> bytes\n",
      "        Decrypts the given message using PKCS#1 v1.5\n",
      "        \n",
      "        The decryption is considered 'failed' when the resulting cleartext doesn't\n",
      "        start with the bytes 00 02, or when the 00 byte between the padding and\n",
      "        the message cannot be found.\n",
      "        \n",
      "        :param crypto: the crypto text as returned by :py:func:`rsa.encrypt`\n",
      "        :param priv_key: the :py:class:`rsa.PrivateKey` to decrypt with.\n",
      "        :raise DecryptionError: when the decryption fails. No details are given as\n",
      "            to why the code thinks the decryption fails, as this would leak\n",
      "            information about the private key.\n",
      "        \n",
      "        \n",
      "        >>> import rsa\n",
      "        >>> (pub_key, priv_key) = rsa.newkeys(256)\n",
      "        \n",
      "        It works with strings:\n",
      "        \n",
      "        >>> crypto = encrypt(b'hello', pub_key)\n",
      "        >>> decrypt(crypto, priv_key)\n",
      "        b'hello'\n",
      "        \n",
      "        And with binary data:\n",
      "        \n",
      "        >>> crypto = encrypt(b'\\x00\\x00\\x00\\x00\\x01', pub_key)\n",
      "        >>> decrypt(crypto, priv_key)\n",
      "        b'\\x00\\x00\\x00\\x00\\x01'\n",
      "        \n",
      "        Altering the encrypted information will *likely* cause a\n",
      "        :py:class:`rsa.pkcs1.DecryptionError`. If you want to be *sure*, use\n",
      "        :py:func:`rsa.sign`.\n",
      "        \n",
      "        \n",
      "        .. warning::\n",
      "        \n",
      "            Never display the stack trace of a\n",
      "            :py:class:`rsa.pkcs1.DecryptionError` exception. It shows where in the\n",
      "            code the exception occurred, and thus leaks information about the key.\n",
      "            It's only a tiny bit of information, but every bit makes cracking the\n",
      "            keys easier.\n",
      "        \n",
      "        >>> crypto = encrypt(b'hello', pub_key)\n",
      "        >>> crypto = crypto[0:5] + b'X' + crypto[6:] # change a byte\n",
      "        >>> decrypt(crypto, priv_key)\n",
      "        Traceback (most recent call last):\n",
      "        ...\n",
      "        rsa.pkcs1.DecryptionError: Decryption failed\n",
      "    \n",
      "    encrypt(message: bytes, pub_key: rsa.key.PublicKey) -> bytes\n",
      "        Encrypts the given message using PKCS#1 v1.5\n",
      "        \n",
      "        :param message: the message to encrypt. Must be a byte string no longer than\n",
      "            ``k-11`` bytes, where ``k`` is the number of bytes needed to encode\n",
      "            the ``n`` component of the public key.\n",
      "        :param pub_key: the :py:class:`rsa.PublicKey` to encrypt with.\n",
      "        :raise OverflowError: when the message is too large to fit in the padded\n",
      "            block.\n",
      "        \n",
      "        >>> from rsa import key, common\n",
      "        >>> (pub_key, priv_key) = key.newkeys(256)\n",
      "        >>> message = b'hello'\n",
      "        >>> crypto = encrypt(message, pub_key)\n",
      "        \n",
      "        The crypto text should be just as long as the public key 'n' component:\n",
      "        \n",
      "        >>> len(crypto) == common.byte_size(pub_key.n)\n",
      "        True\n",
      "    \n",
      "    find_signature_hash(signature: bytes, pub_key: rsa.key.PublicKey) -> str\n",
      "        Returns the hash name detected from the signature.\n",
      "        \n",
      "        If you also want to verify the message, use :py:func:`rsa.verify()` instead.\n",
      "        It also returns the name of the used hash.\n",
      "        \n",
      "        :param signature: the signature block, as created with :py:func:`rsa.sign`.\n",
      "        :param pub_key: the :py:class:`rsa.PublicKey` of the person signing the message.\n",
      "        :returns: the name of the used hash.\n",
      "    \n",
      "    newkeys(nbits: int, accurate: bool = True, poolsize: int = 1, exponent: int = 65537) -> Tuple[rsa.key.PublicKey, rsa.key.PrivateKey]\n",
      "        Generates public and private keys, and returns them as (pub, priv).\n",
      "        \n",
      "        The public key is also known as the 'encryption key', and is a\n",
      "        :py:class:`rsa.PublicKey` object. The private key is also known as the\n",
      "        'decryption key' and is a :py:class:`rsa.PrivateKey` object.\n",
      "        \n",
      "        :param nbits: the number of bits required to store ``n = p*q``.\n",
      "        :param accurate: when True, ``n`` will have exactly the number of bits you\n",
      "            asked for. However, this makes key generation much slower. When False,\n",
      "            `n`` may have slightly less bits.\n",
      "        :param poolsize: the number of processes to use to generate the prime\n",
      "            numbers. If set to a number > 1, a parallel algorithm will be used.\n",
      "            This requires Python 2.6 or newer.\n",
      "        :param exponent: the exponent for the key; only change this if you know\n",
      "            what you're doing, as the exponent influences how difficult your\n",
      "            private key can be cracked. A very common choice for e is 65537.\n",
      "        :type exponent: int\n",
      "        \n",
      "        :returns: a tuple (:py:class:`rsa.PublicKey`, :py:class:`rsa.PrivateKey`)\n",
      "        \n",
      "        The ``poolsize`` parameter was added in *Python-RSA 3.1* and requires\n",
      "        Python 2.6 or newer.\n",
      "    \n",
      "    sign(message: bytes, priv_key: rsa.key.PrivateKey, hash_method: str) -> bytes\n",
      "        Signs the message with the private key.\n",
      "        \n",
      "        Hashes the message, then signs the hash with the given key. This is known\n",
      "        as a \"detached signature\", because the message itself isn't altered.\n",
      "        \n",
      "        :param message: the message to sign. Can be an 8-bit string or a file-like\n",
      "            object. If ``message`` has a ``read()`` method, it is assumed to be a\n",
      "            file-like object.\n",
      "        :param priv_key: the :py:class:`rsa.PrivateKey` to sign with\n",
      "        :param hash_method: the hash method used on the message. Use 'MD5', 'SHA-1',\n",
      "            'SHA-224', SHA-256', 'SHA-384' or 'SHA-512'.\n",
      "        :return: a message signature block.\n",
      "        :raise OverflowError: if the private key is too small to contain the\n",
      "            requested hash.\n",
      "    \n",
      "    sign_hash(hash_value: bytes, priv_key: rsa.key.PrivateKey, hash_method: str) -> bytes\n",
      "        Signs a precomputed hash with the private key.\n",
      "        \n",
      "        Hashes the message, then signs the hash with the given key. This is known\n",
      "        as a \"detached signature\", because the message itself isn't altered.\n",
      "        \n",
      "        :param hash_value: A precomputed hash to sign (ignores message).\n",
      "        :param priv_key: the :py:class:`rsa.PrivateKey` to sign with\n",
      "        :param hash_method: the hash method used on the message. Use 'MD5', 'SHA-1',\n",
      "            'SHA-224', SHA-256', 'SHA-384' or 'SHA-512'.\n",
      "        :return: a message signature block.\n",
      "        :raise OverflowError: if the private key is too small to contain the\n",
      "            requested hash.\n",
      "    \n",
      "    verify(message: bytes, signature: bytes, pub_key: rsa.key.PublicKey) -> str\n",
      "        Verifies that the signature matches the message.\n",
      "        \n",
      "        The hash method is detected automatically from the signature.\n",
      "        \n",
      "        :param message: the signed message. Can be an 8-bit string or a file-like\n",
      "            object. If ``message`` has a ``read()`` method, it is assumed to be a\n",
      "            file-like object.\n",
      "        :param signature: the signature block, as created with :py:func:`rsa.sign`.\n",
      "        :param pub_key: the :py:class:`rsa.PublicKey` of the person signing the message.\n",
      "        :raise VerificationError: when the signature doesn't match the message.\n",
      "        :returns: the name of the used hash.\n",
      "\n",
      "DATA\n",
      "    __all__ = ['newkeys', 'encrypt', 'decrypt', 'sign', 'verify', 'PublicK...\n",
      "\n",
      "VERSION\n",
      "    4.6\n",
      "\n",
      "DATE\n",
      "    2020-06-12\n",
      "\n",
      "AUTHOR\n",
      "    Sybren Stuvel, Barry Mead and Yesudeep Mangalapilly\n",
      "\n",
      "FILE\n",
      "    /home/jyt/anaconda3/lib/python3.7/site-packages/rsa/__init__.py\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(rsa)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Signature numérique RSA  (DSA, Digital Signature Algorithm)\n",
    "\n",
    "La cryptographie à clef publique permet de signer numériquement un document. Le principe est le suivant.\n",
    "On calcule un hachage $h= H(x)$ du document $x$, et on le chiffre avec sa clef privée.\n",
    "La signature est $(h,s) = E(h,K_S))$\n",
    "Alors, tout le monde peut déchiffrer $s$ avec la clef publique, recalculer le hachage et comparer les résultats.\n",
    "\n",
    "Bien entendu, il y a des précautions à prendre dans le choix des paramètres, du bourrage, etc. Les protocoles\n",
    "autorisés sont décrits dans\n",
    "[ce document](fips_186-3.pdf).\n",
    "\n",
    "Le module `rsa` gère les signatures de façon transparente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PublicKey(7496487422217807100249186541091547368226043268417179401207860425209820899065605033306276356511577186576905015081319687471223001768735907148792531143439169, 65537)\n",
      "PrivateKey(7496487422217807100249186541091547368226043268417179401207860425209820899065605033306276356511577186576905015081319687471223001768735907148792531143439169, 65537, 1950159666469191346142612285259773732103785826071448061571216448561915199123581901544222566884669543219217288075688163657958376550213443970968184088130561, 6053569893261905312732947326825457214986020551747364100541460524984696150250963553, 1238358118333114706137872610429255662109475762980378879288541106062056673)\n",
      "La clef du coffre est dans le pot de fleurs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "b'PI^\\xa5\\x97\\x92?\\xb3c\\xa9\\xdfg\\x1d\\xd5\\x13$]\\xf9g\\xea\\xcb\\xacC\\xe2\\x1b\\xa1\\x84\\xec\\x02q\\xc3*\"j\\xb6\\xab\\xe1\\x04\\xdb&\\xcd#\\xba\\x96D\\x15\\\\(\\xd3\\xfa\\xbef\\xd4\\xc3\\x84\\xcf~@\\x84\\xa3\\x14\\xb6\\t#'"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(KP,KS) = rsa.newkeys(512)\n",
    "print (KP)\n",
    "print (KS)\n",
    "message = 'La clef du coffre est dans le pot de fleurs'\n",
    "signature = rsa.sign(message.encode(), KS, 'SHA-1')\n",
    "print (message)\n",
    "signature"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'SHA-1'"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rsa.verify(message.encode(), signature, KP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on function verify in module rsa.pkcs1:\n",
      "\n",
      "verify(message: bytes, signature: bytes, pub_key: rsa.key.PublicKey) -> str\n",
      "    Verifies that the signature matches the message.\n",
      "    \n",
      "    The hash method is detected automatically from the signature.\n",
      "    \n",
      "    :param message: the signed message. Can be an 8-bit string or a file-like\n",
      "        object. If ``message`` has a ``read()`` method, it is assumed to be a\n",
      "        file-like object.\n",
      "    :param signature: the signature block, as created with :py:func:`rsa.sign`.\n",
      "    :param pub_key: the :py:class:`rsa.PublicKey` of the person signing the message.\n",
      "    :raise VerificationError: when the signature doesn't match the message.\n",
      "    :returns: the name of the used hash.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(rsa.verify)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Attaques contre le RSA\n",
    "\n",
    "En pratique, la mise en oeuvre du RSA nécessite certaines précautions, décrites dans les RFC et autres standards officiels.\n",
    "\n",
    "L'attaque la plus évidente est la factorisation du module. Ce qui est impossible aujourd'hui sera peut-être possible demain, avec\n",
    "la découverte de nouveaux algorithmes et l'augmentation de la puissance des machines. \n",
    "\n",
    "### Factorisation du module\n",
    "\n",
    "Ce risque est bien illustré par l'affaire des cartes bancaires.\n",
    "Jusqu'à une date récente, un paiement par carte bancaire se déroulait ainsi. \n",
    "La mémoire de la carte est divisée en deux zones, une accessible avec n'importe quel lecteur, \n",
    "et une autre (zone secrète) qui n'est accessible qu'au processeur de la carte, \n",
    "et illisible autrement. \n",
    "La zone publique contient une valeur d'authentification, qui est obtenue en chiffrant des données publiques \n",
    "(comme le numéro de la carte et sa date d'expiration) \n",
    "avec une clé RSA secrète. \n",
    "Les terminaux de paiement et les distributeurs de billets connaissent la clé publique, \n",
    "et l'utilisent pour vérifier la valeur d'authentification, qui est précisément une signature numérique RSA, sans hachage\n",
    "vu le petit nombre de données.\n",
    "\n",
    "Si la signature est correcte, la carte est considérée comme authentique, et le code est demandé au client. \n",
    "Le terminal envoie le code à la carte qui le compare avec celui contenu dans sa zone secrète, \n",
    "et répond « oui » ou «non ». Si la réponse est « oui », le paiement est accepté.\n",
    "\n",
    "Seulement voilà. Les cartes émises vers 1998 utilisaient la clé publique\n",
    "\n",
    "$$e=3, \\quad n = 2135987035920910082395022704999628797051095341826417406442524165008583957746445088405009430865999$$\n",
    "\n",
    "Cette clé était trop courte, les algorithmes ayant progressé, \n",
    "elle a pu être factorisée. A partir de ce moment, il devenait possible de fabriquer de fausses cartes, \n",
    "en chiffrant des données d'authentification fantaisistes sur une carte programmable, et en programmant la carte pour \n",
    "qu'elle réponde « oui » (les deux octets 0x90, 0x00 dans son langage) \n",
    "quelle que soit la question posée (les fameuses yescards).\n",
    "\n",
    "\n",
    "L'histoire était racontée sur [ce site](http://www.parodie.com/humpich/home.htm/)\n",
    "(qui n'existe plus, mais [archive.org](https://web.archive.org/web/20080220223708/http://www.parodie.com/humpich/home.htm/) peut nous le retrouver).\n",
    "\n",
    "Le programme [msieve](https://sourceforge.net/projects/msieve/)\n",
    "répond en [18 secondes](http://www-igm.univ-mlv.fr/~jyt/Crypto/4/msieve.log) sur une station de travail moyennement récente. \n",
    "\n",
    "\n",
    "### Les clefs faibles\n",
    "\n",
    "S'il est en général impossible de retrouver $p$ et $q$ à partir de $n = pq$ pour deux grands nombres premiers $p$ et $q$, on connaît de nombreux cas particuliers dans lesquels il est possible de craquer la clé RSA. On trouvera [ici](http://www-igm.univ-mlv.fr/~jyt/Crypto/4/slides_iAWACS09_Erra-Grenier_How-to-compute-RSA-keys.pdf) un exposé récent de l'état de l'art dans ce domaine. Une première chose à réaliser, c'est que si on connaît $\\varphi(n)$, alors on peut factoriser $n$. En effet, \n",
    "$\\varphi(n) = (p-1)(q-1)$, donc $p$ et $q$ sont les deux racines de l'équation du second degré $x^2-(n-\\varphi(n)+1)x+n = 0$.\n",
    "\n",
    "Bien sûr, $\\varphi(n)$ n'est pas public, mais dans certaines circonstances, on peut le retrouver. \n",
    "C'est le cas si \n",
    "$3d<n^{1/4}$, $q<p<2q$\n",
    "([attaque de Wiener](http://www-igm.univ-mlv.fr/~jyt/Crypto/4/10.1.1.92.5261.pdf)). \n",
    "Il existe de nombreuses variantes de cette attaque, et d'autres types de clés faibles. \n",
    "Le programme [wiener.py](http://www-igm.univ-mlv.fr/~jyt/Crypto/4/wiener.py) \n",
    "montre comment la mettre en oeuvre. Il utilise quelques fonctions de ent.py, une petite collection d'exemples écrite par W. Stein (maître d'oeuvre du projet SAGE) pour illustrer son cours de cryptographie. Ce fichier sera donné au prochain TD.\n",
    "\n",
    "\n",
    "\n",
    "### Les erreurs de protocole\n",
    "\n",
    "Même si la clé est résistante, un mauvais usage du système peut être catastrophique.\n",
    "\n",
    "Par exemple, supposons que $B$ et $B'$ aient le même module $n$ et des exposants publics $e$ et $e'$, avec $pgcd(e,e')=1$.\n",
    "\n",
    "A envoie un même message $x$ aux deux, donc $y=x^e \\mod n$ à $B$ et $y' = x^{e'} \\mod n$ à $B'$. Si O intercepte $y$ et $y'$, il peut retrouver x sans factoriser la clé. (Problème du module commun).\n",
    "\n",
    "Si $B$, $B'$ et $B''$ ont pour modules $n$, $n'$, et $n''$ (deux à deux premiers entre eux) et un même exposant public $e$ (c'est fréquent, beaucoup de systèmes utilisent $e=3$ par exemple), A envoie $x^3 \\mod n, n'$ et $n''$ aux trois. O intercepte la communication et peut retrouver x sans factoriser la clé.\n",
    "\n",
    "### Autres attaques\n",
    "\n",
    "Il y en a beaucoup, voir [ici](boneh.pdf) pour plus d'information.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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": 1
}