基于線性同余的不定態結果加密算法

王思樂，盧素魁，楊文柱

（河北大學 數學與計算機學院，河北 保定 071002）

基于線性同余的不定態結果加密算法

王思樂，盧素魁，楊文柱

（河北大學 數學與計算機學院，河北 保定 071002）

傳統的加密算法往往比較復雜而難以掌握，復雜的算法往往大大增加程序的復雜度，同一算法加密結果不變又降低了加密結果的抗破解能力.經過對線性同余序列數據特征的研究以及在實踐中經過長時間摸索與檢測，基于線性同余序列提出了一種實用的加密方法，簡單、容易實現；在盡量不損失加密強度的情況下提高了加解密速度，同時，同一輸入得到的加密結果輸出不同，一定程度上增強了抗破解能力.

線性同余；快速；不定態；加密

隨著計算機和網絡應用的不斷普及，信息技術已經滲透到人類生活的方方面面，尤其是軍事、經濟、金融、商業等社會各部門對計算機的依賴程度越來越高.與此同時，信息及網絡安全不斷受到挑戰，對Internet和連接到Internet系統的攻擊正以驚人的速度增加，以至于無法準確統計犯罪案件，計算機犯罪的增長速度遠遠超過了傳統的犯罪，因此，實現通信保密和網絡安全已上升為一個事關國家政治穩定、社會安定、經濟有序運行、構建和諧社會的全局性問題.同時，各個國家對于信息戰也越來越重視，網絡攻防成為很多國家研究的熱點，其中加密技術作為整個安全系統的底層越來越受到人們的關注.

加密算法研究者從加密強度和非對稱加密角度做了大量的工作，構造了一系列行之有效的加密算法［1-3］.從加密本身來說，這些算法往往具有較好的魯棒性和強度，但在一些需要較高加解密速度的領域，由于算法本身的復雜性，往往難以適應.比如網絡IKE交換，往往需要適應快速變換的加解密算法，這就要求存在足夠簡單且有一定強度的加密算法.筆者試圖構造一種方法，在盡量不降低加密強度的前提下適應快速密鑰運算.

1 偽隨機數與隨機序列

真正意義上的隨機數（或者隨機事件）在某次產生過程中是按照實驗過程中表現的分布概率隨機產生的，其結果是不可預測的，是不可見的.而計算機中的隨機函數是按照一定算法模擬產生，其結果是確定的，是可見的.可以這樣認為，這個可預見的結果其出現的概率是100%，所以用計算機隨機函數所產生的“隨機數”并不隨機，是偽隨機數.偽隨機數有2個特點：

1）在某一整數范圍內產生足夠多的隨機數的時候數據在該范圍內均勻分布，也就是說取到各個整數值的機會均等.

2）連續產生的隨機數在較大范圍內不能序列重復［4］.

這里的序列重復是指不應該像循環小數一樣存在循環節，當然，絕大多數隨機數產生算法還是有循環節的，但這個循環節往往非常長.

這2個特點非常適合加密.任何數據經過隨機序列掩碼產生的結果也將具備如上的數據特征，掩碼后的結果在不知道掩碼序列的情況下將很難逆推回原序列，就以這種思路來構造加密算法.

2 大數同余

快速產生隨機序列是提高本方法加密速度的關鍵，筆者研究了一下Visual C＋＋，Turbo C和Delphi的隨機序列產生辦法，它們采用的都是大數的線性同余序列.設m是一個給定的正整數，如果2個整數a，b用m除，所得的余數相同，則稱a，b對模m同余.所謂線性同余法（又叫混合同余法），就是這樣的一個公式：X［i＋1］＝（A＊X［i］＋C）modM；經前人研究表明，在M＝2q的條件下，參數A，C，X［0］按如下選取，周期較大，概率統計特性好［5-6］：

X［0］為任意非負數［7］

同余序列總是進入一個循環，這是一個事實，最終必定在N個數之間無休止的重復循環.在本文中不打算探討同余序列的循環問題，盡管這方面也有很多人在孜孜不倦的努力，但這和本文的核心內容無關，即便采用Turbo C的同余參數，也能得到周期達到2 147 483 647的隨機序列（RAND＿MAX定義），20多億的序列長度對于討論的加密情況來說足夠了，關鍵是線性同余產生的隨機序列不僅滿足第2節所陳述的隨機序列特征，而且速度非常快，在Delphi中甚至短短10行左右的匯編代碼就能實現了，當然，還有很多人研究了偽隨機序列的硬件實現，更能進一步提高速度［8］.

3 新的隨機數發生器

如上所述，即便采用唯一的隨機序列發生器產生的隨機序列進行掩碼，也可以得到均勻分布的加密結果，當然這樣的加密在預知加密算法的前提下對密碼進行碰撞還是很容易解密的，這就需要進一步的增強密碼空間，加大碰撞難度.這里可以利用線性同余算法對于不同的因子可以產生不同的隨機序列這一特點，使加密過程和密碼長度關聯起來，構造一個新的隨機數發生器，它的因子是密碼相關的.

很明顯，常見密碼是可視字符的組合，為了討論方便，不妨按照常見的密碼設置：英文字母，數字和下劃線的組合，稱為密碼空間，這樣密碼就可以表示為函數

綜上，通過詳細介紹醫院中生殖醫學中心候診空間的建設設計要點、診室空間的建設設計要點、醫護工作區的建設設計要點、流線組織的建設設計要點等，能夠幫助醫院中生殖醫學中心建設設計人員更好的了解各個科室的建設設計要求，保證醫院生殖醫學中心建設設計方案更加合理，為患者提供一個更好的就醫環境。

符號＆表示連接.

以x為因子的隨機序列表示為函數RandomSequence（x），根據隨機序列的定義，RandomSequence（x）為x相關的整數有序集合，RandomSequence（x）?Z且當x1≠x2時有RandomSequence（x1）≠RandomSequence（x2）.

定義函數Select（X1，X2，X3，…，Xn，m）為X1∪X2∪X3∪…∪xn到｛X｜X∈X1∪X2∪X2∪…∪Xn｝的一個映射，其中X1～Xn為有序集合，m∈Z＋，表示順序的從X1～Xn取第1個值，取到Xn后返回X1繼續取X1的第2個，X2的第2個以此類推，直到取m個值為止.

對于密碼 Mix（x1，x2，x3，…，xn），隨機序列就是Select（RandomSequence（x1），RandomSequence（x2），RandomSequence（x3），…，RandomSequence（xn），m），m的取值和被加密對象的長度相關.很明顯，如果原隨機序列周期為p，采用這個方法后實際上隨機序列的周期將變為pn，同時，要碰撞出這樣一個序列的話需要驗證的密碼要在n個密碼空間的笛卡爾乘積中選取，即便在當前的設定下，1個密碼空間的長度為63（大小寫字母，下劃線和0～9的數碼），n個字符長度的密碼對應的密碼數量將為63n，只要長度足夠（實際上4位的密碼634＝15 752 961，就已經上千萬了），窮舉破解在時間上應該是不可能的.

4 加密與解密

在隨機序列已經構造的前提下，加密解密是一個非常簡單的過程，這里為了實用性筆者對加密對象做了以下區分：

A.密文可視的；

B.密文可視無關的.

對于A類，是指存儲在文本文件或數據庫中的數據片段，這類數據往往有些格式要求，比如加密結果不能包含0或者其他的特定字符，但可用范圍往往可以界定.B類就是沒有這種考慮的加密對象，很明顯，一個加密算法對不同的對象進行區分不太合適，還不能增加算法的復雜度，所以在算法上筆者是如此考慮的：

Ⅰ.以字節為加密單位進行換碼加密.

這樣就將A，B兩類對象又整合為同一類對象了，為了適應這種情況，在Select（RandomSequence（x1），RandomSequence（x2），RandomSequence（x3），…，RandomSequence（xn），m）中取值后需要對相應范圍取模，假定給定范圍為［a，b］，原文k1k2k3…km，密碼 Mix（x1，x2，x3，…，xn），Select（RandomSequence（x1），RandomSequence（x2），RandomSequence（x3），…，RandomSequence（xn），m）中取的第j個值為Roldj，令rj＝Roldjmod（b-a＋1）.

則換碼加密函數為換碼解密函數為

算法類似于補碼運算，應該不需要做解釋，可以簡單驗證.

原文為′A′（AscII碼為65），范圍為［32，127］（ASCII可視范圍），則Roldj不妨假設為100，則rj＝100mod（127-32＋1）＝4.

本算法已經使用VC 2008實現，使用一般字符串測試，范圍設定為［32，127］，數組測試使用范圍［0，255］，結果如圖1.

圖1 簡單加密測試結果Fig.1 Test result for simple crypt

從圖1可以看出，掩碼后失去了原文的一切特征，即便原文為重復字符，掩碼后內容也完全不同，從密文測度原文是不可能的.對這一點，筆者特別針對圖片做了一個測試，采用2幅圖片，一幅純白（rgb（255，255，255）），一幅為復雜圖像，測試結果如圖2.

圖2 純白圖像加密測試Fig.2 Test for all white image crypt

圖3 復雜圖像加密測試Fig.3 Test for complex image crypt

從圖2和圖3可以看出，即便2幅圖的復雜程度完全不同，掩碼結果也沒有什么太大區別并且完全看不出原圖效果，在未受到攻擊時，可以精確還原原圖像，使用GetTickCount64函數測試，沒做任何優化的情況下一幅256k24位真彩圖片加密時間為16ms，速度已經很快了.

5 關于不定態結果

一般情況下，對于加密算法f以及明文x及其密碼p，其加密結果R＝f（x，p）是唯一的，這樣的話如果有密文，在已知加密算法的情況下可以通過逆推及碰撞的方法去猜測明文，所以一般的加密方法要求盡量采用長密碼串以擴大碰撞空間，達到防破解的目的.筆者的想法是在原文、密碼的加密基礎上在密文中增加一個擾動量，其加密規則如下：

1）定義擾動量Kn為隨機獲取的n個字節集合.

2）原加密密碼x為一個不定長度的字節集合，加密前利用Kn使用前述算法p對密文進行擾動，變換為X＝p（x，Kn）.

3）針對前述算法，使用X對原文S加密形成初步加密結果r＝p（S，X）.

4）將Kn合并到r的固定位置形成最終密文R＝Kn∪r.

解密時：

1）對密文R切除指定位置的n個字節得到密文r和擾碼Kn.

2）使用Kn對密碼x進行擾動變換（同加密）X＝p（x，Kn）.

3）使用X對r進行前述加密變換的逆變換得到原文S＝p-1（r，X）.

過程比較簡單，不再細述.其優點在于擾碼可以隨意獲取，而隨擾碼的不同加密結果在形式上也隨之變換，從密文難以推導原文.

6 結論

基于線性同余的隨機序列對加密進行了一些探討，該方法與傳統加密算法相比，在不喪失加密強度的情況下具備算法簡單、快速的特點，對于需要簡單加密同時又需要一定的加密強度的需求而言，不失為一個適當的解決方案.

［1］ 杜立健，唐曉燕，李守榮.幾種信息加密算法的比較研究［J］.網絡安全技術與應用，2006（8）：88-89.

DU Lijian，TANG Xiaoyan，LI Shourong.Comparative studies of information encryption algorithms［J］.Network Security Technology ＆ Application，2006（8）：88-89.

［2］ 鄭麗娟，鄭麗偉，高帥，等，郵件加密算法PGP的改進［J］.河北大學學報：自然科學版，2004，24（3）：311-314.

ZHENG Lijuan，ZHENG Liwei，GAO Shuai，et al.Improvement of mail encryption algorithm PGP［J］.Journal of Hebei University：Natural Science Edition，2004，24（3）：311-314.

［3］ 吳曉麗.基于“陷門漸縮”原理的公鑰算法［J］.河北大學學報：自然科學版，1999，19（3）：314-316.

WU Xiaoli.Pubic key algorithm based on a principle of“Trap finapsack”［J］.Journal of Hebei University：Natural Science Edition，1999，19（3）：314-316.

［4］ 王怡林.產生偽隨機數的一種新方法［J］.楚雄師專報，1996（3）：63-69.

［5］ GRIFfiN F，SHPARLINSKI I E.On the linear complexity profile of the power generator［J］.IEEE Trans Inform Theory，2000，46（6）：2159-2162.

［6］ GUTIERREZ J，SHPARLINSKI I E，WINTERHOF A.On the linear and nonlinear complexity profile of nonlinear pseudorandom number generators［J］.IEEE Trans Inform Theory，2003，49（1）：60-64.

［7］ 周燕.關于線性同余組合發生器的周期性和統計性質［J］.重慶大學學報：自然科學版，2000，23（6）：67-70.

ZHOU Yan.On the research of the periodicity and statistical characteristics by linear congruence and combined generator［J］.Journal of Chongqing University：Natural Science Edition，2000，23（6）：67-70.

［8］ 束禮寶，宋克柱，王硯.偽隨機數發生器的 FPGA實現與研究［J］.電路與系統學報，2003，8（3）：121-124.

SHU Libao，SONG Kezhu，WANG Yan.The implementation and research on pseudo random number generators with FPGA［J］.Journal of Circuits and Systems，2003，8（3）：121-124.

［9］ 趙玉霞.基于混沌序列的數字圖像置亂算法［J］.商洛學院學報，2009，23（2）：33-37.

ZHAO Yuxia.A digital image scrambling algorithm based on chaotic sequences［J］.Journal of Shangluo University，2009，23（2）：33-37.

［10］ 崔忠偉.基于哥德巴赫猜想的公鑰加密算法的分析與研究［J］.貴州師范學院學報：社會科學版，2010，26（9）：23-25.

CUI Zhongwei.Analysis and research on the public key encryption algorithm based on Goldbach＇s conjecture［J］.Journal of Guizhou Educational College：Social Science Edition，2010，26（9）：23-25.

［11］ 廖文軍，陳曉前.基于多線程技術的 DES加密算法［J］.新鄉學院學報：自然科學版，2009，26（5）：63-64.

LIAO Wenjun，CHEN Xiaoqian.The DES algorithm based on multi-threading technology ［J］.Journal of Xinxiang Teachers College，2009，26（5）：63-64.

［12］ 李元元.橢圓曲線加密算法在指紋加密技術中的應用［J］.計算機安全，2009（8）：48-50.

LI Yuanyuan.ECC Encryption algorithm in fingerprint ttechnology［J］.Network ＆ Computer Security，2009（8）：48-50.

［13］ 李維勇.一種字符型數據加密算法研究［J］.計算機安全，2009（11）：56-58.

LI Weiyong.Research of the encrypted character data in database［J］.Network ＆Computer Security，2009（11）：56-58.

［14］ 方明，余靜.DES加密算法［J］.裝備制造，2009（9）：152.

Uncertain state encryption algorithm based on linear congruential sequence

WANG Sile，LU Sukui，YANG Wenzhu
（College of Mathematics and Computer Science，Hebei University，Baoding 071002，China）

The traditional encryption algorithms is often more complex and difficult to master，complex algorithms tend to greatly increase the complexity of the program，the same encryption algorithm results are the same and reduce the resistance to crack the encryption result ability.After the linear congruential sequences data on study characteristics as well as in practice after long time exploration and detection based on linear congruential sequences，this paper puts forward a practical method of encryption，simple，easy to realize；as far as possible without loss of intensity of encryption cases to improve the encryption speed，at the same time，the same input encryption results the output of different，some extent increase the anti crack capacity.

linear congruential；fast；different from certain extent；encryption

TP30

A

1000-1565（2012）05-0532-06

2012-05-10

河北省人力資源和社會保障課題（JRS-2011-6011）

王思樂（1971-），男，河北廊坊人，河北大學講師，主要從事軟件工程方面研究.E-mail：fontain＠163.com

孟素蘭）