密码学报（中英文）2025，Vol.12Issue(3)：604-626,23.DOI:10.13868/j.cnki.jcr.000784
CRT-RSA的小dp,dq实际攻击研究
Practical Attack on Small dp,dq CRT-RSA
摘要
Abstract
CRT-RSA is a variant of RSA proposed by Quisquater and Couvreur in 1982.It is widely used in many fields such as data encryption,digital signature,protocol,and identity authentication.The small dp,dq attack is one of the important tools to analyze the application security of CRT-RSA,and the best theoretical result of the attack at present is dp,dq<N0.122 given by Takayasu,Lu,and Peng in 2019,where N is the modulus.Nevertheless,due to the degradation of both efficiency and quality of lattice reduction algorithm in high dimensions,the theoretical bound is difficult to be achieved in practice.The best results of the practical attack as we know are dp,dq≤N0.062 with an 1000-bit modulus N and dp,dq≤N0.0645 with a 2000-bit modulus N,which have considerable gaps with the theoretical bound.Based on the attack of Takayasu et al.in 2019,this study explores the upper bound of the small dp,dq attack on CRT-RSA that can be practically achieved and how to improve the bound in practical attacks.Firstly,an optimization is performed for the lattice constructed by Takayasu et al.in 2019(we call it TLP2019 lattice for convenience)by removing two unhelpful polynomials,which leads to a reduction of the dimension of TLP2019 lattice by two.Secondly,in view of the current situation that there is no known effective method for CRT-RSA to estimate the upper bound of small dp,dq that can be practically achieved,combined with the fact that the lengths of the first three vectors in the reduced basis of the TLP2019 lattice are much smaller than the length of the shortest vector in random lattices,an estimation method is given for the upper bound that can be practically achieved based on parameter fitting.The estimation results are consistent with experiments well.Thirdly,according to the"multivalued phenomenon"analogous to that in the practical attack on small private exponent RSA,a practical attack on small dp,dq CRT-RSA is proposed based on the binary search and the upper bound that can be achieved in practice is improved.Specifically,for CRT-RSA with 1000-bit moduli and 2000-bit moduli,the practical attack is completed when dp,dq≤N0.067 and dp,dq≤N0.0665 within two weeks;for some special cases,the upper bound can even be raised to more than N0.07.It is believed that the proposed practical attack exploration can bring inspiration and help to the subsequent research on attacks on small dp,dq CRT-RSA.关键词
CRT-RSA/小dp,dq攻击/实际攻击/高比特猜测/多值现象/二分搜索Key words
CRT-RSA/small dp,dq attack/practical attack/MSBs guess/multivalued phenomenon/binary search分类
信息技术与安全科学引用本文复制引用
李强,郑群雄,戚文峰..CRT-RSA的小dp,dq实际攻击研究[J].密码学报（中英文）,2025,12(3):604-626,23.基金项目
国家自然科学基金(12371526)National Natural Science Foundation of China(12371526) （12371526）
