密码算法篇·RSA
前置知识
互质：两个正整数只有一个公因数1时，则称其为互质。
欧拉函数$\varphi(N)$:小于或等于$N$的正整数中与$N$互质的数的个数
若$p$为素数，则$\varphi(p)=p-1$ (因为每一个小于$p$的数都与$p$互质。)
由此我们有在RSA中，$\varphi(N)=(p-1)(q-1)$
乘法逆元：
在加法中，我们有$a+(-a)=0$,我们称其互为相反数。
在乘法中，我们有$a\cdot(1/a)=1$,我们称其互为倒数，但是其实我们可以用一个统一的称呼：逆元，即某种运算下的逆元素，我们会发现，元素和其逆元素进行运算之后总是一个定值
实际上在代数中，他们构成了一个群(不用深究),而我们进行要了解则是在模意义下的乘法逆元在模$p$意义下，指的是后续的所有运算都是在模$p$的条件下满足，例如$3\cdot4\neq1$但$(3\cdot4) mod\ 11=(1) mod\ 11$,对于这种式子我们称其为同余式，并且有专门的同余符号进行表示
所以参考上面乘法中的逆元运算规则，在模意义下则有我们称$a$和$a^{-1}$互为在模$p$意义下的乘法逆元。例如上述中的 3 与 4 互为在模 11 下的乘法逆元。
欧拉定理：
$且k\mid \phi(n),其中k是a在模n下的阶$
$a^{\phi(p)}\equiv 1\pmod p$
$a^{p-1}\equiv 1\pmod p$
两边都乘a
得到$a^p\equiv a\pmod p$
即费马小定理$(对于任意素数p和整数a\in \mathbb{Z_p},都有a^p\equiv a\pmod p)$
生成公私钥
选取两个不同的大素数$p$和$q$ ,计算$N=p\cdot q$ 。
求欧拉函数值$\varphi(N)=\varphi(p)\varphi(q)=(p-1)(q-1)$。
选择一个小于$\varphi(N)$的整数$e$ ,并且满足$e$和$\varphi ( N) \textbf{互 质 , 求 得 }e$在模$\varphi(N)$意义下的乘法逆元$d$ ,有$ed\equiv1$ (mod $\varphi ( N) )$
销毁$p$和$q$ 。
此时有$(N,e)$为公钥，$(N,d)$为私钥。
加密
首先需要将消息，以一个双方约定好的格式转化为一个小于$N$的整数$m$。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：
此时得到的$c$便是我们的密文。
解密
加密时我们只用到了公钥$(N,e)$,同理解密时我们也只需用到私钥$(N,d)$。有
此时得到的$m$便是我们的明文消息。
正确性证明
转换为证明
$m\equiv c^d
\equiv(m^e)^d
\equiv m^{ed} \pmod N)$
又有 $ed\equiv1 \pmod {\varphi(N)}$,即$ed=1+k\varphi(N)$。
若$gcd(m,N)=1$,则$m^{ed}\equiv m^{ed- 1}\cdot m\equiv m^{k\varphi ( N) }\cdot m\equiv m\pmod N$。
原式得证。
若$gcd(m,N)\neq1$,则$m$为$p$或$q$的整数倍，设$m=hp$,有
其中
可得$m^{k(p-1)(q-1)}=1+xq$ ($x$是一个随机正整数)
原式得证。
Python实现
生成两个大素数P，Q。
这是一个很模糊的概念，我希望各位在学习中能够做到尽量严谨，很显然，这里定义的
大素数到底多大才是大呢？10算大吗？100算吗？10000算吗？葛立恒数算吗？
我们需要一个更加精确的说法，我们生成两个512位的素数（这里包括之后的内容中涉及到的
位都是指二进制位而不是十进制），那么如何使用Python产生一个素数呢，如果不借助任何外力的情况，我们可以从1开始选择，2，3，4…直到某个数满足512位且为素数为止，但是既然我们都使用Python了，为何还要这样做呢？让我们来使用Python强大的开源库
pycryptodome，一般来说你只需要使用pip3 install pycryptodome
# 或
python3 -m pip install pycryptodome便可以成功安装，然后在Python环境中执行以下代码
import Crypto
如果没有显示
ModuleNotFoundError：等诸如此类的错误话，那么恭喜你成功的安装了本库。这里你可能会奇怪为什么安装使用pycryptodome，而引入时使用Crypto，这涉及到这的库和其他库的一些联系，有兴趣的可以自行去查找。然后我们就可以生成素数了，我们引入库中的子包
Crypto.Util.number，这个子包中包含了大量的数学工具，之后我们会经常用到这个子包。from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
print(p)
print(q)执行上面的代码，你便可以得到两个512位的素数，这依赖于我们调用了包中的
getPrime函数，它能够返回一个n位的素数，其中n是我们的传入参数。至此我们便完成了RSA的第一步。$n=p⋅q, φ(n)=(p−1)(q−1)$
后续的过程便简单了很多，我们只需要在之前的基础上完成运算即可，添加下列代码并执行
n = p*q
phi = (p-1)*(q-1)$选取与φ(n)互素的e，计算满足ed≡1(mod\ φ(n))$
这里我们要完成两个数学操作，一个是互素的判断，一个是求解e的乘法逆元。
e = 65537
assert GCD(e, phi) == 1, "该e不满足互素条件"
d = inverse(e, phi)这里
GCD函数能够求解最大公因数（Greatest Common Divisor），之前我们学习了互素的概念就是两个数的最大公因数为1，所以这里我们用断言表达式认定e一定是和phi互素的。为什么我们要选择65537作为e呢，实际上这并不是硬性规定，一些标准提供了一些e的参考值，65537在各类实现与标准中被广泛使用，但是这并不影响你可以将值改变为其他值进行后续的操作。
求d的过程中，我们使用了inverse函数，该函数有两个参数(a,p)，作用便是求解a在模p意义下的乘法逆元，那么这里我们便是求解e在模phi下面的乘法逆元，结果为d。之前我们提到了逆元是互为逆元，所以你可以尝试下面的代码print(inverse(d, phi) == e)打印的结果将为
True，从这里我们也可以看出在RSA中的关键点便是获取这个phi的值，因为得到的phi我们便可以求e或d的值，而这正是我们加解密的密钥参数。$(n,e)$即为公钥，$(n,d)$即为私钥，此时我们便得到了一组RSA的公私钥，随后我们便可以开始用这组密钥来进行加解密操作。
加密：
假设我们要加密的消息为
Hello，我们定义一个字符串进行存储message = b'hello'
注意这里我们定义的是一个
bytes类型字符串，它将每个字符用8位二进制进行存储，是字符串最原生的存储形式。你也可以直接定义'hello'，但在Python3中它是一个Unicode的字符串，需要进行编码操作才能转换为bytes类型进行后续的运算。但我们在RSA中是数与数的运算，该如何将字符串参与操作呢？
我们使用包中的
bytes_to_long函数，从函数名也可以猜出来，这个函数是将字符串转换为数字，运行下列代码m = bytes_to_long(message)
print(m)此时，我们的消息已经被转换为一个字符串了。随后我们便可以对消息进行RSA加密
c = pow(m, e, n)
print(c)我们使用Python自带的
pow函数进行幂运算，注意不要写成m**e % n，二者代表的意义相同，但是pow函数内置快速幂，可以快速得出结果，而m**e % n会将$m^e$的结果先计算出来再取模，$m^e$是一个非常大的数，这会消耗你计算机大量的运算和存储资源。至此，我们便完成了加密过程，得到了RSA的密文C。
解密：
我们执行
msg = pow(c, d, n)
print(msg)此时我们便完成了RSA的解密操作，随后你可以比较一下
msg和m的值，他们会是一样的。
完整代码：
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
n = p*q
phi = (p-1)*(q-1)
e = 65537
assert GCD(e, phi) == 1, "该e不满足互素条件"
d = inverse(e, phi)
print(f'公钥：({e}, {n})')
print(f'私钥：({d}, {n})')
message = b'hello'
m = bytes_to_long(message)
print('消息：', m)
c = pow(m, e, n)
print('密文：', c)
msg = pow(c, d, n)
print('明文：', msg)
assert msg == m, "解密失败"
微信- 支付宝
