Hill密碼的加密與解密-矩陣

Hill密碼的加密、解密與破譯數(shù)學(xué)實(shí)驗(yàn)上海交通大學(xué)數(shù)學(xué)系即使埃斯庫(kù)羅斯被人們遺忘，阿基米德仍會(huì)被人們記住，因?yàn)榧词拐Z(yǔ)言文字會(huì)消亡,數(shù)學(xué)概念也不會(huì)消亡。

—

G.H.Hardy

現(xiàn)代數(shù)學(xué)家象其他從事科學(xué)的人們那樣，在應(yīng)用他們的原理方面化費(fèi)的心血比在了解這些原理方面多得多。

—

G.B.Berkeley密碼的故事ConanDoyle創(chuàng)作的歇洛克.福爾摩斯這段符號(hào)的譯文為

AMHEREABESLANE.呂貝卡的故事－007的故事舞蹈人形戰(zhàn)爭(zhēng)和和平時(shí)期的間諜戰(zhàn)基度山伯爵（大仲馬）誰(shuí)最先使用密碼？密碼學(xué)

—Cryptography源于希臘文字：秘密＋書(shū)寫，古老神秘的學(xué)科JuliusCaesar

(愷撒)密文：Kh

lv

wkh

uxohu

ri

dqflhqw

Urpd明文：HeistherulerofancientRoma目的將信息傳遞給己方的接收者防止敵方知道信息的內(nèi)容主要缺陷：字母出現(xiàn)頻率不變密碼學(xué)名詞明文需要采用某種方法對(duì)其進(jìn)行變換來(lái)隱蔽它所載荷的信息或字符串加密過(guò)程將明文變換成另一種不能被非授權(quán)者所理解的隱蔽信息的消息或字符串的過(guò)程明文經(jīng)過(guò)加密過(guò)程的變換所得的消息或密文字符串將明文變?yōu)槊芪牡淖儞Q加密變換解密變換將密文變?yōu)槊魑牡淖儞Q密鑰加密變換所使用的參數(shù)發(fā)送者簡(jiǎn)單的加密解密過(guò)程模型明文密文普通信道接收者明文竊聽(tīng)、干擾加密器解密器HILL2密碼明文分組(兩個(gè)一組)，按組轉(zhuǎn)換成密文同一字母在不同組中所對(duì)應(yīng)密碼不同HILL2密碼的加密與解密★

假設(shè)要加密的明文是由26個(gè)字母所構(gòu)成★將每個(gè)明文字母與0–25的一個(gè)數(shù)字建立1–1對(duì)應(yīng)關(guān)系，稱為明文字母的表值字母ABCDEFGHIJKLM表值12345678910111213字母NOPQRSTUVWXYZ表值1415161718192021222324250★將明文字母依次按每?jī)蓚€(gè)字母一組查出其表值，得到一組二維向量

★通過(guò)加密矩陣得到，而★查向量i

的字母表值，即得到密文★利用加密矩陣的逆矩陣，由密文得到明文★選擇一個(gè)加密矩陣A—二階正整數(shù)值的矩陣.例如關(guān)于模運(yùn)算（mon26）模m

等價(jià)設(shè)

a,b為兩個(gè)整數(shù),若稱

a模m等價(jià)于b，記作剩余集稱為模m的剩余集運(yùn)算律設(shè)a,b

為兩個(gè)整數(shù)，模m

倒數(shù)

設(shè)，若存在使得，稱a有模m

倒數(shù)記作命題整數(shù)a有模m

倒數(shù)的充要條件為a

與m

無(wú)公共素因子模26倒數(shù)表25175112371931521912523211917151197531a–1(mod26)a怎樣求模m

倒數(shù)即解方程定義Euler函數(shù)：設(shè)m

為一自然數(shù)，Zm中與m

互素的數(shù)的個(gè)數(shù)稱為m

的Euler函數(shù)，記為(m)Euler定理

對(duì)任意整數(shù)k,m,若k,m互素，則

故所求x為可借助軟件Mathematica：

Eulerphi[m]矩陣模m可逆設(shè)為n

階方陣，若存在使得，稱B

為A

的模m逆矩陣，記作命題矩陣A模m

可逆|A|與m

無(wú)公共素因子模m逆矩陣?yán)右粋€(gè)簡(jiǎn)單實(shí)例明文：Ourmarshalwasshot分組：ou

rm

ar

shalwa

sshott補(bǔ)充啞字母對(duì)應(yīng)向量加密：左乘加密矩陣直接結(jié)果密文向量密文ek

rmkbixyj

yc

ee

ls

hh解密只要將解密矩陣左乘密文向量即可求得明文向量，從而查出明文結(jié)論使用Hill密碼時(shí)的加密矩陣應(yīng)該模26

可逆使用MathematicaIn[1]:=a={{1,2},{0,3}};MatrixForm[a]Out[1]//MatrixForm=In[2]:=deta=Mod[Det[a],26]Out[2]=3In[3]:=inva=Inverse[a];MatrixForm[inva]Out[3]//MatrixForm=In[4]:=adja=deta

invaOut[4]//MatrixForm=In[5]:=ideta=9Out[5]=9In[6]:=inva1=Mod[ideta

adja,26];MatrixForm[inva1]Out[6]//MatrixForm=In[7]:=b={{5,18,11,9,25,25,5,12,8},{11,13,2,24,10,3,5,19,8}};c=Mod[inva1.b,26];MatrixForm[c]Out[7]//MatrixForm=HILL2密碼的破譯

關(guān)鍵是求得加密矩陣的逆—解密矩陣

只要分析出兩個(gè)明文向量（線性無(wú)關(guān)）與相應(yīng)的密文向量

若有甲方截獲了一段密文：OJWPISWAZUXAU一個(gè)破譯例子UISEABAUCRSIPLBHAAMMLPJJOTENH經(jīng)分析這段密文是用HILL2密碼編譯的，且這段密文的字母UCRS依次代表了字母TACO，若明文字母的表值如前，試破譯這密文的內(nèi)容？關(guān)系其中其中計(jì)算A－