M1 Cryptographie - TD2

In [1]:
s = open('Hill.txt').read()
In [2]:
s[:100]
Out[2]:
"      UKMHEUTN YP DERJJN,\n\nQSNNO DTWGVF V'ZXA YNNEUMF INJAAQIT, QKMAQKR JFXX SLHFXFRYP, QK'NJ E MTNO"

On compare les codages par couples d'entiers modulo 26 des blocs de 2 lettres du clair et du chiffré.

In [3]:
v = 'MONSIEUR'
w = 'UKMHEUTN'
from string import ascii_uppercase as aa
a = [aa.index(x) for x in v]
b = [aa.index(x) for x in w]
print (a)
print (b)
[12, 14, 13, 18, 8, 4, 20, 17]
[20, 10, 12, 7, 4, 20, 19, 13]

On a par exemple $$ (20,10) = (12,14)\left(\matrix{a&b\cr c&d\cr}\right),\quad (12,7) = (13,18)\left(\matrix{a&b\cr c&d\cr}\right),\quad{\rm donc} \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). $$ où $K=\left(\matrix{a&b\cr c&d\cr}\right)$ est la clef de cryptage. Malheureusement, la matrice $\left(\matrix{12&14\cr 13&18\cr}\right)$ n'est pas inversible :

In [4]:
def det(a,b,c,d): return (a*d-b*c) % 26
In [5]:
det(12,14,13,18)
Out[5]:
8

8 n'est pas premier avec 26. Inutile de continuer avec [12,14] car le déterminant sera multiple de 2. On ne peut pas non plus utiliser [8,4].

In [6]:
det(13,18,20,17)
Out[6]:
17

17 est inversible modulo 26. Pour aller vite, on inverse par force brute :

In [7]:
def i26(x):
    ll = [i for i in range(1,26) if (i*x %26)==1]
    if ll:
        return ll[0]
    else: return None

i26(17)
Out[7]:
23

On bricole ensuite une petite classe pour les matrices $2\times 2$ modulo 26. La matrice connaît ses coefficients (value), son déterminant (det), son inverse (inv), et sait se multiplier avec une autre matrice.

In [8]:
class Mat:
    def __init__(self,a,b,c,d):
        self.value = [[a,b],[c,d]]
        self.d = (a*d -b*c) % 26
        e = i26(self.d)
        if e:
            self.invlist = [e*d %26, (26-b)*e % 26, (26-c)*e %26, e*a%26]

    def det(self):
        return self.d

    def inv(self):
        assert self.d != 0
        return Mat(*self.invlist)

    def __mul__(self,N):
        mm = self.value; nn = N.value
        return Mat((mm[0][0]*nn[0][0]+mm[0][1]*nn[1][0]) % 26,
                   (mm[0][0]*nn[0][1]+mm[0][1]*nn[1][1]) % 26,
                   (mm[1][0]*nn[0][0]+mm[1][1]*nn[1][0]) % 26,
                   (mm[1][0]*nn[0][1]+mm[1][1]*nn[1][1]) % 26)
    

M = Mat(13,18,20,17)
M.inv().value
Out[8]:
[[1, 2], [8, 13]]

La clef est $$K=\left(\matrix{13&18\cr 20&17\cr}\right)^{-1}\left(\matrix{12&7\cr 19&13\cr}\right)$$.

In [9]:
N = Mat(12,7,19,13)
K = M.inv()*N
In [10]:
K.value
Out[10]:
[[24, 7], [5, 17]]
In [11]:
D = K.inv().value
D
Out[11]:
[[25, 5], [11, 20]]

On a donc $$K=\left(\matrix{24&7\cr 5&17\cr}\right)$$ et on déchiffre en multipliant par l'inverse $D$ de $K$ $$ D=\left(\matrix{25&5\cr 11&20\cr}\right) $$

In [36]:
u = [aa.index(x) for x in s if x in aa]


def uncrypt(x,y):
    p=(x*D[0][0]+y*D[1][0])%26
    q=(x*D[0][1]+y*D[1][1])%26
    return ''.join((aa[p], aa[q]))

ll = ''.join([uncrypt(*u[2*i:2*i+2]) for i in range(len(u)//2)])

res = []
i=0
for x in s:
    if x in aa:
        try:
            res.append(ll[i])
            i+=1
        except IndexError: break # il y a un caractère en trop à la fin
    else: res.append(x)

print (''.join(res))
      MONSIEUR LE PREFET,

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.
    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.
    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.
    JE VOUS SERAIS FORT OBLIGE DE BIEN VOULOIR ME FIXER UN PROCHAIN RENDEZ-VOUS AFIN QUE NOUS PUISSIONS DEBATTRE DES CONDITIONS.
    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.

    (SIGNATURE ET ADRESSE)
     (PIERRE DAC)

Pour le chiffre de Hill général, on peut utiliser sympy.

In [37]:
from sympy import *
In [38]:
M = Matrix([[24, 7], [5, 17]])
In [39]:
A=Matrix([[3,6]])
B=A*M
list(B)
Out[39]:
[102, 123]
In [40]:
from string import ascii_uppercase as AA
from string import ascii_lowercase as aa
class Hill(object):
    def __init__(self,M,modulus=26,alphabet=AA):
        self.M = M
        try:
            self.D = M.inv_mod(modulus)
        except ValueError: raise
        assert M.is_square
        self.n = M.shape[0]
        self.m = modulus
        assert len(alphabet) == self.m
        self.A = alphabet
        
        
        
    def text2blocks(self,t):
        
        cc = [self.A.index(c) for c in t if c in self.A]
        r = len(cc)%self.n
        if r: cc.extend([self.m-1]*(self.m-r))
        return cc
    
    def encrypt(self,t):
        bb = self.text2blocks(t)
        res = []
        for i in range(len(bb)//self.n):
            X = Matrix([bb[self.n*i:self.n*(i+1)]])
            Y = X * self.M 
            res.extend(list(Y))
        return ''.join([self.A[i%self.m] for i in res])
    
    def decrypt(self,c):
        bb = self.text2blocks(c)
        res = []
        for i in range(len(bb)//self.n):
            X = Matrix([bb[self.n*i:self.n*(i+1)]])
            Y = X * self.D 
            res.extend(list(Y))
        return ''.join([self.A[i%self.m].lower() for i in res])
           
In [41]:
H = Hill(M)
In [43]:
print (H.encrypt('MONSIEUR'))
UKMHEUTN
In [47]:
text='''      UKMHEUTN YP DERJJN,

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.
    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.
    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.
    XT VUWC QZFOGP DFXG HBMOCH BX TEUB GUWWDRH WW EPAVO RX IKTFDOGH QFPOLD-MUWQ WEPC ZGA SRYE SDWYECLHF VXTRLVGH BEW OSPMBPCIMH.
    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.

    (QOCANKFMF JN PZMFCQP)
     (XEUZSH BKI)
'''
In [48]:
H.decrypt(text)
Out[48]:
'monsieurleprefetayantapprisdunemanierefortuitequoiqueforthonorablequilyauraitprochainementuneplacevacantealapresidencedelarepubliquejailhonneurparlapresentedesolliciterdevotrehautebienveillanceloctroidecetteplacequejemesenscapablederempliravotreentieresatisfactionetaumieuxdesinteretsdevotremaisonjetiensavotredispositionuncurriculumvitaedetailleainsiquelescertificatsdesmaisonsquimontemployedoujesuispartidemonpleingreetlibredetoutengagementjevoussignaleatoutesfinsutilesquejepossedeunhabitunejaquetteuncompletcroiseetquejeporteavecunecertainedesinvolturelechapeauclaquelebicorneetlachechiajevousseraisfortobligedebienvouloirmefixerunprochainrendezvousafinquenouspuissionsdebattredesconditionsenlattentedunepromptereponsejevouspriedagreermonsieurleprefetainsiquevotredamelassurancedemaparfaiteconsiderationsansprejudicedemessalutationsdistingueesetdemescivilitesempresseessignatureetadressepierredac'

On peut donc maintenant utiliser des matrices de taille quelconque, par exemple (6,6) comme dans la version originale.

In [ ]: