RSA公钥密码算法的原理及实现

liqingboyou

最近发现腾讯的webQQ加密算法更改了，所以就看了一下腾讯的加密算法，以前总体的来说就是二进制、八进制、十六进制转换、md5转换、移位运算<<等混合操作来加密。查看新的加密文件mq_comm.js时发现新的算法可能是用RSA Encryption相关算法来实现的。RSA算法应该在几年前就遇到过很多次，但每次都因为复杂的数论知识而没看懂其算法（这也验证了编程的核心是算法，算法的核心是数学的思维，同时也回答了纯数字有什么用的问题。），这次静下心来仔细看了一下，将学习成果总结如下：（下面的文章，遇到不懂的地方可以先了解大概，然后继续看，后面会有详细介绍。看完再回头研究。）
（感谢阮一峰http://www.ruanyifeng.com/blog/archives.html ，最新查找的东西几乎都是在他的网络日志中找到的。无论是设计模式还是加密算法。）

美国麻省理工学院的Rivest、Shamir 和 Adleman 实现了非对称加密算法，用他们名字命名叫RSA算法。是目前使用最广最优秀的加密算法，几乎有网络的地方就要用到它。

对称加密算法DES:加密，解密采用同一密钥。

非对称加密算法RSA：加密采用公钥，解密用私钥，公钥解不开。

一、加密，解密过程。

假设：n=3233，e=17，d=2753

公钥(n,e) =(3233,17)，私钥(n,d)=（3233, 2753）

6、加密：公钥(n,e) =(3233,17)，加密公式：me ≡ c (mod n)

已知明文m，公钥n,e，求密文c.

eg:明文m=65，加密为密文C=2790

m=65à代入公式：6517 ≡ 2790 (mod 3233)à c=2790

7、解密：私钥(n,d)=（3233, 2753），解密公式：cd ≡ m (mod n)

已知密文c,私钥n,d，求明文m。

密文C=2790，解密为明文m=65

c=2790à带入公式27902753 ≡ 65 (mod 3233)àm=65

二、密钥生成：

1、任选两质数p,q。

2、模数n=p*q。

3、欧拉函数φ(n)=(p-1)(q-1)。

4、随机数e，满足1< e < φ(n)，且e与φ(n) 互质

5、模逆d，公式ed ≡ 1 (mod φ(n))

eg: p=61,q=53,n=3233,φ(n)=3120,e=17,d=2753

1、p=61,q=53

2、n = 61×53 = 3233

3、φ(3233)=60×52=3120

4、e=17

5、d=2753

说明：

1、p、q越大，越难破解。

2、n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

4、在1到3120之间，随机选择了17。实际中，常常选择65537。

5、计算e对于φ(n)的模反元素d。使得ed被φ(n)除的余数为1。

d计算步骤：ed ≡ 1 (modφ(n))èed - 1 = kφ(n)èex + φ(n)y = 1已知e=17,φ(n)=3120è17x + 3120y = 1 "扩展欧几里得算法"(x,y)=(2753,-15)è即d=2753。

6、实际中，公钥和私钥的数据都采用ASN.1格式表达。

m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。

如果要加密大于n的整数，有两种解决方法：①把长信息分割成若干段短消息，每段分别加密；②先选择一种"对称性加密算法"（如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。

三、私钥解密证明

为什么用私钥解密，一定可以正确地得到m。也就是证明下面这个式子：

　　cd ≡ m (mod n)

因为，根据加密规则

　　ｍe ≡ c (mod n)

于是，c可以写成下面的形式：

　　c = me - kn

将c代入要我们要证明的那个解密规则：

　　(me - kn)d ≡ m (mod n)

它等同于求证

　　med ≡ m (mod n)

由于

　　ed ≡ 1 (mod φ(n))

所以

　　ed = hφ(n)+1

将ed代入：

　　mhφ(n)+1 ≡ m (mod n)

接下来，分成两种情况证明上面这个式子。

（1）m与n互质。

根据欧拉定理，此时

　　mφ(n) ≡ 1 (mod n)

得到

　　(mφ(n))h × m ≡ m (mod n)

原式得到证明。

（2）m与n不是互质关系。

此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。

以 m = kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立：

　　(kp)q-1 ≡ 1 (mod q)

进一步得到

　　[(kp)q-1]h(p-1) × kp ≡ kp (mod q)

即

　　(kp)ed ≡ kp (mod q)

将它改写成下面的等式

　　(kp)ed = tq + kp

这时t必然能被p整除，即 t=t'p

　　(kp)ed = t'pq + kp

因为 m=kp，n=pq，所以

　　med ≡ m (mod n)

原式得到证明。

说明：1、由于n等于质数p和q的乘积，所以m必然等于kp或kq

因为m与n不是互质关系，说明m与n有共同的公因子g，假设m=hg，由于n=pq，p与q互质，n只有p和q两个因子，所以g和h必然有一个等于q或者p， 所以才有结论“m必然等于kp或kq”

2、t=t'p

因为(kp)ed = tq + kp,=>(p)ed*(k)ed = tq + kp,=>

(p)ed*(k)ed - kp = tq,=>

p[(p)(ed-1)*(k)ed - k ] = tq,

左边是p的倍数，那右边必然也是p的倍数。因为p与q互质，所以t必然是p倍数，即 t=t'p

3、m与n互质。根据欧拉定理，此时mφ(n) ≡ 1 (mod n)

怎么得到(mφ(n))h × m ≡ m (mod n)”？

mφ(n) ≡ 1 (mod n) => mφ(n) = K n +1 , k为自然数

(kn + 1)^h 展开多项式，除了1以外，全部含有kn， 所以其他项都能被n整除而余1.

推出 (mφ(n))h ≡ 1 (mod n)

设(mφ(n))h=r1*n+1,然后(mφ(n))h*m=(r1*n+1)*m,这个和n的余数就是m。

liqingboyou

宝座！

liqingboyou

:):):):):):):):):):):):):):):):):):)

Cheungnotes

膜拜中....！