公钥密码Naccache-Stern的安全性分析

该文对Naccache-Stern公钥密码体制进行了安全性分析，给出了一种攻击方法。其基本思想是，把解密看作一个群分解问题，求解该问题即可获得一个等价明文。当该等价明文向量的各个分量都很小时，则此等价明文就是密文所对应的明文。该攻击算法攻击成功的概率大于直接求解离散对数问题。该算法攻击成功的概率依赖于把一个随机的自然数转化成一个光滑数的概率。

Security Analysis of Naccache-Stern Public Key Cryptosystem

This paper analyzes the security of the Naccache-Stern public key cryptosystem by providing an attack. The basic idea of the attack is that 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.It is also shown that if all the entries of the equivalent plaintext vector are small enough,the equivalent plalntext is the exact plaintext corresponding to the ciphertext.In general,the success probability of the proposed attack is much higher than that of solving the discrete logarithm problem directly.The success probability of the attack relies on with what probability it can successfully transform a random integer into a smooth number.