數(shù)學(xué)實(shí)驗(yàn)課件：Hill密碼與破譯

Hill密碼與破譯

保密通訊在軍事、政治、經(jīng)濟(jì)斗爭(zhēng)和競(jìng)爭(zhēng)中的重要性是不言而喻的.

在斗爭(zhēng)或競(jìng)爭(zhēng)中，一方要將信息傳遞給己方的接收者，同時(shí)又要防止其他人(特別是敵方)知道信息的內(nèi)容.

他采用的一種方式是：將原來的信息(稱為明文)經(jīng)過加密，變成密文之后發(fā)送出去，使敵方即使得到密文也讀不懂，而合法的接收者收到密文之后卻可以按照預(yù)先約定好的方法加以解密，再翻譯成明文.

而敵方卻要千方百計(jì)從密文破譯出明文來.一方如何編制密碼使之不易被破譯，另一方則要找到其弱點(diǎn)加以破譯，這就構(gòu)成了密碼學(xué)的主要內(nèi)容.

從密碼學(xué)的發(fā)展來看，密碼可分為古典密碼(即以字符為基本加密單元的密碼)，以及現(xiàn)代密碼(即以信息塊為基本加密單元的密碼).這里我們將介紹Hill密碼的加密和破譯原理.

本章介紹古典密碼中加密和解密原理.Hill2密碼加密12.1Hill2密碼解密12.2CONTENTSMATLAB求解12.312.1Hill2密碼加密

一般的加密過程是這樣的：

明文→加密器→密文→普通信道→解密器→明文

其中的“→普通信道→解密器”這個(gè)環(huán)節(jié)容易被敵方截獲并加以分析.

在這個(gè)過程中，運(yùn)用的數(shù)學(xué)手段是矩陣運(yùn)算，加密過程的具體步驟如下：ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250表12-1明文字母的表值

1)根據(jù)明文字母的表值，將明文信息用數(shù)字表示，設(shè)明文信息只需要26個(gè)拼音大寫字母A—Z(也可以不止26個(gè)，如還有小寫字母、數(shù)字、標(biāo)點(diǎn)符號(hào)等)，通信雙方給出這26個(gè)字母表值(見表12-1).

2)選擇一個(gè)二階可逆整數(shù)方陣A，稱為Hill2密碼的加密矩陣，它是這個(gè)加密體制的“密鑰”(是加密的關(guān)鍵，僅通信雙方掌握).

3)將明文字母依次逐對(duì)分組.Hill2密碼的加密矩陣為二階矩陣，則明文字母每2個(gè)一組(可以推廣至Hilln密碼，則每n個(gè)明文字母為一組).若最后一組僅有一個(gè)字母，則補(bǔ)充一個(gè)沒有實(shí)際意義的啞字母，這樣使每一組都由2個(gè)明文字母組成.查出每個(gè)明文字母的表值，構(gòu)成一個(gè)二維列向量α.

4)A乘以α，得一新的2維列向量β=Aα，由β的兩個(gè)分量反查字母表值得到的兩個(gè)字母即為密文字母.

以上4步即為Hill2密碼的加密過程.解密過程，即為上述過程的逆過程.例12.1明文為WAWDZG(“我愛我的祖國”的拼音縮寫)，

，求這段明文的Hill2密文.解將明文相鄰字母每2個(gè)分為一組：

WAWDZG(12-1)查表12-1得到每對(duì)字母的表值，并構(gòu)造2維列向量：

(12-2)將上述3個(gè)向量左乘矩陣，得到3個(gè)2維列向量：

(12-3)作模26運(yùn)算(每個(gè)元素都加減26的整數(shù)倍，使其化為0～25之間的一個(gè)整數(shù))得到：反查表12-1得到每對(duì)表值對(duì)應(yīng)的字母為：

YCELNU(12-4)這就得到了密文“YCELNU”.12.2Hill2密碼破譯

要將例12.1密文解密，只要將上述加密過程逆轉(zhuǎn)回去，即將密文按同樣方式分組，查它們的表值即得：

(12-5)

(12-5)是前面的(12-3)經(jīng)模26運(yùn)算的結(jié)果.但如何由式(12-5)中的向量求得(12-2)中的向量呢？這是在模運(yùn)算意義下，如何解方程組：

Aα=β

(12-6)的問題.一個(gè)一般的n階方陣可逆的充要條件為det(A)≠0.但在模26意義下矩陣可逆與一般的矩陣可逆有所不同.記整數(shù)集合

，m為一正整數(shù)，模m可逆定義如下：定義12.1

對(duì)于一個(gè)元素屬于集合zm的n階方陣A，若存在一個(gè)元素屬于集合zm的方陣B，使得稱A為模m可逆，B為A的模m逆矩陣，記為B=A-1(modm).

的意義是，每一個(gè)元素減去m的整數(shù)倍后，可以化成單位矩陣.

例如：

定義12.2

對(duì)于Zm的一個(gè)整數(shù)a，若存在Zm中的中一個(gè)整數(shù)

b，使得

，則稱b為

a的模倒數(shù)或乘法逆，記作

.

可以證明，如果

a與

m無公共素?cái)?shù)因子，則

a有唯一的模

m倒數(shù)(素?cái)?shù)是指除了1與自身外，不能被其他非零整數(shù)整除的正整數(shù))，反之亦然.

例如，

.

命題

元素屬于Zm的方陣

A模

m

可逆的充要條件是，m和det(A)沒有公共素?cái)?shù)因子，即m和det(A)互素.

顯然，所選加密矩陣必須符合該命題的條件.

a1357911151719212325a-11921153197231151725表12-2模26倒數(shù)表表12-2可用下列程序求得：m=26;fora=1:m

fori=1:m

ifmod(a*i,m)==1

fprintf('TheINVERSE(mod%d)ofnumber:%dis:%d\n',m,a,i)end;end;end若

則的模26逆矩陣：例12.3甲方收到與之有秘密通信往來的乙方的一個(gè)密文信息，密文內(nèi)容：WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC按照甲方與乙方的約定，他們之間的密文通信采用Hill2密碼，密鑰為二階矩陣問這段密文的原文是什么？

解已知密鑰

的逆矩陣是

，根據(jù)解密方法，得到分組明文見表12-3.

于是，實(shí)際問題(甲)的解為：

GUDIANMIMASHIYIZIFUWEIJIBENJIAMIDANYUANDEMIMA

即為：“古典密碼是以字符為基本加密單元的密碼”.

12.3MATLAB求解C

=char(A)

將數(shù)組

A

轉(zhuǎn)換為字符數(shù)組

從32到127的整數(shù)對(duì)應(yīng)于可打印的ASCII字符.ASCII字符表中65到90的整數(shù)代表大寫字母A到Z（見表12-3）.序號(hào)分組密文密文表值明文表值分組明文1WK2311721GU2VA22149DI3CP316114AN4E513M

A19I5O1513M

C31A6I919S

X248H7G79I

W2325Y8I99I

Z00Z9U219I

R186F10O1521U

Q1723W11W235E

A19I表12-3分組明文12BA210J

19I13L122B

O155E14H814N

D410J15K119I

C31A16E513M

A19I17F64D

C31A18L1214N

W2325Y19W2321U

C31A20V2214N

L124D21E55E

M1313M22I99I

M1313M23C31A

C31A例12.3字符函數(shù)char舉例.>>A=[776584766566];>>C=char(A)C='MATLAB'>>whosCNameSizeBytesClassAttributesC1x612char>>a='Hello,World';>>double(a)ans=列1至9721011081081114487111114列10至11108100例12.4加密過程可以通過MATLAB編程直接得到密文，程序如下：m=26;enmat=[12;03];ZERO=64;c=[];e1=[];astr=input('輸入要加密的明文文字(全部為大寫字母)：')whileany(double(astr)>90|double(astr)<65)astr=input('輸入錯(cuò)誤，應(yīng)該全部為大寫字母：')enda1=double(astr);lh=length(a1);ifmod(length(a1),2)==1a1=[a1,a1(length(a1))];enda1=a1-ZERO;fori=1:length(a1)ifa1(i)==26a1(i)=0;endendc=reshape(a1,2,length(a1)/2);d1=mod(enmat*c,m);e1=reshape(d1,length(a1),1);e1=e1';e1=e1+ZERO;fori=1:length(e1)ife1(i)==64e1(i)=90;endende1=e1(1:lh);char(e1)%將e1的每個(gè)數(shù)值轉(zhuǎn)換為字符例12.5

解密過程可以通過MATLAB編程直接得到原文，程序如下：m=26;enmat=[1,2;0,3];demat=[1,8;0,9];ZERO=64;c=[];e1=[];astr=input('輸入要解密的密文文字（全部為大寫字母）：')while

any(double(astr)>90|double(astr)<65)

astr=input('輸入錯(cuò)誤，全部應(yīng)該為大寫字母：')enda1=double(astr);lh=length(a1);if

mod(length(a1),2)==1

a