Fermat 小定理、Euler φ 函数、Euler 定理、素数稀疏性、RSA 练习、RSA 变体

我们首先将 130 分解为素因数：\(130 = 2 \times 5 \times 13\)。由于 2、5 和 13 都是素数，我们可以应用费马小定理（Fermat's Little Theorem），即 \(a^p \equiv a \pmod{p}\)，得到以下同余式：

\[m^{13} \equiv m \pmod{13}, \tag{1}\] \[m^5 \equiv m \pmod{5}, \tag{2}\] \[m^2 \equiv m \pmod{2}. \tag{3}\]

现在，我们将 (2) 式乘以 \(m^5 \cdot m^3\)，得到

\[m^{13} \equiv m^5 \cdot m^5 \cdot m^3 \equiv m \cdot m \cdot m^3 \equiv m^5 \pmod{5},\]

又由 (2) 式知 \(m^5 \equiv m \pmod{5}\)，所以

\[m^{13} \equiv m \pmod{5}.\]

类似地，我们将 (3) 式乘以 \((m^2)^5 \cdot m\)，得到

\[m^{13} \equiv m^2 \cdot (m^2)^5 \cdot m \equiv m^7 \equiv (m^2)^3 \cdot m \equiv m^4 \pmod{2}.\]

注意到 \(m^4 \equiv m^2 \cdot m^2 \equiv m \cdot m \equiv m^2 \pmod{2}\)，再由 (3) 式 \(m^2 \equiv m \pmod{2}\)，可得

\[m^{13} \equiv m \pmod{2}.\]

因此，

\[m^{13} \equiv m \pmod{13}, \tag{4}\] \[m^{13} \equiv m \pmod{5}, \tag{5}\] \[m^{13} \equiv m \pmod{2}. \tag{6}\]

令 \(x = m^{13} - m\)。由中国剩余定理（Chinese Remainder Theorem），同余方程组

\[x \equiv 0 \pmod{13}\] \[x \equiv 0 \pmod{5}\] \[x \equiv 0 \pmod{2}\]

在模 \(2 \cdot 5 \cdot 13 = 130\) 下有唯一解，且该唯一解为 \(x \equiv 0 \pmod{130}\)。所以，我们有 \(m^{13} - m \equiv 0 \pmod{130}\)，即 \(m^{13} - m\) 能被 130 整除。

(a) 由于 \(p\) 是素数，从 1 到 \(p-1\) 的所有整数都与 \(p\) 互素。

所以，\(\varphi(p) = p - 1\)。

(b) 小于 \(p^k\) 且与 \(p^k\) 不互素的正整数只有 \(p\) 的倍数。

为什么？因为能与 \(p^k\) 共享的素因数只有 \(p\)。因此，任何与 \(p^k\) 不互素的数必定含有素因数 \(p\)，即它是 \(p\) 的倍数。

小于等于 \(p^k\) 的 \(p\) 的倍数有 \(1 \cdot p, 2 \cdot p, \ldots, p^{k-1} \cdot p\)，共有 \(p^{k-1}\) 个。

小于等于 \(p^k\) 的正整数共有 \(p^k\) 个。

所以 \(\varphi(p^k) = p^k - p^{k-1} = p^{k-1} \cdot (p - 1)\)。

(c) 设 \(A\) 为满足 \(1 \leq i \leq a\) 且 \(\gcd(i,a) = 1\) 的正整数集合，设 \(B\) 为满足 \(1 \leq j \leq b\) 且 \(\gcd(j,b) = 1\) 的正整数集合。由于 \(\gcd(a,b) = 1\)，由中国剩余定理，每一对 \((i, j) \in A \times B\) 对应唯一的整数 \(1 \leq k \leq ab\)，其中 \(k \equiv i \pmod{a}\) 且 \(k \equiv j \pmod{b}\)。于是有 \(\gcd(k,a) = \gcd(i,a) = 1\) 且 \(\gcd(k,b) = \gcd(j,b) = 1\)。因此，\(\gcd(k,ab) = 1\)，即中国剩余定理将每个 \((i, j)\) 映射到唯一的与 \(ab\) 互素的 \(1 \leq k \leq ab\)。

此外，每个与 \(ab\) 互素的 \(1 \leq k \leq ab\) 也可以对应到唯一的 \((i, j) \in A \times B\)，使得 \(k \equiv i \pmod{a}\) 且 \(k \equiv j \pmod{b}\)。因此，\(A \times B\) 与小于等于 \(ab\) 且与 \(ab\) 互素的正整数集合之间存在双射。

由于 \(|A| = \varphi(a)\)，\(|B| = \varphi(b)\)，且小于等于 \(ab\) 且与 \(ab\) 互素的正整数集合的基数为 \(\varphi(ab)\)（由定义），我们得出 \(\varphi(a)\varphi(b) = \varphi(ab)\)。

(d) 对 (c) 进行归纳，我们得到

\[\varphi(n) = \varphi(p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k})\] \[= \prod_{i=1}^{k} \varphi(p_i^{e_i})\] \[= \prod_{i=1}^{k} (p_i - 1)p_i^{e_i-1}\] \[= \prod_{i=1}^{k} \frac{p_i - 1}{p_i} p_i^{e_i}\] \[= n \prod_{i=1}^{k} \frac{p_i - 1}{p_i}.\]

(a) 这个问题类似于费马小定理的证明，只不过我们现在处理的是集合 \(\{m_1, m_2, \ldots, m_{\varphi(n)}\}\)。

由于 \(m_i\) 和 \(a\) 都与 \(n\) 互素，所以 \(a \cdot m_i\) 也与 \(n\) 互素。假设 \(a \cdot m_i\) 与 \(n\) 有公共因子，不妨设它是一个素数 \(p\)。那么，要么 \(p|a\)，要么 \(p|m_i\)。无论哪种情况，\(p\) 都是 \(n\) 与 \(a\) 或 \(m_i\) 的公共因子，矛盾。

现在我们证明 \(f\) 是单射。假设 \(f(x) = f(y)\)，即 \(ax \equiv ay \pmod{n}\)。由于 \(a\) 在模 \(n\) 下有乘法逆元，我们看到 \(x \equiv y \pmod{n}\)，因此 \(f\) 是单射。

继续证明 \(f\) 是满射。任取与 \(n\) 互素的 \(y\)。那么，\(f(a^{-1}y) \equiv y \pmod{n}\)，因此存在 \(x\) 使得 \(f(x) = y\)。此外，\(a^{-1}y \pmod{n}\) 与 \(n\) 互素，因为我们乘了两个都与 \(n\) 互素的数。

(b) 由于两个集合具有相同的元素，只是顺序不同，将它们相乘得到

\[m_1 \cdot m_2 \cdot \ldots \cdot m_{\varphi(n)} \equiv am_1 \cdot am_2 \cdot \ldots \cdot am_{\varphi(n)} \pmod{n},\]

提取 \(a\) 项，

\[m_1 \cdot m_2 \cdot \ldots \cdot m_{\varphi(n)} \equiv a^{\varphi(n)} (m_1 \cdot m_2 \cdot \ldots \cdot m_{\varphi(n)}) \pmod{n}.\]

因此我们有 \(a^{\varphi(n)} \equiv 1 \pmod{n}\)。

我们要找到 \(n\) 使得 \(n+1, n+2, n+3, \ldots, n+k\) 都不是素幂。我们可以通过要求 \(n+1\) 到 \(n+k\) 每个数都有两个不同的素因数来保证这一点。因此，选取 \(2k\) 个素数 \(p_1, p_2, \ldots, p_{2k}\)，并强制以下约束：

\[n + 1 \equiv 0 \pmod{p_1 p_2}\] \[n + 2 \equiv 0 \pmod{p_3 p_4}\] \[\ldots\] \[n + i \equiv 0 \pmod{p_{2i-1} p_{2i}}\] \[\ldots\] \[n + k \equiv 0 \pmod{p_{2k-1} p_{2k}}.\]

由中国剩余定理，我们可以计算出 \(n\) 的值，因此这样的 \(n\) 必然存在，从而 \(n+1\) 到 \(n+k\) 都不是素幂。

更有趣的是，我们可以任意选择我们想要的 \(2k\) 个素数！

(a) 私钥 \(d\) 定义为 \(e\) 在模 \((p-1)(q-1)\) 下的逆元。因此我们需要计算 \(9^{-1} \bmod (5-1)(11-1) = 9^{-1} \bmod 40\)。求 \(e\) 在模 \((5-1)(11-1) = 40\) 下的逆元。计算 \(\text{egcd}(40,9)\)：

\[\text{egcd}(40,9) = \text{egcd}(9,4) \quad [4 = 40 \bmod 9 = 40 - 4(9)]\] \[= \text{egcd}(4,1) \quad [1 = 9 \bmod 4 = 9 - 2(4)].\] \[1 = 9 - 2(4).\] \[1 = 9 - 2(40 - 4(9))\] \[= 9 - 2(40) + 8(9) = 9(9) - 2(40).\]

我们得到 \(-2(40) + 9(9) = 1\)。所以 9 的逆元是 9。因此 \(d = 9\)。

(b) 4 是加密后的消息。我们可以用 \(D(m) \equiv m^d \equiv 4^9 \equiv 14 \pmod{55}\) 来解密。\(4^9 \equiv 14 \pmod{55}\)。因此原始消息是 14。

(c) 第二部分的答案是 14。要加密数字 \(x\)，我们必须计算 \(x^e \bmod N\)。

因此，\(14^9 \equiv 14 \cdot (14^2)^4 \equiv 14 \cdot (31^2)^2 \equiv 14 \cdot (26^2) \equiv 14 \cdot 16 \equiv 4 \pmod{55}\)。这验证了第二部分，因为加密后的消息应该是 4。

(a) 选择 \(e\) 使得它与 \(p-1\) 互素，并选择 \(d \equiv e^{-1} \pmod{p-1}\)。

我们要证明 \(x\) 被 \(E(x)\) 和 \(D(y)\) 恢复，即 \(D(E(x)) = x\)。

换句话说，对于所有 \(x \in \{0, 1, \ldots, N-1\}\)，有 \(x^{ed} \equiv x \pmod{p}\)。

证明：由 \(d\) 的构造，我们知道 \(ed \equiv 1 \pmod{p-1}\)。这意味着可以写出 \(ed = k(p-1) + 1\)，其中 \(k\) 为某个整数，且 \(x^{ed} = x^{k(p-1)+1}\)。

• 若 \(x\) 是 \(p\) 的倍数：则 \(x = 0\)，且确实有 \(x^{ed} \equiv 0 \pmod{p}\)。

• 若 \(x\) 不是 \(p\) 的倍数：则

\[x^{ed} \equiv x^{k(p-1)+1} \pmod{p}\] \[\equiv x^{k(p-1)} x \pmod{p}\] \[\equiv 1^k x \pmod{p}\] \[\equiv x \pmod{p},\]

这里使用了费马小定理。

对于两种情况，我们都证明了 \(x\) 被 \(D(E(x))\) 恢复。

(b) 由于 Eve 知道 \(N = p\)，且 \(d \equiv e^{-1} \pmod{p-1}\)，她现在可以使用扩展欧几里得算法（EGCD）计算 \(d\)。

(c) 设 \(e\) 与 \((p-1)(q-1)(r-1)\) 互素。给出公钥：\((N, e)\)，并计算 \(d = e^{-1} \pmod{(p-1)(q-1)(r-1)}\)。想要给我发送秘密消息 \(x\) 的人发送 \(y = x^e \pmod{N}\)。

我们通过计算 \(y^d \pmod{N}\) 来解密传入的消息 \(y\)。

这有效吗？我们证明 \(x^{ed} - x \equiv 0 \pmod{N}\)，因此 \(x^{ed} = x \pmod{N}\)。

为了证明 \(x^{ed} - x \equiv 0 \pmod{N}\)，我们提取 \(x\) 得到

\[x \cdot (x^{ed-1} - 1) = x \cdot (x^{k(p-1)(q-1)(r-1)+1-1} - 1),\]

因为 \(ed \equiv 1 \pmod{(p-1)(q-1)(r-1)}\)。

我们现在证明 \(x \cdot (x^{k(p-1)(q-1)(r-1)} - 1)\) 能被 \(p\)、\(q\) 和 \(r\) 整除。因此，它能被 \(N\) 整除，且 \(x^{ed} - x \equiv 0 \pmod{N}\)。

证明它能被 \(p\) 整除：

• 若 \(x\) 能被 \(p\) 整除，则整个式子能被 \(p\) 整除。

• 若 \(x\) 不能被 \(p\) 整除，则可以在内部使用费马小定理证明 \((x^{p-1})^{k(q-1)(r-1)} - 1 \equiv 1 - 1 \equiv 0 \pmod{p}\)。因此它能被 \(p\) 整除。

证明它能被 \(q\) 整除：

• 若 \(x\) 能被 \(q\) 整除，则整个式子能被 \(q\) 整除。

• 若 \(x\) 不能被 \(q\) 整除，则可以在内部使用费马小定理证明 \((x^{q-1})^{k(p-1)(r-1)} - 1 \equiv 1 - 1 \equiv 0 \pmod{q}\)。因此它能被 \(q\) 整除。

证明它能被 \(r\) 整除：

• 若 \(x\) 能被 \(r\) 整除，则整个式子能被 \(r\) 整除。

• 若 \(x\) 不能被 \(r\) 整除，则可以在内部使用费马小定理证明 \((x^{r-1})^{k(p-1)(q-1)} - 1 \equiv 1 - 1 \equiv 0 \pmod{r}\)。因此它能被 \(r\) 整除。