素数式在RSA公开密钥密码算法中的分析研究.doc

素数式在RSA公开密钥密码算法中的分析研究 牛 , 它杯寺,,奎 第24卷第4期 2000年8月 武汉交通科技大学 JournalofWuhanTransD0rtati0nUniversity Vo1.24No.4 Augu2000 素数测试在RSA公开密钥密码算法中的分析研究 吴长海孙宝林 (湘北药植高等专科学校武汉430054)(湘北美术学院武汉430060) 摘要:论述丁RSA公开密钥密码技术及RSA安全性分析,介绍了So[ovay—S/rassen索数畏f试算法 以及Miller—Rabin素数测试算法,进一步论述丁产生充分太的素数是切实可行的. 美键词:RSA算法;RsA的安全性分析;SoLovay—S/rassen算法~Miller.Rabin算法 中国法分类号:..¨丁^//8 设是两个不屙奇素数p和g之积,即 0}J言 在今天的信息社会里,通信安全必威体育官网网址问题的 研究已不仅仅出于军事,政治和外交上的需要,科 学技术的研究和发展及商业等方面,无一不与信 息息息相关,由于信息是共享的,信息的扩散会产 生社会影响,所以保护信息的安全是信息时代的 迫切需要【]. 所谓密码技术,就是对信息进行重新编码,从 而达到隐藏信息内容,使非法用户无法获取信息 真实内容的一种手段密钥,是密码体制安全的关 键. 公开密钥密码体制是由Standford大学的研 究人员Diffie和Hellrnan于1976年提出的,它使 密码学发生了一场变革,即使用不同的加密密钥 与解密密钥,是一种由已知加密密钥推导出解密 密钥在计算上是不可行的密码体制,公开密钥密 码体制的产生主要来源于常规密钥密码体制的密 钥分配问题和数字签名的需求1978年由 Rivest,Shamir和Adleman提出了第一个比较完 善的公钥密码算法,这就是着名的RSA算法, lRSA算法的描述 RSA算法的理论基础是一种特殊的可逆模 指数运算,它的安全性是基于分解大整数的困难 性.其算法为: 收稿日期;2000—05—25 吴长海男,46岁.讲师 H—Pq,P—C—Z,()一(P一1)(g一1) K一((n,P,q,口,6)l7t一,P,q是素数,abe----- 1rood()} 对每一个—,P,q,4,6), 定义加密变换为 E()一rood,∈Z 解密变换为 D()一rood,Y∈Z 公开和6,必威体育官网网址P,q和amp;. 公钥密码体制的安全性是指计算安全性,而 绝不是无条件安全性,这是由它的安全性理论基 础即复杂性理论决定的.固为RSA算法的安全性 是基于加密函数E()一modn的单向性,所以 对敌手来说,解密一个密文是计算上不可行的,允 许合法的用户(如B)解密的陷门是分解n一加的 知识,因为B知道这个分解,所以他能计算(n) : (一1)(q一1),从而能计算解密指数口. 2RSA算法的安全性分析 若=pq被因子分解.则RSA便被击破 因为若P.q已知?则(n):(户一1)(q一1)便 可算出,解密密钥d关于e满足: de=1(rood2) 故d便也不难求得,因此RSA的安全性依赖于 因子分解的困难性.目前因子分解速度最快的方 法.其时间复杂性为: ?426?武汉交通科技大学2000年第24眷 exp(sqrt(In()Inln(n))) 若被分解成功,则RSA便被攻破,但还不 能证明对RSA攻击的难度和分解一相当,故对 RSA的攻击的困难不比大数分解更难.当然,若 从求(一)人手对RSA进行攻击,它的难度和分 解相当.但还不能证明对RSA的攻击,其难度 和分解一相当,也没有比因数分解更好的攻击 的方法. 事实上,只要知道),不需要去分解n,只 要用Euclidean算法就可从加密指数b计算出解 密指数日一6rood(n). 但近几年的一些攻击RSA的算法告诫人们: 解密指数算法告诫人们,如果一旦解密指数泄露, 必须重新选择摸;同模攻击告诫人们,不要在不 同的用户之间共享摸;选择密文攻击告诫人们, 应先对明文消息进行处理,如进行杂凑或通过一 个单向变换来破坏RSA算法的同态性质,还必须 注意两个素数P和q不能选择的太接近,否则密 码分析者可先计算sqr(),然后在sqr)的附近 有哪些信誉好的足球投注网站P和q来分解等等. 3素数检测 我们知道,在RSA算法的建立中产生大的 随机素数是必不可步的步骤,在实际中,往往是 首先产生大的随机数,然后使用一个概率多项式 时间算法测试它的素性. 3.1概率测试算法 一 般来说,判定一个数是素数比较难,而否定 它是素数要容易多.如偶数只有2这一个,故偶数 应排除.同样,最后一位为5的数也不是素数,也 应排除,对余下的数再进行素数判定,好在素数的 研究在数论中是比较成熟的.在进行测试前必须 将台数过滤掉,特别是大素数分布具有稀疏的特 点,所以过滤是显得十分