湯建國,汪江樺

新疆財經(jīng)大學 計算機科學與工程學院,烏魯木齊 830012)(*通信作者電子郵箱tjguo@126.com)

基于粗糙集的古典密碼模型

湯建國*,汪江樺

新疆財經(jīng)大學 計算機科學與工程學院,烏魯木齊 830012)(*通信作者電子郵箱tjguo@126.com)

針對傳統(tǒng)古典密碼雖然具備簡潔高效的特性,但其在當前社會計算能力下極易被破解這一問題,提出一種利用粗糙集方法設(shè)計古典密碼模型的算法。在該模型的構(gòu)造中,首先充分融入粗糙集的確定性中蘊含著不確定性以及近似空間規(guī)模會隨論域微增而急劇增大的特點,來弱化模型的統(tǒng)計規(guī)律;其次,借助混合同余法來提升模型產(chǎn)生隨機序列的能力;最后,結(jié)合自定義運算和同余方法特性來讓部分明文信息參與到加密過程中,進一步增強模型抗攻擊的能力。研究分析表明,該模型不僅在時間和空間復雜度上與傳統(tǒng)古典密碼處于同一級別,而且具備了近乎理想的擴散與混淆性能,完全彌補了古典密碼容易被破解的缺陷,能有效抵御窮舉法和統(tǒng)計分析法的攻擊。

粗糙集;古典密碼;近似空間;不確定性;對稱密碼

0 引言

密碼技術(shù)使通信者可以將信息隱藏在毫無規(guī)律的符號組合之中,防止信息的泄露。最初的加密過程通常采用的是人工方式或者機械方式,這種加密手段局限于當時落后的計算水平,使得加密的原理都較為簡單以便于使用。這類密碼中的代表模型有棋盤密碼、Caesar密碼、Vigenere密碼、Playfair密碼和Hill密碼等,后來密碼學者將這類密碼稱為古典密碼[1]。

計算機技術(shù)的出現(xiàn)大幅提升了人類的計算能力與效率,古典密碼的安全性也由此徹底瓦解而淡出了歷史舞臺,取而代之的是基于計算機技術(shù)的流密碼、分組密碼和公鑰密碼等現(xiàn)代密碼。然而,古典密碼的簡潔和高效的特點仍然是現(xiàn)代密碼研究所追求和推崇的。如果能利用現(xiàn)代計算機技術(shù)對古典密碼進行改造，使之在保持簡潔高效的同時，擁有與現(xiàn)代密碼抵御攻擊的能力，那么將對古典密碼的發(fā)展產(chǎn)生積極影響。目前，已有很多學者利用計算機科學研究中的數(shù)學理論去研究密碼學，如基于格論的格密碼[2-3]、基于屬性的屬性密碼[4]和基于混沌理論的密碼[5-7]等,這些研究極大地豐富了密碼學理論的研究方法。

受此啟發(fā),本文將借助粗糙集方法來作一嘗試。粗糙集[8]是一種用于處理不確定性問題的方法,被廣泛應用于人工智能、機器學習和數(shù)據(jù)挖掘等領(lǐng)域。粗糙集的最大特點在于能從客觀數(shù)據(jù)中自行學習和挖掘有用信息,以確定的方式來刻畫不確定問題。而這種刻畫往往會隨著知識粒度或者目標集合的變化而變化,具有很大的不確定性。粗糙集的這些特性非常符合加密模型的技術(shù)需求，因為在設(shè)計密碼時,既需要利用隨機性元素來讓其變得不可捉摸而難以破解,又需要確定性元素使其能夠?qū)γ芪臏蚀_解密。

1 背景知識

1.1 粗糙集

粗糙集理論是通過一對精確的近似集合,即上近似和下近似,來對目標集合進行逼近而得到一個關(guān)于目標集合的近似描述。

定義1 設(shè)U是一個論域,P是U上的一個劃分,X?U。定義X關(guān)于P的下近似和上近似分別為:

P*(X)=∪{B∈P : B?X}

(1)

P*(X)=∪{B ∈ P : B∩X ≠?}

(2)

若P*(X)=P*(X),則稱X是關(guān)于P的一個粗糙集；否則稱X是關(guān)于P的一個可定義集。在上下近似的基礎(chǔ)上分別定義X關(guān)于P的正域PosP(X)、邊界域BnP(X)和負域NegP(X)如下:

PosP(X)=P*(X)

(3)

BnP(X)=P*(X)-P*(X)

(4)

NegP(X)=U-P*(X)

(5)

在粗糙集模型中,當劃分P確定后,不同目標集合X可能產(chǎn)生相同的或者是不同的邊界域,且同一個邊界域可能是由不同的上下近似對形成,這些特性增強了邊界域的不確定性和隨機性的特點。

習慣上,稱一個論域上的集簇或等價關(guān)系為一個知識粒度。論域上不同的集簇或等價關(guān)系就是這一論域上的不同的知識粒度。

1.2 古典密碼

古典密碼編碼方法主要有置換和代換兩種。所謂置換就是只將明文中的字母順序打亂重新組合而不改變字母本身的加密手段。最簡單的置換密碼是把明文中的字母順序倒過來,然后截成固定長度的字母組作為密文。比如將“student”組合成“tneduts”。

代換則是將明文中的字母用其他字母來替換進行加密,比如將“student”替換成“l(fā)ksjdfm”。代換通常又有兩種情況:1)為字母表設(shè)定一個代換字母表,使原字母表中的每個字母與代換字母表中的字母形成一一對應的關(guān)系,其加密和解密過程就是將明文和密文按照這種對應關(guān)系轉(zhuǎn)化為相應的密文和明文;2)利用模運算來確定明文對應的密文,此時需要先將字母表中的每個字母與一個十進制數(shù)相對應,加密或解密時先將明文或密文轉(zhuǎn)化為十進制數(shù),然后通過模運算來實現(xiàn)加密和解密。表1是一種常用的字母與十進制數(shù)對應關(guān)系表。

表1 英文字母和十進制數(shù)字的對應關(guān)系

1.3 擴散與混淆

Shannon[9]在1949年提出了擴散(diffusion)和混淆(confusion)的概念,它們是設(shè)計密碼體制的兩種基本方法,其目的是為了抵抗對手對密碼體制的統(tǒng)計分析。

所謂擴散就是讓明文中的每一位影響密文中的許多位,或者說讓密文中的每一位受明文中的許多位的影響,理想的情況是讓明文中的每一位影響密文中的所有位,或者說讓密文中的每一位受明文中所有位的影響。擴散主要是通過將明文冗余度分散到密文中使之分散開來,使明文和密文關(guān)的關(guān)系變得盡可能復雜,達到明文中任何一點小更動都會使得密文有很大差異的效果。最簡單的擴散方法是置換,即改變代碼的相互位置。

所謂混淆就是將密文與密鑰之間的統(tǒng)計關(guān)系變得盡可能復雜,使攻擊者即使獲取了關(guān)于密文的一些統(tǒng)計特性,也無法推測密鑰。它主要用于掩蓋明文與密文之間的關(guān)系,使密文和對稱式加密方法中密鑰的關(guān)系變得盡可能復雜,以挫敗攻擊者通過研究密文來獲取冗余度和統(tǒng)計模式的企圖。最簡單的混淆方法是代換,即用不同的代碼來替換當前的代碼。

1.4 偽隨機數(shù)生成器-混合同余法

同余法是一種比較好的產(chǎn)生偽隨機數(shù)的方法,其中混合同余法的性能更好?；旌贤喾ㄊ荓ehmer在1951年提出的[10],其具體模型如下:

Zn=AZn-1+C(modN)

(6)

Wn=Zn/N

(7)

其中:A、C和N均為正整數(shù)，N表示模數(shù),A是乘數(shù),C是增量；Z0為初始值(0≤Z0≤N)。Zn是在(0,M)內(nèi)服從均勻分布的隨機變量；Wn則是在(0, 1)內(nèi)服從均勻分布的隨機變量。實驗統(tǒng)計表明,用以下參數(shù)進行混合同余法產(chǎn)生的隨機序列的統(tǒng)計特性較好:

Zn=314 159 269Zn-1+453 806 245(mod 231)

(8)

2 基于粗糙集的古典密碼加密算法

本章將利用粗糙集方法來設(shè)計一種古典密碼加密方案。為了后續(xù)討論方便,給出下面一種運算的定義。

設(shè)U是由若干正整數(shù)形成的論域,P是U上的一個劃分,X?U。定義運算S如下:

(9)

2.1 加密模型

從前面的介紹可知,粗糙集模型中的邊界域具有較強的不確定性,而混合同余法可產(chǎn)生具有良好隨機性的序列,將它們的這些特點用于設(shè)計加密方案將有利于增強加密的安全性。下面給出一種加密設(shè)計方案:

設(shè)U是由若干正整數(shù)形成的論域,P是U上的一個劃分,X={X1,X2,…,Xh}是U的一個子集簇,Y0是一個整數(shù),三元組K=(P,X,Y0)是密鑰。對于任意明文串m=m1m2…mr和密文串c=c1c2…cr,定義其加密和解密分別為:

ci=S(m)+S(BnP(Xqi))+mi(mod |M|)

(10)

mi=ci-S(m)-S(BnP(Xqi)) (mod |M|)

(11)

其中:M為明文空間,|M|表示明文空間的基;S(m)表示所有明文字符對應序號之和;qi是通過結(jié)合密鑰K和式(8)產(chǎn)生得到的隨機數(shù)。qi的計算方法如下:

qi=Zi(mod |X|)

(12)

其中:|X|表示X的基。為了增強加密算法的混淆性,令

Z0=Len(m)*Y0

(13)

其中:Y0是一個初始值,Len(m)表示明文m的長度。

從加密的過程容易發(fā)現(xiàn),對于解密人員來說是無法自行求得S(m)的值,因為解密人員在解密之前不可能知道明文內(nèi)容,為此可通過向解密人員傳遞數(shù)一個數(shù)L′來間接告知其S(m)的值。

(14)

當解密人員獲得L′的值后,便可利用式(14)輕易求得S(m)的值,再根據(jù)式(11)進行解密。L′的設(shè)計也表明,加密者在給解密者發(fā)送的信息里既要包含明文對應的密文,同時也要包含未加密的數(shù)L′。

將由式(10)～(14)確定的加密模型簡稱為基于粗糙集的古典密碼(Rough Sets Based Classical Cryptography, RSCC)。

需說明的是,式(10)和(11)中的mi和ci為對應明文字符和密文字符在表1中的序號。

RSCC模型的密鑰是由P、X和Y0構(gòu)成的三元組,P和X分別是U上的一個劃分和子集簇,Y0往往是一個較大的素數(shù),它們有一個共同特點就是都有著巨大的選擇空間(在后文會具體分析),從而保證了密鑰K不可能用窮舉法破解。Z0的設(shè)計是為了讓明文的長度信息參與到加密中來,當明文長度發(fā)生微小變化時可造成加密結(jié)果發(fā)生巨大變化,從而增強了加密的擴散性和混淆性。此外,在式(10)～(11)中還加入了明文信息S(m),當S(m)發(fā)生微小變化時也能造成加密結(jié)果發(fā)生巨大變化,進一步增強了加密的擴散性和混淆性。式(10)～(11)還在形式上部分借鑒了混合同余法模型,雖然它們中參與運算的對象在數(shù)值大小上遠遠低于混合同余法模型中的運算對象,但由于S(Xqi)和S(BnP(Xqi))的確定過程具有很強隨機性,所以也會使得加密結(jié)果具有良好的混淆性。

2.2 實例分析

下面通過例子來進一步闡述RSCC的加密原理和效果。

例1 設(shè)U={1,2,…,12},P={{1,4},{2,5},{3,11,12},{6,9},{7,8},{10}},X={{1,3,4},{2,5,10,11},{4,9},{5,7,12},{2,7,9,12},{6,8},{3,4,7},{9,11},{1,5}},Y0=119 661 719。明文m=I am a student和密文c=hpdgsopbwtx,請根據(jù)公式分別對m和c進行加密和解密。

解 根據(jù)已知條件可得如表2所示結(jié)果。

表2 計算結(jié)果

根據(jù)式(8)可得Zi如表3所示。

表3 計算Zi

再根據(jù)式(12)可得qi如表4所示。

表4 計算qi

再根據(jù)式(1)、(2)和(4)可得S(BnP(Xqi))如表5所示。

表5 計算S(BnP(Xqi))

最后根據(jù)式(10)可得對明文m=Iamastudent的加密結(jié)果如表6所示。

表6 加密結(jié)果

注:加密中忽略單詞之間的空格,不區(qū)分大小寫。即明文m的加密結(jié)果為: y gu x iuatktq

根據(jù)式(11)可得對密文c=hpdgsopbwtx的解密結(jié)果如表7所示。

表7 解密結(jié)果

即解密結(jié)果為:Iamateacher。

從表6～7可發(fā)現(xiàn)：同一個字符經(jīng)過RSCC加密之后,可以轉(zhuǎn)換為多個不同的字符,而不同的字符可以加密成相同的字符,這說明RSCC具備較好的混淆性能,可有效防止統(tǒng)計分析攻擊。

為了考察加密模型中引入明文信息Len(m)和S(m)對加密的影響,將本例中的明文m分別變?yōu)閙′=Iamestudent和m"=Iamastudentz,即:分別改變了明文中的一個字符和明文長度增加了1,然后分別對m′和m"進行加密,得到加密結(jié)果為:c′=ckyfmyexoxu,c"=tlraxpfotyek。這個結(jié)果表明RSCC模型的擴散和混淆特性達到了一種非常理想狀態(tài),即只要對明文做細微變化就會導致密文出現(xiàn)巨大差異。

此外,通過對加密結(jié)果中不同字符出現(xiàn)的次數(shù)進行統(tǒng)計發(fā)現(xiàn)：當加密樣本較短時不同字符出現(xiàn)的次數(shù)有較大差別；而當明文樣本足夠大時,不同字符的出現(xiàn)次數(shù)差距不斷縮小。這進一步表明RSCC模型加密時具有良好的隨機性。

3 算法設(shè)計

本章將給出基于RSCC的加密和解密算法。首先給出RSCC的初始化算法,該算法將完成RSCC模型中計算目標集簇中各集合的邊界域,以及由RSCC模型的密鑰K可直接計算出的一些中間結(jié)果。

3.1RSCC的初始化

(15)

(16)

其中：a,b∈{0,1}。為了便于描述計算S(BnP(Xi))的算法,不妨假設(shè)|U|=n1,|P|=n2,|X|=n3,“|·|”表示內(nèi)部對象的基數(shù)。

首先將P中的每個集合Bj和X中的每個集合Xi都分別表示成一個n1維的行向量,分別記為αj和βi。然后計算X中的每個集合Xi對應的邊界域BnP(Xi),具體方法是:將P中每個集合對應的行向量αj分別與βi進行“⊕”運算,若得到的結(jié)果為全“1”向量,則將S(Bj)計入s1;否則,讓αj與βi進行“?”運算,若得到的結(jié)果為全“0”向量,則將S(Bj)計入s2;于是可得BnP(Xi)=S(U)-(s1+s2)。最后,計算S(BnP(Xi))。

算法1 初始化。

輸入:K=(P,X,Y0),其中P={B1,B2,…,Bn2},X={X1,X2,…,Xn3}。

Step1i=1;

Step2j=1,s1=0,s2=0;

Step3v=αj?βi;

Step4 若v是全“1”向量,則s1=s1+S(Bj),j++;否則,轉(zhuǎn)到Step6;

Step5 若j≤n2,轉(zhuǎn)到Step3;否則,轉(zhuǎn)到Step8;

Step6v=αj?βi;

Step7 若v是全“0”向量,則s2=s2+S(Bj),j++,轉(zhuǎn)到Step5;

Step8 計算ai=S(BnP(Xi))=S(U)-(s1+s2);

Step9i++;

Step10 若i≤n3,轉(zhuǎn)到Step2;

Step12 結(jié)束。

在算法1中,若v=αj?βi是全“1”向量,說明Bj∩Xi=?,根據(jù)式(5)可知,Bj?NegP(Xi),所有符合條件的Bj并集即是NegP(X),也就是說通過運算“?”可以獲得Xi關(guān)于P的負域;若v=αj?βi不是全“1”向量,則說明Bj∩Xi≠?,進一步進行“?”運算,若v=αj?βi是全“0”向量,說明Bj?Xi,根據(jù)式(3)可知,Bj?PosP(Xi),所有符合條件的Bj并集即是PosP(X),也就是說通過運算“?”可以獲得Xi關(guān)于P的正域。再根據(jù)上下近似的定義可知,BnP(Xi)=U-(NegP(Xi)∪PosP(Xi))。再由算法可知,s1=|NegP(Xi) |,s2=|BnP(Xi)|,所以S(U)-(s1+s2)=S(BnP(Xi))。

3.2RSCC的加密與解密算法

算法2 RSCC加密算法。

輸入:明文串m=m1m2…mr。

輸出:密文串c=c1c2…cr。

Step1 計算Len(m)、S(m)、L′和Z0;

Step2i=1;

Step3 若i>r,跳到Step6;

Step4 計算Zi和qi;

Step5 計算ci,i++,返回Step3;

Step6 輸出加密結(jié)果c;

Step7 結(jié)束。

算法3 RSCC解密算法。

輸入:密文串c=c1c2…cr和L′。

輸出:明文串m=m1m2…mr。

Step1 根據(jù)式(13)和(14)分別計算Z0和S(m);

Step2i=1;

Step3 若i>r,跳到Step6;

Step4 計算Zi和qi;

Step5 計算mi,i++,返回Step3;

Step6 輸出解密結(jié)果m;

Step7 結(jié)束。

4 RSCC的安全性分析

RSCC是基于粗糙集方法的加密模型,它充分利用了粗糙集的確定性中蘊含著不確定性的特性,提升了加密系統(tǒng)的擴散和混淆能力,使得密碼破譯者很難對其進行破譯。下面將從幾個方面來討論RSCC的安全性。

1)模型的數(shù)學基礎(chǔ)。

RSCC模型的密鑰K=(P,X,Y0)是一個三元組,其安全性也是由這三個對象的安全性來確定。為了防止攻擊者利用窮舉法來破解密鑰,密鑰的空間往往需要設(shè)計得足夠大。在RSCC中,論域U是可以公開的信息,它的基數(shù)決定了密鑰K中P和X的選擇空間,而討論這些空間大小的關(guān)鍵在于確定論域U上存在的劃分P的個數(shù)。文獻[11-14]中都研究了一個論域U上有多少個劃分P的問題,這些研究結(jié)果表明論域上的劃分個數(shù)會隨著論域基數(shù)的輕微增大而急劇性地增大,其具體個數(shù)也很難用一個簡單明了的公式予以表示,于是部分學者給出了計算劃分個數(shù)的算法,根據(jù)這些算法統(tǒng)計了論域U的基數(shù)及其對應劃分P的個數(shù),如表8所示。

表8 U和P統(tǒng)計表

從表8可以發(fā)現(xiàn),當論域U的個數(shù)發(fā)生微小變化時,其對應的劃分個數(shù)卻發(fā)生了巨大的變化。在實際計算中,如果將U的個數(shù)設(shè)置為50時，計算機很難在短時間內(nèi)(作者用了將近兩天還未得到結(jié)果)計算出結(jié)果。不過,根據(jù)表8統(tǒng)計結(jié)果顯示出的規(guī)律,當U的基數(shù)為50時對應的劃分個數(shù)至少可以達到1047的量級。與之形成鮮明對比的時,如果U的基數(shù)為100時,計算目標集Xi關(guān)于一個劃分P的邊界域所需要花費的時間是完全可以忽略的。因此,這些統(tǒng)計數(shù)據(jù)足以說明在給定論域上去窮舉劃分P進行密鑰破譯是不可行的。

在RSCC的密鑰K中,X是U上的一個任意子集簇,相對于U上有一定限制條件的劃分來說,X的取法要隨意許多,其在論域上可選個數(shù)也要比劃分的個數(shù)更加龐大。因此,利用窮舉法去確定密鑰中的X也是不可行的。

RSCC密鑰K中的Y0是一個大素數(shù),而自然數(shù)中素數(shù)的個數(shù)已被證明是無窮多的,且素數(shù)的判斷本身就是一個非常耗時的過程。因此,利用窮舉法去確定密鑰中的Y0也是不可行的。

2)模型的設(shè)計。

一方面,在模型的設(shè)計中借鑒了混合同余法,如式(10)、(11)和(14),而混合同余法是被公認的能夠產(chǎn)生具有良好隨機性序列的模型,這為增強RSCC模型加密的擴散和混淆能力奠定了基礎(chǔ);另一方面,將粗糙集方法中的邊界域概念引入到了模型的設(shè)計中,邊界域的不確定性進一步提高了模型的擴散與混淆性能。

3)明文信息參與加密。

明文信息參與到加密中既是RSCC模型相對于傳統(tǒng)古典密碼的一種創(chuàng)新與突破,也是保障RSCC安全性的非常關(guān)鍵的一環(huán)。傳統(tǒng)的古典密碼限于當時極低的計算能力等現(xiàn)實情況,都沒有將明文信息引入到加密過程,而RSCC將明文m的長度信息和S(m)信息很好地融合到加密模型中,使RSCC的擴散與混淆性能達到了Shannon[4]所說的理想狀態(tài),即 “讓明文中的每一位影響密文中的所有位,或者說讓密文中的每一位受明文中所有位的影響”。

5 RSCC與傳統(tǒng)古典密碼的比較分析

通常來說,衡量一個加密算法的性能主要從復雜度和安全性兩個方面進行考量,復雜度反映了加密算法的實現(xiàn)效率,安全性則體現(xiàn)了加密算法的抗攻擊能力。下面從這兩個方面對RSCC和傳統(tǒng)古典密碼作比較分析。

5.1 復雜度分析

算法的復雜度主要包括時間復雜度和空間復雜度兩個方面。傳統(tǒng)古典密碼主要是通過移位、代換和置換等方式進行設(shè)計,其加密原理簡單易于實現(xiàn)(人工方式),沒有出現(xiàn)迭代或多重循環(huán)等復雜運算,在計算量和計算規(guī)模上都很有限,所以它們的時間復雜度都非常低,根據(jù)它們的加密原理容易得出它們的時間復雜度均為O(n)的多項式時間。RSCC算法雖然在算法設(shè)計原理上要比傳統(tǒng)古典密碼復雜,實現(xiàn)過程也相對傳統(tǒng)古典密碼要繁瑣,但根據(jù)本文中的算法2和算法3容易求得它的加解密時間復雜度實際上也均為O(n)。這說明,在時間復雜度方面RSCC和傳統(tǒng)古典密碼處于同一水平,也就是說它們在加解密過程中的時間差別可完全忽略不計。

在空間復雜度方面,RSCC保存或運行數(shù)據(jù)時所需的存儲空間在KB級別,鑒于當前普通計算機的內(nèi)存和硬盤容量都分別達到了GB和TB的級別,這已經(jīng)遠遠超出了諸如RSCC這些古典加密算法對存儲空間的需求量,即便是當前常用的流密碼和分組密碼的加解密算法也無需再去考慮它們的空間復雜度問題,所以RSCC和其他古典密碼之間的空間復雜度差別也是可以忽略不計。

由此可見,RSCC在加解密過程中的時間復雜度和空間復雜度與傳統(tǒng)古典密碼都處在同一級別上,這也說明RSCC很好地繼承了傳統(tǒng)古典密碼的簡潔與高效的特性。

5.2 安全性分析

傳統(tǒng)古典密碼最大的安全威脅便是在當前的計算水平下可被非常容易地破解,這也是古典密碼退出歷史舞臺的根本原因。具體來說,傳統(tǒng)古典密碼的安全缺陷主要有兩個方面,即脆弱的抵抗窮舉法和統(tǒng)計分析法攻擊的能力。

脆弱的抵抗窮舉法能力是由于很多古典密碼的密鑰空間很小,如移位密碼和單表代換密碼,利用現(xiàn)在的計算機技術(shù)可在很短的時間內(nèi)便可窮舉所有可能密鑰對其進行破解。RSCC的密鑰K=(P,X,Y0)是一個三元組,其中P和X的空間大小取決于論域U,從第4章的分析中可知,即便論域U處于一個很小的規(guī)模時,P和X的空間也已經(jīng)非常龐大,完全能夠抵御基于窮舉法的破解攻擊,再加之Y0的參與更進一步地增強了RSCC抵抗窮舉法攻擊的能力。所以說,RSCC的密鑰空間已使其具備了無法用窮舉法對其進行攻擊的能力。

雖然有些古典密碼具備了抵御窮舉法的攻擊,如多表代換密碼等,但它們卻很難抵御統(tǒng)計分析法的攻擊,因為它們在加密過程中的擴散和混淆能力非常脆弱,使得加密后的密文與明文之間往往都存在一定的統(tǒng)計規(guī)律而容易被破解。RSCC在設(shè)計時充分考慮了這一點,除了通過在模型設(shè)計中引入混合同余法,并充分利用粗糙集自身的不確定特性來增強RSCC的擴散與混淆性能之外,還將明文信息Len(m)和S(m)添加到加密模型中,這使得RSCC的擴散與混淆性能達到了近乎理想的狀態(tài)?？梢?RSCC已具備非常強的抵御統(tǒng)計分析法攻擊的能力,這是傳統(tǒng)古典密碼所無法比擬的。

RSCC雖然是一種古典密碼加密模型,但其安全性能與其他古典密碼模型早已不在同一個級別上,甚至遠超當前一些主流分組密碼的安全性,比如數(shù)據(jù)加密標準(DataEncryptionStandard,DES)的密鑰長度是56位,其密鑰空間為256;高級加密標準(AdvancedEncryptionStandard,AES)模型中密鑰最大長度為256位,其密鑰空間為2256,雖然遠大于DES的密鑰空間,但卻仍然遠小于前面例子中RSCC的密鑰空間,所以在安全性上其他古典密碼與RSCC不具有可比性。

6 結(jié)語

本文利用粗糙集的特性構(gòu)建了一種古典密碼加密模型RSCC,研究表明該模型具有其他古典密碼模型無法比擬的安全性,甚至大幅超越了當前一些主流的分組加密模型,而其加解密的過程卻仍然保持了古典密碼的簡潔與高效,同時又具備了非常好的擴散性和混淆性,達到了現(xiàn)實可用的要求。

后續(xù)研究還將通過借鑒現(xiàn)代密碼研究中的方法來繼續(xù)完善和改進RSCC,進一步增強RSCC的擴散和混淆性,并在這些研究的基礎(chǔ)上討論基于粗糙集的分組密碼和公鑰密碼。

)

[1]TRAPPEW,WASHINGTONLC.IntroductiontoCryptographywithCodingTheory[M]. 2ed.PearsonPrenticeHall, 2006: 8-9.

[2]FOUQUEP,HADJIBEYLIB,KIRCHNERP.Homomorphicevaluationoflattice-basedsymmetricencryptionschemes[C]//Proceedingsofthe22ndInternationalConferenceonComputingandCombinatorics.Berlin:Springer, 2016: 269-280.

[3] 王小云, 劉明潔. 格密碼學研究[J]. 密碼學報, 2014, 1(1): 13-27.(WANGXY,LIUMJ.Surveyoflattice-basedcryptography[J].JournalofCryptologicResearch, 2014, 1(1):13-27.)

[4] 馮登國, 陳成. 屬性密碼學研究[J]. 密碼學報, 2014, 1(1): 1-12.(FENGDG,CHENC.Researchonattribute-basedcryptography[J].JournalofCryptologicResearch, 2014, 1(1): 1-12.)

[5] 金建國, 肖瑩, 邸志剛. 基于混沌動態(tài)隨機分組與調(diào)制分數(shù)階FFT旋轉(zhuǎn)因子的圖像加密[J]. 計算機應用, 2016, 36(4):966-972.(JINJG,XIAOY,DIZG.ImageencryptionbasedonchaoticdynamicrandomgroupingandmodulatingfractionalFouriertransformrotationfactor[J].JournalofComputerApplications, 2016, 36(4):966-972.)

[6] 王聰麗, 陳志斌, 葛勇. 利用Lorenz混沌系統(tǒng)實現(xiàn)紅外圖像加密的方案[J]. 計算機應用, 2015, 35(8):2205-2209.(WANGCL,CHENZB,GEY.InfraredimageencryptionschemeusingLorenzchaoticsystem[J].JournalofComputerApplications, 2015, 35(8):2205-2209.)

[7] 徐光憲, 郭曉娟. 基于混沌系統(tǒng)的DNA圖像加密算法[J]. 計算機應用, 2014, 34(11): 3177-3179.(XUGX,GUOXJ.DNAimageencryptionalgorithmbasedonchaoticsystem[J].JournalofComputerApplications, 2014, 34(11): 3177-3179.)

[8]PAWLAKZ.Roughsets[J].InternationalJournalofComputerandInformationSciences, 1982, 11(5): 341-356.

[9]SHANNONCE.Communicationtheoryofsecrecysystems[J].TheBellSystemTechnicalJournal, 1949, 28(4): 656-715.

[10] 郭鳳鳴. 一種生成大周期偽隨機數(shù)的新算法——改進的混合同余法[J]. 地球科學, 1992, 17(6): 733-738.(GUOFM.Anewalgorithmingeneratingpseudorandomnumber—improvedmixingcongruentialmethod[J].EarthSciences, 1992, 17(6): 733-738.)

[11] 錢宏, 羅玉芬. 有限集上等價關(guān)系數(shù)目的計算[J]. 重慶大學學報(自然科學版), 1992, 15(3): 92-95.(QIANH,LUOYF.Aformulaforcomputingthenummberofequivalencerelationsonafiniteset[J].JournalofChongqingUniversity(NaturalScienceEdition), 1992, 15(3): 92-95.)

[12] 何日挺, 王航平. 有限集幾種重要等價類數(shù)目的計算[J]. 浙江海洋學院學報(自然科學版), 2000, 19(3): 282-283.(HERT,WANGHP.Countingthenumberofequivalenceclassesofafewimportantsets[J].JournalofZhejiangOceanUniversity(NaturalScienceEdition), 2000, 19(3): 282-283.)

[13] 陳仁榮. 有限集合上的劃分與覆蓋[J]. 常州工學院學報, 2006, 19(1): 5-8.(CHENRR.Thepartitionandcoveringoffiniteset[J].JournalofChangzhouInstituteofTechnology, 2006, 19(1): 5-8.)

[14] 羅海鵬. 有限集合不同構(gòu)的等價關(guān)系數(shù)[J]. 廣西科學院學報, 1983, 1(2): 12-16.(LUOHP.Thenumberofnon-isomorphismequivalencerelationonfiniteset[J].JournaloftheGuangxiAcademyofSciences, 1983, 1(2): 12-16.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61440047,61562079),theKeyResearchBaseProgramofHumanitiesandSocialSciencesinXinjiangUygurAutonomousRegion(050315C01).

TANG Jianguo, born in 1978, Ph. D., associate professor. His research interests include granular computing, rough set, cryptography.

WANG Jianghua, born in 1982, Ph. D., associate professor. Her research interests include data mining, information retrieval.

Classical cipher model based on rough set

TANG Jianguo*, WANG Jianghua

(School of Computer Science and Engineering, Xinjiang University of Finance and Economics, Urumqi Xinjiang 830012, China)

Although classical cipher is simple and efficient, but it has a serious defect of being cracked easily under the current social computing power. A new classical cipher model based on rough sets was developed to solve this problem. Firstly, two features of rough sets were integrated into the model to weaken the statistical law of the model. One feature is that certainty contains uncertainty in rough sets, another is that the approximate space scale tends to increase sharply with the slight increase of the domain size. Secondly, the ability of producing random sequences of the model was improved by using mixed congruence method. Finally, part of plaintext information was involved in the encryption process by using self-defined arithmetic and congruence method to enhance the anti-attack ability of the model. The analysis shows that the model not only has the same level of time and space complexity as traditional classical cipher, but also has nearly ideal performance of diffusion and confusion, which completely overcomes the defects that classical cipher can be easily cracked, and can effectively resist the attacks such as exhaustive method and statistical analysis method.

rough set; classical cipher; approximation space; uncertainty; symmetric cipher

2016- 09- 19;

2016- 12- 23。

國家自然科學基金資助項目(61440047,61562079);新疆維吾爾自治區(qū)人文社科重點研究基地項目(050315C01)。

湯建國(1978—),男,甘肅武威人,副教授,博士,CCF會員,主要研究方向:粒計算、粗糙集、密碼學; 汪江樺(1982—),女,湖北黃岡人,副教授,博士,主要研究方向:數(shù)據(jù)挖掘、信息檢索。

1001- 9081(2017)04- 0993- 06

10.11772/j.issn.1001- 9081.2017.04.0993

TP309.7

A