包含以下内容:

  • Miller-Rabin 算法
  • 欧拉函数
  • RSA 算法

Miller-Rabin

算法描述:给定输入 $x$,输出一个 bool 类型的变量,表示 $x$ 是/不是素数。算法的时间复杂度为 $O(k \log^3n)$.

原理

费马小定理

如果 $p$ 是素数,该式对于任意的 $a$ 都成立;

如果 $p$ 是合数,那么该式可能成立,也可能不成立。

值得注意的是,如果该式成立,那么 $p$ 大概率是素数,除了某些特殊的情况,比如卡迈尔数(3 个以上互不相同的质数的乘积)。

二次探测

定义 $\mod p$ 意义下,$1$ 的平方根是任意满足 $x^2 \mod p = 1$ 的 $x$。

即 $(x-1)(x+1) \mod p = 0$.

如果 $p$ 是素数,那么 $1$ 的平方根只能是 $1$ 和 $p-1$.

如果在模 $p$ 意义下 $1$ 有不是 $1$, $p-1$ 的平方根,那么 $p$ 就不是素数。

实现

在 $a^{n-1} \equiv 1 \ (\mod n)$ 中,将指数 $n-1$ 分解为 $n-1 = u \times 2^t$,在每轮测试中,先对 $a$ 计算 $a^u \mod n$,之后对这个值执行最多 $t$ 次平方操作。若发现非平凡平方根时即可判断出其不是素数,否则本轮测试通过。

image-20220525143853115内循环实际上每一步在迭代后判断:

  • 如果 $y = 1$,那么不能通过平方根检验
  • 如果 $y = -1$,那么 $n$ 是强伪素数,可以通过两个检验

欧拉函数

定义欧拉函数 $\phi(n)$:$n$ 是正整数,$\phi(n)$ 是比 $n$ 小且与 $n$ 互素的正整数个数。其具有以下性质:

  • $\phi(1) = 0$
  • $\phi(p) = p - 1$,若 $p$ 是素数
  • 当 $(m, n) = 1$ 时, $\phi(mn) = \phi(m) \phi(n)$
  • $\phi(p^e) = p^e - p ^{e-1}$,如果 $p$ 是素数

如果 $n = p_1^{e_1}p_2^{e_2}\cdots p_c^{e_c}$,那么可以分解出 $\phi(n)$ 的值。

只有当 $n$ 可以分解为素数时才可以求出大复合数 $φ(n)$,即求 $φ(n)$ 的困难性依赖于 $n$ 的因数分解的困难性。

欧拉定理是说,如果整数 $m$ 和整数 $n$ 互素,那么 $m^{\phi(n) + 1} \equiv m \mod n$,或者说 $m^{\phi(n)} = 1 \mod n$.

Remark. 给定两个互异的素数 $p, q$ 和两个整数 $n, m$,其中 $n = pq$,$0 < m < n$。那么对于任意的整数 $k$,以下关系均成立:

RSA 算法

RSA 算法的运作流程

首先产生密钥。取两个大质数 $p, q$,计算 $n = pq$ 与欧拉函数 $\phi(n)= (p-1)(q-1)$。任意取一个与 $\phi(n)$ 互素的小整数 $e$,即寻找 $e$,使得 $(e, \phi(n)) = 1$,这里 $1 < e < \phi(n)$。然后寻找 $d$,$d < \phi(n)$,使得 $de \equiv 1 \mod \phi(n)$。然后将 $\{e, n\}$ 作为公钥公开,将 $\{d, n\}$ 作为私钥留存。

加密过程。将待加密的内容分成 $k$ 比特的分组,然后记为 $M$,$k \le \log_2n$。进而加密过程为:$C = M^e \mod n$。

解密过程。$M= C^d \mod n$。

RSA 算法的证明

证明如下。

安全性分析

  • 分解 $n$

密码分析者攻击 RSA 体制的关键点在于如何分解 $n$。若分解成功使得 $n = pq$,则可以算出 $\phi(n) = (p-1)(q-1)$,然后由公开的 $e$ 便可以解出秘密的 $d$。如果想要使 RSA 安全,那么 $p$ 和 $q$ 必须是足够大的素数,使得分析者不能在多项式时间内将 $n$ 分解出来。

  • 攻击 $e$:小加密指数问题

[中国剩余定理]

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组(其中 $n_1, n_2, \cdots, n_k$ 两两互质):

其算法的基本流程如下:

  1. 计算所有模数的积 $n$;
  2. 对于第 $i$ 个方程:
    1. 计算 $m_i = \frac {n} {n_i}$ ;
    2. 计算 $m_i$ 在模 $n_i$ 意义下的逆元 $m_i^{-1}$;
    3. 计算 $c_i = m_im_i^{-1}$(不要对 $n_i$ 取模)。
  3. 方程组的唯一解为:$x=\sum_{i=1}^{k} a_{i} c_{i}(\bmod n)$。
  • 同模攻击

​ 不同的人若使用相同的模数,那么利用自己的 $n = de$ 的关系,便可以分解他人的私钥。

​ 如果 $B$ 与 $C$ 的模数相同,$y_1 = x^{b_1} \bmod n, y_2 = x^{b_2} \bmod n$。若可求得 $c_1, c_2$ 满足 $c_1b_1 + c_2b_2 =1 $,那么可恢复 $x = y_1^{c_1}y_2^{c_2} \bmod n$.