探析初等數論基本知識在密碼學中的應用

（東北大學理學院, 沈陽 110819）

（東北大學理學院, 沈陽 110819）

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

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

1 預備知識

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

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

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

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

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

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

圖1 明文圖像Elain

圖2 密文圖像

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

3 二次剩余及其在文本加密中的應用

二次剩余是數論的基本概念之一。若（a,m）=1，方程x2≡a（modm）有解，則稱a是模m的二次剩余，否則稱a是模m的二次非剩余。為了研究二次剩余在密碼學中的應用，首先介紹幾個相關的概念。

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

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

（1）設n=rs,其中r,s是素數，其大小大約相同，作為私鑰保存。

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

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

取明文序列18,06,23,18，其對應的明文比特序列為：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，加密之后，得到了不同的加密序列，加密效果較好。對應的解密過程如下：

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

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

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

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

綜上，本文列舉了初等數論中兩個基本理論在密碼學和信息安全中的應用，數論這門被人認為是離實際應用很遠的數學學科，在現代信息安全技術中正起著越來越重要的作用，煥發了新的活力。

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

[2]Paul Garrett.密碼學導引[M].北京：機械工業出版社，2003.

[3] 顏松遠.計算數論（第二版）[M].北京：清華大學出版社，2008.

探析初等數論基本知識在密碼學中的應用

朱和貴

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