对REESSE1+公钥密码的明文恢复攻击

对REESSE1+公钥密码的明文恢复攻击

费向东1，潘郁

（南京工业大学经济与管理学院，南京 210009）

摘要：本文提出对REESSE1+公钥密码实施明文恢复攻击的两种启发性方法。一是把解密看

作一个群分解问题，求解该问题即可获得一个等价明文，当该等价明文向量的各个分量都很小时，则此等价明文很可能就是密文所对应的明文；二是如果能在有限域中求解离散对数，从密文恢复明文就转换为解一个低密度、低维数背包问题，可将其规约到一个格的最短向量（SVP） 问题，通过访问一次格预言机求解该背包问题。由于有限域中求解离散对数的计算复杂性是亚指数级的，破译REESSE1+公钥密码的计算复杂性也是亚指数级的。

关键词：REESSE1+公钥密码；乘法背包；明文恢复攻击；群分解；离散对数；格基规约 中图分类号：TP309.7；TN918.4

Plaintext Recovery Attack on REESSE1+ Public Key Cryptosystem

FEI Xiang-dong ，DING Yan-yan，PAN Yu

(College of Economics and Management， Nanjing University of Technology， 210009)

Abstract：Two heuristic approaches to plaintext recovery attack on REESSE1+ public-key cryptosystem are proposed in this paper. First，the decryption of the cryptosystem can be viewed as a group

factorization problem and the solution to the problem gives rise to an equivalent plaintext；If all the entries of the equivalent plaintext vector are small enough, the equivalent plaintext is likely to be the plaintext corresponding to the ciphertext. Second，if discrete logarithm can be computed in finite field，recovering plaintext from ciphertext is translated into solving a knapsack problem with lower density and fewer number of dimensions，which can be reduced to the shortest vector problem（SVP）of a lattice.；The plaintext may be obtained by accessing the lattice oracle one time．As the complexity of computing discrete logarithm in finite field is subexponential，the complexity of breaking REESSE1+ public-key cryptosystem is also subexponential.

Key words: REESSE1+ public key cryptosystem；multiplication knapsack；plaintext recovery attack；group factorization problem；discrete logarithm；lattice reduction

基金项目：江苏省软科学研究计划项目(BR2011057)

费向东（1966.11-），男，江苏无锡人，高级工程师，工学硕士，研究方向为密码算法与安全议，feixd0669@sina.com 潘郁（1955.3-），男，江苏南通人，教授，博士，研究方向为计算管理与商务智能。

1

0 引言

2006年，苏盛辉教授发布了REESSE1+公钥密码算法（以下简称1.0版），之后不断改进直至2.2版，并在全世界范围内重金悬赏征集亚指数时间破解之法。

REESSE1+及改进版为乘法背包公钥密码，其模数是公开的。文献[3] 根据以往的经验，认为一个背包密码只要把模数公布，是注定不安全的。文献[4]正是利用模数，将对该密码的“密钥恢复攻击”规约为求离散对数问题，只要能求解离散对数，就能从公钥恢复出私钥。

本文指出，利用该公钥密码公开的模数，至少有两种途径可对其实施“明文恢复攻击”：一是把解密看作一个群分解问题，将密文表示成公钥向量分量的幂形式，以一定概率从密文恢复明文；二是将“明文恢复”规约为求离散对数问题，只要能求解离散对数，从密文恢复明文就转换为解一个低密度、低维数背包问题，可通过格基规约算法求解该背包。

[5][2]

[1]

1 REESSE1+公钥密码1.0版安全性分析

1.1 第一种明文恢复攻击法

早在1997年的欧密会上，Naccache和Stern就提出了类似的乘法背包公钥密码，其加密机制同REESSE1+公钥密码1.0版。

初始向量a??a1, ... ,an?，素数M作为模数公开，满足M?[6]

?ni?1ai，初始向量a经变

换后形成公钥向量c??c1, ... ,cn?，n比特位长度明文?b?2??b1...bn?被加密为:

C??i?1cibi(modM) （1-1）

文献[7]提出一种攻击方法：ZM??1,???,M?1?构成一个乘法群，从（1-1）式求解

**中把密文C分解成公钥向量分量ci的乘积形式，即：?b?2??b1...bi...bn?等价于在群ZMnC??i?0cifi(modM)

当幂指数fi很小时，f??f1...fi...fn?很可能就是所求明文。该攻击方法适合于包括REESSE1+在内的、具有相同密文结构的乘法背包公钥密码，可以一定概率从密文恢复明文。

n1.2 第二种明文恢复攻击法

由于模数M为素数，故存在M的原根g[8]127，也即g为有限域GF(M)的一个生成元，关于大

素数原根的计算方法早有深入研究[9]。

已知公钥向量的分量ci，生成元g，模数M，存在以下关系： ：

2

ci?guimodM i=1…n ，ui 未知

C?gumodM u 未知

已知密文C，生成元g，模数M，存在以下关系：

如果能求解离散对数ui 和u之值，则根据费马定理

[8]88

，指数之间形成以下关系：

u?b1u1?...?bnun(modM?1)

?b1u1?...?bnun?k(M?1) （1-2）

即：u设|M|和|k|分别表示M和k的二进制比特位长度（简称“长度”）。根据文献[1]，bi∈[0，1]，|b1…bn|=n，|M|=384，n=80，而u1…un 和u是模M-1的余，故|ui|和|u|=|M-1|=384，由此推算：|k|??log(n)?=7

从密文C恢复明文?b1...bn?转换为解一个紧凑型背包问题：

u?x1u1?...?xnun?xn?1(M?1) （1-3）

其中，u为背包值，（u1，…un ，M-1）为背包向量，（x1，…xn ，xn+1）为解向量，其中x1…xn即为希望恢复的明文码?b1...bn?。

攻击背包密码的主要威胁是格攻击。Coster 等人证明

[10]

，如果背包密度D <0.9408，则

可将此背包问题规约为某个格上的最短向量问题(SVP)，当格的维数较低(小于300)时，现有的格基规约算法其应用效果要比理论上好得多，此时格基规约算法可以抽象成一个格预言机，该预言机能以不可忽略的概率输出该背包问题的一个解。

对于（1-3）式背包问题，明文长度=|b1…bn|+|k|=n+|k|，密文长度=|M| 背包密度D = 明文长度/密文长度 =

[5]

n?|k|，如上所述，|M|=384，n=80，|k|=7，故|M|D=0.2266，远远小于0.9408；再则，由于n=80，该背包是一个低维数背包。可将该低密度背

包问题规约到一个低维格的最短向量问题(SVP)，通过访问一次格预言机求解之。

2 REESSE1+公钥密码2.2版安全性分析

2.2版为使形成的密文更复杂，改进了加密机制

[2]5

：

设 ({Ci}， α， β)为公钥，b1…bn ≠ 0 为明文块或对称密钥。 S1: Set ? ← 1， k ← 0，i ←1.

S2: If bi = 0，let k ← k + 1， bi ← 0;

else do bi ← k + 1，k ← 0，? ← ? Ci bi mod M.

3

S3: Let i ← i + 1

If i ≤n，go to S2.

S4: If bn = 0，do ?n-k ← ?n-k + k，? ← ?(Cn-k)k mod M. 由此，得到密文? ≡

?bici(modM) （2-1） i?1nα和β不用于加密过程。

2.2版的加密机制有所变化，具体为：

（1）如 bi = 0， 则 bi ← 0 ；

（2）如 bi = 1， 则 bi ← bi前的连续0的个数+1；

（3）如 bi 是最右端的1，则 bi ← bi前和后的连续0的个数+1；

（1-1）式中bi∈[0，1]，而（2-1）式中bi∈[0，n]，但2.2版的密文结构未变，1.1节的攻击方法仍然有效，通过将密文C表示成公钥向量的分量ci的幂形式，以一定概率从密文恢复明文；再则，只要有能力求解离散对数，从（2-1）式形成的密文?恢复明文可转换为解（1-3）式背包问题，仅仅是解向量的分量xi取值改变为不超过n的整数，但该背包仍然是低密度、低维数背包，因为（2-1）式中，|bi|=?log(n)?，故在（1-3）式背包问题中：

明文长度=n*??log(n)???|k| 密文长度= | M |

由文献[2]，以n = 128 ，lg M ≈ 1216为例，|bi|=?log(n)?=7，|b1…bn|≤n*??log(n)??=896，|M|=1216，而u1…un 和u是模M-1的余，故|ui|和|u|=|M-1|=1216，由此推算：|k|=14

背包密度D = 明文长度/密文长度=

|b1...bn|?|k|=0.7484

|M|远小于0.9408；再则，由于n=128，该背包是一个低维数背包。可将该背包问题规约到一个低维格的最短向量问题(SVP)，通过访问一次格预言机求解之。

需要指出的是，文献[2]认为（1-3）式背包问题的密度大于2，此处计算有误，这已经得到原文作者的确认，该背包是个低密度紧凑型背包。对于此类背包，已有运用格攻击成功破译的例子[11,12]。

3 结语

综合文献[4]和本文提出的攻击方法，破解REESSE1+公钥密码算法的难度不大于求解离散对数，而求解离散对数的计算复杂性是亚指数级的[13]，因此破解REESSE1+公钥密码算法的算复杂性也是亚指数级的。

最后要强调的是，由于乘法背包的模数必须公开，故乘法背包不适宜用于设计公钥密码。

4

参考文献：

[1] 苏盛辉.REESSE1+公钥密码体制的算法［J］.中国科技论文在线，2006，1(3)：208-211 [2] Shenghui Su，Shuwang Lu.The REESSE1+ Public Key Cryptosystem Version 2.2[EB/OL]. [2012-7-25]. http://eprint.iacr.org/2006/420.pdf. [3] 费向东，潘郁.安全背包公钥密码的要点和设计[EB/OL]. [2012-7-25].

http://www.paper.edu.cn/index.php/default/download/downPaper/201207-201 [4] 顾海华，谷大武，谢文录.REESSE1+ 公钥密码的安全性分析[EB/OL]. [2012-7-25].

http://www.paper.edu.cn/index.php/default/releasepaper/content/201111-131 [5] Lenstra A K，Lenstra H W Jr，Lovaasz L. Factoring polynomials with rational coefficients[J]. Mathematische Annualen. 1982，261：513-534

[6] Naccache D and Stern J. A new public-key cryptosystem. Advances in Cryptology.

EUROCRYPT’97， Berlin，Springer，1997，LNCS 1233: 27-36

[7] 王保仓，胡予濮.公钥密码Naccache-Stern的安全性分析[J] .电子与信息学报，2007，29（10）：2448-2450

[8] 许春香.信息安全数学基础[M].成都：电子科技大学出版社，2008

[9] 李作新，卢庆堂.大素数原根的算法[J].科学通报，1983，21(11)：1281-1284

[10] Coster M J，Joux A，LaMacchia B A，et al. Improved low-density subset sum algorithms[J]. Computational Complexity，1992，2(2): 111-128.

[11] 于志强，罗世新，徐树民等.对一个公钥密码体制的格攻击[J].信息安全与通信保密，2008，（10）：105-107

[12] 毕经国，韩立东，刘明洁.基于中国剩余定理的公钥加密算法的破解[J].北京工业大学学

报，2012，38（5）：768-772

[13] A. Odlyzko.Discrete logarithms：The past and the future，Designs，Codes and Cryptography，

19：129-145，2000.

5

本文来源：https://www.bwwdw.com/article/nvkw.html