|国家预印本平台
首页|对REESSE1+公钥密码的明文恢复攻击

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

Plaintext Recovery Attack on REESSE1+ Public Key Cryptosystem

中文摘要英文摘要

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

In this paper two heuristic approaches to plaintext recovery attack on REESSE1+ public-key cryptosystem are proposed . 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.

费向东、潘郁

计算技术、计算机技术

数据安全REESSE1+公钥密码乘法背包明文恢复攻击群分解离散对数格基规约

data securityREESSE1+ public key cryptosystemmultiplication knapsackplaintext recovery attackgroup factorization problemdiscrete logarithmlattice reduction

费向东,潘郁.对REESSE1+公钥密码的明文恢复攻击[EB/OL].(2012-10-10)[2025-08-18].http://www.paper.edu.cn/releasepaper/content/201210-73.点此复制

评论