希爾算法的加密與解密（希爾密碼的加密）

2023-05-09 14:38:48

簡介

希爾密碼是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。

每個字母當作26進位數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果模26。（注意用作加密的矩陣（即密匙）在必須是可逆的，否則就不可能解碼。只有矩陣的行列式和26互質，才是可逆的。）

例子：

用希爾密碼對明文串 x = EastChinaNormalUniversity 進行加密，

密鑰矩陣

加密：

密文向量 = 明文向量 * 密鑰矩陣 (mod 26)

1. 先將明文串對應英文字母編碼表進行數字轉化 4 0 18 19 2 7 8 13 0 13 14 17 12 0 11 20 13 8 21 4 17 18 8 19 24

兩兩一組寫成矩陣形式

我去，發現少了一個，老師出題就不能湊個整嗎？？？這樣子，我們做補0處理。

2. 接下來開始加密

得到密文矩陣後，按照分組對應的向量轉成字母：

IK BX NB DH NN JD YE SR OB KB UJ HL W

python實現：

import numpy as npdef encode(string, size): # 轉換小寫字母 if not string.islower: string = string.lower # 分成 size個字的分段 blocks = [string[i:i size] for i in range(0, len(string), size)] # 明文字串與密鑰矩陣階數不整除。。字串補a if len(blocks[-1]) != size: blocks[-1] = blocks[-1].ljust(size,'a') # 將 a-z 編碼為 0-25 temp = np.array([list(map(ord, block)) for block in blocks]) - ord('a')# print(temp) return tempdef analysis(crypter, code): return ((crypter @ code.T) % 26).T ord('a')# 要加密的信息encode_msg = 'eastchinanormaluniversity'.lowerprint('待加密的信息：' encode_msg)# 密鑰encryption_matrix = np.array([[2, 5], [9, 5]])print('密鑰：')print(encryption_matrix)# 加密代碼encrypted_code = analysis(encryption_matrix, encode(encode_msg, 2))# 密文Decryption_matrixtext = ''.join(map(chr, encrypted_code.ravel))print("密文：" Decryption_matrixtext[:len(encode_msg)].upper)"""待加密的信息：eastchinanormaluniversity密鑰：[[2 5] [9 5]]密文：IKBXNBDHNNJDYESROBKBUJHLW"""

解密:

不會求逆的參考:同餘方程、歐拉函數、乘法逆元、定義在Zm上的矩陣求逆

解密和加密類似，先通過剛剛的方法計算出模 m 的逆矩陣，然後用 A−1 再進行解密:

分析與破解

例子：

假設已知明文friday利用n=2的希爾密碼加密，得到密文VYUZSM，求秘鑰K.

n等於2，說明把friday分成3段，矩陣是2*2的

根據字母與整數的對應關係：

(5,17)---->(21,24),

(8,3)---->(20,25),

(0,24)—>(18,12),得到