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

湯建國,汪江樺

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

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

湯建國*,汪江樺

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

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

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

0 引言

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

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

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

1 背景知識

1.1 粗糙集

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

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

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

(1)

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

(2)

若P*(X)=P*(X),則稱X是關于P的一個粗糙集；否則稱X是關于P的一個可定義集。在上下近似的基礎上分別定義X關于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可能產生相同的或者是不同的邊界域,且同一個邊界域可能是由不同的上下近似對形成,這些特性增強了邊界域的不確定性和隨機性的特點。

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

1.2 古典密碼

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

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

表1 英文字母和十進制數字的對應關系

1.3 擴散與混淆

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

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

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

1.4 偽隨機數生成器-混合同余法

同余法是一種比較好的產生偽隨機數的方法,其中混合同余法的性能更好。混合同余法是Lehmer在1951年提出的[10],其具體模型如下:

Zn=AZn-1+C(modN)

(6)

Wn=Zn/N

(7)

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

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

(8)

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

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

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

(9)

2.1 加密模型

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

設U是由若干正整數形成的論域,P是U上的一個劃分,X={X1,X2,…,Xh}是U的一個子集簇,Y0是一個整數,三元組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是通過結合密鑰K和式(8)產生得到的隨機數。qi的計算方法如下:

qi=Zi(mod |X|)

(12)

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

Z0=Len(m)*Y0

(13)

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

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

(14)

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

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

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

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

2.2 實例分析

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

例1 設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,請根據公式分別對m和c進行加密和解密。

解 根據已知條件可得如表2所示結果。

表2 計算結果

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

表3 計算Zi

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

表4 計算qi

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

表5 計算S(BnP(Xqi))

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

表6 加密結果

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

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

表7 解密結果

即解密結果為:Iamateacher。

從表6～7可發現：同一個字符經過RSCC加密之后,可以轉換為多個不同的字符,而不同的字符可以加密成相同的字符,這說明RSCC具備較好的混淆性能,可有效防止統計分析攻擊。

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

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

3 算法設計

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

3.1RSCC的初始化

(15)

(16)

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

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

Step5 若j≤n2,轉到Step3;否則,轉到Step8;

Step6v=αj?βi;

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

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

Step9i++;

Step10 若i≤n3,轉到Step2;

Step12 結束。

在算法1中,若v=αj?βi是全“1”向量,說明Bj∩Xi=?,根據式(5)可知,Bj?NegP(Xi),所有符合條件的Bj并集即是NegP(X),也就是說通過運算“?”可以獲得Xi關于P的負域;若v=αj?βi不是全“1”向量,則說明Bj∩Xi≠?,進一步進行“?”運算,若v=αj?βi是全“0”向量,說明Bj?Xi,根據式(3)可知,Bj?PosP(Xi),所有符合條件的Bj并集即是PosP(X),也就是說通過運算“?”可以獲得Xi關于P的正域。再根據上下近似的定義可知,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 輸出加密結果c;

Step7 結束。

算法3 RSCC解密算法。

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

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

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

Step2i=1;

Step3 若i>r,跳到Step6;

Step4 計算Zi和qi;

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

Step6 輸出解密結果m;

Step7 結束。

4 RSCC的安全性分析

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

1)模型的數學基礎。

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

表8 U和P統計表

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

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

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

2)模型的設計。

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

3)明文信息參與加密。

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

5 RSCC與傳統古典密碼的比較分析

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

5.1 復雜度分析

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

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

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

5.2 安全性分析

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

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

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

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

6 結語

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

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

)

[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] 金建國, 肖瑩, 邸志剛. 基于混沌動態隨機分組與調制分數階FFT旋轉因子的圖像加密[J]. 計算機應用, 2016, 36(4):966-972.(JINJG,XIAOY,DIZG.ImageencryptionbasedonchaoticdynamicrandomgroupingandmodulatingfractionalFouriertransformrotationfactor[J].JournalofComputerApplications, 2016, 36(4):966-972.)

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

[7] 徐光憲, 郭曉娟. 基于混沌系統的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] 郭鳳鳴. 一種生成大周期偽隨機數的新算法——改進的混合同余法[J]. 地球科學, 1992, 17(6): 733-738.(GUOFM.Anewalgorithmingeneratingpseudorandomnumber—improvedmixingcongruentialmethod[J].EarthSciences, 1992, 17(6): 733-738.)

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

[12] 何日挺, 王航平. 有限集幾種重要等價類數目的計算[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] 羅海鵬. 有限集合不同構的等價關系數[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);新疆維吾爾自治區人文社科重點研究基地項目(050315C01)。

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

1001- 9081(2017)04- 0993- 06

10.11772/j.issn.1001- 9081.2017.04.0993

TP309.7

A