论文部分内容阅读
[摘要]RSA密钥体制运行中，信息发送方采用公开的密钥加密明文，信息接收方则使用私有的解密密钥解读密文，该算法易于理解和操作，可同时用于加密和数字签名，被广泛应用于众多计算机信息安全领域，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。
[关键词]RSA 密钥 算法
中图分类号：TP3文献标识码：A 文章编号：1671－7597(2008)0610056－01
在计算机信息传递中，信息发送方-甲方，为了保护传输的明文信息不被第三方窃取，采用一个密钥A对要发送的信息进行加密而形成密文M并且发送给乙方，信息的接收方-乙方用另一把密钥B对密文M解密，得到明文消息，从而完成密文通讯。密钥A和密钥B是采用事先商定的某种计算机算法产生的密钥对，其中密钥A为用户私有，密钥B对网络上的大众是公开的，这种安全机制被称为公开密钥加密，公开密钥加密算法又叫非对称密钥加密算法，RSA就是其中最流行的一种，被广泛应用于简短信息加密和数字签名等领域。
一、RSA加密算法简介
RSA加密算法诞生于1978年，是以三位发明人的名字(Rivest，Shamir和Adleman)首字母命名的，它是利用质数因子分解的困难性开发的算法，其保密强度是建立在计算的复杂性的基础之上的。RSA应用中要求每一个用户拥有自己的一种密钥：公开的加密密钥，用于加密明文；保密的解密密钥，用于解密密文。
在RSA密钥体制运行中，信息发送方用公开的密钥加密明文，信息接收方则使用解密密钥解读密文，其特点是：密钥配发方便，每个用户只需要持有一组密钥对就可以实现与网络中任何一个用户保密通信；加密原理基于单向函数，非法接收者利用公开密钥不可能在有限时间内推算出解密密钥。
二、RSA加密算法原理
RSA公开密钥加密算法的基本原理是：
（一）产生密钥对
首先，选择两个大质数，p 和q，计算：
n = p * q
然后，随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互质，且0 < e < ( p - 1 ) * ( q - 1 )。
最后，计算解密密钥d, 要求满足：
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )
其中n和d也要互质。数e和 n是公钥，用于加密信息，对所有使用者公开；数d和n是私钥，用于解密信息，用户自己保存。
（二）加密
信息发送者取得对方的公钥e和 n后，对发送的明文信息m进行加密运算可获得加密信息c，对应的密文计算方法是：
c = me mod n
然后通过通信渠道把密文信息c传递给信息接收者。
（三）解密
信息接收者接收到密文信息c后，采用自己掌握的私钥d和n进行解密获取明文信息m，对应的解密运算方法是：
m = cd mod n
由于RSA加密算法速度较慢，通常适用于对少量数据的加密，所以在加密明文信息 m时，首先把m分成等长数据块m1，m2，...,mi ，然后分别对m1，m2，..., mi进行加密，即m = m1m2... mi，c = c1c2... ci ，解密时也是如此。
下面举例验证RSA加密算法原理的科学性：
例1：假定发送明文信息m = key,为方便运算，把26个英文字母从0126进行自定义编码，如a = 01,b = 02…z = 26，对应的m = key = 110525，把m分成6个等长模块m1，m2，…m6，即m1 = 1，m2 = 1，m3 = 0，m4 = 5，m5 = 2，m 6= 5。
取素数p和q，满足n =p * q，且mi <= n，理论上素数p和q的值越大加密的安全性越高，破解的难度也就越大，但是从降低运算的复杂性方便验证算法科学性的角度考虑，我们尽可能取最小的值。比如，取p = 2，q = 5，那么n = p * q = 10。
然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) = 4 互质且0 < e < 4，显然e = 3满足要求。
最后，计算解密密钥d, 要求满足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )， 其中n和d也要互质，即3 * d除以4的余数为1，且d和10互质，可以取值d = 7。
对应的密文是：
发送方把明文信息m按照自定义的编码转换成数值110525，然后采用RSA算法产生的加密密钥（3，10）加密后形成密文信息c=110585，发给接收方，接收方采用解密密钥（7，10）对接收的密文信息c进行解密，获取解密后的信息m’。接收方按照事前商定规则同样把收到的密文信息c分成6个等长模块分别对每个模块进行解密从而获取明文值 m’=
比对原始明文信息m和解密后获取的明文信息m’,显然m’ = m。
例2：为了简化运算流程，假设我们需要加密的明文信息为m = 14，取符合算法要求的p、q值分别为5和11。
计算n = p * q = 55，( p - 1 ) * ( q - 1 ) = 40。
然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) = 40 互质且0 < e < 40， 可以取e = 3。
最后，计算解密密钥d, 要求满足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )，即3 * d = 1mod 40，可以取d = 27。
加密：
解密：
解密结果与原明文信息一致。
以上实例足以证明RSA加密算法原理的科学性，使用RSA加密算法进行保密通信是可以信赖的。实际操作时，通常先选定e，再找出并确定质数p和q，使得计算出d后，它们能满足RSA加密算法计算原理的要求。
三、RSA加密算法应用
RSA加密算法除了用于少量数据加密之外，最主要的应用就是数字签
名。数字签名是通过密码运算生成一组符号及代码，用于鉴定签名人的身份以及对电子数据内容的认可，它还能验证出文件的原文在传输过程中有无变动，确保传输电子文件的完整性、真实性和不可抵赖性。
（一）数字签名的原理
被发送的文件用SHA编码加密产生128bit的数字摘要；发送方用自己的私有密钥对摘要再加密，形成数字签名；将原文和加密的摘要同时传给对方；对方用发送方的公共密钥对摘要解密，同时对收到的文件用SHA编码加密产生又一摘要；将解密后的摘要和重新用SHA编码加密收到的文件所产生的摘要相互对比。如两者一致，则说明签名可信而且传送过程中信息没有被破坏或篡改过。否则不然。
（二）数字签名运算
数字签名使用者首先采用SHA编码法对欲签名的文件信息m进行数字摘要运算，得出摘要值h（m），再用自己掌握的私钥d和n进行签名运算，可获得数字签名s，对应的数字签名计算方法是：
。之后将数字签名s和文件信息m一起发送给对方。
（三）数字签名验证
文件信息接收方收到数字签名s和文件信息m后，首先采用SHA编码法对欲签名的文件信息m进行数字摘要运算，得出摘要值h（m），再用从对方处取得的公钥e和n对数字签名s进行解密运算，获取摘要值h（m）’，对应的解密运算方法是：，最后比对h(m)’和h(m)，若h(m)’=h(m)，则签名s正确，反之则不然。
四、RSA加密算法的缺陷
RSA加密算法的原理和规则都是公开的，理论上攻击者掌握了密文信息和加密密钥后，采用逆向的方式反复尝试是可以破解密钥的，因此为增强其安全性，取素数p和q的值要尽可能大，使得运算复杂性增高，攻击者短期内不能如愿。一般攻击者是将某一信息作伪装后，让拥有私钥的实体签署，然后，经过计算就可得到它所想要的数据。实际上，攻击利用的都是同一个弱点，即乘幂保留了输入的乘法结构：。
由此可以看出，尽管RSA加密算法有着充足的科学依据，而且在很大程度上能保障信息传输的保密性，但是RSA机制仍然存在一些不容忽视的弊端：
1. 产生密钥很麻烦。RSA是利用质数因子分解的困难性开发的算法，由于受到质数产生技术的限制，因而难以做到一次一密；
2. 分组长度太大。RSA的保密强度是建立在计算的复杂性的基础之上的，为保证其安全性，n至少也要 600 bits以上，使得运算代价太高，尤其是运算速度很慢，随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。
五、结束语
RSA加密算法是被研究得最广泛的公钥算法，易于理解和操作，可同时用于加密和数字签名，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，尽管存在一些瑕疵，但还是被普遍认为是目前最优秀的公钥方案之一。在电子商务应用系统中，RSA加密算法更是惯用的技术之一。目前，SET协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。据专家测算，攻破512位密钥RSA算法大约需要8个月时间；而一个768位密钥RSA算法在2004年之前无法攻破；在技术上暂时还无法预测攻破具有2048位密钥的RSA加密算法需要多少时间，因此，遵照SET协议开发的电子商务系统的安全性是非常高的。
参考文献：
[1]冯素琴，RSA公钥密码算法的研究与实现[J]，忻州师范学院学报，2006（2）.
[2]曹建国，基于RSA公钥密码安全性的研究[J]，计算机技术与发展，2007（1）.
[3]鄢喜爱，RSA公钥密码算法的分析[J]，长春工业大学学报（自然科学版），2006（2）.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
[关键词]RSA 密钥 算法
中图分类号：TP3文献标识码：A 文章编号：1671－7597(2008)0610056－01
在计算机信息传递中，信息发送方-甲方，为了保护传输的明文信息不被第三方窃取，采用一个密钥A对要发送的信息进行加密而形成密文M并且发送给乙方，信息的接收方-乙方用另一把密钥B对密文M解密，得到明文消息，从而完成密文通讯。密钥A和密钥B是采用事先商定的某种计算机算法产生的密钥对，其中密钥A为用户私有，密钥B对网络上的大众是公开的，这种安全机制被称为公开密钥加密，公开密钥加密算法又叫非对称密钥加密算法，RSA就是其中最流行的一种，被广泛应用于简短信息加密和数字签名等领域。
一、RSA加密算法简介
RSA加密算法诞生于1978年，是以三位发明人的名字(Rivest，Shamir和Adleman)首字母命名的，它是利用质数因子分解的困难性开发的算法，其保密强度是建立在计算的复杂性的基础之上的。RSA应用中要求每一个用户拥有自己的一种密钥：公开的加密密钥，用于加密明文；保密的解密密钥，用于解密密文。
在RSA密钥体制运行中，信息发送方用公开的密钥加密明文，信息接收方则使用解密密钥解读密文，其特点是：密钥配发方便，每个用户只需要持有一组密钥对就可以实现与网络中任何一个用户保密通信；加密原理基于单向函数，非法接收者利用公开密钥不可能在有限时间内推算出解密密钥。
二、RSA加密算法原理
RSA公开密钥加密算法的基本原理是：
（一）产生密钥对
首先，选择两个大质数，p 和q，计算：
n = p * q
然后，随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互质，且0 < e < ( p - 1 ) * ( q - 1 )。
最后，计算解密密钥d, 要求满足：
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )
其中n和d也要互质。数e和 n是公钥，用于加密信息，对所有使用者公开；数d和n是私钥，用于解密信息，用户自己保存。
（二）加密
信息发送者取得对方的公钥e和 n后，对发送的明文信息m进行加密运算可获得加密信息c，对应的密文计算方法是：
c = me mod n
然后通过通信渠道把密文信息c传递给信息接收者。
（三）解密
信息接收者接收到密文信息c后，采用自己掌握的私钥d和n进行解密获取明文信息m，对应的解密运算方法是：
m = cd mod n
由于RSA加密算法速度较慢，通常适用于对少量数据的加密，所以在加密明文信息 m时，首先把m分成等长数据块m1，m2，...,mi ，然后分别对m1，m2，..., mi进行加密，即m = m1m2... mi，c = c1c2... ci ，解密时也是如此。
下面举例验证RSA加密算法原理的科学性：
例1：假定发送明文信息m = key,为方便运算，把26个英文字母从0126进行自定义编码，如a = 01,b = 02…z = 26，对应的m = key = 110525，把m分成6个等长模块m1，m2，…m6，即m1 = 1，m2 = 1，m3 = 0，m4 = 5，m5 = 2，m 6= 5。
取素数p和q，满足n =p * q，且mi <= n，理论上素数p和q的值越大加密的安全性越高，破解的难度也就越大，但是从降低运算的复杂性方便验证算法科学性的角度考虑，我们尽可能取最小的值。比如，取p = 2，q = 5，那么n = p * q = 10。
然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) = 4 互质且0 < e < 4，显然e = 3满足要求。
最后，计算解密密钥d, 要求满足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )， 其中n和d也要互质，即3 * d除以4的余数为1，且d和10互质，可以取值d = 7。
对应的密文是：
发送方把明文信息m按照自定义的编码转换成数值110525，然后采用RSA算法产生的加密密钥（3，10）加密后形成密文信息c=110585，发给接收方，接收方采用解密密钥（7，10）对接收的密文信息c进行解密，获取解密后的信息m’。接收方按照事前商定规则同样把收到的密文信息c分成6个等长模块分别对每个模块进行解密从而获取明文值 m’=
比对原始明文信息m和解密后获取的明文信息m’,显然m’ = m。
例2：为了简化运算流程，假设我们需要加密的明文信息为m = 14，取符合算法要求的p、q值分别为5和11。
计算n = p * q = 55，( p - 1 ) * ( q - 1 ) = 40。
然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) = 40 互质且0 < e < 40， 可以取e = 3。
最后，计算解密密钥d, 要求满足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )，即3 * d = 1mod 40，可以取d = 27。
加密：
解密：
解密结果与原明文信息一致。
以上实例足以证明RSA加密算法原理的科学性，使用RSA加密算法进行保密通信是可以信赖的。实际操作时，通常先选定e，再找出并确定质数p和q，使得计算出d后，它们能满足RSA加密算法计算原理的要求。
三、RSA加密算法应用
RSA加密算法除了用于少量数据加密之外，最主要的应用就是数字签
名。数字签名是通过密码运算生成一组符号及代码，用于鉴定签名人的身份以及对电子数据内容的认可，它还能验证出文件的原文在传输过程中有无变动，确保传输电子文件的完整性、真实性和不可抵赖性。
（一）数字签名的原理
被发送的文件用SHA编码加密产生128bit的数字摘要；发送方用自己的私有密钥对摘要再加密，形成数字签名；将原文和加密的摘要同时传给对方；对方用发送方的公共密钥对摘要解密，同时对收到的文件用SHA编码加密产生又一摘要；将解密后的摘要和重新用SHA编码加密收到的文件所产生的摘要相互对比。如两者一致，则说明签名可信而且传送过程中信息没有被破坏或篡改过。否则不然。
（二）数字签名运算
数字签名使用者首先采用SHA编码法对欲签名的文件信息m进行数字摘要运算，得出摘要值h（m），再用自己掌握的私钥d和n进行签名运算，可获得数字签名s，对应的数字签名计算方法是：
。之后将数字签名s和文件信息m一起发送给对方。
（三）数字签名验证
文件信息接收方收到数字签名s和文件信息m后，首先采用SHA编码法对欲签名的文件信息m进行数字摘要运算，得出摘要值h（m），再用从对方处取得的公钥e和n对数字签名s进行解密运算，获取摘要值h（m）’，对应的解密运算方法是：，最后比对h(m)’和h(m)，若h(m)’=h(m)，则签名s正确，反之则不然。
四、RSA加密算法的缺陷
RSA加密算法的原理和规则都是公开的，理论上攻击者掌握了密文信息和加密密钥后，采用逆向的方式反复尝试是可以破解密钥的，因此为增强其安全性，取素数p和q的值要尽可能大，使得运算复杂性增高，攻击者短期内不能如愿。一般攻击者是将某一信息作伪装后，让拥有私钥的实体签署，然后，经过计算就可得到它所想要的数据。实际上，攻击利用的都是同一个弱点，即乘幂保留了输入的乘法结构：。
由此可以看出，尽管RSA加密算法有着充足的科学依据，而且在很大程度上能保障信息传输的保密性，但是RSA机制仍然存在一些不容忽视的弊端：
1. 产生密钥很麻烦。RSA是利用质数因子分解的困难性开发的算法，由于受到质数产生技术的限制，因而难以做到一次一密；
2. 分组长度太大。RSA的保密强度是建立在计算的复杂性的基础之上的，为保证其安全性，n至少也要 600 bits以上，使得运算代价太高，尤其是运算速度很慢，随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。
五、结束语
RSA加密算法是被研究得最广泛的公钥算法，易于理解和操作，可同时用于加密和数字签名，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，尽管存在一些瑕疵，但还是被普遍认为是目前最优秀的公钥方案之一。在电子商务应用系统中，RSA加密算法更是惯用的技术之一。目前，SET协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。据专家测算，攻破512位密钥RSA算法大约需要8个月时间；而一个768位密钥RSA算法在2004年之前无法攻破；在技术上暂时还无法预测攻破具有2048位密钥的RSA加密算法需要多少时间，因此，遵照SET协议开发的电子商务系统的安全性是非常高的。
参考文献：
[1]冯素琴，RSA公钥密码算法的研究与实现[J]，忻州师范学院学报，2006（2）.
[2]曹建国，基于RSA公钥密码安全性的研究[J]，计算机技术与发展，2007（1）.
[3]鄢喜爱，RSA公钥密码算法的分析[J]，长春工业大学学报（自然科学版），2006（2）.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”