代數在密碼學中的應用*

付 麗,丁 慧

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

代數在密碼學中的應用*

付 麗,丁 慧

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

矩陣的初等變換是線性代數的重要內容，而密碼學中很多經典的密碼及其編碼與解密的方法，都要用到矩陣及初等變換，如棋盤密碼、希爾密碼、凱撒密碼、Walsh譜等.

棋盤密碼;希爾密碼;凱撒密碼;Walsh譜

1 引言

二戰期間，一些優秀的數學家，包括著名數學家圖靈等對己方信息的加密和對敵方信息的破譯工作做出了突出貢獻.目前密碼學的應用不再局限于軍事、政治和外交，而擴大到商務、金融和社會各個領域，特別是全球范圍的互聯網的出現和發展，為人們提供了快捷、高速和廉價的通信，大量敏感信息常常要通過互聯網進行交換.現代電子商務也是以互聯網為基礎，人們十分關心在網絡上交換信息的安全性.因此在計算機安全方面研究了數據庫保密和保密數據庫的攻擊問題，形成了一個廣闊的研究領域.數學在密碼學中具有重要的地位，線性代數、概率論與數理統計、數論等知識都是對密碼進行加密和解密的常用工具.

表1 碼字表

2 矩陣在密碼學中的簡單應用

我們把消息稱為明文.用某種方法偽裝消息以隱藏它的內容的過程稱為加密.加了密的消息稱為密文.把密文轉換成明文的過程稱為解密.無論是加密還是解密的過程都會用到代數學的知識.例如可逆矩陣可用來對需要傳輸的信息加密，首先要給每個字母指派一個碼字(如表1).[1]

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

2.1 棋盤密碼[2]

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

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

另一種常見的排列法ADFGX：

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

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

2.2 希爾密碼

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

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

c1=b1a11+b2a21+…+bmam1(mod26)，

c2=b1a12+b2a22+…+bmam2(mod26)，

…………,

cm=b1a1m+b2a2m+…+bmamm(mod26)，

這樣可以利用矩陣對整個明文進行加密，如果明文就是一個l×m的矩陣，l為分組數，m表示分組的大小.

這就是用希爾密碼進行加密和解密的一個簡單的例子.實際應用中，用于加密的可逆矩陣A的階數可能很大，其構造也十分復雜，同時密碼的編制還有許多其他方法.

2.3 凱撒密碼

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

若明文為Iwishyouhappiness,對應的數據矩陣為(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.4Walsh譜[4]

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

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

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

則

3 結論

雖然在密碼學中運用的代數知識都比較簡單，但足以看出代數是一個重要的工具，它的應用是十分廣泛的，特別是矩陣的知識.所以老師在進行這部分教學時，應該講解一些應用的實例，這樣不僅能提高學生學習的興趣，使學生在學習中體會到所學知識在解決問題中可以發揮巨大作用，也能逐漸增強學生應用數學解決實際問題的意識，提高學生應用數學知識解決問題的能力.

[1]吳香華,熊萍萍,朱連華.線性代數教學中的一點體會[J].科技創新導報,2009(36).

[2]湯燕.矩陣在密碼學中的應用[J].科教文匯,2010(08).

[3]劉木蘭.數學在密碼中的某些應用[J].數學的實踐與認識,1986(03).

[4]周建欽.密碼學中的線性變換[J].電子科技大學學報,2007(1).

[5]章照止.現代密碼學基礎[M].北京:北京郵電大學出版社,2004.

(責任編輯:王宏志)

2013-12-10

付麗(1982-),女,黑龍江綏化人,講師.

綏化學院青年基金項目(項目編號：QK1103002).

O

A

1008-7974(2014)01-0029-03