区块链中的数学 – RSA算法加解密过程及原理

区块链技术 11 4 月 22, 2024 0 区块链315

本节主要介绍了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\ ???\ ? $也是成立的，证毕。