RSA非对称加密算法——瞎聊

1.什么是RSA算法：

RSA是目前使用比较多的公钥算法，使用非常广泛，也是目前号称最安全的加密算法。
对称密码：加密和解密使用同一种密钥。
公钥密码：加密和解密使用不同中的密钥，也叫非对称密钥。
RSA就是非对称密钥。

1.1 RSA算法历史

RSA算法诞生之前使用的是对称密码；加密解密规则用的同一套规则：

1.甲方选择某一套规则对信息进行加密；
2.乙方使用同一套规则对信息进行解密；

思考点：如果甲方乙方从来不能碰面，那甲方的规则怎么被乙方获取？
因此，规则必须通过网络从甲方传输到乙方，但这样就会带来一个问题，如果在传输的过程中规则被截获了，这样甲方和乙方所有的通信消息将是透明的；这就是对称密钥的缺点。

---

假设下，如果加密和解密使用的不是同一套规则，是不是可以避免这样的问题？？？
比如甲方有一个公钥和私钥；乙方同样有公钥和私钥；甲方用乙方的公钥加密然后发给乙方，乙方用自己的私钥解密；反之亦然。如下：

1.甲方先通知乙方，乙方根据某种算法算出本次与甲方通信的公钥和密钥；
2.乙方将生成的公钥发送给甲方（公钥是公开的，就算泄漏也没有问题）；
3.甲方将需要传送的信息用乙方的公钥进行加密，然后发给乙方；
4.乙方接收到甲方的信息后用自己的私钥进行解密；

思考：如上所述，看起来可以解决对称加密的缺点。但是会衍生出另一个问题：

如果一开始双方发送公钥的时候，就被截取了，然后冒充另一方身份和你通信，这太可怕了~~~？？？？

这个问题我们在后续里面讲解。。。。

---

RSA算法就是为了解决对称加密不安全的问题而诞生的，私钥不在网络传输，因此比较安全。RSA算法非常可靠，密钥越长，它越难被破解，下面会介绍原理。值得一提的是RSA在https安全协议中也是经常使用的。

2.RSA加密原理：

2.1 必备数学知识

素数 ：又称质数，除了1和自身外，不能被任何自然数整除的数。
互质数：公因数只有1的两个数叫做互质数。
“≡”同余：给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即(a-b)modm=0，那么就称整数a与b对模m同余，记作a≡b(modm)，同时可成立a mod m=b
欧拉函数：φ(n)是小于或等于n的正整数中与n互质的数的数目。（如果n为质数，除了自身都互质，φ(n)=n-1）

2.2 常用定理：

判断互质的方法有很多：

1. 任意两个质数一定构成互质
2. 两个数中的大数是质数的话，两个数一定是质数
3. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系
4. 1和任何一个自然数在一起都是互质数
5. 相邻的两个自然数是互质数
6. 相邻的两个奇数是互质数

欧拉函数扩展：

1. 如果n可以分解成两个互质的整数之积，即n=p×q，则有：φ(n)=φ(pq)=φ(p)φ(q); 其证明过程参考：http://blog.csdn.net/paxhujing/article/details/51353672
2. 根据“大数是质数的两个数一定是互质数”可以知道：一个数如果是质数，则小于它的所有正整数与它都是互质数；所以如果一个数p是质数，则有：φ(p)=p-1

2.3 RSA算法原理：

RSA算法主要是使用欧拉函数的原理，下面着重介绍RSA的原理：

2.3.1. 欧拉定理和模反函数（证明略复杂，有兴趣可以搜了看看）
如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：

欧拉定理
模反函数

2.3.2. 举个例子：

假设甲要发送一串秘密数字m=65给乙；
乙发送了一个公钥(n,e)=(3233,17)给甲；

甲根据以下公式及公钥对密文m加密成c； image.png 甲将使用公钥加密的密文c=2790发给乙方；
乙收到c=2790的密文后，使用私钥(n,d)=(3233,2753)根据以下公式进行解密； image.png

乙方计算得出m=65；

从例子中可以看出，乙方的密钥自己保存着，公钥传给甲方。那么问题来了：例子中的m，n，e，d怎么算出来的？？？

2.3.3. 计算密钥

1.随机选择两个不相等的质数p和q（乙选择了61和53）
2.计算p和q的乘积n=p×q=61×53=3233
3.根据本文“欧拉函数”介绍过的公式
φ(n)=(p-1)(q-1)
代入计算n的欧拉函数值
φ(3233)=(61-1)×(53-1)=60×52=3120
4.随机选择一个整数e，条件是1<e<φ(n)，且e与φ(n)互质
乙就在1到3120之间，随机选择了17
5.因为e与φ(n)互质，根据求模反元素的公式计算e，对于e的模反元素d有：
ed≡1(modφ(n))
这个式子等价于(ed-1)/φ(n)=k（k为任意正整数）即ed-kφ(n)=1，代入数据得：17d-3120k=1
实质上就是对以上这个二元一次方程求解
得到一组解为：(d,k)=(2753,15)
6.将n和e封装成公钥，n和d封装成私钥
n=3233，e=17，d=2753
所以公钥就是(3233,17)，私钥就是(3233,2753)

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

2.3.4. 安全性：
公钥中包含n=3233，因式分解为61x53。如果要计算密钥的流程，不就可以根据公钥得出私钥。
事实上，RSA的安全性就是源自你没办法轻易的对大整数“因式分解”。

3.后续

我们上面说的如果有个中间人在第一次甲方乙方联系时就获取了公钥，然后冒充两方，这样就极度危险了。对称密钥存在的问题是可以截取密钥；非对称密钥也存在一开始就被截取密钥的情况；就是“鸡生蛋，蛋生鸡”的问题。
为了解决这个问题，证书这个概念诞生了，就像现实社会中的公证处；但是证书在传递过程中也会被全部修改，因此又诞生了概念：数字签名。
实现的方法如下：

1.乙方将自己的信息通过hash算法生成一个消息摘要；
2.然后这个消息摘要通过公证处的私钥加密，生成数字签名；
3.然后乙方将自己的信息和数字证书发给甲方；
4.甲方把乙方的信息hash生成摘要，然后把数字签名用公证处的公钥解密，两个进行比对；

当然公证处也会被伪造，但是这样就无止境了，我们选择相信公证处，而且公证处也有证书证明自己的证书。

此外还有个问题，据实验证明来看，非对称的密钥算法比对称密钥算法要慢上百倍；因此可以把对称密钥和非对称密钥结合使用；用非对称算法传递对称算法的密钥，之后直接用对称密钥传输消息。https的流程大致如下：

image.png