{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import string\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "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', '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', '.', '?', '!', ',', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9']\n"
     ]
    }
   ],
   "source": [
    "# signes est une chaîne de caractère contenant tous les signes utilisés dans les messages\n",
    "# on ajoute l'alphabet majuscule et majuscule grâce à string.ascii_uppercase+string.ascii_lowercase\n",
    "# la commande list transforme une chaîne de caractère en liste\n",
    "\n",
    "L=list(' '+string.ascii_uppercase+string.ascii_lowercase+'.?!,0123456789') \n",
    "print(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67\n"
     ]
    }
   ],
   "source": [
    "nL = len(L) # nombre de caractères dans notre langage\n",
    "print(nL)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def codage(M):\n",
    "    n = 0\n",
    "    for k in range(len(M)):\n",
    "        n = n + L.index(M[k])*nL**k\n",
    "    return n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6772894412117139825371"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M = \"Hello world!\"\n",
    "codage(M)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Base(n,b): #Ecriture de n en base b (cf TP précédent), on s'en servira plus tard\n",
    "    L=[]\n",
    "    while n>0:\n",
    "        L=L+[n%b]\n",
    "        n=n//b\n",
    "    return L  \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BaseNb(l,b): # renvoie le nombre à partir de la liste de son écriture en base b\n",
    "    n = 0\n",
    "    for k in range(len(l)):\n",
    "        n = n + l[k]*b**k\n",
    "    return n\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# On renvoie un couple d, [u,v] où d=pgcd(a,b) et ua+bv = d, cf TP algo d'Euclide\n",
    "\n",
    "def Euclide(a,b):\n",
    "    X=np.array([[a],[b]])          # vecteur colonne (a,b)\n",
    "    P=np.array([[1,0],[0,1]])      # Matrice identité\n",
    "    if a<b:  \n",
    "        X=np.array([[b],[a]])      # Si a et plus petit que b on les inverse\n",
    "        P=np.array([[0,1],[1,0]])  # Matrice pour inverser a et b par laquel il faudra multiplier\n",
    "    while X[1,0]!=0:               # On boucle tant qu'on n'a pas atteint le vecteur (d,0) (qui signifie la fin de l'algo)\n",
    "        Q=np.array([[0, 1], [1,-(X[0,0]//X[1,0])]])\n",
    "        X= Q@X                     # On remplace le vecteur (a,b) par (b,a-bq) où q est le quotient de a par b\n",
    "        P = Q@P                    # On garde en mémoire le produit matriciel pour pouvoir avoir les coeff de Bézout à la fin \n",
    "    return X[0,0], P[0,:]   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decodage(n):\n",
    "    M = \"\"\n",
    "    G = Base(n,nL) # tableau donnant l'écriture de n en base nL (cf au début pour la déf)\n",
    "    for k in G:\n",
    "        M = M+L[k]\n",
    "    return M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55737102343898885806\n",
      "Hello world\n"
     ]
    }
   ],
   "source": [
    "M = \"Hello world\"\n",
    "k = codage(M)\n",
    "print(k)\n",
    "print(decodage(k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Coder(M,N):\n",
    "    return Base(codage(M),N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Decoder(l,N):\n",
    "    return decodage(BaseNb(l,N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[335, 395, 541, 274, 361, 389, 26, 90]\n",
      "Hello world!\n"
     ]
    }
   ],
   "source": [
    "M = \"Hello world!\"\n",
    "G = Coder(M,691)\n",
    "print(G)\n",
    "\n",
    "print(Decoder(G,691))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "# e et n sont supposés premiers entre eux. On pourrait ajouter un test pour le vérifier.\n",
    "# On renvoie d entre 0 et n-1 tel que e*d = 1 mod n\n",
    "def Inverse(e,n): \n",
    "    (u,v) = Euclide(e,n)[1] # on récupère les coeff de Bézout de sorte que ue + nv = pgcd(e,n)\n",
    "    return u%n # en prenant u mod n on obtient un nombre entre 0 et n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# On teste avec e = 37 et n = 11. On trouve d = 3. On vérifie que 3*37 = 1 mod 11\n",
    "d=Inverse(37,11)\n",
    "print(d)\n",
    "print(d*37%11)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ExpRapide(a,n,N): #Calcul de a^n modulo N par exponentiation rapide, cf TP Précédent\n",
    "    L=Base(n,2)\n",
    "    P=[a%N]\n",
    "    for i in range(len(L)):  #Calcul des carrés itérés de a modulo N\n",
    "        b=(P[i]*P[i])%N\n",
    "        P=P+[b]\n",
    "    p=1\n",
    "    for i in range(len(L)): #Calcul le produit des carrés itérés de a associés aux coefficients non nuls de L\n",
    "        if L[i]!=0:\n",
    "            p=(p*P[i])%N\n",
    "    return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "# l = liste d'entiers. On élève chacun des éléments de l à la puissance k et on réduit mod N\n",
    "# Il est important d'utiliser l'exponentiation rapide sinon les temps de calculs sont trop longs\n",
    "def Puissance(l,k,N):\n",
    "    G = []\n",
    "    for i in l:\n",
    "        G = G+[ExpRapide(i,k,N)]\n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 25, 34, 33, 30]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Puissance([1,2,3,4,5],10,37)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# On vérifie sur le dernier élément que 37 à  la puissance 10 est congru à 30 mod 37...\n",
    "5**10%37"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [],
   "source": [
    "# M =  message à chiffrer, e = partie de la clef publique\n",
    "\n",
    "def Chiffrer(M,N,e):\n",
    "    l = Coder(M,N) # On transforme le message M en un tableau de nombre entre 0 et N-1\n",
    "    return Puissance(l,e,N) # On code le message en élevant à la puissance e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "#  l = message chiffré à décoder. d = clef privée\n",
    "def Dechiffrer(l,N,d):\n",
    "    L = Puissance(l,d,N) # on décode en élevant à la puissance d\n",
    "    return Decoder(L,N)  # on transforme le tableau d'entiers en message"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 440334654777631\n",
    "q = 145295143558111\n",
    "N = p*q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "# On teste si un nombre est premier\n",
    "def isPrime(n):\n",
    "    for i in range(2,int(n**0.5)+1):\n",
    "        if n%i==0:\n",
    "            return False       \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(isPrime(p))\n",
    "print(isPrime(q))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [],
   "source": [
    "e = 1193"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30568095156186201333234581057\n"
     ]
    }
   ],
   "source": [
    "d = Inverse(e,(p-1)*(q-1))\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.gcd(e,(p-1)*(q-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = \"Hello world! Quelle est la longueur du cercle ? En supposant son rayon qui vaut 1... et sans utiliser apostrophes et accents\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [],
   "source": [
    "H = Chiffrer(M,N,e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Hello world! Quelle est la longueur du cercle ? En supposant son rayon qui vaut 1... et sans utiliser apostrophes et accents'"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Dechiffrer(H,N,d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12208690884647187408"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "codage(M)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}