RSA公钥密码算法

高嵩

摘要：：RSA加密算法是一种非对称加密算法。是第一个比较完善的公开密钥算法。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。在公开密钥密码体制中，加密密钥（即公开密钥）是公开信息，而解密密钥（即秘密密钥）是需要保密的。加密算法和解密算法也都是公开的。虽然解密密钥是由公开密钥决定的，由于无法计算出大数n的欧拉函数phi（N），所以不能根据公开密钥计算出秘密密钥。

关键词： RSA;公钥;私钥

近十年来信息技术飞速发展，数字信息化给经济社会带来了巨大利益，但是伴随着网络的快速发展与普及，数据通信的逐步开放，通信安全问题逐步的显露出来，信息传输的安全隐患问题日渐严峻。通信安全问题成为信息安全研究的重点。

RSA是第一个比较完善的非对称公开密鑰算法，它不仅能用于加密，也同样能用于数字签名。RSA以它的三个发明者Ron Rivest， Adi Shamir， Leonard Adleman的名字首字母命名，这个算法经受住了多年深入的密码分析考验，虽然进行密码分析的人既不能证明RSA的安全性，也不能否定RSA的安全性，但这恰恰说明该算法具有的的可信性。[1]

一、RSA算法结构

（1）选择两个不同的、足够大的素数p，q。

（2）计算n=pq。

（3）计算f（n）=（p-1）（q-1），同时对p， q严加保密，绝不能泄露。

（4）计算一个与k（n）互质的数e，并且使1

（5）计算出d=e-1（mod（p-1）（q-1）），使得d e≡1 mod f（n）。

公式中，≡符号的左右两边模运算结果相等。不管k（n）取什么值，1 mod k（n）的运算结果都等于1;符号左边d与e的乘积做的模运算结果也必须等于1。这就需要计算出d的值，使得这个同余等式能够成立。

（6）公钥GY=（e，n），私钥SY=（d，n）。

（7）在加密时，先将明文信息变换成0至n-1的一个整数M。若明文比较长，可先分割成合适的分组，然后再进行变换。假设密文为C，则加密过程为：C = me mod n。

（8）解密过程为：M = cd mod n。

二、实例解析

通过一个实例来了解RSA的工作原理。为了便于计算。在下面的实例中只选取较小数值的素数p，q，以及e，假定用户A需要将明文“key”通过RSA加密后传递给用户B，过程如下：

（1）设计公钥GY（e，n）私钥SY（d，n）所以密钥对即为（e，d，n）。

求n：准备两个质数=5，q=7，所以n=35。

求l：l 是 p-1=4 和 q-1=6的最小公倍数12。

求e：e必须满足两个条件：e是一个比1大比l小的数，e和l的最大公约数为1。

用gcd（X，Y）来表示X，Y的最大公约数则e条件如下：

1 < e < l=12

gcd（e，l）=1

e=5

之所以需要e和l的最大公约数为1就是为了保证必须存在解密时需要使用的数d。现在我们已经求出了e和n，也就是说我们已经生成了密钥对中的加密秘钥（公钥）了。

求d：数d是由数e计算出来的。d、e和l之间必须满足以下关系：

1 < d < l=12

e*d mod l = 1

现在私钥已经生成了，密钥对也就自然生成了，即d=5。

设p=5，q=7，得出n=p×q=5×7=35;f（n）=（p-1）（q-1）=4×6=24;取e=5，（3与20互质）则e×d≡1 mod f（n），即5×d≡1 mod 24。

鉴于两个素数比较小，我们也可以可以用试算的办法来查找。

我们通过计算找到，当d=5时，e×d≡1 mod f（n）同余等式成立。因此，令d=5。从而我们可以设计出一对公私密钥，加密秘钥（公钥为）：GY =（e，n）=（5，35），解密密钥（私钥）为：SY =（d，n）=（5，35）。

（2）数字化英文加密。

将明文信息先数字化，并将每块两个数字分为一组。假定明文英文字母编码表就按字母顺序排列，即a=01、b=02、……、z=26以此类推。

则得到的分组后key的明文编码信息为：k=11，e=05，y=25。

（3）明文加密

用户加密密钥（5，35） 将数字化信息明文分组信息加密成密文。由C≡Me（mod n）得：

C1≡（M1）e （mod n）=115（mod 35）=16

C2≡（M1）e （mod n）=055（mod 35）=25

C3≡（M1）e （mod n）=255（mod 35）=30

因此，得到相应的密文信息为：16，25，35。

（4）密文解密。

用户B收到密文，若将其解密，只需要计算M = cd mod n，即：

M1≡（c1）d （mod n）=165（mod 35）=11

M1≡（c1）d （mod n）=255（mod 35）=05

M1≡（c1）d （mod n）=355（mod 35）=25

用户B得到明文信息为：11，05，25。根据上面制定的的编码表将其转换为英文，我们又得到了恢复后的明文“key”。

三、小结

一般来说RSA的安全性完全依赖于大数的因子分解，可是并不是从理论上证明破译RSA的难度与大数分解难度等价相同。所以RSA的重大缺陷是不能从理论上确保它的保密性能是怎样的。RSA密码算法实现中涉及到的数学问题相对较少且每个模块相对简单，但组合起来想要破译却相当困难，今后涉及到的公钥私钥密码可能会在数学问题上的编程中产生许多问题。

参考文献：

[1]陈航，周剑岚，冯珊.基于SHA和RSA算法实用有效的双向身份认证系统.《计算机安全》，2006

[2]李云飞，柳青，郝林，周保林.一种有效的RSA算法改进方案.《计算机应用》，2010

[3]黄俊，许娟，左洪福.基于RSA算法的注册码软件加密保护.《计算机应用》，2005