本节主要介绍了RSA算法加解密过程及原理，RSA还有很多相关内容，包括签名，具体运算过程，背景知识，安全性等。后续几篇将分别介绍，以求知识系统的完备性。
写在前面
上一节介绍了数论中的费马小定理，这一节继续讲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
