密码学基础之数论四大定理

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

• 欧拉定理
• 费马小定理
• 中国剩余定理
• 威尔逊定理

欧拉定理

设 ，如果有 ，则有

（其中 是欧拉函数， 表示模 的简化剩余系中元素的个数）

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

设模 剩余系中的元素为 ，与 互素的非零整数 ，我们定义一个集合

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

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

即 ，

等价于

也即

于是有

由于 ，且 ，因此有

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

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

证明：已知 ，由于 ，

因此

欧拉定理证明： 我们将集合 中的元素全部相乘，有

根据前面两个引理，集合 中元素互不模 同余，且均与 互素；因此对于其中的任意元素 均能在模 的简化剩余系中找到对应的满足 的元素，于是有

将（2）式带入 （1）式我们得到

第一颗?：设 ，有

模 的简化剩余系为 ，集合 ，可以将集合 中的元素和模 简化剩余系中的元素一一匹配：

即

于是  

因此

即  

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

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

已知有 RSA 参数 ，其中 是两个素数; 公钥 和 私钥 满足 。明文 加密为密文 的式子是 ；密文 解密为明文 的式子是 。现在我们需要验证解密算法的正确性，即证明

由于 ，带入（1）式即证明

根据 ，所以

因此有

由于 ，根据欧拉定理有 ，带入（2）式得

（3）式显然成立，因此 RSA 解密算法正确性得证。

费马小定理

设有素数 ，对于模 的简化剩余系中的任意元素 （  ）有

是欧拉定理的特殊情况，证明过程也差不多，就不赘述了。

中国剩余定理

设正整数两两互素，则同余方程组

有整数解。并且在模 下的解是唯一的，解为

注意其中， 为 在模 下的逆元。

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

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

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

证明：

由 ，

因为 ，

于是

所以有

正确性验证：

已知

我们验证一下是否有

根据 引理 3，我们有

由于 ，所以

因此 均为 的倍数，由于有

于是

又因为 是 在模 下的逆元，于是

于是有

同理我们还可以得出 ，于是 满足同余方程组中的所有方程。

另外可以知道，方程组的通解为：

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

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

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

第二颗?：设有素数 ，，已知下述同余方程组

由于 ，根据 引理 3 我们有 ，因此我们重构同余方程组为

此时 ，因此使用中国剩余定理我们可以求得值 ，满足   。

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

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

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

签名的式子为 ，根据引理 3  我们有

设

因此

根据 费马小定理（，我们有 ，

因此

同理能够得到

因此在计算 RSA 签名时，我们可以先计算 和

再根据已知同余方程组

使用中国剩余定理，我们就能得到

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

威尔逊定理

当且仅当有素数 ，则有   。其中 表示阶乘。

因此同余式    是 为素数的充要条件。

证明：

充分性：

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

1. 有

2. 有

3. 当 ，且 为平方数，设 ，，所以当 时，，

   因此 ，其中  是其他元素的乘积

   于是

4. 当 ，且 不为平方数，那么肯定存在两个数 满足 ，设 ，

   因此 ，其中  是其他元素的乘积

   于是

必要性：

当 为素数是，考虑 的解，当且仅当 的时候，解相同。因此抛开 两个数不管，对于元素 ，必然存在一个与之不相等的逆元 满足

所以必然有 对数相乘为 ，即

同余式两边再同时乘一个 即可得到威尔逊定理

虽然但是，威尔逊定理的应用场景并没有很广泛，一般用于辅助数学推导，或者简化数学运算。

例如，已知整数 ，且它们是两个相邻的素数满足 ，求 的值或者 的值。