M1 Cryptographie - TD2

In [1]:
s = open('Hill.txt').read()
In [2]:
s[:100]
Out[2]:
"      UKMHEUTN YP DERJJN,\n\nQSNNO DTWGVF V'ZXA YNNR\xc3\xa8HR JFXKFBPU, OEOMQGA INJA EBSRSPBMU, OA'QU R WCS"

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). \]\(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 [12]:
u = [aa.index(x) for x in s if x.isalpha()]

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.isalpha():
        res.append(ll[i])
        i+=1
    else: res.append(x)

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

AYANT APPRIS D'UNE MANIèRE 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)
C


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

In [13]:
from sympy import *
In [14]:
M = Matrix([[24, 7], [5, 17]])
In [15]:
A=Matrix([[3,6]])
B=A*M
list(B)
Out[15]:
[102, 123]
In [16]:
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 [17]:
H = Hill(M)
In [18]:
print H.encrypt('MONSIEUR')
UKMHEUTN

In [19]:
text='''      UKMHEUTN YP DERJJN,

QSNNO DTWGVF V'ZXA YNNRèHR JFXKFBPU, OEOMQGA INJA EBSRSPBMU, OA'QU R WCSPBP DEICMXXRAYFPK FUD ZGKIT VKINNIT D FX VMFECOLKVH BV HH DPXRBSFQKL, Z'OG N'OLHUDTN, WBV UX VMFKMRYH, BE WBZSFKUITH OT VPFMF MXDVX TEUBGGIHENNQE, W'DNZKTZ DC KJNIT ZGKIU OGA CB WW KMMH WOWBBMH BZ FAYZGRH B TPFMF FPCJZFE WRLWYQJNZCIU DO DU GEUXL OLE CRYZFJNF VT VPFMF CGWYLH.
    CB CJFPQ W CVVGH BWYOFECCJLH ZX "SQZSUMPPUG YXODH" BJNOGHES CXREC QKV HEW QEJAJLUMRLF VEW CGWYLHS IAQ U'KRY AYZGOMH, B'UW CB MYWY WBJAZ DA YLH ZGGIE LMF JN SFFKH BJ NUWI TELEYAYFPH.
    AT VUWC QOCANYP, R LUWITP DXRM YCJYPS, IGA CB OFCQHBO EJ CFRBP, ZXL ZCMGAFOO, EK VGQZGJN DRMAKM JN QKL ZP XFXIT BTCK ZXC KZFODXRH BEWXRCVVKTNV HC KMXQRWC ZTCMGA, YP MNOSFCM SR IK IGNFDKE.
    CB CVYE KMSPWY INJA DLSFIG OL MNFP CVPPMAA LR JVFZF ZX DEICMXXR MFPMNL-CVYE ZHXR QKF PUWN RAQCQCIMH OLYHFOMF OLA ELHIBCJLHK.
    MD S'RLITRYH B'ZXP XKTZBIT MFOFMHL, ZT VUWN RGVH B'EYMFZF, UKMHEUTN YP DERJJN, OGMHM QGA CVVGH BIWV, H'MUMYSPKVH BA YX VHDQJBPC KLHECOLSPCJLH QWMH DELZBJUMH BA YEW QWABODCJLHF VWYCJELGAEW JN OL WWA ELXNJBPEW AYDEEWKMEW.

    (ECBDRLTNM SO DBYEWKM)
     (KHZFMF UVG)
W'''
In [20]:
H.decrypt(text)
Out[20]:
'monsieurleprefetayantapprisdunemanirefortuitequoiqueforthonorablequilyauraitprochainementuneplacevacantealapresidencedelarepubliquejailhonneurparlapresentedesolliciterdevotrehautebienveillanceloctroidecetteplacequejemesenscapablederempliravotreentieresatisfactionetaumieuxdesinteretsdevotremaisonjetiensavotredispositionuncurriculumvitaedetailleainsiquelescertificatsdesmaisonsquimontemployedoujesuispartidemonpleingreetlibredetoutengagementjevoussignaleatoutesfinsutilesquejepossedeunhabitunejaquetteuncompletcroiseetquejeporteavecunecertainedesinvolturelechapeauclaquelebicorneetlachechiajevousseraisfortobligedebienvouloirmefixerunprochainrendezvousafinquenouspuissionsdebattredesconditionsenlattentedunepromptereponsejevouspriedagreermonsieurleprefetainsiquevotredamelassurancedemaparfaiteconsiderationsansprejudicedemessalutationsdistingueesetdemescivilitesempresseessignatureetadressepierredacc'

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

In [ ]: