s = open('Hill.txt').read()
s[:100]
On compare les codages par couples d'entiers modulo 26 des blocs de 2 lettres du clair et du chiffré.
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)
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 :
def det(a,b,c,d): return (a*d-b*c) % 26
det(12,14,13,18)
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].
det(13,18,20,17)
17 est inversible modulo 26. Pour aller vite, on inverse par force brute :
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)
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.
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
La clef est $$K=\left(\matrix{13&18\cr 20&17\cr}\right)^{-1}\left(\matrix{12&7\cr 19&13\cr}\right)$$.
N = Mat(12,7,19,13)
K = M.inv()*N
K.value
D = K.inv().value
D
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) $$
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))
Pour le chiffre de Hill général, on peut utiliser sympy
.
from sympy import *
M = Matrix([[24, 7], [5, 17]])
A=Matrix([[3,6]])
B=A*M
list(B)
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])
H = Hill(M)
print (H.encrypt('MONSIEUR'))
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)
'''
H.decrypt(text)
On peut donc maintenant utiliser des matrices de taille quelconque, par exemple (6,6) comme dans la version originale.