本节主要介绍了RSA算法加解密过程及原理，RSA还有很多相关内容，包括签名，具体运算过程，背景知识，安全性等。后续几篇将分别介绍，以求知识系统的完备性。

## 写在前面

上一节介绍了[数论中的费马小定理](https://learnblockchain.cn/article/1558)，这一节继续讲RSA算法。RSA算法依赖的数论知识点较多，除了上篇说的费马小定理，还包括欧拉定理(欧拉函数)等。关于RSA知识点打算分三个章节讲解。采取知其然再深究所以然的方法来说明。

## 预备知识

RSA算法是1977年由Ron Rivest、Adi Shamir 和 Leonard Adleman三人共同提出。原始论文A Method for Obtaining Digital Signatures and Public-Key Cryptosystems，感兴趣可以搜索查阅。下面先说下RSA算法预备知识

1. 费马小定理

上一节说过，可自行查看

2. 欧拉定理

这里简要说明一下，后续专门章节详细说明。

若n,a为正整数，且n,a互质，则

$a^{\varphi (n)} \equiv 1\ mod\ n$

上式中$\varphi(n)$代表欧拉函数：是1到n−1中(也就是[1,n−1])且与n互质的整数的个数.

RSA算法中涉及到的欧拉函数性质如下：

(1) 若n是素数，$\varphi(n) = n-1$;

(2) 若m,n互质, $\varphi(m*n)=\varphi(m)\varphi(n)$;

(3) 若m,n互质且都是素数,$\varphi(m*n) =\varphi(m)\varphi(n) = (m-1)*(n-1)$

更多性质以及证明后面专门介绍，以上列出的是本节需要用到的知识点。

## 密钥生成过程

用户按照以下步骤生成公私钥：

1. 秘密选取两个大的素数𝑝和𝑞。

2. 计算𝑝和𝑞的乘积：𝑛 = 𝑝 × 𝑞。

3. 随机选取一个与𝜙(𝑛)=(𝑝−1)×(𝑞−1)[注：欧拉函数性质(3)]互质的数𝑒，应用中通常选取𝑒=65537【注：这是有原因的】。

4. 计算𝑒模𝜙(𝑛)的模反元素𝑑，也即是计算满足：

𝑒⋅𝑑 = 1(𝑚𝑜𝑑𝜙(𝑛)) = 𝑒⋅𝑑 =1(𝑚𝑜𝑑(𝑝−1)⋅(𝑞−1))。【求[模逆元可参考历史文章](https://learnblockchain.cn/article/1556)】

5. 将(𝑒,𝑛)作为公开的公钥；𝑑作为私钥，秘密保存。

可见，在RSA加密算法中，公钥以一个正整数对的形式出现，同理私钥也是如此。这与前面说过的椭圆曲线加密算法有所不同。椭圆曲线加密算法中公钥是一个点坐标。

## 加密解密过程

总体来说，加解密过程操作比较简单.

假设A与B通信：

1. 加密过程

(1) A首先将明文分解成若干块，每个块可以表示为一个整数(基于n的大小分块)，以𝑀表示，使得1⩽𝑀⩽𝑛−1。为方便起见，只考虑对一个明文数据块进行加密的流程。

(2)A用B的公钥(n,e)进行如下运算得到密文

$C=M^e\ mod\ n$

2. 解密过程

B收到密文C后，做如下运算：

$M =c^d\ mod\ n$ 得到原始消息M。

## 解密验证

我们反推一下为什么这样解密就能得到原始消息M呢？

解密运算：

$C^d\ mod n =M^{ed}\ mod\ n$

由于 𝑒⋅𝑑 = 1(𝑚𝑜𝑑𝜙(𝑛)) 可得：

e*d = k𝜙(𝑛) +1

代入上式得：$C^d\ mod\ n =M^{k\varphi(n)+1}\ mod\ n$

由于M也是一个整数，所以有以下两种情况：

1. M与n互质

2. M与n不互质

下面分情况证明$M^{k\varphi(n)+1}\ mod\ n = M$ 。

1. M与n互质

这种情况下，由欧拉定理得：

$M^{\varphi(n)}\equiv 1(𝑚𝑜𝑑\ 𝑛)$

所以：

$M^{k\varphi(n)+1}\equiv(M^{\varphi(n)})^k*M \equiv M (mod\ n)$。得证。

1. M与n不互质

由于𝑛的素因子分解只能是𝑛=𝑝×𝑞 *[见上述密钥生成过程]*，所以M，n最大公因子𝑔𝑐𝑑(𝑀,𝑛)或者是𝑝或者是𝑞，

也即是𝑀 = ℎ𝑝或者𝑀 = ℎ𝑞。

假设𝑀 = ℎ𝑞，此时𝑀必然与𝑝互质[由p.q互质可得]。

由费马小定理可到下式：

$M^{k\varphi(n)+1}\equiv(M^{p-1)})^{k_{(q-1)}}\cdot M \equiv M (mod\ p)$

代入𝑀 = ℎ𝑞， 得：

$(hq)^{k\varphi(n)+1} = jp + hq$

式子左边是q的倍数，右边也必然是q的倍数，即jp也是q的倍数。由于p,q互质所以j是q的倍数，可表示为 j=kq

所以上式变为：

$(hq)^{k\varphi(n)+1} = jp + hq = kqp + hq = kn + hq$

两边对n 取模得到 :

mod n = M mod n 。得证

同理，𝑀=ℎ𝑝时可以得到相同的结论。大家可自行推导。

综合1和2两种情况,可以得出结论：

$M^{k\varphi(n)+1}≡ 𝑀(𝑚𝑜𝑑\ 𝑛)$总是成立的，所以$𝑀= C^d\ 𝑚𝑜𝑑\ 𝑛 $也是成立的，证毕。

## 小结

本节主要介绍了RSA算法加解密过程及原理，RSA还有很多相关内容，包括签名，具体运算过程，背景知识，安全性等。后续几篇将分别介绍，以求知识系统的完备性。

好了，下一节讲背景知识中的[欧拉定理和欧拉函数](https://learnblockchain.cn/article/1559)。

欢迎关注公众号：blocksight

写在前面

上一节介绍了数论中的费马小定理，这一节继续讲RSA算法。RSA算法依赖的数论知识点较多，除了上篇说的费马小定理，还包括欧拉定理(欧拉函数)等。关于RSA知识点打算分三个章节讲解。采取知其然再深究所以然的方法来说明。

预备知识

RSA算法是1977年由Ron Rivest、Adi Shamir 和 Leonard Adleman三人共同提出。原始论文A Method for Obtaining Digital Signatures and Public-Key Cryptosystems，感兴趣可以搜索查阅。下面先说下RSA算法预备知识

费马小定理

上一节说过，可自行查看

欧拉定理

这里简要说明一下，后续专门章节详细说明。

若n,a为正整数，且n,a互质，则

$a^{\varphi (n)} \equiv 1\ mod\ n$

上式中$\varphi(n)$代表欧拉函数：是1到n−1中(也就是[1,n−1])且与n互质的整数的个数.

RSA算法中涉及到的欧拉函数性质如下：

(1) 若n是素数，$\varphi(n) = n-1$;

(2) 若m,n互质, $\varphi(mn)=\varphi(m)\varphi(n)$;

(3) 若m,n互质且都是素数,$\varphi(mn) =\varphi(m)\varphi(n) = (m-1)*(n-1)$

更多性质以及证明后面专门介绍，以上列出的是本节需要用到的知识点。

密钥生成过程

用户按照以下步骤生成公私钥：

秘密选取两个大的素数𝑝和𝑞。

计算𝑝和𝑞的乘积：𝑛 = 𝑝 × 𝑞。

随机选取一个与𝜙(𝑛)=(𝑝−1)×(𝑞−1)[注：欧拉函数性质(3)]互质的数𝑒，应用中通常选取𝑒=65537【注：这是有原因的】。

计算𝑒模𝜙(𝑛)的模反元素𝑑，也即是计算满足：

𝑒⋅𝑑 = 1(𝑚𝑜𝑑𝜙(𝑛)) = 𝑒⋅𝑑 =1(𝑚𝑜𝑑(𝑝−1)⋅(𝑞−1))。【求模逆元可参考历史文章】

将(𝑒,𝑛)作为公开的公钥；𝑑作为私钥，秘密保存。

可见，在RSA加密算法中，公钥以一个正整数对的形式出现，同理私钥也是如此。这与前面说过的椭圆曲线加密算法有所不同。椭圆曲线加密算法中公钥是一个点坐标。

加密解密过程

总体来说，加解密过程操作比较简单.

假设A与B通信：

加密过程

(1) A首先将明文分解成若干块，每个块可以表示为一个整数(基于n的大小分块)，以𝑀表示，使得1⩽𝑀⩽𝑛−1。为方便起见，只考虑对一个明文数据块进行加密的流程。

(2)A用B的公钥(n,e)进行如下运算得到密文

$C=M^e\ mod\ n$

解密过程

B收到密文C后，做如下运算：

$M =c^d\ mod\ n$ 得到原始消息M。

解密验证

我们反推一下为什么这样解密就能得到原始消息M呢？

解密运算：

$C^d\ mod n =M^{ed}\ mod\ n$

由于 𝑒⋅𝑑 = 1(𝑚𝑜𝑑𝜙(𝑛)) 可得：

e*d = k𝜙(𝑛) +1

代入上式得：$C^d\ mod\ n =M^{k\varphi(n)+1}\ mod\ n$

由于M也是一个整数，所以有以下两种情况：

M与n互质

M与n不互质

下面分情况证明$M^{k\varphi(n)+1}\ mod\ n = M$ 。

M与n互质

这种情况下，由欧拉定理得：

$M^{\varphi(n)}\equiv 1(𝑚𝑜𝑑\ 𝑛)$

所以：

$M^{k\varphi(n)+1}\equiv(M^{\varphi(n)})^k*M \equiv M (mod\ n)$。得证。

M与n不互质

由于𝑛的素因子分解只能是𝑛=𝑝×𝑞 [见上述密钥生成过程]，所以M，n最大公因子𝑔𝑐𝑑(𝑀,𝑛)或者是𝑝或者是𝑞，

也即是𝑀 = ℎ𝑝或者𝑀 = ℎ𝑞。

假设𝑀 = ℎ𝑞，此时𝑀必然与𝑝互质[由p.q互质可得]。

由费马小定理可到下式：

$M^{k\varphi(n)+1}\equiv(M^{p-1)})^{k_{(q-1)}}\cdot M \equiv M (mod\ p)$

代入𝑀 = ℎ𝑞， 得：

$(hq)^{k\varphi(n)+1} = jp + hq$

式子左边是q的倍数，右边也必然是q的倍数，即jp也是q的倍数。由于p,q互质所以j是q的倍数，可表示为 j=kq

所以上式变为：

$(hq)^{k\varphi(n)+1} = jp + hq = kqp + hq = kn + hq$

两边对n 取模得到 :

mod n = M mod n 。得证

同理，𝑀=ℎ𝑝时可以得到相同的结论。大家可自行推导。

综合1和2两种情况,可以得出结论：

$M^{k\varphi(n)+1}≡ 𝑀(𝑚𝑜𝑑\ 𝑛)$总是成立的，所以$𝑀= C^d\ 𝑚𝑜𝑑\ 𝑛 $也是成立的，证毕。

小结

本节主要介绍了RSA算法加解密过程及原理，RSA还有很多相关内容，包括签名，具体运算过程，背景知识，安全性等。后续几篇将分别介绍，以求知识系统的完备性。

好了，下一节讲背景知识中的欧拉定理和欧拉函数。

欢迎关注公众号：blocksight

本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。

发表于 2020-06-09 12:13

阅读 ( 260 )

学分 ( 0 )