计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (20): 91-95.

• 网络、通信、安全 • 上一篇    下一篇

整数分解的升级算法及对RSA密码体制的影响

姚金江1,武传坤2   

  1. 1.山东临沂师范学院 理学院,山东 临沂 276005
    2.中国科学院 软件研究所,北京 100190
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-11 发布日期:2011-07-11

Upgrade factorization of integers and impact on RSA cryptosystem

YAO Jinjiang1,WU Chuankun2   

  1. 1.School of Sciences,Linyi Normal University,Linyi,Shandong 276005,China
    2.Institute of Software,Chinese Academy of Sciences,Beijing 100190,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-07-11 Published:2011-07-11

摘要: 对Pollard的(p-1)-整数分解算法进行了修改,使其在提高了运行速度的同时,也适用于一些不满足原始(p-1)-整数分解算法的局限条件的数;在(p-1)-分解算法基础上,进一步提出了一种高阶升级分解算法;并给出了在对抗整数分解方面,素数好坏的一种度量方法,在这种新度量方法下,提出了素数稳定阶数的概念,从而说明满足Rivest 条件的数仅仅在对抗二级升级算法时是安全的。

关键词: 整数分解, (p-1)-算法, RSA 密码体制

Abstract: This paper gives a generalization of Pollard’s [(p-1)]-factorization method so that the generalized algorithm not only works more efficiently,but also works on some integers on which the original Pollard’s [(p-1)]-factorization algorithm does not work;based on the [(p-1)]-factorization method,it proposes a higher order upgrade factorization algorithm.This paper further proposes a measure on the robustness of prime numbers in terms of resisting factorization.Under this new measure,this paper proposes the concept of stability order of prime numbers,which means that those numbers satisfying Rivest’s condition are robust only against the second order upgrade factorization.

Key words: integer factorization, the (p-1)-method, RSA cryptography