Plaintext Recovery Attack on REESSE1+ Public Key Cryptosystem
Yu Pan · Xinxi wangluo anquan · 2013
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 REESSE1+ public-key cryptosystem is also subexponential.