基于線性同余的不定態(tài)結(jié)果加密算法

王思樂(lè)，盧素魁，楊文柱

（河北大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，河北 保定 071002）

基于線性同余的不定態(tài)結(jié)果加密算法

王思樂(lè)，盧素魁，楊文柱

（河北大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，河北 保定 071002）

傳統(tǒng)的加密算法往往比較復(fù)雜而難以掌握，復(fù)雜的算法往往大大增加程序的復(fù)雜度，同一算法加密結(jié)果不變又降低了加密結(jié)果的抗破解能力.經(jīng)過(guò)對(duì)線性同余序列數(shù)據(jù)特征的研究以及在實(shí)踐中經(jīng)過(guò)長(zhǎng)時(shí)間摸索與檢測(cè)，基于線性同余序列提出了一種實(shí)用的加密方法，簡(jiǎn)單、容易實(shí)現(xiàn)；在盡量不損失加密強(qiáng)度的情況下提高了加解密速度，同時(shí)，同一輸入得到的加密結(jié)果輸出不同，一定程度上增強(qiáng)了抗破解能力.

線性同余；快速；不定態(tài)；加密

隨著計(jì)算機(jī)和網(wǎng)絡(luò)應(yīng)用的不斷普及，信息技術(shù)已經(jīng)滲透到人類生活的方方面面，尤其是軍事、經(jīng)濟(jì)、金融、商業(yè)等社會(huì)各部門(mén)對(duì)計(jì)算機(jī)的依賴程度越來(lái)越高.與此同時(shí)，信息及網(wǎng)絡(luò)安全不斷受到挑戰(zhàn)，對(duì)Internet和連接到Internet系統(tǒng)的攻擊正以驚人的速度增加，以至于無(wú)法準(zhǔn)確統(tǒng)計(jì)犯罪案件，計(jì)算機(jī)犯罪的增長(zhǎng)速度遠(yuǎn)遠(yuǎn)超過(guò)了傳統(tǒng)的犯罪，因此，實(shí)現(xiàn)通信保密和網(wǎng)絡(luò)安全已上升為一個(gè)事關(guān)國(guó)家政治穩(wěn)定、社會(huì)安定、經(jīng)濟(jì)有序運(yùn)行、構(gòu)建和諧社會(huì)的全局性問(wèn)題.同時(shí)，各個(gè)國(guó)家對(duì)于信息戰(zhàn)也越來(lái)越重視，網(wǎng)絡(luò)攻防成為很多國(guó)家研究的熱點(diǎn)，其中加密技術(shù)作為整個(gè)安全系統(tǒng)的底層越來(lái)越受到人們的關(guān)注.

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

1 偽隨機(jī)數(shù)與隨機(jī)序列

真正意義上的隨機(jī)數(shù)（或者隨機(jī)事件）在某次產(chǎn)生過(guò)程中是按照實(shí)驗(yàn)過(guò)程中表現(xiàn)的分布概率隨機(jī)產(chǎn)生的，其結(jié)果是不可預(yù)測(cè)的，是不可見(jiàn)的.而計(jì)算機(jī)中的隨機(jī)函數(shù)是按照一定算法模擬產(chǎn)生，其結(jié)果是確定的，是可見(jiàn)的.可以這樣認(rèn)為，這個(gè)可預(yù)見(jiàn)的結(jié)果其出現(xiàn)的概率是100%，所以用計(jì)算機(jī)隨機(jī)函數(shù)所產(chǎn)生的“隨機(jī)數(shù)”并不隨機(jī)，是偽隨機(jī)數(shù).偽隨機(jī)數(shù)有2個(gè)特點(diǎn)：

1）在某一整數(shù)范圍內(nèi)產(chǎn)生足夠多的隨機(jī)數(shù)的時(shí)候數(shù)據(jù)在該范圍內(nèi)均勻分布，也就是說(shuō)取到各個(gè)整數(shù)值的機(jī)會(huì)均等.

2）連續(xù)產(chǎn)生的隨機(jī)數(shù)在較大范圍內(nèi)不能序列重復(fù)［4］.

這里的序列重復(fù)是指不應(yīng)該像循環(huán)小數(shù)一樣存在循環(huán)節(jié)，當(dāng)然，絕大多數(shù)隨機(jī)數(shù)產(chǎn)生算法還是有循環(huán)節(jié)的，但這個(gè)循環(huán)節(jié)往往非常長(zhǎng).

這2個(gè)特點(diǎn)非常適合加密.任何數(shù)據(jù)經(jīng)過(guò)隨機(jī)序列掩碼產(chǎn)生的結(jié)果也將具備如上的數(shù)據(jù)特征，掩碼后的結(jié)果在不知道掩碼序列的情況下將很難逆推回原序列，就以這種思路來(lái)構(gòu)造加密算法.

2 大數(shù)同余

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

X［0］為任意非負(fù)數(shù)［7］

同余序列總是進(jìn)入一個(gè)循環(huán)，這是一個(gè)事實(shí)，最終必定在N個(gè)數(shù)之間無(wú)休止的重復(fù)循環(huán).在本文中不打算探討同余序列的循環(huán)問(wèn)題，盡管這方面也有很多人在孜孜不倦的努力，但這和本文的核心內(nèi)容無(wú)關(guān)，即便采用Turbo C的同余參數(shù)，也能得到周期達(dá)到2 147 483 647的隨機(jī)序列（RAND＿M(jìn)AX定義），20多億的序列長(zhǎng)度對(duì)于討論的加密情況來(lái)說(shuō)足夠了，關(guān)鍵是線性同余產(chǎn)生的隨機(jī)序列不僅滿足第2節(jié)所陳述的隨機(jī)序列特征，而且速度非?？?，在Delphi中甚至短短10行左右的匯編代碼就能實(shí)現(xiàn)了，當(dāng)然，還有很多人研究了偽隨機(jī)序列的硬件實(shí)現(xiàn)，更能進(jìn)一步提高速度［8］.

3 新的隨機(jī)數(shù)發(fā)生器

如上所述，即便采用唯一的隨機(jī)序列發(fā)生器產(chǎn)生的隨機(jī)序列進(jìn)行掩碼，也可以得到均勻分布的加密結(jié)果，當(dāng)然這樣的加密在預(yù)知加密算法的前提下對(duì)密碼進(jìn)行碰撞還是很容易解密的，這就需要進(jìn)一步的增強(qiáng)密碼空間，加大碰撞難度.這里可以利用線性同余算法對(duì)于不同的因子可以產(chǎn)生不同的隨機(jī)序列這一特點(diǎn)，使加密過(guò)程和密碼長(zhǎng)度關(guān)聯(lián)起來(lái)，構(gòu)造一個(gè)新的隨機(jī)數(shù)發(fā)生器，它的因子是密碼相關(guān)的.

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

綜上，通過(guò)詳細(xì)介紹醫(yī)院中生殖醫(yī)學(xué)中心候診空間的建設(shè)設(shè)計(jì)要點(diǎn)、診室空間的建設(shè)設(shè)計(jì)要點(diǎn)、醫(yī)護(hù)工作區(qū)的建設(shè)設(shè)計(jì)要點(diǎn)、流線組織的建設(shè)設(shè)計(jì)要點(diǎn)等，能夠幫助醫(yī)院中生殖醫(yī)學(xué)中心建設(shè)設(shè)計(jì)人員更好的了解各個(gè)科室的建設(shè)設(shè)計(jì)要求，保證醫(yī)院生殖醫(yī)學(xué)中心建設(shè)設(shè)計(jì)方案更加合理，為患者提供一個(gè)更好的就醫(yī)環(huán)境。

符號(hào)＆表示連接.

以x為因子的隨機(jī)序列表示為函數(shù)RandomSequence（x），根據(jù)隨機(jī)序列的定義，RandomSequence（x）為x相關(guān)的整數(shù)有序集合，RandomSequence（x）?Z且當(dāng)x1≠x2時(shí)有RandomSequence（x1）≠RandomSequence（x2）.

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

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

4 加密與解密

在隨機(jī)序列已經(jīng)構(gòu)造的前提下，加密解密是一個(gè)非常簡(jiǎn)單的過(guò)程，這里為了實(shí)用性筆者對(duì)加密對(duì)象做了以下區(qū)分：

A.密文可視的；

B.密文可視無(wú)關(guān)的.

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

Ⅰ.以字節(jié)為加密單位進(jìn)行換碼加密.

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

則換碼加密函數(shù)為換碼解密函數(shù)為

算法類似于補(bǔ)碼運(yùn)算，應(yīng)該不需要做解釋，可以簡(jiǎn)單驗(yàn)證.

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

本算法已經(jīng)使用VC 2008實(shí)現(xiàn)，使用一般字符串測(cè)試，范圍設(shè)定為［32，127］，數(shù)組測(cè)試使用范圍［0，255］，結(jié)果如圖1.

圖1 簡(jiǎn)單加密測(cè)試結(jié)果Fig.1 Test result for simple crypt

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

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

圖3 復(fù)雜圖像加密測(cè)試Fig.3 Test for complex image crypt

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

5 關(guān)于不定態(tài)結(jié)果

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

1）定義擾動(dòng)量Kn為隨機(jī)獲取的n個(gè)字節(jié)集合.

2）原加密密碼x為一個(gè)不定長(zhǎng)度的字節(jié)集合，加密前利用Kn使用前述算法p對(duì)密文進(jìn)行擾動(dòng)，變換為X＝p（x，Kn）.

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

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

解密時(shí)：

1）對(duì)密文R切除指定位置的n個(gè)字節(jié)得到密文r和擾碼Kn.

2）使用Kn對(duì)密碼x進(jìn)行擾動(dòng)變換（同加密）X＝p（x，Kn）.

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

過(guò)程比較簡(jiǎn)單，不再細(xì)述.其優(yōu)點(diǎn)在于擾碼可以隨意獲取，而隨擾碼的不同加密結(jié)果在形式上也隨之變換，從密文難以推導(dǎo)原文.

6 結(jié)論

基于線性同余的隨機(jī)序列對(duì)加密進(jìn)行了一些探討，該方法與傳統(tǒng)加密算法相比，在不喪失加密強(qiáng)度的情況下具備算法簡(jiǎn)單、快速的特點(diǎn)，對(duì)于需要簡(jiǎn)單加密同時(shí)又需要一定的加密強(qiáng)度的需求而言，不失為一個(gè)適當(dāng)?shù)慕鉀Q方案.

［1］ 杜立健，唐曉燕，李守榮.幾種信息加密算法的比較研究［J］.網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，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ìn)［J］.河北大學(xué)學(xué)報(bào)：自然科學(xué)版，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］ 吳曉麗.基于“陷門(mén)漸縮”原理的公鑰算法［J］.河北大學(xué)學(xué)報(bào)：自然科學(xué)版，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］ 王怡林.產(chǎn)生偽隨機(jī)數(shù)的一種新方法［J］.楚雄師專報(bào)，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］ 周燕.關(guān)于線性同余組合發(fā)生器的周期性和統(tǒng)計(jì)性質(zhì)［J］.重慶大學(xué)學(xué)報(bào)：自然科學(xué)版，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］ 束禮寶，宋克柱，王硯.偽隨機(jī)數(shù)發(fā)生器的 FPGA實(shí)現(xiàn)與研究［J］.電路與系統(tǒng)學(xué)報(bào)，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］ 趙玉霞.基于混沌序列的數(shù)字圖像置亂算法［J］.商洛學(xué)院學(xué)報(bào)，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］.貴州師范學(xué)院學(xué)報(bào)：社會(huì)科學(xué)版，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］ 廖文軍，陳曉前.基于多線程技術(shù)的 DES加密算法［J］.新鄉(xiāng)學(xué)院學(xué)報(bào)：自然科學(xué)版，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］ 李元元.橢圓曲線加密算法在指紋加密技術(shù)中的應(yīng)用［J］.計(jì)算機(jī)安全，2009（8）：48-50.

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

［13］ 李維勇.一種字符型數(shù)據(jù)加密算法研究［J］.計(jì)算機(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

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

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

孟素蘭）