计算机应用   2017, Vol. 37 Issue (4): 993-998  DOI: 10.11772/j.issn.1001-9081.2017.04.0993
0

引用本文 

汤建国, 汪江桦. 基于粗糙集的古典密码模型[J]. 计算机应用, 2017, 37(4): 993-998.DOI: 10.11772/j.issn.1001-9081.2017.04.0993.
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.

基金项目

国家自然科学基金资助项目(61440047,61562079);新疆维吾尔自治区人文社科重点研究基地项目(050315C01)

通讯作者

汤建国 (1978-), 男, 甘肃武威人, 副教授, 博士, CCF会员, 主要研究方向:粒计算、粗糙集、密码学, E-mail: tjguo@126.com

作者简介

汪江桦 (1982-), 女, 湖北黄冈人, 副教授, 博士, 主要研究方向:数据挖掘、信息检索

文章历史

收稿日期:2016-09-19
修回日期:2016-12-23
基于粗糙集的古典密码模型
汤建国, 汪江桦    
新疆财经大学 计算机科学与工程学院, 乌鲁木齐 830012
摘要: 针对传统古典密码虽然具备简洁高效的特性,但其在当前社会计算能力下极易被破解这一问题,提出一种利用粗糙集方法设计古典密码模型的算法。在该模型的构造中,首先充分融入粗糙集的确定性中蕴含着不确定性以及近似空间规模会随论域微增而急剧增大的特点,来弱化模型的统计规律;其次,借助混合同余法来提升模型产生随机序列的能力;最后,结合自定义运算和同余方法特性来让部分明文信息参与到加密过程中,进一步增强模型抗攻击的能力。研究分析表明,该模型不仅在时间和空间复杂度上与传统古典密码处于同一级别,而且具备了近乎理想的扩散与混淆性能,完全弥补了古典密码容易被破解的缺陷,能有效抵御穷举法和统计分析法的攻击。
关键词: 粗糙集    古典密码    近似空间    不确定性    对称密码    
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 引言

密码技术使通信者可以将信息隐藏在毫无规律的符号组合之中, 防止信息的泄露。最初的加密过程通常采用的是人工方式或者机械方式, 这种加密手段局限于当时落后的计算水平, 使得加密的原理都较为简单以便于使用。这类密码中的代表模型有棋盘密码、Caesar密码、Vigenere密码、Playfair密码和Hill密码等, 后来密码学者将这类密码称为古典密码[1]

计算机技术的出现大幅提升了人类的计算能力与效率, 古典密码的安全性也由此彻底瓦解而淡出了历史舞台, 取而代之的是基于计算机技术的流密码、分组密码和公钥密码等现代密码。然而, 古典密码的简洁和高效的特点仍然是现代密码研究所追求和推崇的。如果能利用现代计算机技术对古典密码进行改造,使之在保持简洁高效的同时,拥有与现代密码抵御攻击的能力,那么将对古典密码的发展产生积极影响。目前,已有很多学者利用计算机科学研究中的数学理论去研究密码学,如基于格论的格密码[2-3]、基于属性的属性密码[4]和基于混沌理论的密码[5-7]等, 这些研究极大地丰富了密码学理论的研究方法。

受此启发, 本文将借助粗糙集方法来作一尝试。粗糙集[8]是一种用于处理不确定性问题的方法, 被广泛应用于人工智能、机器学习和数据挖掘等领域。粗糙集的最大特点在于能从客观数据中自行学习和挖掘有用信息, 以确定的方式来刻画不确定问题。而这种刻画往往会随着知识粒度或者目标集合的变化而变化, 具有很大的不确定性。粗糙集的这些特性非常符合加密模型的技术需求,因为在设计密码时, 既需要利用随机性元素来让其变得不可捉摸而难以破解, 又需要确定性元素使其能够对密文准确解密。

1 背景知识 1.1 粗糙集

粗糙集理论是通过一对精确的近似集合, 即上近似和下近似, 来对目标集合进行逼近而得到一个关于目标集合的近似描述。

定义1    设U是一个论域, PU上的一个划分, XU。定义X关于P的下近似和上近似分别为:

$ {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)

在粗糙集模型中, 当划分P确定后, 不同目标集合X可能产生相同的或者是不同的边界域, 且同一个边界域可能是由不同的上下近似对形成, 这些特性增强了边界域的不确定性和随机性的特点。

习惯上, 称一个论域上的集簇或等价关系为一个知识粒度。论域上不同的集簇或等价关系就是这一论域上的不同的知识粒度。

1.2 古典密码

古典密码编码方法主要有置换和代换两种。所谓置换就是只将明文中的字母顺序打乱重新组合而不改变字母本身的加密手段。最简单的置换密码是把明文中的字母顺序倒过来, 然后截成固定长度的字母组作为密文。比如将“student”组合成“tneduts”。

代换则是将明文中的字母用其他字母来替换进行加密, 比如将“student”替换成“lksjdfm”。代换通常又有两种情况:1) 为字母表设定一个代换字母表, 使原字母表中的每个字母与代换字母表中的字母形成一一对应的关系, 其加密和解密过程就是将明文和密文按照这种对应关系转化为相应的密文和明文; 2) 利用模运算来确定明文对应的密文, 此时需要先将字母表中的每个字母与一个十进制数相对应, 加密或解密时先将明文或密文转化为十进制数, 然后通过模运算来实现加密和解密。表 1是一种常用的字母与十进制数对应关系表。

表 1 英文字母和十进制数字的对应关系 Table 1 Relationship between English letters and decimal numbers
1.3 扩散与混淆

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

所谓扩散就是让明文中的每一位影响密文中的许多位, 或者说让密文中的每一位受明文中的许多位的影响, 理想的情况是让明文中的每一位影响密文中的所有位, 或者说让密文中的每一位受明文中所有位的影响。扩散主要是通过将明文冗余度分散到密文中使之分散开来, 使明文和密文关的关系变得尽可能复杂, 达到明文中任何一点小更动都会使得密文有很大差异的效果。最简单的扩散方法是置换, 即改变代码的相互位置。

所谓混淆就是将密文与密钥之间的统计关系变得尽可能复杂, 使攻击者即使获取了关于密文的一些统计特性, 也无法推测密钥。它主要用于掩盖明文与密文之间的关系, 使密文和对称式加密方法中密钥的关系变得尽可能复杂, 以挫败攻击者通过研究密文来获取冗余度和统计模式的企图。最简单的混淆方法是代换, 即用不同的代码来替换当前的代码。

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

同余法是一种比较好的产生伪随机数的方法, 其中混合同余法的性能更好。混合同余法是Lehmer在1951年提出的[10], 其具体模型如下:

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

其中:ACN均为正整数,N表示模数, A是乘数, C是增量;Z0为初始值 (0≤Z0N)。Zn是在 (0, M) 内服从均匀分布的随机变量;Wn则是在 (0, 1) 内服从均匀分布的随机变量。实验统计表明, 用以下参数进行混合同余法产生的随机序列的统计特性较好:

$ {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)

其中:M为明文空间, |M|表示明文空间的基; S(m) 表示所有明文字符对应序号之和; qi是通过结合密钥K和式 (8) 产生得到的随机数。qi的计算方法如下:

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

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

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

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

从加密的过程容易发现, 对于解密人员来说是无法自行求得S(m) 的值, 因为解密人员在解密之前不可能知道明文内容, 为此可通过向解密人员传递数一个数L′来间接告知其S(m) 的值。

$ 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)

当解密人员获得L′的值后, 便可利用式 (14) 轻易求得S(m) 的值, 再根据式 (11) 进行解密。L′的设计也表明, 加密者在给解密者发送的信息里既要包含明文对应的密文, 同时也要包含未加密的数L′。

将由式 (10)~(14) 确定的加密模型简称为基于粗糙集的古典密码 (Rough Sets Based Classical Cryptography, RSCC)。

需说明的是, 式 (10) 和 (11) 中的mici为对应明文字符和密文字符在表 1中的序号。

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

在RSCC模型中, L′是一个较为巧妙的设计, 它的目的是在于:一方面, 在公式的定义上借鉴了混合同余法形式, 以增强的L′随机性, 而且同余运算不仅能降低L′的大小还能充分隐藏重要信息, 如$\sum\limits_{{X_i} \in X} {S({X_i})} $Y0; 另一方面, 模|M|Len(m) 也并非随意而定的, 其中|M|为明文空间的基, 对于任意一个明文字符mi都有|M|>mi成立, 进而可得S(m) < |M|Len(m), 即S(m) (mod |M|Len(m))=S(m), 这就保证了解密人员可以根据L′的值来准确获得明文信息S(m) 的值。

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, 请根据公式分别对mc进行加密和解密。

解    根据已知条件可得如表 2所示结果。

表 2 计算结果 Table 2 Calculation results

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

表 3 计算Zi Table 3 Calculation of Zi

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

表 4 计算qi Table 4 Calculation of qi

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

表 5 计算S(BnP(Xqi)) Table 5 Calculation of S(BnP(Xqi))

最后根据式 (10) 可得对明文m=I am a student的加密结果如表 6所示。

表 6 加密结果 Table 6 Encryption results

注:加密中忽略单词之间的空格, 不区分大小写。即明文m的加密结果为: y gu x iuatktq

根据式 (11) 可得对密文c=hpdgsopbwtx的解密结果如表 7所示。

表 7 解密结果 Table 7 Decryption results

即解密结果为:I am a teacher。

表 6~7可发现:同一个字符经过RSCC加密之后, 可以转换为多个不同的字符, 而不同的字符可以加密成相同的字符, 这说明RSCC具备较好的混淆性能, 可有效防止统计分析攻击。

为了考察加密模型中引入明文信息Len(m) 和S(m) 对加密的影响, 将本例中的明文m分别变为m′=I am e student和m"=I am a studentz, 即:分别改变了明文中的一个字符和明文长度增加了1, 然后分别对m′和m"进行加密, 得到加密结果为:c′=c ky f myexoxu, c"=t lr a xpfotyek。这个结果表明RSCC模型的扩散和混淆特性达到了一种非常理想状态, 即只要对明文做细微变化就会导致密文出现巨大差异。

此外, 通过对加密结果中不同字符出现的次数进行统计发现:当加密样本较短时不同字符出现的次数有较大差别;而当明文样本足够大时, 不同字符的出现次数差距不断缩小。这进一步表明RSCC模型加密时具有良好的随机性。

3 算法设计

本章将给出基于RSCC的加密和解密算法。首先给出RSCC的初始化算法, 该算法将完成RSCC模型中计算目标集簇中各集合的边界域, 以及由RSCC模型的密钥K可直接计算出的一些中间结果。

3.1 RSCC的初始化

在RSCC模型的加解密过程中, 有些在计算过程中需要用到的中间结果可以根据给定的密钥K提前获得并存储, 以便在使用时可直接调用它们, 提高加解密的效率。这些中间结果主要包括S(BnP(Xi))、$\sum\limits_{{X_i} \in X} {S({X_i})} $和|X|等, 其中S(BnP(Xi)) 的计算相对要繁琐一些, 为此定义如下运算:

$ 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)

其中:a, b∈{0, 1}。为了便于描述计算S(BnP(Xi)) 的算法, 不妨假设|U|=n1, |P|=n2, |X|=n3, “|·|”表示内部对象的基数。

首先将P中的每个集合BjX中的每个集合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}。

输出:S(BnP(Xi)), 1≤in3, $\sum\limits_{{X_i} \in X} {S({X_i})} $、|X|和|M|。

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    结束。

在算法1中, 若v = αjβi是全“1”向量, 说明BjXi=Ø, 根据式 (5) 可知, BjNegP(Xi), 所有符合条件的Bj并集即是NegP(X), 也就是说通过运算“⊕”可以获得Xi关于P的负域; 若v = αjβi不是全“1”向量, 则说明BjXi ≠Ø, 进一步进行“⊗”运算, 若v = αjβi是全“0”向量, 说明BjXi, 根据式 (3) 可知, BjPosP(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.2 RSCC的加密与解密算法

算法2    RSCC加密算法。

输入:明文串m=m1m2mr

输出:密文串c=c1c2cr

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

Step2    i=1;

Step3    若i>r, 跳到Step6;

Step4    计算Ziqi;

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

Step6    输出加密结果c;

Step7    结束。

算法3    RSCC解密算法。

输入:密文串c=c1c2crL′。

输出:明文串m=m1m2mr

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所示。

表 8 UP统计表 Table 8 Statistical table of U and P

表 8可以发现, 当论域U的个数发生微小变化时, 其对应的划分个数却发生了巨大的变化。在实际计算中, 如果将U的个数设置为50时,计算机很难在短时间内 (作者用了将近两天还未得到结果) 计算出结果。不过, 根据表 8统计结果显示出的规律, 当U的基数为50时对应的划分个数至少可以达到1047的量级。与之形成鲜明对比的时, 如果U的基数为100时, 计算目标集Xi关于一个划分P的边界域所需要花费的时间是完全可以忽略的。因此, 这些统计数据足以说明在给定论域上去穷举划分P进行密钥破译是不可行的。

在RSCC的密钥K中, XU上的一个任意子集簇, 相对于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) 是一个三元组, 其中PX的空间大小取决于论域U, 从第4章的分析中可知, 即便论域U处于一个很小的规模时, PX的空间也已经非常庞大, 完全能够抵御基于穷举法的破解攻击, 再加之Y0的参与更进一步地增强了RSCC抵抗穷举法攻击的能力。所以说, RSCC的密钥空间已使其具备了无法用穷举法对其进行攻击的能力。

虽然有些古典密码具备了抵御穷举法的攻击, 如多表代换密码等, 但它们却很难抵御统计分析法的攻击, 因为它们在加密过程中的扩散和混淆能力非常脆弱, 使得加密后的密文与明文之间往往都存在一定的统计规律而容易被破解。RSCC在设计时充分考虑了这一点, 除了通过在模型设计中引入混合同余法, 并充分利用粗糙集自身的不确定特性来增强RSCC的扩散与混淆性能之外, 还将明文信息Len(m) 和S(m) 添加到加密模型中, 这使得RSCC的扩散与混淆性能达到了近乎理想的状态。可见, RSCC已具备非常强的抵御统计分析法攻击的能力, 这是传统古典密码所无法比拟的。

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

6 结语

本文利用粗糙集的特性构建了一种古典密码加密模型RSCC, 研究表明该模型具有其他古典密码模型无法比拟的安全性, 甚至大幅超越了当前一些主流的分组加密模型, 而其加解密的过程却仍然保持了古典密码的简洁与高效, 同时又具备了非常好的扩散性和混淆性, 达到了现实可用的要求。

后续研究还将通过借鉴现代密码研究中的方法来继续完善和改进RSCC, 进一步增强RSCC的扩散和混淆性, 并在这些研究的基础上讨论基于粗糙集的分组密码和公钥密码。

参考文献
[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. )