RSA加算法的安全性分析.doc

RSA 加密算法的安全性分析* 肖媛媛 ( 潍坊学院, 山东 潍坊 261061) 摘 要: 描述了RSA 算法, 给出了RSA 加解密的算法以及它的抗攻击能力分析表, 总结了常见的攻 击方式, 最后分析了在实际应用中存在的一些弊端。 关键词: RSA; 公钥密码体制; 安全性 中图分类号: T P309 文献标识码: A 文章编号: 1671- 4288( 2009) 06- 0050- 03 随着当前网络技术和电子商务的高速发展和普 及, 对网络数据安全的需求日益迫切, 如何保证网络 上的信息安全成为一个重要的研究课题, 而数据加 密是保护信息安全的一种重要方法。密码学的鼻祖 香农[ 1] 提出了一些概念和基本理论, 论证了只有一 种密码算法在理论上是不可解的。 目前, 在各种公钥密码算法中, RSA 公钥密码 算法是用途比较完备、使用最为广泛的一种公钥密 码体制。它表达方法简单, 保密性强, 没有密钥管理 的麻烦; 并且可用于数字签名、认证等服务, 特别适 合于现代保密通信的需要。但由于其算法是基于大 数的模幂模乘运算, 特别是目前为防止各种攻击, 其 模长在不断增加, 算法运行的速度成为RSA 密码算 法的一个显著缺陷, 特别是在软件环境下, 加解密速 度比较慢。 1 RSA 算法原理 1978 年, Rivest R L、Shamir A 和Adleman L 发表了著名的论文/ A Method fo r Obtaining Dig ital Sig natures and Public - Key Cyr ptosystems0, 继 MH 背包公钥密码体制以后, 提出了第一个有效的 公钥密码体制, 现被用他们的名字的首字PI 命名, 称为RSA 公钥密码体制[ 2] 。 1. 1 RSA 的密钥生成步骤 1 找到2 个大质数p, q; o 做乘法n = p* q; ? 选择一个数e, 满足e n 且与( p - 1) * ( q - 1) 互质; ?计算d = mod[ ( p- 1) ( q- 1) ] / e; ? e 就是公开指数, d 是私密指数; ?公匙就是( n, e) , 私匙是( n, d) ; ? 销毁p 和q; 加密算法是这样的, 把明文分成比n 小的数据 块用公开指数作乘方取模运算 c = memodn( m 是明文块( messag e) , c 是密文 块( cipher) ) 。 解密过程正相反, 把密文数据块用私密指数作 乘方取模运算 m = cdmodn 攻击者有公匙, 就是e 和n, 想获得私匙, 换句 话就是d, 对n 进行因数分解来获得p, q 从而算出d 是最好的攻击方法, 直接穷举d 或推断( p - 1) ( q- 1) 都要慢许多[ 3] 。 1. 2 几种因数分解的算法 1 试探除法: 最古老也是最笨拙的方法, 穷举所 有小于sqr t( n) 的质数, 耗时以指数率增长。 o 二次筛法( QS) [ 4] : 对10110 以内的数是最快 的算法。 ? MPQS: QS 的改进版本, 速度要快一些。 ?分区筛法( NFS) [ 5] : 目前对大于10110的数是 最快的算法, 曾被用来成功地分解过第9 费马数。 这些算法代表了人们对RSA 攻击的探索历程, 最好的算法具有超多项式率( 亚指数率) 的时间复杂 度, NFS 具有最接近于多项式率的表现。 大数分解仍然是困难的, 但随着数论的发展和 计算能力的增强而变得容易了。1977 年, RonR-i v est 说过分解一个125 位的数需要花费4 @ 1013 a。 在1994 年RSA129 被分解了, 花费了5 000MIPS # a 的机时, 是利用Internet 上一些计算机的空闲 ) 50 ) 第9 卷第6 期 潍坊学院学报 Vo l. 9 No. 6 2009 年11 月 Jo ur nal of Weifang Univ ersity Nov . 2009 * 收稿日期: 2009- 06- 24 作者简介: 肖媛媛( 1982- ) , 女, 山东淄博人, 潍坊学院信息与控制工程学院助教。 CPU 周期一共花了8 个月完成的。1995 年, Blacknet 密钥被分解, 用了几十台工作站和1 台Mar Par, 共用400 MIPS # a, 历时3 个月。随着时间的推移, 可能被分解的密钥长度还会增加。表1 是常用的几 种RSA 密钥长度( PGP 精选出的) 与其对应的NFS 分解算法所耗费的时间。 表1 NFS 因数分解时间表 密钥长NFS 分解算法耗费的时间/ MIPS # a 512 30 000 768 200 000 000 1024 300 000 000 000 2