代數(shù)在密碼學(xué)中的應(yīng)用*

付 麗,丁 慧

(綏化學(xué)院 信息工程學(xué)院,黑龍江 綏化 152061)

1 引言

二戰(zhàn)期間，一些優(yōu)秀的數(shù)學(xué)家，包括著名數(shù)學(xué)家圖靈等對(duì)己方信息的加密和對(duì)敵方信息的破譯工作做出了突出貢獻(xiàn).目前密碼學(xué)的應(yīng)用不再局限于軍事、政治和外交，而擴(kuò)大到商務(wù)、金融和社會(huì)各個(gè)領(lǐng)域，特別是全球范圍的互聯(lián)網(wǎng)的出現(xiàn)和發(fā)展，為人們提供了快捷、高速和廉價(jià)的通信，大量敏感信息常常要通過互聯(lián)網(wǎng)進(jìn)行交換.現(xiàn)代電子商務(wù)也是以互聯(lián)網(wǎng)為基礎(chǔ)，人們十分關(guān)心在網(wǎng)絡(luò)上交換信息的安全性.因此在計(jì)算機(jī)安全方面研究了數(shù)據(jù)庫(kù)保密和保密數(shù)據(jù)庫(kù)的攻擊問題，形成了一個(gè)廣闊的研究領(lǐng)域.數(shù)學(xué)在密碼學(xué)中具有重要的地位，線性代數(shù)、概率論與數(shù)理統(tǒng)計(jì)、數(shù)論等知識(shí)都是對(duì)密碼進(jìn)行加密和解密的常用工具.

表1 碼字表

2 矩陣在密碼學(xué)中的簡(jiǎn)單應(yīng)用

我們把消息稱為明文.用某種方法偽裝消息以隱藏它的內(nèi)容的過程稱為加密.加了密的消息稱為密文.把密文轉(zhuǎn)換成明文的過程稱為解密.無論是加密還是解密的過程都會(huì)用到代數(shù)學(xué)的知識(shí).例如可逆矩陣可用來對(duì)需要傳輸?shù)男畔⒓用?，首先要給每個(gè)字母指派一個(gè)碼字(如表1).[1]

如果直接發(fā)送矩陣B，這是不加密的信息，容易被破譯，無論軍事或商業(yè)上均不可行，因此必須對(duì)信息予以加密，使得只有知道密鑰的接收者才能準(zhǔn)確、快速破譯.為此，可以取定3階可逆矩陣A，并且滿足A的元素均為整數(shù)；|A|=±1，這樣A-1的元素也均為整數(shù).令C=AB(即對(duì)B做線性變換)，則C是3×4矩陣，其元素也均為整數(shù).現(xiàn)發(fā)送加密后的信息矩陣C，己方接收者只需用A-1(即對(duì)C做線性變換)進(jìn)行解密，就得到發(fā)送者的信息：B=A-1C.

2.1 棋盤密碼[2]

棋盤密碼產(chǎn)生于公元前兩世紀(jì)的希臘，相傳是世界上最早的一種密碼.簡(jiǎn)單的來說就是把字母排列好，用坐標(biāo)的形式表現(xiàn)出來.字母是密文，明文便是字母的坐標(biāo).常見的排列方法：

從這個(gè)密碼誕生開始表中i和j就在同一格中.每個(gè)字母對(duì)應(yīng)一個(gè)二元有序組ij，i是字母所在行號(hào)，j是所在的列號(hào).這是一個(gè)比較常用的排列方法.不同的國(guó)家有不同的排列法.舉個(gè)例子school，加密后就是43 13 23 31 34 34 31.

另一種常見的排列法ADFGX：

這里字母的順序打亂了，但與前面一種相同的是i和j視為同一個(gè)字，使字母數(shù)量仍符合5×5格.

第一次世界大戰(zhàn)將要結(jié)束時(shí)，法軍截獲了一份所有單詞都由A、D、F、G、X五個(gè)字母拼成的德軍電報(bào)，因此被稱為ADFGX密碼.1918年3月德軍上校Fritz Nebel發(fā)明了ADFGX密碼，其是結(jié)合了Polybius密碼和置換密碼的雙重加密方案.還是上面那個(gè)例子school，使用這個(gè)表格加密，就是FG GF DD DF DF AG.但由于ADFGX的加密法發(fā)送含有大量數(shù)字的簡(jiǎn)短信息.1918年6月又加入了一個(gè)字符V對(duì)ADFGX進(jìn)行擴(kuò)充，變成了共36個(gè)字符的6×6格的加密，這就是ADFGVX.這使得數(shù)字0到9以及所有英文字母(不再將i和j視為同一個(gè)字)都可以混合使用.

2.2 希爾密碼

希爾密碼是1929年提出的一種密碼體制，主要思想是利用矩陣的線性變換方法，運(yùn)用基本矩陣論原理的替換密碼.每個(gè)字母當(dāng)作26進(jìn)制數(shù)字：A=0,B=1,C=2…一串字母當(dāng)成n維向量，跟一個(gè)n×n的矩陣相乘，再將得出的結(jié)果模26.用作加密的矩陣(即密匙)必須是可逆的，否則就不可譯碼.只有矩陣的行列式和26互質(zhì)，才是可逆的.在希爾密碼中，密鑰是一個(gè)可逆的m×m方陣，m表示分組的大小.如果把密鑰矩陣稱為A，矩陣的每個(gè)元素就是aij.

把明文中每個(gè)分組中的m字符稱為b1,b2,…,bm，相應(yīng)的密文中的字符稱為c1,c2,…,cm，則加密算法為

c1=b1a11+b2a21+…+bmam1(mod26)，
c2=b1a12+b2a22+…+bmam2(mod26)，
…………,
cm=b1a1m+b2a2m+…+bmamm(mod26)，

這樣可以利用矩陣對(duì)整個(gè)明文進(jìn)行加密，如果明文就是一個(gè)l×m的矩陣，l為分組數(shù)，m表示分組的大小.

這就是用希爾密碼進(jìn)行加密和解密的一個(gè)簡(jiǎn)單的例子.實(shí)際應(yīng)用中，用于加密的可逆矩陣A的階數(shù)可能很大，其構(gòu)造也十分復(fù)雜，同時(shí)密碼的編制還有許多其他方法.

2.3 凱撒密碼

凱撒密碼是一種代換密碼.他的基本思想是：通過把字母移動(dòng)一定的位數(shù)來實(shí)現(xiàn)加密和解密.明文中的所有字母都在字母表上向后(或向前)按照一個(gè)固定數(shù)目進(jìn)行偏移后被替換成密文.若將26個(gè)字母分別對(duì)應(yīng)于0,1，…，25，則凱撒密碼加密變換可以看做矩陣的加法再模26的計(jì)算:ci≡mi+k(mod26),i=1,2,…,n.其中M=(m1.m2,…,mn)是明文對(duì)應(yīng)的數(shù)據(jù)矩陣，C=(c1,c2,…,cn)是與之對(duì)應(yīng)的密文數(shù)據(jù)矩陣，k=(k1,k2,…,kn)是密鑰數(shù)據(jù)矩陣.例如，當(dāng)偏移量是3的時(shí)候，所有的字母A將被替換成D，B變成E，以此類推X將變成A，Y變成B，Z變成C.由此可見，位數(shù)就是凱撒密碼加密和解密的密鑰.

若明文為I wish you happiness,對(duì)應(yīng)的數(shù)據(jù)矩陣為(9,0,23,9,19,8,0,25,15,21,0,8,1,16,16,9,14,5,19,19)，密鑰矩陣為(3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3)，則密文為lczlvkcarxckdsslqhvv.

2.4 Walsh譜[4]

稱為f(x)的第一種譜或Walsh譜.

定理1S(f)(w)與Sf(w)關(guān)系如下：

定理2 設(shè)x=(x1,…,xn)，w=(w1,…,wn)∈GF(2)n，f(x)是n元布爾函數(shù)，

3 結(jié)論

雖然在密碼學(xué)中運(yùn)用的代數(shù)知識(shí)都比較簡(jiǎn)單，但足以看出代數(shù)是一個(gè)重要的工具，它的應(yīng)用是十分廣泛的，特別是矩陣的知識(shí).所以老師在進(jìn)行這部分教學(xué)時(shí)，應(yīng)該講解一些應(yīng)用的實(shí)例，這樣不僅能提高學(xué)生學(xué)習(xí)的興趣，使學(xué)生在學(xué)習(xí)中體會(huì)到所學(xué)知識(shí)在解決問題中可以發(fā)揮巨大作用，也能逐漸增強(qiáng)學(xué)生應(yīng)用數(shù)學(xué)解決實(shí)際問題的意識(shí)，提高學(xué)生應(yīng)用數(shù)學(xué)知識(shí)解決問題的能力.