| New Weak Keys in RSA |
| |
| 作者姓名： | WANG Baocang LIU Shuanggen HU Yupu |
| |
| 作者单位： | [1]Key Laboratory of Computer Network and Information Security, Ministry of Edueation, Xidian University, Xi＇an 710071, Shaanxi, China [2]College of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, Jiangxi, China |
| |
| 基金项目： | Supported by the National Natural Science Foun dation of China （60473029） |
| |
| 摘 要： | The security of the RSA system with the prime pairs of some special form is investigated. A new special-purpose algorithm for factoring RSA numbers is proposed. The basic idea of the method is to factor RSA numbers by factoring a well-chosen quadratic polynomial with integral coefficients. When viewed as a general-purpose algorithm, the new algorithm has a high computational complexity. It is shown thai the RSA number n = pq can be easily factored if p and q have the special form of p = as＋b, q=cs＋d, where a, b, c, d are relatively small numbers. Such prime pairs （p, q） are the weak keys of RSA, so when we generate RSA modulus, we should avoid using such prime pairs （p, q）.
|
| 关 键 词： | 整数因数分解 RSA 公钥密码 算法 信息安全 |
| 文章编号： | 1007-1202（2006）06-1529-04 |
| 收稿时间： | 2006-03-20 |
New weak keys in RSA |
| |
| WANG Baocang LIU Shuanggen HU Yupu.New Weak Keys in RSA[J].Wuhan University Journal of Natural Sciences,2006,11(6):1529-1532. |
| |
| Authors: | Wang Baocang Liu Shuanggen Hu Yupu |
| |
| Institution: | (1) Key Laboratory of Computer Network and Information, Xidian University, Security, Ministry of Education Xi'an, Shaanxi, 710071, China;(2) College of Computer Information Engineering, Jiangxi Normal University, 330022 Nanchang, Jiangxi, China |
| |
| Abstract: | The security of the RSA system with the prime pairs of some special form is investigated. A new special-purpose algorithm for factoring RSA numbers is proposed. The basic idea of the method is to factor RSA numbers by factoring a well-chosen quadratic polynomial with integral coefficients. When viewed as a general-purpose algorithm, the new algorithm has a high computational complexity. It is shown that the RSA number n=pq can be easily factored if p and q have the special form of p=as+b, q=cs+d, where a, b, c, d are relatively small numbers. Such prime pairs (p, q) are the weak keys of RSA, so when we generate RSA modulus, we should avoid using such prime pairs (p, q). |
| |
| Keywords: | integer factorization RSA number public key cryptosystem special-purpose algorithm |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
|
