密碼學(xué) 希爾密碼

簡(jiǎn)介

希爾密碼（Hill Cipher）是運(yùn)用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發(fā)明。每個(gè)字母當(dāng)作26進(jìn)制數(shù)字：A=0, B=1, C=2... 一串字母當(dāng)成n維向量，跟一個(gè)n×n的矩陣相乘，再將得出的結(jié)果MOD26。

解析

對(duì)于密碼體制的五元組（P, C, K, E, D）有 P=C=(Z26)m，m是一個(gè)不小于2的正整數(shù)

• K是定義在Z26上的m×m可逆矩陣的集合
• 取密鑰k∈K，k為一個(gè)m×m矩陣，記為(kij)，對(duì) x=(x1,x2,...,xm)∈P, y= (y1,y2,...,ym)∈C，定義
  • ek(x)=xk
  • dk(y)=yk-1 ? k-1表示k的逆矩陣
• 以上運(yùn)算均在Z26上運(yùn)行(模26)

例題

題目

在線代的課本上出現(xiàn)了一堆神秘字母

dloguszijluswogany

而旁邊的矩陣是

1 2 0 1

快找出flag吧

key格式:simCTF{}

解答

1.求矩陣M= 1 2 0 1 的逆矩陣 即 M^-1= 1 -2 0 1

求逆矩陣方法：
1、伴隨矩陣：伴隨矩陣是矩陣元素所對(duì)應(yīng)的代數(shù)余子式，所構(gòu)成的矩陣，轉(zhuǎn)置后得到的新矩陣。
2、初等變換：寫出增廣矩陣A|E，即矩陣M右側(cè)放置一個(gè)同階的單位矩陣，得到一個(gè)新矩陣。然后進(jìn)行初等行變換，將增廣矩陣的左側(cè)變換為一個(gè)同階單位矩陣，這時(shí)右側(cè)為所求M的逆矩陣。

2、根據(jù)字母表順序?qū)⒚芪膿Q成矩陣數(shù)值

3、將密鑰的逆矩陣與密文變換成的矩陣做乘運(yùn)算

4、將得到的矩陣mod26

5.可求明文：flagis hillissoeasy所以simCTF{hillissoeapy}

實(shí)現(xiàn)

使用numpy庫(kù)的矩陣對(duì)象，可以十分方便地進(jìn)行矩陣乘法，矩陣求逆和取模等運(yùn)算。

import numpy as np


m = 'YOURPINNOISFOURONETWOSIX'  #明文
a = np.matrix([[11,2,19],[5,23,25],[20,7,17]])  #密鑰LCTFXZUHR
num_m = []
temp = []
count = 1
for i in m:  #將明文分為三個(gè)一組
    temp.append(ord(i)-ord('A'))
    if count % 3 == 0:
        num_m.append(temp)
        temp = []
    count += 1
mat_m = [np.matrix(i).T for i in num_m]  #將明文分組轉(zhuǎn)換為向量形式
mat_c = [a * i % 26 for i in mat_m]  #得到密文分組的向量形式
num_c = []
temp = []
for i in mat_c:  #將密文向量轉(zhuǎn)換為列表形式，且合并到一個(gè)列表
    temp = i.tolist()
    for j in range(3):
        num_c.append(temp[j][0])
c = [chr(i+ord('A')) for i in num_c]
print(''.join(c))  #連接成字符串,輸出密文