RSA

e: 加密公钥
d: 解密密钥
N/n: 大数
p,q: 两个素数
m: 明文
c: 密文

数学前提

欧拉函数 $ϕ (n)$ : 小于 $n$ ，且与 $n$ 互素的数的个数
欧拉定理：若 $g c d (x, n) = 1$ ，则 $X^{ϕ (n)} \equiv 1 \mod n$
费马小定理：若 p 为素数，则 $X^{p - 1} \equiv 1 \mod p$
欧拉函数的乘法性质：若 $gcd (x, y) = 1$ ， $ϕ (x y) = ϕ (x) ϕ (y)$

密钥生成流程

选取两个大素数 p 和 q
计算出 n = p * q
随机选取加密密钥 e(公钥)，使得 gcd(e,(p-1)(q-1))=1
计算出 e 在 (p-1)(q-1) 下的乘法逆元 d，作为解密密钥 (私钥)
公开 (e,n) 作为公钥

加解密

加密 $c = m^{e} m o d N$
解密 $m = c^{d} m o d N$

RSA 签名

加密邮件的步骤（信件 L 由 A 发给 B）
1. 信件 L 用 B 的公钥加密
2. 把内容发给 B
3. B 用私钥解密信件
验证邮件的步骤（信件 L 由 A 发给 B）
1. L 做 MD5 摘要，M=MD5(L)
2. 用 A 的私钥进行加密 M'=RSA(M,A 的私钥)
3. 把 L、M' 和 A 的公钥发送给 B
4. B 用 A 的私钥解密 m=RSA(M',A 的公钥)
5. 判断 MD5(L) 是否等于 m

RSA 正确性证明

已知 $c = m^{e} m o d N$ , $e d \equiv 1 \mod (p - 1) (q - 1)$ , p、q 互素， $N = p * q$
证明 $m = c^{d} m o d N$

Step1 公式化简

\begin{aligned} c^{d} m o d N \\ = & (m^{e})^{d} m o d N \\ = & m^{e d} m o d N \\ = & m^{k (p - 1) (q - 1) + 1} m o d N \\ = & m * (m^{(p - 1) (q - 1)})^{k} m o d N \end{aligned}

Step2 分类讨论证明

（1）若 $gcd (m, N) = 1$ ，则 $m^{ϕ (N)} \equiv 1 \mod N$

\begin{aligned} ∵ g c b (p, q) = 1, ϕ (p) = p - 1, ϕ (q) = q - 1 \\ ∴ ϕ (p q) = ϕ (p) ϕ (q) = (p - 1) (q - 1) \\ ∴ m^{(p - 1) (q - 1)} = m^{ϕ (p q)} = m^{ϕ (N)} \equiv 1 \mod N \\ ∴ m * (m^{(p - 1) (q - 1)})^{k} \equiv m \mod N \end{aligned}

（2）若 $gcd (m, N) \neq 1$

\begin{aligned} ∵ m < N, gcd (m, N) \neq 1 \\ 假 设 g c d (m, M) = p (m = c p), 则 m \equiv 1 \mod q \\ ∴ m^{k (p - 1) (q - 1)} \equiv (m^{q - 1})^{k (p - 1)} \equiv 1 \mod q \\ 令 m^{k (p - 1) (q - 1)} = s q + 1 \\ ∴ m * m^{k (p - 1) (q - 1)} = m * (s * q + 1) = c * s * p * q + m = c * s * N + m \equiv m \mod N \end{aligned}

QED