付 麗,丁 慧

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

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

付 麗,丁 慧

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

矩陣的初等變換是線性代數(shù)的重要內(nèi)容，而密碼學(xué)中很多經(jīng)典的密碼及其編碼與解密的方法，都要用到矩陣及初等變換，如棋盤密碼、希爾密碼、凱撒密碼、Walsh譜等.

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

1 引言

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

表1 碼字表

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

我們把消息稱為明文.用某種方法偽裝消息以隱藏它的內(nèi)容的過程稱為加密.加了密的消息稱為密文.把密文轉(zhuǎn)換成明文的過程稱為解密.無論是加密還是解密的過程都會用到代數(shù)學(xué)的知識.例如可逆矩陣可用來對需要傳輸?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]

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

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

另一種常見的排列法ADFGX：

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

第一次世界大戰(zhàn)將要結(jié)束時，法軍截獲了一份所有單詞都由A、D、F、G、X五個字母拼成的德軍電報，因此被稱為ADFGX密碼.1918年3月德軍上校FritzNebel發(fā)明了ADFGX密碼，其是結(jié)合了Polybius密碼和置換密碼的雙重加密方案.還是上面那個例子school，使用這個表格加密，就是FGGFDDDFDFAG.但由于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的矩陣相乘，再將得出的結(jié)果模26.用作加密的矩陣(即密匙)必須是可逆的，否則就不可譯碼.只有矩陣的行列式和26互質(zhì)，才是可逆的.在希爾密碼中，密鑰是一個可逆的m×m方陣，m表示分組的大小.如果把密鑰矩陣稱為A，矩陣的每個元素就是aij.

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

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

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

…………,

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

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

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

2.3 凱撒密碼

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

若明文為Iwishyouhappiness,對應(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.4Walsh譜[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é)中運用的代數(shù)知識都比較簡單，但足以看出代數(shù)是一個重要的工具，它的應(yīng)用是十分廣泛的，特別是矩陣的知識.所以老師在進行這部分教學(xué)時，應(yīng)該講解一些應(yīng)用的實例，這樣不僅能提高學(xué)生學(xué)習(xí)的興趣，使學(xué)生在學(xué)習(xí)中體會到所學(xué)知識在解決問題中可以發(fā)揮巨大作用，也能逐漸增強學(xué)生應(yīng)用數(shù)學(xué)解決實際問題的意識，提高學(xué)生應(yīng)用數(shù)學(xué)知識解決問題的能力.

[1]吳香華,熊萍萍,朱連華.線性代數(shù)教學(xué)中的一點體會[J].科技創(chuàng)新導(dǎo)報,2009(36).

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

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

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

[5]章照止.現(xiàn)代密碼學(xué)基礎(chǔ)[M].北京:北京郵電大學(xué)出版社,2004.

(責任編輯:王宏志)

2013-12-10

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

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

O

A

1008-7974(2014)01-0029-03