关于微信公众号

本来应该是上周五密码学基础系列的文章，因为“熵密杯”，然后上周末又打了 NepCTF。。。不过，随迟但到好吧。今天我们分享数论四大定理相关的东西。

[TOC]

欧拉定理

设 $n,a \in \mathbb{Z}$，如果有 $gcd(a,b)=1$，则有
$$
a^{\varphi(n) } \equiv 1 \pmod n
$$
（其中 $\varphi()$ 是欧拉函数，$\varphi(n)$ 表示模 $n$ 的简化剩余系中元素的个数）

在证明欧拉定理之前，我们需要先证明两个引理。

设模 $n$ 剩余系中的元素为 $x_1,x_2,\cdots,x_{\varphi(n)}$，与 $n$ 互素的非零整数 $a$，我们定义一个集合 $M ={m_1,m_2,\cdots,m_{\varphi(n)}}={a\cdot x 1,a\cdot x_2,\cdots,a\cdot x{\varphi(n)}}$

引理一：集合 $M$ 中的任意两个元素都不模 $n$ 同余。

这里我们用反证法，假设模 $n$ 的简化剩余系中存在两个元素 $m_a,m_b$ 模 $n$ 同余，

即 $m_a \equiv m_b \pmod n$，

等价于 $m_a -m_b = kn$

也即 $a\cdot x_a -a\cdot x_b = a(x_a-x_b) = kn$

于是有 $a(x_a-x_b) \equiv 0 \pmod n$

由于 $gcd(a,n)=1$，且 $a \neq 0$，因此有 $x_a - x_b \equiv 0 \pmod n$

又因为$ x_a,x_b$ 都是小于 $n$ 的且不相等，因此上式不成立，即假设不成立。引理一得证。

引理二： 集合 $M$ 中的元素均与 $n$ 互素。

证明：已知 $m_i = a \cdot x_i$，由于 $gcd(a,n)=1,gcd(x_i,n)=1$，

因此 $gcd(a\cdot x_i ,n) = gcd(m_i,n)=1$

欧拉定理证明： 我们将集合 $M$ 中的元素全部相乘，有
$$
\prod_{i=1}^{\varphi(n)} m_i = \prod_{i=1}^{\varphi(n)} a\cdot x_i = a^{\varphi(n)}\prod_{i=1}^{\varphi(n)}x_i \tag{1}
$$
根据前面两个引理，集合 $M$ 中元素互不模 $n$ 同余，且均与 $n$ 互素；因此对于其中的任意元素 $m_i$ 均能在模 $n$ 的简化剩余系中找到对应的满足 $m_i \equiv x_j \pmod n,j \in{1,2,\cdots,\varphi(n)}$ 的元素，于是有
$$
\prod_{i=1}^{\varphi(n)} m_i \equiv \prod_{i=1}^{\varphi(n)} x_i \pmod n \tag{2}
$$
将（2）式带入 （1）式我们得到 $a^{\varphi(n)} \equiv 1 \pmod n$

第一颗🌰：设 $n=5,a=3$，有 $\varphi(5)=4$

模 $n$ 的简化剩余系为 ${1,2,3,4}$，集合 $M = {3,6,9,12}$，可以将集合 $M$ 中的元素和模 $n$ 简化剩余系中的元素一一匹配：

$6 \equiv 1 \pmod 5,12 \equiv 2 \pmod 5,3 \equiv 3 \pmod 5,9 \equiv 4 \pmod 5$

即 $m_2 \equiv x_1 \pmod n,m_4 \equiv x_2 \pmod n,m_1 \equiv x_3 \pmod n,m_3\equiv x_4 \pmod n$

于是 $\prod_{i=1}^{\varphi(n)} m_i \equiv \prod_{i=1}^{\varphi(n)} x_i \pmod n$

因此 $a^{\varphi(n)}\equiv 1\mod n$

即 $3^4 \equiv 1 \pmod 5$

欧拉定理应用：RSA 解密算法正确性验证

欧拉定理可用于 RSA 解密算法的正确性验证。

已知有 RSA 参数 $n = p\cdot q$，其中 $p,q$ 是两个素数; 公钥 $e$ 和 私钥 $d$ 满足 $e \cdot d \equiv 1 \pmod {\varphi(n)}$。明文 $m(m\neq p,m \neq q)$ 加密为密文 $c$ 的式子是 $c \equiv m^e \pmod n$；密文 $c$ 解密为明文 $m$ 的式子是 $m \equiv c^d \pmod n$。现在我们需要验证解密算法的正确性，即证明
$$
m \equiv c^d \pmod n \tag{1}
$$
由于 $c \equiv m^e \pmod n$，带入（1）式即证明 $m \equiv m^{ed} \pmod n$

根据 $e \cdot d \equiv 1 \pmod {\varphi(n)}$，所以 $ed = 1 + k\varphi(n)$

因此有
$$
m \equiv m^{1+k\varphi(n)} \equiv m \cdot m^{k\varphi(n)} \equiv m \cdot (m^{\varphi(n)})^k \pmod n \tag{2}
$$
由于 $gcd(m,n)=1$ ，根据欧拉定理有 $m^{\varphi(n)} \equiv 1 \pmod n$，带入（2）式得
$$
m \equiv m \cdot (1)^k \equiv m \pmod n \tag{3}
$$
（3）式显然成立，因此 RSA 解密算法正确性得证。

费马小定理

设有素数 $p $，对于模 $p$ 的简化剩余系中的任意元素 $a$ （ $a \in {x|1 \le x \le p-1}$ ）有
$$
a^{\varphi(p) } \equiv 1 \pmod p
$$
是欧拉定理的特殊情况，证明过程也差不多，就不赘述了。

中国剩余定理

设正整数$m_1,m_2…m_k$两两互素，则同余方程组
$$
\begin{align*}
\begin{split}
\left {
\begin{array}{ll}
x \equiv a_1 \pmod{m_1} \
x \equiv a_2 \pmod{m_2} \
\ \ \ \ \ \vdots \
x \equiv a_k \pmod{m_k} \

\end{array}
\right.
\end{split}
\end{align*}
$$
有整数解。并且在模 $M = m_1 \cdot m_2 \cdots m_k$ 下的解是唯一的，解为
$$
x \equiv (a_1M_1M_1^{-1} + a_2M_2M_2^{-1} + \cdots + a_kM_kM_k^{-1}) \mod M
$$
注意其中$M_i = M / m_i$，$M_i^{-1}$ 为 $M_i$ 在模 $m_i$ 下的逆元。

有一说一中国剩余定理算是一个工具，我其实也不太能够证明出这个式子，只能说想出这个式子的人真厉害。这里我们就来探讨一下这个式子的正确性。

首先我们需要推一个很重要的引理，

引理 3： 根据算数基本定理任意整数 $n$ 都可以唯一表示为多个素数的乘积，设 $n$ 有素因子 $p$，如果有同余式 $a \equiv b \pmod n$ 成立，则同余式 $a \equiv b \pmod p$ 也成立。

证明：

由 $a \equiv b \pmod n \to a = b + k_1n,k_1 \in \mathbb{Z}$，

因为 $p | n \to n = k_2 p,k_2 \in \mathbb{Z}$，

于是 $a = b+k_1n = b+k_1k_2p$

所以有 $a \equiv b \pmod p$

正确性验证：

已知 $x \equiv (a_1M_1M_1^{-1} + a_2M_2M_2^{-1} + \cdots + a_kM_kM_k^{-1}) \mod M$

我们验证一下是否有 $x \equiv a_1 \pmod {m_1}$

根据 引理 3，我们有 $x \equiv (a_1M_1M_1^{-1} + a_2M_2M_2^{-1} + \cdots + a_kM_kM_k^{-1}) \mod m_1$

由于 $M = m_1 \cdot m_2 \cdots m_k$ ，所以

$M_1 = M/m_1 = m_2\cdot m_3 \cdots m_k$

$M_2 = M/m_2 = m_1\cdot m_3 \cdots m_k$

$\vdots$

$M_k = M/m_k = m_1\cdot m_2 \cdots m_{k-1}$

因此 $M_{i | 1 \lt i\le k}$ 均为 $m_1$ 的倍数，由于有 $M_{i | 1 \lt i\le k} \equiv 0 \pmod {m_i}$

于是 $x \equiv a_1 M_1 M_1^{-1} \pmod {m_1}$

又因为 $M_1^{-1}$ 是 $M_1$ 在模 $m_1$ 下的逆元，于是 $M_1 \cdot M^{-1} \equiv1 \pmod {m_1}$

于是有 $x \equiv a_1 \pmod {m_1}$

同理我们还可以得出 $x \equiv a_i \pmod {m_i}, 1 \lt i \le k$，于是 $x$ 满足同余方程组中的所有方程。

另外可以知道，方程组的通解为：$x+kM \ (k \in \mathbb{Z})$

直观上来看，中国剩余定理的作用就是根据约束条件来增大 $x$ 的值：如果我们只有一条约束 $x \equiv a_1 \pmod {m_1}$，那么我们只有 $x = a_1 + k{m_1}$，假设 $x$ 原来值远大于 $m_1$，我们就很难通过爆破 $k$ 的方式来恢复出原始的 $x$。如果此时能够多一条约束 $x \equiv a_2 \pmod {m_2}$，并且满足 $m_1 \cdot m_2 \gt x$，我们就能够通过中国剩余定理来直接计算出 $x$ 的原始值。

需要注意到的是，由于对于每一个 $M_i$ ，我们都需要在 $m_i$ 下求逆，因此必须满足所有的 $m_i$ 均互素才能使用上面的式子。

如果 $m_i$ 之间不互素，那么我们就需要先将他们公因子的那部分“消除”掉才能继续使用中国剩余定理。

第二颗🌰：设有素数 $p,q,r$，$m_1=p\cdot q,m_2 = p \cdot r$，已知下述同余方程组
$$
\begin{align*}
\begin{split}
\left {
\begin{array}{ll}
x \equiv a_1 \pmod{m_1} \
x \equiv a_2 \pmod{m_2} \

\end{array}
\right.
\end{split}
\end{align}
$$
由于 $gcd(m_1,m_2) = p$，根据 引理 3 我们有 $x \equiv a_1 \pmod q$，因此我们重构同余方程组为
$$
\begin{align}
\begin{split}
\left {
\begin{array}{ll}
x \equiv a_1 \pmod{q} \
x \equiv a_2 \pmod{m_2} \

\end{array}
\right.
\end{split}
\end{align*}
$$
此时 $gcd(m_1,q)=1$，因此使用中国剩余定理我们可以求得值 $a$，满足 $x \equiv a \pmod{p\cdot q\cdot r}$ 。

费马小定理 & 中国剩余定理应用：RSA-CRT 签名算法

当 RSA 算法用作签名的时候，首先会将消息 msg 进行哈希得到 H(msg)，然后签名者使用自己的私钥进行签名 $sig \equiv H(m)^d \pmod n$；验签者使用签名者的公钥进行验证是否满足 $sig^e \equiv H(m) \pmod n$ 以判断签名的有效性。

注意到签名时使用的是私钥，显然私钥越大，计算签名所需要的计算资源就越多。因此在实际应用中，考虑到效率问题，就会使用较小的私钥，于是维纳攻击、Boneh-Durfee 攻击就应运而生。为了避免此类攻击，可以选择 $RSA-CRT$ 模式进行签名：

签名的式子为 $sig \equiv H(m)^d \pmod n$，根据引理 3 我们有
$$
\begin{align*}
\begin{split}
\left {
\begin{array}{ll}
sig \equiv H(m)^d \pmod{p} \
sig \equiv H(m)^d \pmod{q} \

\end{array}
\right.
\end{split}
\end{align*}
$$
设 $d_p \equiv d \pmod {\varphi(p)} \to d = d_p+k\varphi(p)$

因此 $sig \equiv H(m)^d \equiv H(m)^{d_p + k\varphi(p)} \equiv H(m)^{d_p} \cdot H(m)^{k\varphi(p)} \pmod p$

根据 费马小定理（$H(m) \neq p)$，我们有 $H(m)^{\varphi(p)} \equiv 1 \pmod p$，

因此 $sig \equiv H(m)^d \equiv H(m)^{d_p} \pmod p$

同理能够得到 $sig \equiv H(m)^d \equiv H(m)^{d_q} \pmod q$

因此在计算 RSA 签名时，我们可以先计算 $sig_p \equiv H(m)^{d_p} \pmod p$ 和 $sig_q \equiv H(m)^{d_q} \pmod q$

再根据已知同余方程组
$$
\begin{align*}
\begin{split}
\left {
\begin{array}{ll}
sig \equiv sig_p \pmod{p} \
sig \equiv sig_q \pmod{q} \

\end{array}
\right.
\end{split}
\end{align}
$$
使用*中国剩余定理**，我们就能得到 $sig \equiv H(m)^d \pmod n$

可以注意到在 $RSA-CRT$ 模式计算签名过程中，参与计算的最大的数约为 $\sqrt{n}$，相比于直接计算，显而易见的这种模式能够节省大量的计算资源，从而提高计算效率。

威尔逊定理

当且仅当有素数 $p$，则有 $(p−1) ! \equiv −1\pmod{p}$ 。其中 $!$ 表示阶乘。

因此同余式 $(p−1) ! \equiv −1\pmod{p}$ 是 $p$ 为素数的充要条件。

证明：

充分性：

当 $p$ 不为素数时，我们分为四种情况进行讨论

1. $p=1$ 有 $(1-1)! \equiv 0 \pmod 1$

2. $p=4$ 有 $(4-1)! \equiv 2 \pmod 4$

3. 当 $p \gt 4$，且 $p$ 为平方数，设 $k^2 = p,k \gt2$，$2k - k^2 = k(2-k)$，所以当 $k \gt 2$ 时，$2k \lt k^2$，

   因此 $(p-1)! = 1 \cdot 2 \cdot 3\cdots k\cdots 2k \cdots (p-1) = 2k^2 \cdot j$，其中 $j$ 是其他元素的乘积

   于是 $(p-1)!= 2jp \equiv 0 \pmod p$

4. 当 $p \gt 4$，且 $p$ 不为平方数，那么肯定存在两个数 $a,b$ 满足 $a \cdot b = p$，设 $a \lt b$，

   因此 $(p-1)! = 1 \cdot 2 \cdot 3\cdots a\cdots b \cdots (p-1) = ab \cdot j$，其中 $j$ 是其他元素的乘积

   于是 $(p-1)!= jp \equiv 0 \pmod p$

必要性：

当 $p$ 为素数是，考虑 $x^2 \equiv 1 \pmod p$ 的解，当且仅当 $x \equiv \pm 1 \pmod p$ 的时候，解相同。因此抛开 $1,p-1$ 两个数不管，对于元素 $a \in [2,p-2]$，必然存在一个与之不相等的逆元 $a^{-1} \in [2,p-2]$ 满足
$$
a \cdot a ^{-1} \equiv 1 \pmod p
$$
所以必然有 $\frac{p-2-2+1}{2} = \frac{p-3}{2}$ 对数相乘为 $1$，即
$$
\prod_{i=2}^{p-2} i = (p-2) ! \equiv 1 \pmod p
$$
同余式两边再同时乘一个 $p-1$ 即可得到威尔逊定理
$$
(p-1)! \equiv p-1 \equiv -1\pmod p
$$
虽然但是，威尔逊定理的应用场景并没有很广泛，一般用于辅助数学推导，或者简化数学运算。

例如，已知整数 $p,q$ ，且它们是两个相邻的素数满足 $p \lt q$，求 $q! \pmod p$ 的值或者 $p! \pmod q$ 的值。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com