一种新概率公钥密码系统的研究

张佳茜+夏若时+张勇

摘 要：在BG公钥密码的基础上，利用以Blum数为模的二次同余的平方根不可计算的理论，采用引入随机数进行多轮二次同余计算，组成随机的二进制矩阵并逐位加密的新方法，设计了一种新型的概率公钥密码系统。此密码系统的强度是多项式安全的，加密速度比RSA快，密文膨胀率略大于1，适合加密长消息，能抵抗选择明文攻击。

关键词：概率密码；二次同余；矩阵加密

中图分类号： TP309.7 文献标识码：A

Research of A New Probabilistic Public Key Cryptosystem

Zhang Jia-xi1， Xia Ruo-shi2， Zhang Yong3

（1.Hubei Wuchang Experimental High School， Hubei Wuhan 430060；

2.Wuhan Foreign Languages Schooll， Hubei Wuhan 430022；

3.Wuhan Vocational College of Software and Engineeringl， Hubei Wuhan 430205）

Abstract： Based on the BG public key cryptosystem， a new probabilistic public key cryptosystem is proposed， using the theory of the intractability of solving the square roots in quadratic congruence equation with a Blum integer modulus， making use of the new method by means of introducing a random number in several rounds of quadratic congruence calculation， consisting of binary matrix with random and encrypting data bit by bit. The strength of this cryptosystem is polynomial secure. The encryption speed is faster than RSA， Ciphertext expansion rate is slightly more than 1， being suitable for encrypting long messages and resisting chosen plaintext attack.

Key words： Probabilistic Cryptosystem； Quadratic Congruence； Matric Encryption

1 引言

在密码学里，公钥密码体制有着许多对称密钥密码体制所没有的优势，它能很好地实现数字签名、密钥分发、防抵赖及身份认证等。但通常所说的公钥密码是确定型的密码，即当加密密钥确定后，对于相同的明文只能产生相同的密文。由于公钥密码体制都是公开加密密钥的，因此这种确定型的公钥密码无法抵抗选择明文攻击。针对这一弱点，1984年S.Goldwasser 和S.Micali发表了基于“不可逼近陷门谓词”理论[1]的概率加密（Probabilistic Encryption）的思想，并设计了GM概率密码体制，但其密文膨胀率是明文的400多倍，而无实用价值。1985年，M.Blum和S.Goldwasser提出了BG概率公钥密码系统[2]。该系统将密文膨胀率降低到1+（其中k表示密码体制中模数的长度，即安全系数，l表示明文的长度），能基本符合实际使用的要求。

本文是針对确定型公钥密码体制中存在着可能受到选择明文攻击的缺陷，专门对概率型的公钥密码BG密码进行了深入地研究，并在其基础上，对其加密和解密方法进行了重新设计和改进，提出了基于二次同余理论，使用二次同余数二进制矩阵逐位加密的概率密码的新算法，能有效防止选择明文攻击，同时还具有安全性是多项式安全，密文膨胀率低，加密效率高于RSA，可用于长消息加密等优点。

2 二次同余理论中的相关知识

二次同余理论，也叫平方剩余问题，是被广泛用于密码学特别是用于概率密码的数学理论基础。

设n是正整数集，， 。

定义2.1[4] 若，且存在x满足二次同余式 ，则称a为模n的二次同余，称x为模n下a的平方根。模n的所有二次同余的集合记为Qn，若且，则称a为模n的非二次同余，模n的所有非二次同余的集合记为。

定义2.2[4] 若n=p·q，其中p和q为两个互不相同的素数，并且满足，则称n为Blum数。

定理2.1[16] （欧拉定理）

若 a、n互素，即（a，n）=1，则：

其中为欧拉数，若n=p·q（p 、 q均为素数），===

定理2.2[4] 二次同余的判定定理----欧拉准则

设p为素数，则对任意的，若，当且仅当；

引理1[16] 二次非同余的充分必要条件是。

定理2.3[16] 设p、q为两个互不相同的素数， n=p·q，则对任一整数，有，等价于 且。

此定理说明对于n=p·q（p、q为互不相同的素数），则a是模n的二次同余的充要条件为：a是模 p的二次同余且a是模q的二次同余。

定理2.4[4] 若p为素数且，（Qp为模p的所有二次同余的集合），则在模p下有且仅有二个平方根，分别为。endprint

定理2.5[4] 设n=p·q为Blum数，，则对于有：

①在模n下有四个平方根；

②这四个平方根中仅有一个，其表达式為：

定理2.6[4] 设n=p·q，其中p和q为两个互不相同的奇素数，则分解n计算上等价于求模n的平方根。

定理2.7[4] 设n为合数，并且有形如的完全分解，则当且仅当 ，于是当且仅当对任意的素数pi，i=1，2，3，……k有成立。

可见，若已知n的分解，给定，x模n的二次同余就可以通过确定每个素数p|n的二次同余来确定，而这是可以通过验证欧拉准则来确定的。

但是，如果不知道n的分解，确定模n的二次同余就是非常困难的。

定理2.8[4] 设素数p满足，且。令 ，

1） 如果y有一个模p的平方根，那么y模p的平方根是±x；

2） 如果y没有模p的平方根，那么-y有一个模 的平方根，并且-y模p的平方根是±x。

3 密码算法设计

3.1 二次同余矩阵逐位加密的概率密码的设计思想

BG密码加解密速度比具有同等安全系数的公钥密码如RSA、椭圆曲线密码等要快得多，但是其加密后的密文膨胀率较大，为1+k/l，其中k为模数n的位数，即密码的安全系数，l为明文的长度。同时，为了使加密后的密文有更好的随机性，以增加密文破解难度。鉴于此种情况，基于BG密码的加密思想，在BG密码的加密过程中，引入一个由随机数源起的二次同余数序列组成的矩阵，并把这个矩阵表示成二进制形式后，通过特定算法，用这个矩阵中的某些位上的元素值来对明文进行异或运算，达到加密的目的。这样就进一步地加强了加密后密文的随机性，还提高了破解密码的复杂性，使密码安全性增加，又不影响加密的效率和速度。

3.2 密码具体算法

密码的具体算法设计如下：

现假设实体A要将明文m加密后传送给实体B。

（1）算法预处理过程

① 实体B构造两个不同的大素数p和q，使得 ，并计算n=p·q，则n为Blum数。实体B通过PKI（公钥基础设施）公开n。

② 实体B将（p、q）作为自己的私钥保密。

（2）加密算法

（实体A进行的操作）

① 先将明文M表示成二进制数并划分成（m1，m2，…，mr）组，每一组mi的长度为t。

② 从PKI中找到实体B公开的公钥n。并选择随机数s，使，并作如下计算：

（其中i=1，2，3，…，t）

③ 将x1，x2，…xt表示为二进制数，该二进制数的位数为w，并排成如下矩阵：

其中每一个元素，形成一个二进制数的矩阵，该矩阵有t行w列。

④ 对于每一组明文mi，表示成二进制后形如（bi1bi2…bit），对i=1，2，3，…r，分别计算：

其中j=1，2，3，…t（j表示明文二进制数的第几位）

⑤ 将计算出来的ui，j组装成密文，使分组密文

ci=ui1ui2…uit

i=1，2，3，…r （其中r为明文组数）

⑥ 再计算出。

⑦ 传送密文C=（c1，c2，…cr，xt+1）给实体B。

（3）解密算法

（实体B进行的操作）

① 实体B接收到密文C后，由定理2.7，对i=1，2，3，…t分别作如下计算：

② 重复加密过程中的第③步骤，得到矩阵A。

③ 对于每一组密文 ，表示成二进制后形如（ci1，ci2，…cir ），对i=1，2，3，…r，分别计算：

其中j=1，2，3，…t（j表示明文二进制数的第几位）

④ 将计算出来的bi，j组装成明文，得到分组明文mi=（bi1bi2…bit），其中i=1，2，3，…r（r为明文组数）

⑤ 最后得出明文M=（m1，m2，…，mr），从而恢复出原信息。

4 密码算法分析与评价

4.1 密码算法的正确性分析

由于实体B拥有私钥p和q，由此易得，而由定理2.7，可知对于n=p·q为Blum数，则对于每一个在模n下有四个平方根并且这四个平方根中仅有一个，其表达式为：，则可以唯一求得xi。因此，可据此依次求出xi，xi-1，……，x1，x0，故可从密文中的xi+1求得加密矩阵A。

另外，由上述计算得出的 ，可组成二进制矩阵 。对于加密和解密过程来说， 矩阵是完全相同的，同时在加密和解密过程中又采用相同的取法，得到的密钥也是相同的，从而对明文进行异或加密，再用相同密钥进行异或解密，可恢复出明文来。

4.2 密码算法的安全性分析

本密码算法是多项式安全的。因为对于给定两个明文和，如果只知道它们是两个随机密文和 中之一的明文，则不可能在多项式时间内来确定这两个明文和密文的对应关系。

假设敌手截获了密文和 ，想破译出明文的部分或全部信息，则必须计算数模n的平方根，然而根据定理2.6。当n足够大时，求模n的平方根，等价于求大数n分解为两个不同的奇素数的难度，这在计算上是不可行的。也就是其密码强度就是RSA的密码强度，是多项式安全的。同时，由于经过随机数产生的矩阵的复杂转换，密文的随机性更好，即多次加密不相同的明文时，得到的密文跟明文的差异没有固定地特征变化，因此本密码强度不低于RSA的密码强度。

4.3 密码的加、解密效率分析

本密码在加密时的时间开销主要为平方求余计算，解密时是模的幂运算，其时间复杂度等同于BG密码，而远小于RSA等公钥密码系统的时间复杂度O（k3）。效率较高。endprint

4.4 密文膨胀率分析

密文膨胀率是指被加密后得到的密文与原来明文之间的比率。这里所设计的密码，是将明文（m1，m2，…，mr）經加密变换为c1，c2，…cr，xt+1，可见密文膨胀率为1+w/（t·r），w为xt+1的二进制位数，t为明文分组每组的二进制长度，r为明文分组的组数。当明文越长时，其密文膨胀率越接近于1。但一般而言，其膨胀率不高于BG密码的密文膨胀率，略大于1。

4.5 密码算法评价

（1）可防止选择明文攻击。本算法由于遵循了概率密码思想，在加密过程中引入了随机数，对于相同明文使用相同密钥加密后得到的密文是不相同的。因此可以有效地防止选择明文攻击。

（2）有更好的随机性，增大了破解的难度。同时因为采用了矩阵变换加密密钥，使加密密钥更具有很好的随机性，信息隐蔽性更好，加大了解密的难度。对采用明文攻击或密文攻击等攻击方法的难度比BG密码更大。

（3）时间复杂度低于RSA，数据膨胀率接近于1，可用于加密长消息。但本密码在加大解密难度的同时，并没有增加其加、解密的时间复杂度，其时间复杂度仍等同于BG密码，比RSA和椭圆曲线密码等公钥密码的时间复杂度要低。正因为有这样的优点，所以，本密码体系适合对长文档的加密，并且文档越长，密文的膨胀率越低，越接近于1，效率越高。

参考文献

[1] S Goldwasser， S Micali.Probabilistic Encryption.Journal of Computer and System Sciences，1984，28（2）：207-229.

[2] Blum M， Goldwasser S.An efficient probabilistic public-key encryption scheme which hidesall partial information.Advances in Cryptology Procedings of CRYPTO，84 （LNCSI96），1985：289-299.

[3] Atul Kahate.Cryptography and Network Security.Tata McGraw-Hill.2002.

[4] 王小非，崔国华，李俊，汤学明.一个数据膨胀率为1的概率公钥密码系统[J].计算机科学，2007，34（1）：117～119.

[5] 陈振宇，王丽维.信息安全在公钥密码体制中的实现技术[J].现代计算机，2008.9： 60～61，69.

[6] J.Wade Trappe， Lawrence C.Washington.Introduction to Cryptography with Co-

ding Theory， Post&Telecom Press ，2004.6

[7] 王滨，张远洋.一次性口令身份认证方案的研究[J].计算机工程，2006，32（14）：149-150.

[8] 李大兴，张泽增.一种基于RSA的公开密钥密码体制及其安全性[J].计算机学报，1989.4：279～288.

[9] 洪帆，崔国华，付小青.信息安全概论[M].华中科技大学出版社，2005.9.

[10] Daemen，L.R.Knudsenand，VRjjmen.The Block CIPher Square Fast Sotfware Encry-

ption .Desringer Verlag haiaf Israel，Januay.1997：149～165.

[11] Neal Koblitz.Elliptic Curve Cryptosystems.Mathematics of Computation/American Mathematical Society， 2007， 48（177）：203～209.

[12] 赖溪松，韩亮，张真诚.计算机密码学及其应用[M].北京：国防工业出版社，2001.

[13] William Stallings，白国强.网络安全基础应用与标准[M].北京：清华大学出版社，2007.1.

[14] 何敬民.概率加密方法的设计[J].计算机研究与发展，1989.9：61～65.

[15] 王尚平，王育民. Blum-Goldwasser概率公钥密码体制的一种改进方案[J].西安电子科技大学学报，2001，8（28）：24～27.

[16] Katz J， Yung M. Characterization of Security Notions for Probabilistic Private-Key Encryption[EB/OL].J.Cryptology，Springer-Verlag，2005，DOI：10·1007/s00145-005-0310-8.endprint