RSA
Generation
- 取两个大质数 $p$ 和 $q$ ，为了安全性 $p$ 和 $q$ 长度应 大于 $2048$ 位；
- 设 $n = pq$；
- 设 $m = \phi(n) = (p-1)(q-1)$；
- 取 $e$，使得 $2 < e < m$且 $gcd(e, m) = 1$；
- 取 $d$，使得 $d \times e \equiv 1 \ (mod\ m)$；
- 此时，公钥为 $(n, e)$，私钥为 $(n, d)$。
Encryption
约定 $x$ 为 plaintext， $y$ 为 cyphertext。
$$ y = x^e \ mod \ n $$
Decryption
$$ x = y^d\ mod \ n $$
Proof
当 $x$ 与 $n$ 互质时，有
$$ \begin{align*} x &= y^d \ mod \ n \\ x’ &= x^{ed} \ mod \ n \end{align*} $$
设 $k$ 为一自然数，则由同余的定义，有
$$ \begin{align*} x’ &= x^{km + 1} \ mod \ n \\ &= x \times (x^{\phi(n)})^k \ mod \ n \end{align*} $$
由欧拉定理，得
$$ x’ = x \ mod \ n = x $$
当 $x$ 与 $n$ 不互质时，不妨设 $x$ 为 $p$ 的倍数，记为 $x = ap$，其中 $a$ 是一正整数。
$$ \begin{align*} x^{\phi(q)} &\equiv 1 \ (mod \ q) \\ x^{k\phi(p)\phi(q)} &\equiv 1 \ (mod \ q) \\ x^{k\phi(p)\phi(q)} &= 1 + bq \end{align*} $$
则
$$ \begin{align*} x’ &= x^{km+1} \ mod \ n \\ &= x \times (1 + bq) \ mod \ n \\ &= (x + bqx) \ mod \ n \\ &= x \ mod\ n = x \end{align*} $$
Security
若想通过公钥推知私钥，则必须对密钥 $n$ 进行分解质因数，由于这是一个数论难题，因此只需要将 $n$ 设置的足够大，则可以确保安全性。
RSA-CRT
由于接收者同时知道 $q$ 和 $p$ ，故由中国剩余定理(CRT)，将 $mod \ n$的操作拆分，可实现加速。
Decryption
$$ \begin{align*} m_1 &= y^d \ mod \ q \\ m_2 &= y^d \ mod \ p \end{align*} $$
通过预处理出 $(d \ mod \ q)$ 和 $(d \ mod \ p)$，将上式转化为
$$ \begin{align*} m_1 &= y^{d \ mod \ q} \ mod \ q \\ m_2 &= y^{d \ mod \ p} \ mod \ p \end{align*} $$
根据CRT即可在不对 $n$ 进行模运算的情况下求出原文，此处的结论是
$$ x = m_2 + q \times (p^{-1} \times (m_1 - m_2) \ mod \ q) $$
注意后面的 $mod \ q$ 括号内的操作均视为在Galois域 $GF(q)$ 内进行的操作。
参考文献
[1] “RSA —— 经典的非对称加密算法,” 知乎专栏. https://zhuanlan.zhihu.com/p/450180396