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

Plaintext Recovery Attack on REESSE1+ Public Key Cryptosystem

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

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 broken by invoking the Lenstra-Lestra-Lovasz （LLL） algorithm. As the complexity of computing discrete logarithm in finite field is subexponential, the complexity of breaking REESSE 1＋ public-key cryptosystem is also subexponential.