代數(shù)在密碼學中的應用*

付 麗,丁 慧

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

1 引言

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

表1 碼字表

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

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

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

2.1 棋盤密碼[2]

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

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

另一種常見的排列法ADFGX：

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

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

2.2 希爾密碼

希爾密碼是1929年提出的一種密碼體制，主要思想是利用矩陣的線性變換方法，運用基本矩陣論原理的替換密碼.每個字母當作26進制數(shù)字：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為分組數(shù)，m表示分組的大小.

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

2.3 凱撒密碼

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

若明文為I wish you happiness,對應的數(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)關系如下：

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

3 結論

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