探析初等數(shù)論基本知識在密碼學(xué)中的應(yīng)用

（東北大學(xué)理學(xué)院, 沈陽 110819）

（東北大學(xué)理學(xué)院, 沈陽 110819）

一次同余方程、二次剩余是初等數(shù)論中基本的理論，本文分別討論了它們在圖像加密和文本加密中的應(yīng)用。

一次同余方程；二次剩余；圖像加密；文本加密

1 預(yù)備知識

隨著信息技術(shù)特別是網(wǎng)絡(luò)技術(shù)的快速發(fā)展，圖像、視頻，聲音等多媒體信息在網(wǎng)絡(luò)上隨處可見。人們在網(wǎng)絡(luò)不斷傳送，共享著這些信息，在這些信息的傳送過程中，通信雙方都希望以一種安全的方式在非安全通信信道傳送。密碼學(xué)的根本的目的是要使通信雙方以一種非授權(quán)用戶不能理解的通信方式在不安全信道上通信。需要加密的信息被稱為明文，用M或者P表示，它可能是文本，圖像，語音信息或者視頻信息。用某種方法偽裝消息以隱藏它的內(nèi)容的過程稱為加密，加密后的沒有實(shí)際意義的信息稱為密文，密文用C表示，加密函數(shù)對明文進(jìn)行加密得到密文，同樣利用解密函數(shù)將密文轉(zhuǎn)變?yōu)槊魑牡倪^程稱為解密。明文通過加密解密之后，明文消息得到恢復(fù)。初等數(shù)論主要包括整除、同余式、二次剩余和連分?jǐn)?shù)等。信息技術(shù)特別是密碼學(xué)的發(fā)展，給數(shù)論的發(fā)展注入了新的發(fā)展活力，數(shù)論這門純之又純的數(shù)學(xué)迎來了新的發(fā)展歷程，本文以數(shù)論中的兩個(gè)基本知識為例，探討數(shù)論在密碼學(xué)和信息安全中的應(yīng)用。

2 一次線性同余方程及其在圖像加密中的應(yīng)用

同余方程是同余理論中的核心內(nèi)容，是應(yīng)用同余思想來研究整數(shù)問題的有力工具。一次同余方程是最基本的同余方程，即形如：ax≡b（modm）的方程，將其簡單變形得到加密函數(shù)：C（x）≡ax+b（modm），其中x是明文，C（x）是密文。若滿足（a,m）≡1，則其解密函數(shù)如下：D（C（x））≡a-1（ax+b（modm）-b）（modm）≡a-1（ax+b-b（modm）≡a-1ax≡x（modm），其中a-1,a滿足a-1a≡1（modm）。將其應(yīng)用于圖像加密，具體過程描述如下：

（1）將明文圖像按照從左到右，從上到下的順序轉(zhuǎn)為一維序列，并利用Logistic混沌映射對其進(jìn)行置亂，得到置亂后的一維明文序列：p={p1,p2,…,phxw},這里h,w是明文圖像的高和寬。

（2）對于每個(gè)pi，計(jì)算其密文：C（x）≡api+b（mod256），其中（a,256）=1

（3）對于明文圖像（圖1），利用上述算法其加密效果如圖2，

圖1 明文圖像Elain

圖2 密文圖像

顯然，明文信息得到了很好的隱藏。

3 二次剩余及其在文本加密中的應(yīng)用

二次剩余是數(shù)論的基本概念之一。若（a,m）=1，方程x2≡a（modm）有解，則稱a是模m的二次剩余，否則稱a是模m的二次非剩余。為了研究二次剩余在密碼學(xué)中的應(yīng)用，首先介紹幾個(gè)相關(guān)的概念。

利用Legendre符號，我們又給出了Jacobi符號的定義：對任意給定的整數(shù)滿足（a,n）=1,n的素?cái)?shù)分解表達(dá)式為n=，則Jacobi符號為Legendre符號的乘積：

若a是模n的二次剩余,記為a∈Qn ,二次剩余問題可以描述為，給定正整數(shù)a和n，確定a∈Qn是否成立，求解二次剩余問題等價(jià)于求解n的素因式分解，這在計(jì)算上是不可行的。

（1）設(shè)n=rs,其中r,s是素?cái)?shù)，其大小大約相同，作為私鑰保存。

（3）對于給定的文本序列中的每一個(gè)元素gi，轉(zhuǎn)換為0～25之間的整數(shù)，然后再轉(zhuǎn)化為一個(gè)二進(jìn)制序列{b1,b2,…,b8} 對每個(gè)bk，k=1,…8,我們隨機(jī)選擇某個(gè)剩余類中的元素tk， 計(jì)算

這樣，能保證同一個(gè)明文得到不同的密文，從而得到其加密序列{ci1,ci2,…ci8}。

取明文序列18,06,23,18，其對應(yīng)的明文比特序列為：00010010,00000110,00010111, 00010010。利用上述加密算法，其密文為：100 82 16 127 130 22 140 81, , 56 82 49 56 1 40 140 114, 36 75 104 134 1 129 117 120, 126 48 49 134 81 4 43 16。

從加密過程可以看出，對于同樣的明文18，加密之后，得到了不同的加密序列，加密效果較好。對應(yīng)的解密過程如下：

（1）對于每一個(gè)整數(shù)密文cij，i=1…，8N，j=1,… ,8其中8N是

密文比特序列的長度。計(jì)算Legendre符號：

（2）根據(jù)計(jì)算出來的Legendre符號決定mi的取值，若, 則mi=0，其他mi=1。

（3）得到解密后的明文比特序列：{m1,m2,…,m8N} ，然后按照沒8位一組轉(zhuǎn)換為明文整數(shù)序列，得到解密后的明文。

綜上，本文列舉了初等數(shù)論中兩個(gè)基本理論在密碼學(xué)和信息安全中的應(yīng)用，數(shù)論這門被人認(rèn)為是離實(shí)際應(yīng)用很遠(yuǎn)的數(shù)學(xué)學(xué)科，在現(xiàn)代信息安全技術(shù)中正起著越來越重要的作用，煥發(fā)了新的活力。

[1]潘承洞、潘承彪.初等數(shù)論（第二版）[M].北京：北京大學(xué)出版社，2004.

[2]Paul Garrett.密碼學(xué)導(dǎo)引[M].北京：機(jī)械工業(yè)出版社，2003.

[3] 顏松遠(yuǎn).計(jì)算數(shù)論（第二版）[M].北京：清華大學(xué)出版社，2008.

探析初等數(shù)論基本知識在密碼學(xué)中的應(yīng)用

朱和貴

朱和貴（1980-）,男，湖南雙峰人，講師，研究方向：信息安全。