基于模糊幂半群的概率加密方法设计*

2020-01-06晁海洲倪翔飞

通信技术 2020年7期

晁海洲，倪翔飞

（1.上海财经大学浙江学院，浙江金华 321013；2.浙江师范大学数计学院，浙江金华 321001）

0 引言

随着日常生活数字化的日益加深，信息加密技术的重要性也越来越凸显。

按照加密过程是否可逆，一般可将加密方法分为对称加密和非对称加密技术。对称加密技术的加密过程可以看做由明文空间到密文空间的一个可逆变换，诸如古典密码、分组密码等[1]。他们的加密和解密密钥是相同的，密钥作为私有信息被通信双方密密保存，并不对外公开。对密密通信的窃听或者破坏者主要通过密文和明文关系，推断出私有密钥而破解整个密码系统。对称加密系统很难抵抗暴力破解攻击，因此假定计算机能力足够优良，则传统的对称加密系统不存在理论上的绝对安全性。非对称加密技术主要是以公钥密码为代表，诸如依赖计算不可解问题的RSA 和椭圆曲线加密方法[2]等。除此以外通过考虑一密对多明产生了Rabin密码[1]，反向的考虑一明对多密产生了概率加密方法[3]。非对称加密技术核心思想是将对称的可逆加密变换转化为一个非对称的不可逆变换，从而使得密码系统对密钥私有的依赖性大大降低。但大部分非对称加密技术依然基于数论中计算不可解问题，同样的随着计算机性能的提升，特别是量子计算机从理论走向实用，传统非对称密码系统也会受到较大的冲击。

由于每次加密密钥均不相同，一次一密加密技术理论上具有不可破译的良好性能。但在计算机上很难实现真随机选择，并且一次一密加密系统需要较大的密钥存储空间，所以其实现较为困难。比较好的近似一次一密加密技术是通过移位寄存器实现加密密钥的变换的序列密码[4]，但因为移位寄存器具有规律性，所以可以通过对移位寄存器的工作原理分析而破译序列密码。

半群结构在密码系统设计中有着广泛的应用[5-7]。本文将在模糊集理论[8]基础上，利用素数阶群上的模糊幂半群的结构给出一种非对称加密方法。基于这种方法可以实现密钥存储空间较小的一次一密加密。

1 约简模糊幂半群的结构

作为基础，本节首先给出一些模糊集理论的有关知识和结论。以下如非特殊声明，G均为素数阶群，即就是说G是有限循环可交换的，且每个非单位元均为G的素元。·为G中的二元运算，方便起见称为G中的乘法。G的一个模糊子集A等价于一个由G到区间[0,1]的映射，也称为A的隶属函数，一般不加区别地统一用A表示。函数值A(x)表示元素x隶属于G的程度，称为x在A中的隶属度。·可按如下方式扩展为G的两个模糊子集A,B上的二元运算○，A○B=C，其中C也是G的一个模糊子集，且C(x)=∨{A(y)∧B(z)|yz=x;y,z∈G}。称○为G的模糊子集间的乘法运算。G的所有模糊子集构成的集合在○下满足结合律且是封闭的，因此构成一个半群，称为G的模糊幂半群，记为 F(G)。

记 F*(G)是 F(G)中的由所有单位元在A中隶属度最大的模糊子集构成的子集合，即F*(G)={A∈F(G)|A(e)=max{A(x)|x∈G}}。

F*(G)在乘法运算○下是封闭的，因此它是F(G)的一个子半群，我们称之为G的约简模糊幂半群。

定义1.1 F*(G)称为G的约简模糊幂半群。

设A∈F(G)，若函数序列A,A2,A3,…,An,…的极限存在，则称该极限为模糊集合A的OP-极限。显然该极限也是G的一个模糊子集，且。利用OP-极限我们得到了约简模糊幂半的结构。下面不加证明的列出有关结论。

定义1.2 称A和B是同层的，若对于，记为A～B。

显然同层关系是一个等价关系，且两个同层的模糊子集具有相同的OP-极限。事实上同层关系等价类构成了 F*(G)的一个子半群。若A∈F*(G)，且有0 ≤t≤h=A(e)，使得。

则 F*(G)中任何模糊子集的OP-极限均具有如上形态，也就是说 F*(G)中所有模糊子集的OP-极限均可以由参数h和t完全决定，因此我们将单位元隶属度为h，其余元素隶属度为t的OP-极限记为(h,t)lim。(h,t)lim自乘不变，因此(h,t)lim为 F*(G)中的幂等元。当A～B时，。

此时有结论：

定理1.1A～B的充分必要条件为：A(e)=B(e)=h且max{A(x)|x∈G{e}}=max{B{x}|x∈G{e}}=t成立。

由上面定理可知，同层等价类构成的子半群中所有元素具有共同的特征参数h和t，即就是说该子半群完全由h和t所决定。而任一(h,t)lim属于且只能属于一个等价类。为方便讨论有如下定义：

定义1.3 在 F*(G)中把同层关系下的等价类子半群称为 F*(G)的一个平层。若(h,t)lim属于该平层，则将h称为该平层的轴高；将t称为该平层的厚度。轴高为h，厚度为t的平层记为L(h,t)，其中0 ≤h≤1,0 ≤t≤h。

每个平层包含且仅包含一个 F*(G)中的幂等元(h,t)lim，而下面结论说明 F*(G)中所有的幂等元就是所有的(h,t)lim。

定理1.2 F*(G)中所有幂等元构成集合Λ={(h,t)lim|0 ≤h≤1,0 ≤t≤h}。

在OP-极限下约简模糊幂半群的结构可以完全由它的平层形态确定下来。约简模糊幂半群的每一个平层都是以单位元“高度”为轴高，以次大元“高度”为厚度，围绕唯一的幂等元形成的“盘状”平层。所有约简模糊幂半群中的幂等元“个数”决定了所有的平层“个数”。将所有平层依次“堆叠”起来就得到了约简模糊幂半群。即如下面定理所述，F*(G)可以表示成为一族含唯一幂等元的子半群的不交并。

(h,t)lim不仅是 F*(G)中的幂等元，而且是L(h,t)中的零元。即对任意L(h,t)中的模糊集合A，A与(h,t)lim的乘积都等于(h,t)lim本身。

定理1.4 若A∈L(h,t)，则一定有A○(h,t)lim=(h,t)lim。

立即有如下推论。

定理1.5 对任意C∈F(G)和A∈L(h,t)，有C○A○(h,t)lim=C○(h,t)lim。

证明：由于 F*(G)是半群，故C○A○(h,t)lim=C○(A○(h,t)lim)，由定理1.4，立即可得C○A○(h,t)lim=C○(h,t)lim成立。

注意这一结论在随后加密方案中扮演着重要的角色。

2 加密方法的实现

由定理1.5 容易发现，对于确定的A∈F(G)和L(h,t)，任取B∈L(h,t){(h,t)lim}，则立即有A○B○(h,t)lim恒等于A○(h,t)lim。即就是说在不知道B的情况下，想从A○B中知道A是困难的；但容易从A○(h,t)lim中恢复出A。由此我们可以得到下面的概率加密方案。

准备工作。首先选择合适的素数p，构造p阶有限循环群Gp。记其模糊幂半群为 F(Gp)，约简模糊幂半群为 F*(Gp)。为便于计算机算法实现，对F(Gp)和 F*(Gp)进行离散化处理，取可能隶属度为2s个离散值。方便讨论起见，随后仍旧使用F(Gp)和 F*(Gp)表示Gp经离散化后的模糊幂半群和约简模糊幂半群。

密钥空间的选择。利用B对明文A加密需要先选择 F*(Gp)的一个平层L(h,t)。取0 ≤t≤h≤1，得到L(h,t)。事实上我们不需要保存整个子半群L(h,t)，只需要保存L(h,t)的生成集即可。任一加密密钥B均可由生成集生成。记L(h,t)的生成集为Λ，记L(h,t)=＜Λ＞。则加密密钥空间即为＜Λ＞{(h,t)lim}。确定了加密密钥空间，则解密密钥即为唯一的(h,t)lim。

明文集合的确定。一般加密方案中均假定明文空间没有限制，仅仅考虑加密、解密密钥及加密、解密方法，也就是说在这个加密映射中对定义域和值域无太多限制，仅仅针对对应规则进行讨论。事实上，实际传输中的信息往往是存在于有限多状态或者可以由有限状态表示出来。因此经过适当选择可用明文的表示，在一定程度上也可以起到对信息的保护。假设实际传输中有意义的基本明文字段有m个，其余明文信息均可由该m个基本明文字段构造，则我们只需要考虑如何加密传输这有限m个明文即可。通过映射 M 将m个明文字段对应到F(Gp)L(h,t)中的m个模糊子集上，从而得到相应的明文集合。明文在 F(Gp)中的分布应能使得通过B加密后的更好的隐藏明文信息，监听者从密文A○B中很难猜测出相应的明文A；同时接受者要能容易从密文A○B中恢复出明文A。

显然A不能落在L(h,t) 中，因为此时必有A(e)=h和max{A(x)|X≠e}=t，从而立即A○B∈L(h,t)，即A○(h,t)lim=(h,t)lim，此时接受者也无法利用A○(h,t)lim从密文A○B中恢复出明文A。

若对两明文A1,A2∈F(G)有对同一平层L(h,t)，A1○(h,t)lim=A2○(h,t)lim，则利用同一密钥B∈L(h,t)，两个明文会产生同样密文。此时接收者是无法区分明文A1和A2的。因此明文选择必须避免这样的情况发生。若A和B与(h,t)lim乘积相同，则称为同义的。同义构成等价类。明文选择在每个同义等价类中只能选择一个。

若有A1,A2∈F(G)和B1∈L(h1,t1)，B2∈L(h2,t2)，使得A1○B1=A2○B2，称之为对不同密钥空间产生了碰撞。则此时在不知道密钥是B1还是B2时，很难通过密文破解密码系统。因此明文集合选择应以对不同密钥空间产生尽可能多的碰撞为宜。

解密表。发送密文A○B被接收者接收后，解密过程中接受者只需要进行运算A○B○(h,t)lim即可。在这个过程中由于零元性质实际上已经破坏了原来明文信息内容，因此乘积结果并不直接等于明文本身。因此实际上解密过程需要先算出所有明文与(h,t)lim乘积的结果，再和密文与(h,t)lim乘积结果比较，从而完成解密。为此可以先预算出所有明文与(h,t)lim乘积的结果并保存、生成解密表。记明文为Aλ时对应的解密表内容为Dλ，则整个解密表为集合Λ={Dλ}。

双方确定素数P和数2s，构造 F(Gp)和F*(Gp)，并在 F(Gp) F*(Gp)中确定并保存有限明文集合。

加密过程。消息接受者在 F*(Gp)中选择平层L(h,t)，保存(h,t)lim作为解密密钥，计算所有明文与(h,t)lim乘积，保存为解密表，并经安全信道发送参数h,t。消息发送方恢复平层L(h,t)的生成集合并保存。消息发送方通过平层L(h,t)的生成集合产生加密密钥B，加密所需要传输的明文得到A○B=C。经公开信道传送密文C。

解密过程。收到C后，消息接收方计算C○(h,t)lim，比较解密表，得到明文A。

3 性能分析

本文提出的加密方案是一种一次一密的非对称私钥概率加密方案。下面将本方案与对称私钥加密方案、序列密码、公钥加密方案等进行比较。

对称私钥加密方案可以看做由私密钥产生对应关系得到的明文空间到密文空间的可逆映射。其特点是算法复杂度低、易于实现。但对称私钥加密方案对密钥保密性要求很高，当私密钥被窃取则加密系统将失去安全性；同时对称私钥加密对应一个可逆映射，这就意味着当已知足够的明文-密文对，即可通过统计分析破解加密系统。本文提出的方案密钥是非对称的，攻击者很难通过对明文-密文对的统计分析破解系统；但由于约简模糊幂半群的特征，若密钥B被窃密者截获则容易利用约简模糊幂半群的结构特点分析得到解密密钥从而破解系统。因此本方案对密钥保密性要求较高，是一种私钥加密体系。

序列密码一般是由移位寄存器生成密钥序列对明文加密、解密的。其特点是易于实现，计算复杂度较低，且由于每次生成的加密密钥不同使得加密方案安全性较好，能抵抗明文-密文对攻击。但序列密码作为对称私钥密码，解密密钥需要和加密密钥一致，这就导致序列密码一般要求高度的时钟同步，这在很多环境中难于实现；另外由于移位寄存器的结构相对固定，因此通过对其结构的分析就能够攻破序列密码体系。本文提供的方案与序列密码类似的地方在于可以实现一次一密加密过程，因此类似于序列密码，想要通过密文和明文-密文对破解密码体系一般来说是困难的。同时由于其非对称性，加密密钥和解密密钥不相同，因此时钟同步性上要求不高，适应环境更广泛。同时由于对不同密钥空间碰撞的存在，使得想通过统计分析或者针对使用的模糊幂半群结构分析破解密码系统是困难的。但相对于移位寄存器，计算半群乘法运算复杂度较高。

公钥密码方案是通过单向陷门函数产生非对称的加密、解密密钥进行保密通信的。由于从加密密钥很难破解出解密密钥，因此加密密钥是可以公开的。不需要通过安全的私有传输信道传送加密密钥。共要密码方案最大的优点就是保密通信对信道的密钥传输信道的安全性要求很低。但大部分共要密码方案所产生的的密钥对是相对固定的，对不同明文消息的加密、解密采用相同的密钥。这使得保密系统在采用统计分析方法进行的攻击下容易被攻破。本文方案具有类似于非对称密钥的特征，但由于代数结构的存在，加密密钥须通过安全私有信道发送，故相比较公钥密码方案对密钥传送信道要求较高。但其可实现一次一密的特性能较好地抵抗统计分析攻击。