A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants
A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants
复制标题
DOI：
10.1007/11935230_18
复制
发表时间：
2006-12
期刊：
影响因子：
--
通讯作者：
E. Jochemsz;Alexander May
中科院分区：
文献类型：
--
作者：
E. Jochemsz;Alexander May
我们描述了一种策略，使用基于格的Coppermith技术找到小的模和整数根的多元多项式。应用我们的策略，我们获得了新的多项式时间攻击的两个RSA变种。首先，我们攻击了Qiao-Lam方案，该方案使用了中国剩余解密过程，其私有指数差异很小。其次，我们攻击所谓的Common Prime RSA变体，其中RSA素数以规避Wiener攻击的方式构造。
We describe a strategy for finding small modular and integer roots of multivariate polynomials using lattice-based Coppersmith techniques. Applying our strategy, we obtain new polynomial-time attacks on two RSA variants. First, we attack the Qiao-Lam scheme that uses a Chinese Remaindering decryption process with a small difference in the private exponents. Second, we attack the so-called Common Prime RSA variant, where the RSA primes are constructed in a way that circumvents the Wiener attack.