RSA加密是一种非对称加密，原理是：
- 使⽤算法可以⽣成两把钥匙 A 和 B
- 使⽤ A 加密的信息，使⽤ B 可以解开
- 使⽤ B 加密的信息，使⽤ A 可以解开
⽇常使⽤中，我们把⼀把作为公钥公开发布。⼀把作为私钥，⾃⼰保留。这样，任何⼈都可以使⽤我们的公钥加密信息发给我们，我们则可以使⽤⾃⼰的私钥解开。
只要把私钥保存好，这个通信系统就⾮常安全。
数学基础
1. 欧拉函数
欧拉函数的输入是一个正整数，输出小于这个正整数的、跟它互质的整数数量。
定义是：
\[\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m}) \]\(p_1, p_2, \cdots, p_m\) 表示 \(n\) 的 $ m $ 个质因子，重复的算一个。
比如5，它是个质数，只有它自己一个因子，所以\(\phi(5) = 5 \times (1 - \frac{1}{5}) = 4\)。
当然你也能猜出来，因为跟一个质数互质的数就是从1到它的前驱数的全部自然数，所以对于任意质数 \(p\) 都有
对于合数呢？比如 \(6 = 2 \times 3\)，所以 \(\phi(6) = 6 \times \frac{1}{2} \times \frac{2}{3} = 2\) ，也就是6有2个互质数，我们数一下就是1和5。
再看一个比如12，\(12 = 2^2 \times 3\)，所以 \(\phi(12) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4\)。我们数一下12的互质数有1、5、7、11四个。
规定\(\phi(1)=1\)
欧拉函数的证明比较简单，可以自行AI。
2. 欧拉定理
当正整数 \(a\) 和 \(n\) 互质时，有
\[a^{\phi(n)}\equiv 1 (\textbf{mod } n ) \]换句话说，\(a^{\phi(n)} - 1\) 可以被 \(n\) 整除。
例如，7和10互质。\(7^{\phi(10)} = 7^4 = 2401\)，减去1时10的倍数；
反过来，\(10^{\phi(7)} = 10^6 = 100,0000\)，减去1是999999，\(999999 \div 7 = 142857\) （就是1/7 的循环节）。
3. 模反元素
从上面计算的过程可以看出来，如果正整数 \(a\) 和 \(n\) 互质时，一定能找出一个正整数 \(b\)，使得
\[ab \equiv 1 (\textbf{mod } n) \]\(b\) 就叫 \(a\) 的模反元素。
模反元素肯定存在。最起码，由于 \(a^{\phi(n)} = a a^{\phi(n) - 1} \equiv 1 (\textbf{mod } n)\) 所以 $ b = a^{\phi(n) - 1}$。
实际上，\(b\) 加减 \(n\) 的倍数都是 \(a\) 的模反元素。
比如上面看到了，10对7的模反元素可以是10万，因为100万减1是7的倍数。那么用10万减去7的14285倍也就是99995得到5，5乘以10得到50，再减1也是7的倍数。
密钥生成
上面就是全部的数学基础。通过这些可以来生成密钥了。
1. 随机选择两个大质数p和q并计算他们的积n
为了演示，这里选择p = 7和q = 11，有 n = 77。
实际应用中，要求n的位数在600位以上才能保证安全。
因为要求n的二进制位大于2048，折成十进制就是617位以上
2. 计算n的欧拉函数 \(\phi(n)\)
虽然n很大，但是由于p和q是质数，所以就简单了
\[\phi(n) = (p -1)(q-1) \]在我们例子里就是6*10 = 60。
后面为了写起来方便，用字母 \(z\) 表示欧拉函数的结果：\(z = \phi(n)\)。
3. 选择一个数e跟 \(\phi(n)\) 互质并计算e的模反元素d
要找一个数跟 \(z\) 互质，e可以比 \(\phi(n)\) 更大。不过 \(\phi(n)\) 已经很大了，所以一般最大也就使用65537。
使用公开的数不会降低系统安全性
这里需要跟60互质，我们选择e = 13。
简单应用上面的方法，可以得到 \(d = e^{\phi({60})-1}\)。
这个60比较小，\(60=2^2 \times 3 \times 5\)， 所以\(\phi(60) = 16\)， \(d = 13 ^ {15}\) 虽然大但是也能算出来。
但是在实际中，\(z\) 通常大得很，就算能求出它的欧拉函数值，模反元素也算不出来。
扩展欧几里得算法
换一种思路。既然 \(ed \equiv 1 (\textbf{mod } z)\)，也就是 \(ed-kz=1\)，k是某个整数。
而扩展欧几里得算法不仅可以求出两个整数a和b的最大公约数d，还可以找到整数x和y，使得
算法实现很简单：
fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
if b == 0 {
(a, 1, 0)
} else {
let (gcd, x1, y1) = extended_gcd(b, a % b);
let x = y1;
let y = x1 - (a / b) * y1;
(gcd, x, y)
}
}
代入13和60，得到d=-23。给它加60的倍数使它变成正数，所以d=37。
这样，公钥就是[n, e]=[77,13]，私钥就是[n,d]=[77,37]。
私钥的安全性
已知公钥能算出私钥吗？
- 因为 \(ed \equiv 1 (\textbf{mod } z)\)，而e已知，所以想算出d需要知道z
- \(z = \phi(n) = (p -1)(q-1)\)，需要拿到p和q
- \(n = p \times q\)，n已知，分解质因数可得p和q
所以这套逻辑的保证就是第三步很难。而一旦成功分解了，私钥就很容易算了。
加密和解密
加密过程
被加密的消息 m 需要是⼀个⼩于 n 的整数（我们可以将任意字节流直接解读为⼀个⽆符号整数）。如果消息太⼤，解读为整数以后⽐ n 要⼤，那么就分段加密。
实际应用中，我们不会直接⽤ RSA 来加密消息，⽽是⽤ RSA 来加密⼀个对称秘钥，再⽤这个秘钥加密消息。
加密的过程就是计算下面这个c的过程：
\[m^{e} \equiv c (\textbf{ mod } n) \]假设我们要加密的消息是50，使用上面的计算
\[50^{13} \equiv c (\textbf{ mod } 77) \]可得c=29，这就是加密后的消息。
计算c的算法可以参考
fn main() {
let base = 50; // 原始消息，不能大于77
let exponent = 13;
let modulus = 77;
let result = modular_exponentiation(base, exponent, modulus);
println!("{}", result); // 加密结果
}
fn modular_exponentiation(base: i64, exponent: i64, modulus: i64) -> i64 {
let mut result = 1;
let mut base = base % modulus;
let mut exponent = exponent;
while exponent > 0 {
if exponent % 2 == 1 {
result = (result * base) % modulus;
}
exponent >>= 1;
base = (base * base) % modulus;
}
result
}
解密过程
解密过程是一样的，依据是
\[c^{d} \equiv m (\textbf{ mod } n) \] let base = 29;
let exponent = 37;
let modulus = 77;
let result = modular_exponentiation(base, exponent, modulus);
println!("{}", result);
输出结果是50，就是我们原来的消息。
解密依据的证明
为什么当 \(m^{e} \equiv c (\textbf{ mod } n)\) 时会有 \(c^{d} \equiv m (\textbf{ mod } n)\) 呢？
\[\because m^{e} \equiv c (\textbf{ mod } n) \\ \therefore c= m^e-kn \]
代入目标式：
\[({m^e-kn})^d\equiv m (\textbf{ mod } n) \]根据二项式定理，左边展开后除了第一项是$ m^{ed}$ 其余项都含有 \(kn\)，必然是n的倍数，所以舍弃这些项。只要证明
\[m^{ed} \equiv m (\textbf{ mod } n) \]即可。
根据定义，
代入可得
\[m^{1+hz} = m^{h \phi(n) + 1} \equiv m (\textbf{ mod } n) \]- 当m和n互质时
得证。
2. 当m和n不互质
不互质时m只能时p或q的倍数。
以 \(m = kp\) 为例，k必然小于q，因为m<n。因为q是质数，所以k与q互质。同时m也跟q互质，否则m就大于n了。
又根据二项式定理
\[(kp)^{(q-1)h(p-1)} \equiv 1(\textbf{ mod } q) \\ \therefore (kp)^{(q-1)h(p-1)} kp \equiv kp (\textbf{ mod } q) \\ (kp)^{ed} \equiv kp (\textbf{ mod } q) \\ \therefore (kp)^{ed} = kp + tq \]要使等式成立，每一项都需要是p的倍数，所以tq是p的倍数。因为q不是p的倍数，所以t是p的倍数 t = vp：
\[(kp)^{ed} = kp + vpq \\ m^{ed} = m + vn \\ \therefore m^{ed} \equiv m (\textbf{ mod } n) \]得证。
标签：实践,phi,RSA,textbf,kp,let,原理,mod,equiv From： https://www.cnblogs.com/somefuture/p/18674659