包括模运算、欧拉公式、欧拉定理、模返元素、RSA 证明。

模运算

模运算即为求余，用 $mod$ 来表示，编程中用 $\%$ 来表示。

比如：

  • $9\ mod\ 7 = 2$
  • $23\ mod\ 7 = 2$

也可记为同余，用符号 $\equiv$ 表示：

  • $9 \equiv 2\ (mod\ 7)$
  • $23 \equiv 2\ (mod\ 7)$
  • $23 \equiv 9\ (mod\ 7)$

从上可以得出一个较为简单的规律（同余算法的传递性）：

$a \equiv b\ (mod\ p) 且 b \equiv c\ (mod\ p) \to a \equiv c\ (mod\ p)$

模运算规则（加法）

证明： $(a_1 + a_2)\ mod\ b = (a_1\ mod\ b + a_2\ mod\ b)\ mod\ b$

这个好像没啥好证明的，举个列子：

$(13 + 10) mod \ 7 = ( 13\ mod\ 7 + 10\ mod\ 7)\ mod\ 7 = (6 + 3)\ mod \ 7 = 2$

模运算规则（乘法）

证明： $(a_1 \times a_2)\ mod\ b = (a_1\ mod\ b \times a_2\ mod\ b) mod\ b$

设 $a_1 = k_1 b + c_1; a_2 = k_2 b + c_2, 其中\ {k_1, k_2} \in \mathbb{Z}$

代入公式可得，并通过加法规则可知：

\[\begin{align*} \to (a_1 \times a_2)\ mod\ b &= ((k_1b + c_1) \times (k_2b + c_2))\ mod\ b \\ &= (k_1b \times k_2b + k_1b \times c_2 + c_1 \times k_2b + c_1 \times c_2 )\ mod\ b \\ &= ((k_1b \times k_2b)\ mod\ b + (k_1b \times c_2)\ mod\ b + (c_1 \times k_2b)\ mod\ b + (c_1 \times c_2 )\ mod\ b)\ mod\ b \end{align*} \\\]

其中如果是 $b$ 的倍数，则 $mod\ b$ 结果为0，包括

\[\begin{align*} \because (k_1b \times k_2b )\ mod\ b &= 0 \\ (k_1b \times c_2)\ mod\ b &= 0 \\ (c_1 \times k_2b)\ mod\ b &= 0 \end{align*}\]

所以，我们能得到如下公式：

\[\begin{align*} \to (a_1 \times a_2)\ mod\ b &= (c_1 \times c_2)\ mod\ b, (其中c_1 = a_1\ mod\ b; c_2 = a_2\ mod \ b ) \\ &= ((a_1 \ mod \ b) \times (a_2 \ mod\ b)) mod\ b \end{align*}\]

这个可用于后续计算 $(a^b)mod\ p$ 的实现：

// a ^ b mod p
function expMod(a, b, p) {
  let res = 1;
  let a1 = a % p;
  for (let i = 1; i <= b; i++ ) {
    res = (res * a1) % p;
  }
  return res;
}

欧拉函数

在数论中，对正整数 $n$，欧拉函数 $ \varphi (n)$ 是小于等于n的正整数中与n互质的数的数目。

例如$\varphi (8)=4$，因为 $1,3,5,7$ 均和8互质。

所以，欧拉函数有以下表达式，参考：rsa_algorithm_part_one

\[\varphi(n) = \begin{cases} 1&(n = 1) \\ n-1&(n是质数) \\ \varphi(n_1)\varphi(n_2)\cdots\varphi(n_i)&(n_1,n_2\cdots,n_i互质) \end{cases}\]

第一种和第二种 case，是第三种 case 的特殊形式。

$\varphi(n)$ 的计算

有了以上的相关前提条件之后，根据 算术基本定理 就能得到一般公式。

算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。

\[\begin{align*} n &= p_1^{k_1}p_2^{k_2}p_3^{k_3}...p_n^{k_r} \\ \to \varphi(n) &= n(1 - \frac{1}{p_1})\cdots(1 - \frac{1}{p_n}) \end{align*}\]

例如:

  • $20=2^{2}\times 5$
  • $\varphi(n) = 20 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{5}) = 8$

简单理解上述公式

  • $20 \times (1 - \frac{1}{2})$ 可理解为在前 20 个数中，有 $\frac{1}{2}$ 不是 2 的倍数，即和 20 是互质，有 $1, 3, 5, 7, 9, 11, 13, 15, 17, 19$

  • $20 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{5}) = 10 \times (1 - \frac{1}{5}) $ 可理解为在刚刚的 10 个数字中，每 5 个数中，必然有一个 5 的倍数，去掉这些数字（5，15），就是和 20 互质的个数，即为上一步的 $\frac{4}{5}$ 个数，最终为 $8$，分别是 $1, 3, 7, 9, 11, 13, 17, 19$

欧拉函数的积性

$\varphi(n) = \varphi(p) \varphi(q) $ 其中 $p\ q$ 互质。

从刚刚分解质因数的思路来看，可以类推，例如：

  • $20=2^{2}\times 5$
  • $\varphi(n) = \varphi(4) \varphi(5) = [4 \times (1 - \frac{1}{2})] \times [5 \times (1 - \frac{1}{5})]= [4 \times 5] \times (1 - \frac{1}{2}) \times (1 - \frac{1}{5}) = 8$

和刚刚 $\varphi(20)$ 的形式是一致的，所以关键在于 $p\ q$ 互质，$p\ q$ 互质的情况下，质因数分解就不会出现相同质数，从而可以使得上述等式不变。

由此，也可以在此基础上扩展出一般的积性：

\[\begin{align*} n &= p_1^{k_1}p_2^{k_2}p_3^{k_3} \cdots p_n^{k_r} \\ \to \varphi(n) &= \varphi(p_1^{k_1})\varphi(p_2^{k_2}) \cdots \varphi(p_n^{k_r}) \end{align*}\]

欧拉定理

若 $n,a$ 为正整数，且 $n,a$ 互素（即 $\gcd(a,n)=1$ 最大公约数为 1），则有以下定理：

\[a^{\varphi(n)} \equiv 1 (mod\ n)\]

证明待详写。

模反元素

如果 $n, a$ 互质，根据欧拉定理可知：

\[a^{\varphi(n)} \equiv 1 (mod\ n) \\ \to a \times a^{\varphi(n) - 1} \equiv 1 (mod\ n)\]

其中 $b = a^{\varphi(n) - 1} + kn, k \in \mathbb{Z}$, 称为 模反元素, 是一个集合。

RSA

变量名列表，举个例子

变量 含义 例子
p 一个质数,来自 prime 的简写 61
q 一个质数 53
n 为 pq 相乘 $ = p \times q $ $3233 = 61 \times 53$
$\varphi(n)$ 根据欧拉定理,由于 pq 都为质数, 所以 $\varphi(n) = \varphi(pq) = \varphi(p) \varphi(q) = (p-1)(q-1)$ $\varphi(3233) = (61 - 1) \times (53 - 1) = 60 \times 52 = 3120$
e $ 1 < e < \varphi(n) $ 的质数 17
d $ed \equiv 1(mod \ \varphi(n))$ $17^{\varphi(3120) - 1} mod\ 3120 = 17^{(768-1)} mod\ 3120 = 2753$
$k_1,k_2,\cdots k_n$ 用于 mod 运算的等式转换 $a\equiv b(mod\ c)$ 转 $a=b + kc, k \in \mathbb{Z} $
  • 私钥为 (n, d)
  • 公钥为 (n, e)

加密

m 为需要加密的 message， c 为加密后的文本 encrypt

\[m^e \equiv c (mod\ n)\]

解密

c 为需要解密的内容，m 为解密后的 message

\[　c^d \equiv m (mod\ n)\]

加解密证明

由加密公式可得：

\[\begin{align*} m^e &\equiv c (mod\ n) \\ m^e + k_1n &= c;\ k_1 \in \mathbb{Z} \\ \to c &= m^e + k_1n \end{align*}\]

从解密公式得知，并将 $c$ 代入公式：

\[\begin{align*} 　c^d &\equiv m (mod\ n) \\ c^d + k_2n &= m;\ k_2 \in \mathbb{Z} \\ \to (m^e + k_1n) ^ d + k_2n &= m\ (将 c 代入可得) \\ \to [(m^e + k_1n) ^ d + k_2n]\ mod\ n &= m\ mod\ n \ (两边都对 n 取余) \\ \to m^{ed}\ mod\ n &= m\ mod\ n \ ( 当为 n 的倍数时，取余为 0) \\ m^{ed} &\equiv m (mod\ n) \end{align*}\]

为了证明左右等式成立，仅需证明 $m^{ed} \equiv m (mod\ n)$，即有以下表达式：

\[\begin{align*} \\ \because ed &\equiv 1(mod φ(n)) \\ \therefore ed &= k_3 \varphi(n) + 1; k_3 \in \mathbb{Z} \\ \to m^{ed}\ mod\ n &= m ^ {k_3 \varphi(n) + 1} \ mod\ n \\ &= ((m^{\varphi(n)})^{k_3} \times m) \ mod\ n \\ &= ((m^{\varphi(n)})^{k_3} \ mod\ n \times m) \ mod\ n \\ &= \{[(m^{\varphi(n)}\ mod\ n)^{k_3})\ mod\ n] \times m\ \}\ mod \ n \end{align*}\]

m 与 n 互质

\[\begin{align*} \\ \because m^{\varphi(n)} &\equiv 1 (mod\ n) \\ \therefore m^{ed}\ mod\ n &= \{[(m^{\varphi(n)}\ mod\ n)^{k_3})\ mod\ n] \times m\ \}\ mod \ n \\ &= \{[(1)\ mod\ n]^{k_3} \times m\ \}\ mod \ n \\ &= (1 \times m)\ mod \ n \\ &= m\ mod\ n \end{align*}\]

m 与 n 不互质

m 与 n 不互质的情况，因为 $n=p \times q$，且 $m < n$, 所以 $m = k_4 \times p$ 或 $m = k_5 \times q;\ k_4, k_5 \in \mathbb{Z}$（m 必然是 $pq$ 其中一个质数的倍数），假设: $m = k_4 \times p$

自己使用正向证明的方式，证明不出来，参考 rsa_algorithm_part_two 反向证明。

\[\begin{align*} \because m &= k_4p \\ \because m^{\varphi(q)} &\equiv 1\ (mod \ q)\ (欧拉定理，pq 互质) \\ \to (k_4p)^{q - 1} &\equiv 1\ (mod \ q)\ (pq 为质数) \\ \to (k_4p)^{(q - 1)k_5(p - 1)} &\equiv 1\ (mod \ q) \\ \to (k_4p)^{(q - 1)k_5(p - 1)} \times k_4p &\equiv k_4p\ (mod \ q) \\ \to (k_4p)^{(q - 1)k_5(p - 1) + 1} &\equiv k_4p\ (mod \ q) \end{align*}\]

将上述等式改写为以下等式

\[\begin{align*} \because ed &\equiv 1\ (mod\ n) \\ n &= (p - 1)(q - 1) \\ \therefore ed &= k(p - 1)(q - 1) + 1, k \in \mathbb{Z} \\ \therefore (k_4p)^{(q - 1)k_5(p - 1) + 1} &= k_4p + k_6q \\ \to k_4p^{ed} &= k_4p + k_6q \\ k_4p \times k_4p^{ed - 1} &= k_4p (1 + \frac{k_6q}{k_4p}) \\ \because (1 + \frac{k_6q}{k_4p}) &= k_4p^{ed - 1} \\ \therefore \frac{k_6q}{k_4p} &\in \mathbb{Z}, 必然是一个整数，可被整除 \\ \therefore 设 \ k_6 &= k_7p, \ \{k_6, k_7\} \in \mathbb{Z} \\ \end{align*}\]

所以，可以将以上式子改写成如下形式：

\[\begin{align*} \to k_4p^{ed} &= k_4p + k_6q \\ &= k_4p + k_7pq \\ &= k_4p + k_7n \\ \because k_4p^{ed} &= k_4p + k_7n \\ \therefore m^{ed} &= m + k_7n \\ \therefore m^{ed} &\equiv m\ (mod\ n) \end{align*}\]

即当 $m = k_4p$ 的时候，等式成立。

同理，当 $m=k_5q$ 的时候，等式成立。

参考

  1. 模运算 Wiki
  2. 欧拉函数
  3. rsa_algorithm_part_one
  4. rsa_algorithm_part_two
  5. 相关链接&私钥格式
  6. 欧拉&模反
  7. 模运算 Baidu