﻿ 基于粗糙集的古典密码模型
 计算机应用   2017, Vol. 37 Issue (4): 993-998  DOI: 10.11772/j.issn.1001-9081.2017.04.0993 0

### 引用本文

TANG Jianguo, WANG Jianghua. Classical cipher model based on rough set[J]. Journal of Computer Applications, 2017, 37(4): 993-998. DOI: 10.11772/j.issn.1001-9081.2017.04.0993.

### 文章历史

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
Abstract: 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.
Key words: rough set    classical cipher    approximation space    uncertainty    symmetric cipher
0 引言

1 背景知识 1.1 粗糙集

 ${P_*}\left( X \right) = \cup \left\{ {B \in P{\rm{ }}:{\rm{ }}B \subseteq X} \right\}$ (1)
 ${P^*}\left( X \right) = \cup \left\{ {B{\rm{ }} \in {\rm{ }}P{\rm{ }}:{\rm{ }}B \cap X{\rm{ }} \ne \emptyset } \right\}$ (2)

P*(X)=P*(X), 则称X是关于P的一个粗糙集；否则称X是关于P的一个可定义集。在上下近似的基础上分别定义X关于P的正域PosP(X)、边界域BnP(X) 和负域NegP(X) 如下:

 $Po{s_P}\left( X \right) = {P_*}\left( X \right)$ (3)
 $B{n_P}\left( X \right) = {P^*}\left( X \right) - {P_*}\left( X \right)$ (4)
 $Ne{g_P}\left( X \right) = U - {P^*}\left( X \right)$ (5)

1.2 古典密码

1.3 扩散与混淆

Shannon[9]在1949年提出了扩散 (diffusion) 和混淆 (confusion) 的概念, 它们是设计密码体制的两种基本方法, 其目的是为了抵抗对手对密码体制的统计分析。

1.4 伪随机数生成器-混合同余法

 ${Z_n} = A{Z_{n - 1}} + C({\rm{mod}}\;N)$ (6)
 ${W_n} = \frac{{{Z_n}}}{N}$ (7)

 ${Z_n} = 314\;159\;269{Z_{n - 1}} + 453\;806\;245({\rm{mod}}\;{2^{31}})$ (8)
2 基于粗糙集的古典密码加密算法

U是由若干正整数形成的论域, PU上的一个划分, XU。定义运算S如下:

 $S\left( X \right) = \sum\limits_{x \in X} x$ (9)
2.1 加密模型

U是由若干正整数形成的论域, PU上的一个划分, X={X1, X2, …, Xh}是U的一个子集簇, Y0是一个整数, 三元组K=(P, X, Y0) 是密钥。对于任意明文串m=m1m2mr和密文串c=c1c2cr, 定义其加密和解密分别为:

 ${c_i} = S\left( m \right) + S(B{n_P}({X_{{q_i}}})) + {m_i}({\rm{mod}}\left| M \right|)$ (10)
 ${m_i} = {c_i} - S\left( m \right) - S(B{n_P}({X_{{q_i}}}))\;({\rm{mod}}\left| M \right|)$ (11)

 ${q_i} = {Z_i}({\rm{mod}}\left| X \right|)$ (12)

 ${Z_0} = Len\left( m \right)*{Y_0}$ (13)

 $L' = \sum\limits_{{X_i} \in X} {S({X_i})} {Y_0} + S\left( m \right)({\rm{mod}}\left| M \right|Len\left( m \right))$ (14)

RSCC模型的密钥是由PXY0构成的三元组, PX分别是U上的一个划分和子集簇, Y0往往是一个较大的素数, 它们有一个共同特点就是都有着巨大的选择空间 (在后文会具体分析), 从而保证了密钥K不可能用穷举法破解。Z0的设计是为了让明文的长度信息参与到加密中来, 当明文长度发生微小变化时可造成加密结果发生巨大变化, 从而增强了加密的扩散性和混淆性。此外, 在式 (10)~(11) 中还加入了明文信息S(m), 当S(m) 发生微小变化时也能造成加密结果发生巨大变化, 进一步增强了加密的扩散性和混淆性。式 (10)~(11) 还在形式上部分借鉴了混合同余法模型, 虽然它们中参与运算的对象在数值大小上远远低于混合同余法模型中的运算对象, 但由于S(Xqi) 和S(BnP(Xqi)) 的确定过程具有很强随机性, 所以也会使得加密结果具有良好的混淆性。

2.2 实例分析

3 算法设计

3.1 RSCC的初始化

 $a \oplus b = \left\{ \begin{array}{l} 1,\;\;\;\;\;a \ne b\\ 0,\;\;\;\;\;a = b \end{array} \right.$ (15)
 $a \otimes b = \left\{ \begin{array}{l} 1,\;\;\;\;\;a = 1,b = 0\\ 0,\;\;\;\;其他 \end{array} \right.$ (16)

Step1    i=1;

Step2    j=1, s1=0, s2=0;

Step3     v = αjβi;

Step4    若v是全“1”向量, 则s1=s1+S(Bj), j + +; 否则, 转到Step6;

Step5    若jn2, 转到Step3;否则, 转到Step8;

Step6     v = αjβi;

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

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

Step9    i + +;

Step10    若in3, 转到Step2;

Step11    计算$\sum\limits_{{X_i} \in X} {S({X_i})}$、|X|和|M|;

Step12    结束。

3.2 RSCC的加密与解密算法

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

Step2    i=1;

Step3    若i>r, 跳到Step6;

Step4    计算Ziqi;

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

Step6    输出加密结果c;

Step7    结束。

Step1    根据式 (13) 和 (14) 分别计算Z0S(m);

Step2    i=1;

Step3    若i>r, 跳到Step6;

Step4    计算Ziqi;

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

Step6    输出解密结果m;

Step7    结束。

4 RSCC的安全性分析

RSCC是基于粗糙集方法的加密模型, 它充分利用了粗糙集的确定性中蕴含着不确定性的特性, 提升了加密系统的扩散和混淆能力, 使得密码破译者很难对其进行破译。下面将从几个方面来讨论RSCC的安全性。

1) 模型的数学基础。

RSCC模型的密钥K=(P, X, Y0) 是一个三元组, 其安全性也是由这三个对象的安全性来确定。为了防止攻击者利用穷举法来破解密钥, 密钥的空间往往需要设计得足够大。在RSCC中, 论域U是可以公开的信息, 它的基数决定了密钥KPX的选择空间, 而讨论这些空间大小的关键在于确定论域U上存在的划分P的个数。文献[11-14]中都研究了一个论域U上有多少个划分P的问题, 这些研究结果表明论域上的划分个数会随着论域基数的轻微增大而急剧性地增大, 其具体个数也很难用一个简单明了的公式予以表示, 于是部分学者给出了计算划分个数的算法, 根据这些算法统计了论域U的基数及其对应划分P的个数, 如表 8所示。

RSCC密钥K中的Y0是一个大素数, 而自然数中素数的个数已被证明是无穷多的, 且素数的判断本身就是一个非常耗时的过程。因此, 利用穷举法去确定密钥中的Y0也是不可行的。

2) 模型的设计。

3) 明文信息参与加密。

5 RSCC与传统古典密码的比较分析

5.1 复杂度分析

5.2 安全性分析

RSCC虽然是一种古典密码加密模型, 但其安全性能与其他古典密码模型早已不在同一个级别上, 甚至远超当前一些主流分组密码的安全性, 比如数据加密标准 (Data Encryption Standard, DES) 的密钥长度是56位, 其密钥空间为256; 高级加密标准 (Advanced Encryption Standard, AES) 模型中密钥最大长度为256位, 其密钥空间为2256, 虽然远大于DES的密钥空间, 但却仍然远小于前面例子中RSCC的密钥空间, 所以在安全性上其他古典密码与RSCC不具有可比性。

6 结语

 [1] TRAPPE W, WASHINGTON L C. Introduction to Cryptography with Coding Theory[M]. 2006 : 8 -9. [2] FOUQUE P, HADJIBEYLI B, KIRCHNER P. Homomorphic evaluation of lattice-based symmetric encryption schemes[C]//Proceedings of the 22nd International Conference on Computing and Combinatorics. Berlin: Springer, 2016: 269-280. http://link.springer.com/chapter/10.1007/978-3-319-42634-1_22 [3] 王小云, 刘明洁. 格密码学研究[J]. 密码学报, 2014, 1 (1) : 13-27. ( WANG X Y, LIU M J. Survey of lattice-based cryptography[J]. Journal of Cryptologic Research, 2014, 1 (1) : 13-27. ) [4] 冯登国, 陈成. 属性密码学研究[J]. 密码学报, 2014, 1 (1) : 1-12. ( FENG D G, CHEN C. Research on attribute-based cryptography[J]. Journal of Cryptologic Research, 2014, 1 (1) : 1-12. ) [5] 金建国, 肖莹, 邸志刚. 基于混沌动态随机分组与调制分数阶FFT旋转因子的图像加密[J]. 计算机应用, 2016, 36 (4) : 966-972. ( JIN J G, XIAO Y, DI Z G. Image encryption based on chaotic dynamic random grouping and modulating fractional Fourier transform rotation factor[J]. Journal of Computer Applications, 2016, 36 (4) : 966-972. ) [6] 王聪丽, 陈志斌, 葛勇. 利用Lorenz混沌系统实现红外图像加密的方案[J]. 计算机应用, 2015, 35 (8) : 2205-2209. ( WANG C L, CHEN Z B, GE Y. Infrared image encryption scheme using Lorenz chaotic system[J]. Journal of Computer Applications, 2015, 35 (8) : 2205-2209. ) [7] 徐光宪, 郭晓娟. 基于混沌系统的DNA图像加密算法[J]. 计算机应用, 2014, 34 (11) : 3177-3179. ( XU G X, GUO X J. DNA image encryption algorithm based on chaotic system[J]. Journal of Computer Applications, 2014, 34 (11) : 3177-3179. ) [8] PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Sciences, 1982, 11 (5) : 341-356. doi: 10.1007/BF01001956 [9] SHANNON C E. Communication theory of secrecy systems[J]. The Bell System Technical Journal, 1949, 28 (4) : 656-715. doi: 10.1002/bltj.1949.28.issue-4 [10] 郭凤鸣. 一种生成大周期伪随机数的新算法——改进的混合同余法[J]. 地球科学, 1992, 17 (6) : 733-738. ( GUO F M. A new algorithm in generating pseudo random number-improved mixing congruential method[J]. Earth Sciences, 1992, 17 (6) : 733-738. ) [11] 钱宏, 罗玉芬. 有限集上等价关系数目的计算[J]. 重庆大学学报 (自然科学版), 1992, 15 (3) : 92-95. ( QIAN H, LUO Y F. A formula for computing the nummber of equivalence relations on a finite set[J]. Journal of Chongqing University (Natural Science Edition), 1992, 15 (3) : 92-95. ) [12] 何日挺, 王航平. 有限集几种重要等价类数目的计算[J]. 浙江海洋学院学报 (自然科学版), 2000, 19 (3) : 282-283. ( HE R T, WANG H P. Counting the number of equivalence classes of a few important sets[J]. Journal of Zhejiang Ocean University (Natural Science Edition), 2000, 19 (3) : 282-283. ) [13] 陈仁荣. 有限集合上的划分与覆盖[J]. 常州工学院学报, 2006, 19 (1) : 5-8. ( CHEN R R. The partition and covering of finite set[J]. Journal of Changzhou Institute of Technology, 2006, 19 (1) : 5-8. ) [14] 罗海鹏. 有限集合不同构的等价关系数[J]. 广西科学院学报, 1983, 1 (2) : 12-16. ( LUO H P. The number of non-isomorphism equivalence relation on finite set[J]. Journal of the Guangxi Academy of Sciences, 1983, 1 (2) : 12-16. )