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

密码学 10个月前 admin
174 0 0

本来应该是上周五密码学基础系列的文章,因为“熵密杯”,然后上周末又打了 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. ,且 不为平方数,那么肯定存在两个数 满足 ,设

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

    于是

必要性:

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

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

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

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

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


原文始发于微信公众号(Van1sh):密码学基础之数论四大定理

版权声明:admin 发表于 2023年8月18日 上午9:01。
转载请注明:密码学基础之数论四大定理 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...