一、非对称加密

1. 非对称加密是什么？

非对称加密（asymmetric cryptography），也称为公开密钥加密、双密码加密，含有一对密钥（公钥和私钥），使用一个密钥加密，另一个密钥解密。公钥对外开放，私钥则需严格秘密。

非对称加密具有如下特性：

（1）加密具有双向性：也就是公钥和私钥中的任一个均可用作加密，任一个也可用作解密；

（2）无法通过公钥推导出私钥：非对称加密基于数学问题求解的困难性来确保安全性。公钥对外开放，就需要保证不能或者无法在有限的时间内通过公钥推导出私钥。

2. 为什么会产生非对称加密？

非对称加密之前，采用的是对称加密。

对称加密使用相同的密钥。不同用户间需要使用不同的密钥。这些密钥需要在网络上进行传输，存在安全性的问题。

同时，对称加密无法实现通信身份的鉴别，也就是不可抵赖性，无法进行数字签名。

1976年，“密码学的新方向”一文中提出了非对称加密的思想。

3. 非对称加密如何实现？

要实现非对称加密，需要设计一种称为：单向陷门函数。

“单向”，也就是不可逆性：对于一个函数y=f(x)，已知x，计算出y很容易；但是已知y要计算出x则很困难，也就是只能一个方向计算；

“陷门”，也就是“后门”：如果存在一个z，能够很容易计算出x=f ^(-1) (y)，而不知道z的情况下，则无法计算出x=f ^(-1) (y)。

4. 非对称加密适用于哪些场景？

（1）加密

公钥对外开放，发送消息前，使用公钥加密并形成密文；接收端收到消息，使用私钥解密并得到明文。具体场景，如使用HTTPS进行通信。

（2）数字签名

现实生活中，每个人都有自己的笔迹。网络通信时，也需要这种“笔迹”，用私钥表示。

数字签名的实现方式：先对明文进行哈希运算，再通过私钥加密哈希值并形成密文，最后将明文和密文一起发送。

5. 与对称加密的关系是怎样的？

（1）对称加密的加密效率高，适合于对大量数据进行加密；非对称加密加密效率低，但保密性较好。

（2）使用方法：安全通信协议中，往往通过协商得到对称加密密钥（随机数字），使用非对称加密传递密钥，然后通过密钥对信息进行加密，进行后续的传输。

二、RSA的原理

1. RSA是什么？

数学家Ron Rivest、Adi Shamir 和 Leonard Adleman提出了一种非对称加密算法，而使用这三人名字进行命名。

RSA的数学基础为：

多个质数相乘得到一个数n很容易，然而将这个数n分解成多个质数则很困难的。

如果两个正整数e和n互质，那么一定可以找到整数d，使得ed-1被n整除，也就是ed和1对n同余。

为了更清晰地理解RSA，需要了解一些数学概念：

（1）互质

质数是什么？

在正整数中，除了1和它本身外，没有其他公约数的数。如1、2、3、5、7、11、13.....

互质是什么？

只有1是公约数的两个整数。如2、3、5、7中任意两个互质。

（2）欧拉函数是什么？

问题：在小于n的正整数中，与n互质的数的个数有多少个？

解决此问题的函数，称为欧拉函数，记为φ(n)函数，读作'toʊʃənt。

有如下推论：

（1）n为质数时：φ(n)=n-1；

（2）n为质数p、q的乘积，即n=p*q，φ(p*q)=φ(p)*φ(q)=(p-1)*(q-1) ；

 （3）n为质数，幂次方为φ(n^k)=n^k-n^(k-1)

（4）同余式是什么？

求余数，也称取余或取模，对应mod。

如果 a mod m = r，b mod m = r，那么就说a、b同余，记作a≡b%m 或者a≡b(mod m)。

进一步，a = k1*m + r，b= k2*m + r，则a-b = (k1-k2)*m，推导a-b = k*m 。

模逆元是什么？

如果ed ≡ 1(mod n)，则ed与1同余；又设定e为3，n为11，求解d的值。

那么，d就是e取模n的模逆元。推导：3*d ≡ 1(mod 11) ，3*d - 1 = k * 11。

（4）欧拉定理是什么？

对于任何互质的两个整数，a和n，有a^φ(n) ≡ 1(mod n)。 

2. RSA公私钥是如何生成的？

（1）随机找两个质数p、q；

（2）计算n：φ(n)=φ(p*q)=φ(p)*φ(q)=(p-1)*(q-1)；

（3）随机选择e，条件是：1< e < m，且e与m互质；

（4）计算d，使得ed≡1 ( mod φ(n))，也就是求e对φ(N)的模逆元d；

（5）取（n，e）为公钥，取（n，d）为私钥；

前面提到公钥是对外开放的，那么大家都会知道n，e的值。

进一步思考：我们能否通过n，e推导出d？

这个问题，我们可以沿着（4）--（3）--（2）的路径推导，问题转换为将n分解成p和q。

而大数分解质数是较难做到的事情。

3. RSA加密过程是怎样的？

（1）将明文转换为ascii值或unicode值--m，m是一个正整数，且m < n ；

（2）如果m的值大于n，则需进行分段，对每段进行加密；

（2）计算：m^e ≡ c (mod n)，得到密文c。

4. RSA解密过程是怎样的？

计算：c^d ≡ m (mod n)，得到明文m。