从零到壹学习密码学第十三讲：RSA加密解密

作者：黎跃春

孔壹学院创始人兼CEO

黎跃春：孔壹学院创始人兼CEO，国内区块链布道先行者，通信和信息技术培养工程区块链高级授课专家。如果您有任何关于区块链的问题，可以加入区块链技术交流QQ群729666975，我们会为您一一解答。

从零到壹学习密码学为一个系列，一共20讲，包括初识密码学、Hash 函数、对称加密算法、数字签名、椭圆曲线加解密、公钥基础设施( PKI )、零知识证明、随机数等，为大家详尽的介绍密码学的学习过程。今天我们将为大家介绍第十三讲：RSA加密解密。话不多说，马上开启我们的密码学学习之旅。

资料获取，添加莉莉微信kongyixueyuan。

孔壹学院

什么是RSA

RSA是一种公钥密码算法，它的名字是由它的三位开发者，即Ron Rivest、Adi Shamir 和 Leonard Adleman的姓氏的首字母组成的( Rivest-Shamir-Adleman )。

RSA可以被用于公钥密码和数字签名。

RSA加密

在RSA中，明文、密钥和密文都是数字。RSA的加密过程可以用下列公式来表达：

密文=明文Emod N(RSA加密)

RSA的密文是对代表明文的数字的E次方求mod N的结果。换句话说，就是将明文和自己做E次乘法,然后将其结果除以N求余数，这个余数就是密文。

加密公式中出现的两个数和 ，到底都是什么数呢? RSA的加密是求明文的次方mod ，因此只要知道E和N这两个数，任何人都可以完成加密的运算。所以说， 和 是RSA加密的密钥，也就是说， 和 的组合就是公钥。

RSA解密

RSA的解密和加密一样简单，可以用下面的公式来表达:

明文=密文Dmod N( RSA解密)

表示密文的数字的D次方求 mod N就可以得到明文。

这里所使用的数字N和加密时使用的数字N是相同的。数 和数 组合起来就是RSA的解密密钥，因此D和N的组合就是私钥。

在RSA中，加密和解密的形式是相同的。加密是求“明文的E次方的 modN"，而解密则是求“密文的D次方的 mod N"。

生成密钥对

在RSA中，加密是求“明文的E次方的 modN"，而解密则是求“密文的D次方的 mod N"。

由于E和N是公钥，D和N是私钥，因此求E、D和N这三个数就是生成密钥对。RSA密钥对的生成步骤如下：

求N

求L( L是仅在生成密钥对的过程中使用的数)

求E

求D

求N

首先准备两个很大的质数。这两个很大的质数为p和q。p和q太小的话，密码会变得容易破译，但太大的话计算时间又会变得很长。

判断一个数是不是质数并不是看它能不能分解质因数，而是通过数学上的判断方法来完成。

准备好两个很大的质数之后，我们将这两个数相乘，其结果就是数N。也就是说，数 N 可以用下列公式来表达：

求L

这个数在RSA的加密和解密过程中都不出现，它只出现在生成密钥对的过程中。

是 和 的最小公倍数( least common multiple, lcm )。

如果用lcm(X, Y) 来表示 “X和Y的最小公倍数”，则L可以写成下列形式。

求E

E是一个比1大、比L小的数。此外，E和L的最大公约数( greatest common divisor, gcd)必须为1。

如果用gcd(X, Y)来表示X和Y的最大公约数，则E和L之间存在下列关系。

求D

数D是由数E计算得到的。D、E和L之间必须具备下列关系。

举个密钥对生成的例子

求N

首先我们准备两个质数p、q,这里我们选择17和19,它们都是质数。

求L

L是p-1和q- 1的最小公倍数。

求E

E和L的最大公约数必须是1。

满足条件的E有很多，例如下面这些数都可以。

这些数好像都是质数，但其实并不是这样的，比如25就不是质数。这些数称为和 L “互质的数”，也就是相对于L是质数的意思。我们选择5来作为E。

E=5, N=323 就是公钥。

求D

D必须满足下列条件:

D = 29可以满足上面的条件，因为:

我们已经成功生成了密钥对，即:

公钥:私钥:

公钥(E,N)=(5,323)是可以任意公开的，但是私钥(D,N)= (29,323)必须妥善保管。

加密

要加密的明文必须是小于N的数，也就是小于323的数，我们假设要加密的明文是123，加密时使用的是公钥 。

明文Emod N = 1235mod 323 = 255

因此密文就是 255。

解密

我们对密文225进行解密。解密时使用的是私钥D=29、N=323。

密文29mod N = 22529mod 323 = 123

中间人攻击( man-in-the-middle attack )

中间人攻击虽然不能破译RSA,但却是一种针对机密性的有效攻击。所谓中间人攻击，就是主动攻击者Mallory混入发送者和接收者的中间，对发送者伪装成接收者，对接收者伪装成发送者的攻击方式，在这里，Mallory就是“中间人”。

这种攻击不仅针对RSA,而是可以针对任何公钥密码。在这个过程中，公钥密码并没有被破译，所有的密码算法也都正常工作并确保了机密性。然而，所谓的机密性并非在Alice和Bob之间，而是在Alice和Mallory之间，以及Mallory和Bob之间成立的。仅靠公钥密码本身,是无法防御中间人攻击的。

要防御中间人攻击，还需要一种手段来确认所收到的公钥是否真的属于Bob,这种手段称为认证。在这种情况下，我们可以使用公钥的证书。