RSA密码体制的实现及分析

RSA密码体制的实现及分析

摘要:网络服务的丰富, 尤其是电子商务的发展, 需要强健的密码技术来确保安全地传递信息. 密码算法的工程实现对商业和军事都有着重要的意义. RSA 是第一个公钥密码的实际实现, 在1978年Rivest、Adleman、Shamir提出该算法之后, 已广泛应用于各种硬软件产品. 本文研究RSA的算法实现, 分析RSA算法的缺陷并给出解决方法. 从而进一步说明RSA在理论和实际应用中的重要性.

关键词: RSA;数字签名;公钥密码体制

中图分类号:TP309文献标识码: A

1引言

随着网络技术的飞速发展, 信息安全性已成为亟待解决的问题. 公钥密码体制[1], 由于其解密和加密密钥不同, 解密和加密可分离, 通信双方无须事先交换密钥就可建立起保密通信, 因此较好地解决了传统密码体制在网络通信中出现的问题. 另外, 随着电子商务的发展, 网络上资金的电子交换日益频繁, 如何防止信息的伪造和欺骗也成为非常重要的问题. 数字签名[2]可以起到身份认证、核准数据完整性的作用. 目前关于数字签名的研究主要集中基于公钥密码体制的数字签名.

公钥密码体制已成为确保信息的安全性的关键技术. 自从1976 年Diffie 和Hellman两位教授提出公开密钥密码学的新概念后, 由于公开密钥密码学具有优良的密码学特性和广阔的应用前景, 很快吸引了全世界的密码爱好者, 他们提出了各种各样的公开密钥密码算法和应用方案, 密码学进入了一个空前繁荣的阶段. 然而公开密钥密码学的研究绝非易事, 尽管提出的算法很多, 但是能经得起时间考验的却寥寥无几.

RSA 算法是由美国麻省理工学院的学者Ron Rivest, Adi Shamir和Leonard Adleman[3]于1978 年提出的公开密钥算法, 该算法已经经受了密码分析家多年深入的分析. RSA算法基于大数分解的困难性, 其公开密钥和私人密钥是一对大素数的函数, 从一个公开密钥和密文中恢复出明文, 难度等价于分解两个大素数的乘积. 大大提高了RSA密码体制的安全性.

2RSA的算法描述

2.1算法参数 的构成

(1)选取两个强素数;

(2)计算 ;

(3)随机选取 , 满足 , 那么公钥即 ;

(4)计算 , 那么私钥即 ;

(5)最后销毁 , 其中 为欧拉函数 , 保存私钥, 公开公钥.

很明显, 在公钥 中, 若 能被因子分解, 则通过 可求出解密密钥 , 进而整个RSA系统即不安全.

2.2加解密过程

首先将明文数字化并分块, 每个数字化的明文的长度不大于 , 然后对每个明文块 ,一次进行加、解密变换:

设 为明文,为密文.

(1)加密 (1)

(2)解密 (2)

证明:

RSA算法的安全性的理论基础是大素数的因子分解问题, 此问题至今没有很好的算法, 因而公开 和 是不易求出 和 及 的, 但是为保证安全性, RSA 算法要求是两个足够大的素数(通常要求100 位以上的十进制数).

例2.1[4]:

假定用户B选择了两个素数

, 因而 ,B取 , 然后又Euclidean算法求得 .

B公开 , 保密 和 ;

假定另一个用户A想把明文 发给B, 则A计算秘密指数,进行解密 得到明文信息.

3RSA算法的实现细节

结合RSA算法的步骤, 我们讨论RSA的实现过程中考虑的细节问题.

3.1大素数 的选择

因为若 被分解, 则RSA就被攻破, 所以大素数 的选择就很重要.

(1) 多大合适. 从安全性角度考虑, 选择多大的素数取决于目前因数分解的能力. 目前, 最新记录是129位十进制在网络上通过分布式计算被分解成功; 如果在亿次计算机上对200位十进制数进行分解, 估计需要55万年. 所以, 用户应当 为100位的十进制数. 这样,将达到200位, 从而使现有的分解攻击失效.

(2) 要适当大. 因为 , 则 可以写成 , 设 , 则 ,, 故

若 比较接近, 则 将是一个很小的数, 而 比 稍大. 这样, 可以检查大于 的每一个整数, 直到找到 为止. 这样,便可以表示为 的形式, 从而可以分解为 .

(3) 和 都应当有很大的素数因子. 这一要求是针对RSA的模数 的 因子分解攻击和循环加密攻击.

(4) 应较小. 假若 较大, 将 和 的最小公倍数记作 ,则 会较小; 由于满足 的 一定满足 , 所以 在较小的情况下可以通过穷举方法找到 .

满足上述条件的素数称为安全素数.

3.2 的选择

不能太小, 以免穷举攻击. 当 时,是较容易确定的, 这也是实现RSA系统时应先选择 的原因. 选择完 后, 可以用扩展的欧几里得算法计算出 , 其依据是: 若 , 则存在整数 使得 成立.

3.3模指数运算

RSA加解密变换都要进行 的模指数运算, 为提高运算加速和节约存储空间, 采用对指数的二进制化来实现. 具体算法[5]如下:

(1) 转(2).

(2)若 则输出 , 结束; 否则, 转(3).

(3)若 , 转(4); 否则, 转(5).

(4) , 转(3).

(5) ,转(2).

其算法流程框图如图所示.

3.4模数的使用

若系统中共用一个模数, 只是不同的人拥有不同的 和 , 则系统将是危险的. 最普遍的情况是同一信息用不同的公钥加密, 这些公钥共模而且互质, 那么该信息无需私钥就可得到恢复. 设 为信息明文, 两个加密密钥为 , 公共模数是 , 则密文分别为 、 . 窃听者截获密文 后, 可以用如下的方法得到明文 :

(1)用扩展的欧几里得算法求出满足 的两个整数 ;

(2)计算 就可以得到明文.

另外, 还有其他几种利用公共模数攻击的方法. 总之, 如果知道给定模数的一对 和 , 一是有利于攻击者分解模数; 二是有利于攻击者计算出其他成对的 和 , 而无需分解模数. 解决方法只有一个, 那就是不要共享模数 .

4RSA算法缺陷分析及解决方法

通过上述分析, 我们知道, RSA算法是比较优秀的加密算法, 尤其是在数字签名方面得到了广泛的应用. 但笔者在教学及实验过程中发现该算法存在两个缺陷, 下面, 笔者从几个实例出发, 介绍RSA算法存在的缺陷, 并提出了有效的解决方法.

4.1算法缺陷之一

例4.1[6]数字签名实例: 设用户 的身份代码为数字3, 并设 两用户产生公开密钥的基数为: 用户 , 用户 .

要求用户 用自己的身份代号作为身份向用户 发艺数字签名, 并将数字签名用 的公开密钥加密. 用户 收到该数字签名消息后, 先用 用户的私有密钥解密,用户的公开密钥进行身份验证;

首先计算 两用户的公开密钥和私有密钥如下: 用户 : 公开密钥 和私有密钥 均为: . 用户 : 公开密钥 和私有密钥 均为: .

用户的操作步骤如下:

第一步:用户以其身份代号“3”作为身份数字签名:

数字“33”就是用户 的数字签名.

第二步: 将此数字签名用 用户的公开密钥 加密:

这里的“12”就是通过加密以后的数字签名.

用户收到 用户发来的经加密后的数字签名“12”后,操作步骤如下:

第一步: 先用自身的私有密钥进行解密:

第二步: 用 用户的公开密钥进行身份验证:

从上面结果看出, 得到用户 的身份是“33”而不是“3”, 其结果是错误的, 从一例子可看出了RSA算法的不可用性.

仔细分析上述计算过程, 发现其原因是,用户用于产生密钥的基数太小. 从这里我们可以得到这样一个结论, 只要用户 的数字签名结果大于用户 产生密钥的基数乘积 , 就必然会产生这一缺陷.

解决这一问题问题的方法有二, 一是加大RSA的算法密钥基数 和 , 越大越好, 以避免用户 的数字签名结果大于用户 的密钥基数 和 乘积 的现象的发生. 其二, 在实际应用中, 不允许公开密钥和私有密钥一致.

4.2算法缺陷之二

例4.2[6]设用户 的身份代号为35, 并设其公开密钥产生的基数为: ,

通过计算, 其公开密钥 和私有密钥 分别为:

对用户 的身份进行数字签名:

从上计算可看出, 当用户 的身份代号为35时, 其数字签名的结果为0, 致使接收方不能确认发送方的身份.

进过实验, 除35以外, 当用户 身份代号为105, 175, 245, 315, 385, 455等时, 其数字签名结果都为0,

我们再举一个例子:

例4.3[6] 设通过计算, 其公开密钥 和私有密钥 分别为:

当用户身份为143, 223, 251, 285, 287, 297等时, 其数字签名结果均为0.

通过分析发现, 任何一个公开密钥对, 至少存在一个用户身份代码, 使得其数字签名结果为0.其验证方法很简单, 当用户身份代码与素数 和 的乘积 一致时, 其数字签名的结果肯定为0.

解决这一问题的途径有三:

(1) 一个用户至少应有两个以上(含两个)的公开密钥对, 且这两个公开密钥对的产生基数 和 的乘

积 应是互质的. 这样, 当在签名时发现用一个密钥对进行数字签名的结果为0时, 即改用另一个密钥对进行数字签名.

(2) 用户身份代号尽可能的小, 至少要小于用于产生加密密钥的基数 和 的乘积.

(3) 用于产生加密密钥的基数 应尽可能的大,理想的 和 应在100位以上的十进制数. 这样做有两个方面的好处: 一是可有效地避免数字签名的结果为0 (因为任何一个用户的身份代号不可能是100位以上的十进制数) ; 另一方面是增加了密钥破解的难度.

5结论

本文从数学的角度对RSA公钥密码算法的简化计算方法和算法进行了探讨和分析. 在公开密钥加密算法中, RSA已经作为标准, 几乎在各种信息安全需求中给出很好的解决方案, 其最大的优点是密钥空间大, 缺点是长密钥带来巨大的计算量, 导致加密速度慢. 随着解密方法的进步和计算硬件技术的不断发展,RSA算法应用显得越来越笨拙. 但是RSA 加密算法是目前应用最广泛的公钥加密算法, 特别适用于通过Internet传送数据. 不管怎样,RSA算法还是会在将来很长一段时间继续成为公开密钥加密算法的主流.

参考文献:

[1]W. Trappe, L.C. Washington. 密码学概论 [M]. 北京: 人民邮电出版社, 2004.6: 98~103.

[2]D.R. Stinson.. 密码学原理与实践 [M] . 北京: 电子工业出版社, 2003.2: 142~144.

[3]R.L. Rivest, A. Ahamir, L.M. Adleman. A method for obtaining digital signatures and public-key cryptosystems [J]. Communications of the ACM, 1978, 21(2): 120~126.

[4]张海燕, 高树风, 毕秀丽, 吴方. RSA算法安全性分析 [J]. 计算机安全, 2008, 7: 43~48.

[5]陈传波, 祝中涛. RSA算法应用及实现细节 [J]. 计算机工程与科学, 2006,28(9), 13~14、87.

[6]杨云江. RSA的算法缺陷分析 [J]. 贵州大学学报, 2006,23(1) , 35~39.