公钥密码

发送方只需要加密，接收方只需要脱密。如果加密脱密有两个不同密钥，那么双方只需要有各自需要的密钥就行了。

基本思想

单向函数

1. 对于 $F(x)$ 定义域中的任何 $x$，可容易地求出函数值 $y = F(x)$。

2. 对于值域中的绝大多数 $y$，很难求出相应的 $x$ 使 $y = F(x)$。

单向陷门函数

1. 对于 $F$ 的定义域中任何 $x$，可容易地求出 $y = F(x)$。

2. 如果不知道函数 $F$ 的可变参数，则对于值域中的绝大多数 $y$，很难求出对应的 $x$ 使 $y = F(x)$。

3. 若知道函数 $F$ 的可变参数，可以容易地求出 $x$ 使 $y = F(x)$ 成立。

其中可变参数就是陷门信息。

RSA公钥密码

1. 用户选取两个不同的大素数 $p,q$ 算出 $N = p q, \lambda(N) = lcm(p - 1, q - 1)$。

2. 选择加密密钥 $e: 0 < e < \lambda(N)$，使 $gcd(e, \lambda(N)) = 1$，由 $e d = 1 \mod \lambda(N)$ 求出 $e$ 的逆元 $d: 0 < d < \lambda(N)$，将 $d$ 作为脱密密钥。

公开参数 $N, e$，保密参数 $p, q, d, \lambda(N)$，明文与密文空间 $Z/(N)$

加密

$$c = m^e \mod N$$

脱密

$$m = c^d \mod N$$

为什么可以这样脱密？

由于 $N = p q$ 为两个不同素数之积，故由 $e d \mod \lambda(N) = 1$ 可知，对所有 $m \in Z / (N)$，都有：

$$c^d \mod N = m^{e d} \mod N = m^{e d mod \lambda(N)} \mod N = m^1 \mod N = m$$

性能分析

大合数真的非常大，一般 2048 bit 或以上；

模指数运算可用平方乘算法实现，设 $e = e_{m} e_{m-1} ... e_{0}$ 其中 1 的个数为 $k$，则完成 $x^e \mod n$ 需要执行 $m$ 次模 $n$ 平方运算和 $k$ 次模乘运算。

快速脱密

孙子定理

$$\left\{ \begin{matrix} x \mod p = x_1 \\ x \mod q = x_2 \end{matrix} \right.$$

在 $Z(n)$ 中有唯一解：

$$x = (q q^{-1} x_1 + p p^{-1} x_2) \mod n$$

其中 $n = p q$，且

$$p^{-1} \in Z / (q) 使 p p^{-1} \mod q = 1 \\ q^{-1} \in Z / (p) 使 q q^{-1} \mod p = 1$$

即 $x \longmapsto (x \mod p, x \mod q)$ 是 $Z(n)$ 至 $Z(p) \times Z/(q)$ 的双射。

大数模运算

类似于没有 AVX 时的 workaround.

一般采用蒙哥马利算法。

大素数生成算法

一般是先生成随机大数，再检验素性。

素性检验

有确定性算法和概率算法（常用 Rabin、 Miller算法）。

例如，Rabin素性检测法：

欧拉定理已知，若 $n$ 为素数

$$\forall a \in Z^*_n \qquad a^{n-1} \equiv 1 \mod n$$

反之若 $a^{n-1} \neq 1 mod n$，就一定是合数。

若 $a^{n-1} \equiv 1 \mod n$，可能为素数也可能为合数。

---

设 $n$ 为奇，则 $n - 1 = 2^e u$，$u$ 为奇，

由 $a^{n-1} \equiv 1 \mod n$

可得 $(a^u - 1) \prod_{t=0}^{e-1} (a^{2^t u} + 1) = 0 \mod n$

若 $n$ 为素数，则下列式子必有一个成立

$$\begin{matrix} a^u - 1 = 0 \mod n \\ a^{2^t u} + 1 = 0 \mod n \\ (t = 0,1,2,...,e-1) \end{matrix}$$

于是引入素性集

$$P_n = \{ n: \forall a \in Z^*_n, a^u \neq 1 \mod n, \forall t < e, a^{2^t u} \neq -1 \mod n \}$$

若选取的某个奇数 $n$ 在该集合中，必为合数，否则可能为素数也可能为合数。

误判概率 $\le \frac{1}{4}$，多判几次，素数概率就非常高。