随着信息时代的到来 , 计算机网络 , 无线通信获 得了巨大的发展 , 人们的生活愈来愈依赖于通过这 些途径获得信息 , 运作商业 。 这样使得通信的安全 性受到越来越大的关注 , 并且也影响了国家的国防 , 经济 , 政治等多个方面 。
密码学和安全 协议是通信系 统安全的技术核 心 。 传统的密码技术主要是建立在基本的替代和置 换工具上的对称密钥加密技术 , 包括有 DES , 3DES , IDEA , AES , Blowfish 等 。Diffie 和 Hellman 在 1976 年 首次公开引进公开密钥密码技术的概念 , 但并没有 给出一种有效的算法 , 直到两年后 , 由 MIT(麻省理 工学院)的 Ron Rivest , Adi Shamir 和 Len Aleman 提 出了 RSA 的通用公开加密方法 , 从而使得公开加密 技术在国防 、商业上获得越来越广泛的应用 , 国际上 ISO , ITU , SWIFT 等标准化组织已把 RSA 体制作为 标准 。
摘 要 :RSA 算法是最为重要的公开密钥密码算法之一 。现主要阐述了 RSA 密码技术的基本理 论 , 算法的基本实现 , 着重讨论了 RSA 算法的安全特性 。 关键词 :公开密码加密算法 ;RSA ;安全性
RSA cipher algorithm and security research
CHEN Cheng , ZHOU Yu-jie
一般可以通过选择极难分解的 n 来反破解 , 对 p , q 可以这样选择 :
(1)p 和 q 长度相差几个数字 , 不能过分悬殊 ; (2)(p -1)和(q -1)都应该包含大素数因子 ; (3)gcd(p -1 , q -1)应该很小 。 3 .2 选择密文攻击 RSA 的模幂运算有保 持输入的 乘法结构 的特 性 , 即有 EK (ab)≡EK (a)EK (b)(modn), 这将影响 RSA 算法协议的安全性 。 (1)破译密文 用户甲发布了他的公钥(e , n), 攻击者监听到一 段发给甲的密文 c , c = memodn , 为了解析出明文 m , 攻击者随机选取了一个小于 n 的数 r , 计算 y = remodn , t =yc(modn), 并且令 k =r-1(modn), 则 k =y -dmod n 。现在攻击者拿 t 给用户甲签名(甲得用 私钥签名 , 而非计算 hash 值), 当甲把签名返回给攻 击者时 , 攻击者就得到了 s = tdmodn 。这样攻击者 就可以计算 : ks(modn)= y-d ×t d(modn)= y-d ×yd ×cd(modn)= cdmodn = m 于是攻击者获得了明文 m 。 (2)骗取签名 同样对于用户甲 , 攻击者有非法消息 mi 要获得 甲的签名 , 但 mi 直接给甲不能被接受 , 于是攻击者 选择 一 个 r , 算 得 y = re(modn), 再 计 算 m = ymi(modn), 将 m 给甲签字 , 获得 s =md(modn), 这
机的出现会给 RSA 安全更大的威胁 , 还有是因子分 解算法的不断改进 。 对于一些特殊形式的大数 , 特 殊数域筛比广义数域筛具有更快的速度 。 可以预计 将来会有更有 效的分 解技术 , 所以取一 个 1024 或 2048bits 的密钥才能保证 RSA 更好的安全性 。
另外 , 如果采用另外的途径破译 RSA , 如在不确 定 p 和 q 的情况下求得 Υ(n), 或不先确定 Υ(n) 而直接确定 d , 但其难度并不小于分解 N 。
Υ(n)=(p -1)＊(q -1); (4)选择一个 e , 使得 gcd(Υ(n), e)=1 ;
1 <e < Υ(n); (5)计算 d ≡ e-1mod Υ(n), 这样私有密钥就是 {d , n}, 公开密钥是{e , n}。 这样用户 A 就可以公开 他的公开密钥 , 用户 B 要发送报文 M 给 A , 可以先 计算 C = Memodn , 在把 C 传给 A 。A 收到密文 C 后 , 计算 M =Cdmodn 进行解密 。
Hastad 证明如果采用不同的模 n , 相同的公钥 e , 则对 e(e +1)/2 个线性相关的消息加密 , 系统就 会受到威胁 。所以一般选取 16 位以上素数 , 速度也 快 , 并且可防止这样的攻击 。 而对短的消息 , 使用独 立随机数填充以保证 me(mod n)≠me , 从而杜绝低 加密指数攻击 。
3 RSA 安全性分析
RSA 的核心算法就是大数的模幂运算 , 下面主 要介绍涉及 RSA 系统安全性的几个问题 。 3 .1 因子分解问题
对 RSA 算法的数学攻击本质上就是对两个素 数乘积的因子分解 。理论上 , RSA 的安全性决定于 大数 N 因子分解的难度 。 一旦 N 分解为两个素数 因子 , RSA 就被破解 。 但数学上至今还未找到分解 一个具有大素数因子的大数的有效办法 , 也不能证 明这种分解就是 NP 问 题 , 可能有尚未发现的多项 式时间分解算法 。常用的因子分解方法有二次筛法 (QS), 改 进 的 二次 筛 (MPQS), 广 义 数 域 筛 GNFS (generalized number field sieve), 特 殊 数 域 筛 SNFS (special number field sieve)。对于素因子在 60 位(十
一般在商业用途的 RSA 设备中 , 模 N 经常是一 个极大的数 , 至少是 512bits , 更多用到 1024bits , 和 2048bits , 这样从上面的计算式看出 RSA 加密解密 所进行的运算量是十分惊人的 , 如果先对大数进行 指数运算 , 再进行模 N 运算 , 中间结果及其巨大 , 并 且运算时间也是惊人的 。 所以 , 一般计算大数模幂 , 都会先分解为一系列大数模乘来完成 。 算法如下 :
1 RSA 加密算法
RSA 算法的基本运算是大数的模幂运算 。 将明 文分组成许多的模块 , 每个模块为小于某个数 n 的 二进制值 , 即模块的大小必须不能大于 log2(n);实 际使用中 , 模块大小取 k bits , 其中 2k <n <2k+1 。对 于明文模块 M 和相应的密文 C , 有这样的关系 :
当有几个用户共用一个相同的模 n 时 , 他们公 布的密钥会存在一定的关系 , 这种关系将给系统带 来威胁 。
如用户甲和用户乙有共用模 n , 公钥分别为 e1 , e2 , 且 gcd(e1 , e2)=1 , 它们用来加密同一个明文时 候 m , 则 c1 = me1(modn), c2 = me2(modn), 因为 e1 , e2 互素 , 则可有 re1 +se2 = 1 , 设 r 为负数 , 由 Euclidean 算法可计算 :(c1-1)-r ×c2s =m(modn), 从而得到了明文 。
相同 , 且 m <n1 , m <n2 , m <n3 。 一般安全性考虑 , n1 , n2 , n3 是互素的 , 这样由中国余数定理可从 c1 , c2 , c3 计 算 出 c , 且 c = m3(modn1 n2 n3), 显 然 m3 < n1n2 n3 , 所以 m = 3 c 。
(Department of Electronic Engineering, Shanghai Jiaotong University , Shanghai 200030, China)
Abstract :RSA algorithm is one of the most important public -key cipher algorithms .This paper mainly discusses the basic theory of RSA cipher technology and its general implementation , with a focus on the security of RSA algorithm . Key words :public -key cipher algorithm ;RSA ;security
而一般为了得到更高的速度 , RSA 硬件实现更 多采用 Montgomery 模乘 , 因为 Montgomery 算法把部 分积对 N 取模转化为对基数 R 的取模 , 可以通过加 和移位实现模乘 , 大大提高 RSA 系统的运算速度 。
另外 , 也 可以使 用中国 余数定 理(Chinese Remainder Theorem)加速解密运算 。 但这样要用到秘密 参数 p , q , 会给系统的安全性带来一定隐患 。
样就可釉计算 , sr -1 = ydmidr -1(modn)=r ×r -1 × mid(modn)= mi d(modn)
— 99。 所以 , 安全起见 , 不要给陌生人提交的随机性文
件签名 , 并且最好先采用单向的散列函数 。 ISO9796 的分组格式可用来防止这样的攻击 。 3 .3 共模攻击
— 98 —
C =Me =modn M = Cdmodn =(Me)dmodn = Medmodn 在整个加解密过程中 , 存在公开密钥 KU ={e , n}和私有密钥 KR ={d , n}, 发送方 B 只知道公钥 KU , 而私钥也只有接受方 A 知道 。 从上面的算法可 以看出必须有可靠的 e , d , n 才能保证算法有效 。 一般生成 RSA 密钥方法是 : (1)随机生成 2 个大素数 p , q ; (2)计算 n =p＊q ; (3)计算 n 的欧拉 totient 函数
信息技术
2005 年第 10 期
中图分类号 :TP393.08 文献标识码 :A 文章编号 :1009-2552(2005)10-0098-03
RSA 加 密 算 法 及 其 安 全 性 研 究
陈 诚 , 周玉洁
(上海交通大学电子工程系 , 上海 200030)