{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# M1 Cryptographie - TD2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = open('Hill.txt').read()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"      UKMHEUTN YP DERJJN,\\n\\nQSNNO DTWGVF V'ZXA YNNEUMF INJAAQIT, QKMAQKR JFXX SLHFXFRYP, QK'NJ E MTNO\""
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s[:100]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On compare les codages par couples d'entiers modulo 26 des blocs de 2 lettres du clair et du chiffré."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[12, 14, 13, 18, 8, 4, 20, 17]\n",
      "[20, 10, 12, 7, 4, 20, 19, 13]\n"
     ]
    }
   ],
   "source": [
    "v = 'MONSIEUR'\n",
    "w = 'UKMHEUTN'\n",
    "from string import ascii_uppercase as aa\n",
    "a = [aa.index(x) for x in v]\n",
    "b = [aa.index(x) for x in w]\n",
    "print (a)\n",
    "print (b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a par exemple\n",
    "$$\n",
    "(20,10) = (12,14)\\left(\\matrix{a&b\\cr c&d\\cr}\\right),\\quad\n",
    "(12,7)  = (13,18)\\left(\\matrix{a&b\\cr c&d\\cr}\\right),\\quad{\\rm donc}\n",
    "\\left(\\matrix{20&10\\cr 12&7\\cr}\\right)=\\left(\\matrix{12&14\\cr 13&18\\cr}\\right)\\left(\\matrix{a&b\\cr c&d\\cr}\\right).\n",
    "$$\n",
    "où $K=\\left(\\matrix{a&b\\cr c&d\\cr}\\right)$ est la clef de cryptage. Malheureusement, la matrice\n",
    "$\\left(\\matrix{12&14\\cr 13&18\\cr}\\right)$ n'est pas inversible :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def det(a,b,c,d): return (a*d-b*c) % 26"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "det(12,14,13,18)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "8 n'est pas premier avec 26. Inutile de continuer avec [12,14] car le déterminant sera multiple de 2.\n",
    "On ne peut pas non plus utiliser [8,4]. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "det(13,18,20,17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "17 est inversible modulo 26. Pour aller vite, on inverse par force brute :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def i26(x):\n",
    "    ll = [i for i in range(1,26) if (i*x %26)==1]\n",
    "    if ll:\n",
    "        return ll[0]\n",
    "    else: return None\n",
    "\n",
    "i26(17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On bricole ensuite une petite classe pour les matrices $2\\times 2$ modulo 26. La matrice connaît ses coefficients\n",
    "(value), son déterminant (det), son inverse (inv), et sait se multiplier avec une autre matrice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2], [8, 13]]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Mat:\n",
    "    def __init__(self,a,b,c,d):\n",
    "        self.value = [[a,b],[c,d]]\n",
    "        self.d = (a*d -b*c) % 26\n",
    "        e = i26(self.d)\n",
    "        if e:\n",
    "            self.invlist = [e*d %26, (26-b)*e % 26, (26-c)*e %26, e*a%26]\n",
    "\n",
    "    def det(self):\n",
    "        return self.d\n",
    "\n",
    "    def inv(self):\n",
    "        assert self.d != 0\n",
    "        return Mat(*self.invlist)\n",
    "\n",
    "    def __mul__(self,N):\n",
    "        mm = self.value; nn = N.value\n",
    "        return Mat((mm[0][0]*nn[0][0]+mm[0][1]*nn[1][0]) % 26,\n",
    "                   (mm[0][0]*nn[0][1]+mm[0][1]*nn[1][1]) % 26,\n",
    "                   (mm[1][0]*nn[0][0]+mm[1][1]*nn[1][0]) % 26,\n",
    "                   (mm[1][0]*nn[0][1]+mm[1][1]*nn[1][1]) % 26)\n",
    "    \n",
    "\n",
    "M = Mat(13,18,20,17)\n",
    "M.inv().value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La clef est $$K=\\left(\\matrix{13&18\\cr 20&17\\cr}\\right)^{-1}\\left(\\matrix{12&7\\cr 19&13\\cr}\\right)$$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = Mat(12,7,19,13)\n",
    "K = M.inv()*N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[24, 7], [5, 17]]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[25, 5], [11, 20]]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = K.inv().value\n",
    "D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a donc $$K=\\left(\\matrix{24&7\\cr 5&17\\cr}\\right)$$\n",
    "et on déchiffre en multipliant par l'inverse $D$ de $K$\n",
    "$$\n",
    "D=\\left(\\matrix{25&5\\cr 11&20\\cr}\\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "      MONSIEUR LE PREFET,\n",
      "\n",
      "AYANT APPRIS D'UNE MANIERE FORTUITE, QUOIQUE FORT HONORABLE, QU'IL Y AURAIT PROCHAINEMENT UNE PLACE VACANTE A LA PRESIDENCE DE LA REPUBLIQUE, J'AI L'HONNEUR, PAR LA PRESENTE, DE SOLLICITER DE VOTRE HAUTE BIENVEILLANCE, L'OCTROI DE CETTE PLACE QUE JE ME SENS CAPABLE DE REMPLIR A VOTRE ENTIERE SATISFACTION ET AU MIEUX DES INTERETS DE VOTRE MAISON.\n",
      "    JE TIENS A VOTRE DISPOSITION UN \"CURRICULUM VITAE\" DETAILLE AINSI QUE LES CERTIFICATS DES MAISONS QUI M'ONT EMPLOYE, D'OU JE SUIS PARTI DE MON PLEIN GRE ET LIBRE DE TOUT ENGAGEMENT.\n",
      "    JE VOUS SIGNALE, A TOUTES FINS UTILES, QUE JE POSSEDE UN HABIT, UNE JAQUETTE, UN COMPLET CROISE ET QUE JE PORTE AVEC UNE CERTAINE DESINVOLTURE LE CHAPEAU CLAQUE, LE BICORNE ET LA CHECHIA.\n",
      "    JE VOUS SERAIS FORT OBLIGE DE BIEN VOULOIR ME FIXER UN PROCHAIN RENDEZ-VOUS AFIN QUE NOUS PUISSIONS DEBATTRE DES CONDITIONS.\n",
      "    EN L'ATTENTE D'UNE PROMPTE REPONSE, JE VOUS PRIE D'AGREER, MONSIEUR LE PREFET, AINSI QUE VOTRE DAME, L'ASSURANCE DE MA PARFAITE CONSIDERATION SANS PREJUDICE DE MES SALUTATIONS DISTINGUEES ET DE MES CIVILITES EMPRESSEES.\n",
      "\n",
      "    (SIGNATURE ET ADRESSE)\n",
      "     (PIERRE DAC)\n",
      "\n"
     ]
    }
   ],
   "source": [
    "u = [aa.index(x) for x in s if x in aa]\n",
    "\n",
    "\n",
    "def uncrypt(x,y):\n",
    "    p=(x*D[0][0]+y*D[1][0])%26\n",
    "    q=(x*D[0][1]+y*D[1][1])%26\n",
    "    return ''.join((aa[p], aa[q]))\n",
    "\n",
    "ll = ''.join([uncrypt(*u[2*i:2*i+2]) for i in range(len(u)//2)])\n",
    "\n",
    "res = []\n",
    "i=0\n",
    "for x in s:\n",
    "    if x in aa:\n",
    "        try:\n",
    "            res.append(ll[i])\n",
    "            i+=1\n",
    "        except IndexError: break # il y a un caractère en trop à la fin\n",
    "    else: res.append(x)\n",
    "\n",
    "print (''.join(res))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour le chiffre de Hill général, on peut utiliser `sympy`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sympy import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = Matrix([[24, 7], [5, 17]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[102, 123]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A=Matrix([[3,6]])\n",
    "B=A*M\n",
    "list(B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from string import ascii_uppercase as AA\n",
    "from string import ascii_lowercase as aa\n",
    "class Hill(object):\n",
    "    def __init__(self,M,modulus=26,alphabet=AA):\n",
    "        self.M = M\n",
    "        try:\n",
    "            self.D = M.inv_mod(modulus)\n",
    "        except ValueError: raise\n",
    "        assert M.is_square\n",
    "        self.n = M.shape[0]\n",
    "        self.m = modulus\n",
    "        assert len(alphabet) == self.m\n",
    "        self.A = alphabet\n",
    "        \n",
    "        \n",
    "        \n",
    "    def text2blocks(self,t):\n",
    "        \n",
    "        cc = [self.A.index(c) for c in t if c in self.A]\n",
    "        r = len(cc)%self.n\n",
    "        if r: cc.extend([self.m-1]*(self.m-r))\n",
    "        return cc\n",
    "    \n",
    "    def encrypt(self,t):\n",
    "        bb = self.text2blocks(t)\n",
    "        res = []\n",
    "        for i in range(len(bb)//self.n):\n",
    "            X = Matrix([bb[self.n*i:self.n*(i+1)]])\n",
    "            Y = X * self.M \n",
    "            res.extend(list(Y))\n",
    "        return ''.join([self.A[i%self.m] for i in res])\n",
    "    \n",
    "    def decrypt(self,c):\n",
    "        bb = self.text2blocks(c)\n",
    "        res = []\n",
    "        for i in range(len(bb)//self.n):\n",
    "            X = Matrix([bb[self.n*i:self.n*(i+1)]])\n",
    "            Y = X * self.D \n",
    "            res.extend(list(Y))\n",
    "        return ''.join([self.A[i%self.m].lower() for i in res])\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "H = Hill(M)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "UKMHEUTN\n"
     ]
    }
   ],
   "source": [
    "print (H.encrypt('MONSIEUR'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "text='''      UKMHEUTN YP DERJJN,\n",
    "\n",
    "QSNNO DTWGVF V'ZXA YNNEUMF INJAAQIT, QKMAQKR JFXX SLHFXFRYP, QK'NJ E MTNOGL YKTFDOGUDWWRY ZXP XEZQE KRWORYS C EZ DEEWZDFPQE OL EZ MFSDBMMQGA, I'LN J'EBNAOEP, KHD EZ DEEWFPIT, OL IAHEUMBPZF OL CVVGB RWCIT MNFPEHNJEZKVV, H'ICVGMA OL QEFOP XEZQE QKL ZA YE WFPA EXVFRYP OL MFZBSFS P CVVGM SRYEUMF QWCJPDKICJLH JN WC QMOEV EEW XRITMFAX OL CVVGA YOGIAT.\n",
    "    KJ NEUMH B TPFMF IBNRKOBPCIW PK \"VTNGVSQABD ZBPUQ\" OLODNJYP OGMHM QGA YPA EZFCJEPWOAX OLY SOGIAMH QKS A'LHI TZBWDYC, M'ZF HE WAQN RHDCJ OL UKX IYPXR VTM SR IPVMF OL GHDV FPOQIGWWRY.\n",
    "    CB CVYE ECBDDFS, C GHDVEW EPMH DVNJEW, QKL ZP XKOKMOL ZX MXMNK, FUD ILQKJNIT, ZX OSZBYPY LKTWYM SQ PGA CB OFJAS CEHS QUD QEJAOGUD OLECBGBZKFMF YP FDXVSCW SEZQKV, HX TUMFXUD JN EZ FDCKADT.\n",
    "    XT VUWC QZFOGP DFXG HBMOCH BX TEUB GUWWDRH WW EPAVO RX IKTFDOGH QFPOLD-MUWQ WEPC ZGA SRYE SDWYECLHF VXTRLVGH BEW OSPMBPCIMH.\n",
    "    FP E'ZFOFPIT Q'XUD DEGQNMZ FPXLHKM, CB CVYE DEEU U'VVTMSA, LLHECOEV UP XMFKZO, DXREC QKT VPFMF UVWW, E'ZCQTNNNQE OL CG WBRWOGIT OSMHZDZFRLCIM HNNN RMFENIBQE OL WWC QDFDVRLCIMH IBHHXRKSMSK MD CA YEW KUYXSFITK MZBMFCQMSC.\n",
    "\n",
    "    (QOCANKFMF JN PZMFCQP)\n",
    "     (XEUZSH BKI)\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'monsieurleprefetayantapprisdunemanierefortuitequoiqueforthonorablequilyauraitprochainementuneplacevacantealapresidencedelarepubliquejailhonneurparlapresentedesolliciterdevotrehautebienveillanceloctroidecetteplacequejemesenscapablederempliravotreentieresatisfactionetaumieuxdesinteretsdevotremaisonjetiensavotredispositionuncurriculumvitaedetailleainsiquelescertificatsdesmaisonsquimontemployedoujesuispartidemonpleingreetlibredetoutengagementjevoussignaleatoutesfinsutilesquejepossedeunhabitunejaquetteuncompletcroiseetquejeporteavecunecertainedesinvolturelechapeauclaquelebicorneetlachechiajevousseraisfortobligedebienvouloirmefixerunprochainrendezvousafinquenouspuissionsdebattredesconditionsenlattentedunepromptereponsejevouspriedagreermonsieurleprefetainsiquevotredamelassurancedemaparfaiteconsiderationsansprejudicedemessalutationsdistingueesetdemescivilitesempresseessignatureetadressepierredac'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H.decrypt(text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut donc maintenant utiliser des matrices de taille quelconque, par exemple (6,6) comme dans la version originale."
   ]
  },
  {
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}