RSA Algorithem

欧拉函数

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？） from 阮一峰

\[\varphi(n) = \begin{cases} 1&(n = 1) \\ n-1&(n是质数) \\ p^k - p^{k-1}&(n是某个质数的次方，p为质数 prime 的简写) \\ \varphi(p1)\varphi(p2)&(n为两个互质整数之积) \end{cases}\]

其中在 阮一峰 的第三种 case 有错误：

$\varphi(p^k) = p^k - p^{(k-1)}$

当一个数不包含质数 p，才能与 n 互质。而包含质数 p 的数一共有 $p^{k-1}$ 个，分别是

$1$, $1 \times p$, $2 \times p$, $(p^{k-1} - 1) \times p$

最后那个 $(p^{k-1} \times p)$ 是 $p^k$ 本身，不应该包含，而第一个 $1$ 需要包含进去。所以，一共有 $(p^{k-1}-1) + 1 = p^{k-1}$ 个。

分解质因数 和 $\varphi(n)$ 的计算

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

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

其中每一项又可写成如下形式：

\[\begin{align*} \because \varphi(p^k) &= p^k - p^{k-1} \\ &= p^k( 1 - \frac{1}{p}) \end{align*}\]

代入公式可得：

\[\begin{align*} \therefore \varphi(n) &= p_1^{k_1} p_2^{k_2} ... p_r^{k_r} (1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_r}) \\ &= n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_r}) \end{align*}\]

Example:

$\varphi(1323) = \varphi(3^3 \times 7 ^ 2) = 1323(1 - \frac{1}{3})(1 - \frac{1}{7}) = 756$

欧拉函数速查表

image

模反元素

\[当 a 与 n 互质时，b 一定存在，使得 ab - 1 被 n 整除。 \\ ab \equiv 1 (mod\ n) \\ \because a^{\varphi(n)} \equiv 1 (mod\ n) \\ \because a \times a^{\varphi(n) - 1} = a \times b \equiv 1 (mod\ n) \\ \therefore b = a^{\varphi(n) - 1}\]

由于模反元素不止一个，所以集合 $b$ 有： $ {b} = b + kn, k \in \mathbb{Z}$

RAS 过程

变量名列表，举个例子

变量 含义 例子
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)$ $(61 - 1) \times (53 - 1) = 60 \times 52 = 3120$
e $ 1 < e < \varphi(n) $ 的质数 17
d $ed \equiv 1(mod \ \varphi(n)) \to {d} = e^{\varphi(\varphi(n)) - 1} + kn, k \in \mathbb{Z} $ $17^{\varphi(3120) - 1} mod\ 3120 = 17^{(768-1)} mod\ 3120 = 2753$
  • 欧拉函数计算器 eulertotientfunction calculators
  • d 的计算，由于正常的计算机无法计算出 $17^{767}$，所以，只能用循环处理掉。 
    // a ^ b mod c
function expMod(a, b, c) {
let res = 1;
for (let i = 1; i <= b; i++ ) {
  res = (res * a) % c;
}
return res;
}
expMod(17, 767, 3120)
> 2753

质因数分解困难吗？

  • 首先分解质因数不难，给定整数，用试除法一个个试就行
  • 但是大整数的分解比较困难，这里的困难是指：没有高效的方式来分解，除了一个个试。
    • 那一个个试有多难？有了素数表是否就不难了？
    • 有素数表，也只能用试除法，增长是线性的。
    • 小于 n 的素数个数约为 $ \frac{x}{lnx}$

  • 大的素数表可行吗？
    • 基本不可行，如果简单的按 ASCII 码存储
      • 一个 1000 位的整数（目前 RAS 通常使用 2048 位），约占 1KB
      • 存 1000 个 1000 位的整数就需要 1MB
      • 1e6 个 1000 位的整数就需要 1GB
      • 1e9 个 1000 位的整数就需要 1TB
      • 。。。
      • 而我们需要存的是 1e1000 个 1000 位的整数，这个存储是个天文数字
  • 参考
    • https://www.reddit.com/r/math/comments/2jo786/why_is_the_prime_factorization_of_very_large/
    • https://www.quora.com/Why-is-factoring-numbers-into-primes-a-difficult-problem

References