密码学学习笔记 之 数论四大定理及应用

首发于安全客

前言

可以发现RSA中的很多攻击方法都是从数论四大定理推导出的，所以找时间好好学习了一下数论四大定理的证明及其应用场景——Rabin算法。

欧拉定理

若$n,a$为正整数，且$n,a$互素，即$gcd(a,n) = 1$，则

$a^{φ(n)}\equiv1\pmod{n}$

证明

首先，我们需要知道欧拉定理是什么：

数论上的欧拉定理，指的是

$a^{φ(n)}\equiv1\pmod{n}$

这个式子实在$a$和$n$互质的前提下成立的。

证明

首先，我们知道在1到$n$的数中，与n互质的一共有$φ(n$)个，所以我们把这$φ(n)$个数拿出来，放到设出的集合X中，即为$x_1,x_2……x_{φ(n)}$

那么接下来，我们可以再设出一个集合为M，设M中的数为：

$m_1=a∗x_1,m_2=a∗x_2……m_φ(n)=a∗x_{φ(n)}$

下面我们证明两个推理：

反证法。

证明：假设M中存在两个数设为$m_a,m_b$模$n$同余。

即$m_a\equiv m_b$

移项得到：$m_a−m_b=n∗k$

再将m用x来表示得到：$a∗x_a−a∗x_b=n∗k$

提取公因式得到：$a∗(x_a−x_b)=n∗k$

我们现在已知$a$与$n$互质，那么式子就可以转化为：

$x_a−x_b\equiv 0 \pmod{n}$

因为$a$中没有与$n$的公因子（1除外）所以$a !\equiv 0 \pmod{n}$ 所有只能是$ x_a−x_b\equiv 0\pmod{n}$。

又因为$x_a,x_b$都是小于$n$的并且不会相同，那么上述的式子自然全都不成立。

假设不成立。

证得：$M$中任意两个数都不模$4$同余。

证明：我们已知$m_i=a∗x_i$

又因为$a$与$n$互质，$x_i$与$n$互质，所以可得$m_i$与$n$互质。

带入到欧几里得算法中推一步就好了。

即：

$gcd(a∗xi,n)=gcd(mi,n)=gcd(n,mi mod n)=1$

证毕。

首先，根据前两个推论可以知道，$M$中的数分别对应$X$中的每个数模$n$同余。

（即是双射关系：首先M中的数在模n下不同余，即不相同，然后有$φ(n)$个$m$；其次有$φ(n)$个不相同的$x$与$n$互质，所以$m$与$x$是双射关系）

所以可以得到：

$m_1∗m_2∗……∗m_{φ(n)}\equiv x_1∗x_2∗……∗x_{φ(n)}\pmod{n}$

现在我们把替换成x的形式，就可以得到：

$a∗x_1∗a∗x_2∗……∗a∗x_{φ(n)}\equiv x_1∗x_2∗……∗x_{φ(n)}\pmod{n}$

$a^{φ(n)}∗(x_1∗x_2……∗x_{φ(n)})\equiv x_1∗x_2……∗x_{φ(n)}\pmod{n}$

$(a^φ(n)−1)∗(x_1∗x_2……∗x_{φ(n)})\equiv 0\pmod{n}$

然后，由于$(x_1∗x_2……∗x_{φ(n)}) !\equiv 0\pmod{n}$

所以 $(a^{φ(n)}−1)\equiv 0\pmod{n}$

所以 $a^{φ(n)}\equiv 1\pmod{n}$

应用：RSA的解密

欧拉定理在RSA中可用于证明 $M\equiv C^d \pmod{N}$ ：

费马小定理（欧拉定理特殊型情况）

对于质数p，任意整数a，均满足：$a^{p-1}\equiv 1 \pmod{p}$

那么，$a^{p-2}$就是a在模p下的逆元了

孙子定理（中国剩余定理 CRT）

设正整数$m_1,m_2…m_k$两两互素，则同余方程组$x \equiv a_1 \pmod{m_1}$$x \equiv a_2 \pmod{m_2}$$x \equiv a_3 \pmod{m_3}$…$x \equiv a_k \pmod{m_k}$

有整数解。并且在模$M = m_1 \cdot m_2 \cdot … \cdot m_k$下的解是唯一的，解为$x \equiv (a_1M_1M_1^{-1} + a_2M_2M_2^{-1} + … + a_kM_kM_k^{-1}) \mod M$

其中$M_i = M / m_i$，而$M_i^{-1}$为$M_i$模$m_i$的逆元。

证明

具体证明如下：

例：找出所有整数x,使其被3，5和7除时，余数分别为2，3和2

$x\equiv 2 \pmod{3}$

$x\equiv 3 \pmod{5}$

$x\equiv 2 \pmod{7}$

=> $x = △ + 357*t$ (△为期中的一个解，t为整数）

在同余中最重要的观念就是求出第一个解，那么$x = △ + 357*t$就是通解。那怎么求一个解呢？

利用同余的加性：

把$x$拆成$a+b+c$,即$x = a + b + c $

令

$a\equiv 2 \pmod{3}$

$a\equiv 0 \pmod{5}$

$a\equiv 0 \pmod{7}$

=> $a=35p$ ( 可以看到p取1的时候满足$a\equiv 2\pmod{3}$,即$a=35 $)

为何这样取？从接下来的取法可知：b 和 c 都会取 3 的倍数，这样子就能保证，x mod 3 = 2，我们标记这样的取法为FLAG

接下来要求b：

$b\equiv 0\pmod{3}$

$b\equiv 3\pmod{5}$

$b\equiv 0\pmod{7}$

=>$b=21q$ (可以看到q取3的时候满足$b\equiv 3\pmod{5}$,即$b=63$)

求c

$c\equiv 0\pmod{3}$

$c\equiv 0\pmod{5}$

$c\equiv 2\pmod{7}$

$=>$$c=15m$(可以看到m取2的时候满足$c\equiv 2\pmod{7}$,即$c=30$)

得

$x\equiv 2\pmod{3} \equiv a + b + c$

$x\equiv 3\pmod{5} \equiv a + b + c$

$x\equiv 2\pmod{7} \equiv a + b + c$

a b c 都求出来之后，可以利用同余的加性

$x = a + b + c = 128$是一个解， $x = 128 + 105t $在适当调整$t$之后就可以求出$x$在任何范围内的解，比如说求最小正整数解，这时候$t$取$-1$，得$x=23$

利用同余的乘性：

之前令$x = a + b + c$,用同余的乘性之后$x = 2a’ + 3b’ + 2c’$ (此时令$a’=b’=c’=1$，就相当于同余的加性了)

$a’\equiv 1\pmod{3} $

$a’\equiv 0\pmod{5}$

$a’\equiv 0\pmod{7}$

$ =>a’=35p$(可以看到p取2的时候满足$a’\equiv 1\pmod{3}$,即$a’=70$)

接下来要求b’：

$b’\equiv 0\pmod{3}$

$b’\equiv 1\pmod{5}$

$b’\equiv 0\pmod{7}$

$=>b’=21q$(可以看到$q$取1的时候满足$b’\equiv 1\pmod{5}$,即$b’=21$)

现在来看c’

$c’\equiv 0\pmod{3}$

$c’\equiv 0\pmod{5} $

$c’\equiv 1\pmod{7}$

$=>c’=15m$(可以看到m取1的时候满足$c’\equiv 1\pmod{7}$,即$c’=15$)

有了$a’ b’ c’$之后就可以得到 $x = 2a’ + 3b’ + 2*c’ $代入$a’ b’ c’$之后就可以得到$x$的一个解及其通解

$x = 270 + 321 +2*15 $

$x = 233 + 105t$

在知道同余的加性和乘性之后再看下面这个公式就没有什么问题了

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

其中，$a_i$就是题目所要求的剩余，$M_1$就是前文提到的标记取法FLAG，而$M_1^{-1}$就是在同余的乘法性中为了满足$a_1’\equiv 1 \pmod{m_i}$

威尔逊定理

当且仅当p为素数时有，

$(p−1) ! \equiv −1\pmod{p}$

证明：

首先：

$p−1 \equiv −1\pmod{p}$

那么我们只需要证明 $(p−2)!\equiv 1\pmod{p} $

也就是说，除去 $1$ 后，如果 $2,3,…,p−2$ 能够两两配对，且每对数乘积模 $p$ 后为 $1$ 的话，威尔逊定理就成立了，然后我们考虑这其实就是对于$ 2,3,…,p−2$去找 模 $p$ 意义下的逆元。

然后考虑一下二次剩余里面的衍生知识，我们可以知道对于 $x^2\equiv 1\pmod{p}$只有两个解$（1，p-1）$，而这两个数已经被我们安排掉了，也就是说 $2,3,…,p−2$中不存在某个数的逆元是自己本身。

然后 集合$ A={1,2,3,…p -1}$; 构成模p乘法的缩系，即任意$i∈A$ ,存在$j∈A$,使得: $( i，j ) \equiv 1\pmod{p}$

也就是说，除去$1$和$p-1$外，其余的两两配对互为逆元

证毕

应用：Rabin算法

在解Rabin算法前，我们需要一些定理、推论

定理1

欧拉判别定理， c是模p的平方剩余的充要条件是 ，$(c^\frac{1}{2})^{φ(n)} \equiv 1\pmod{p}$

首先，由于$p$是一个奇素数，由费马小定理，$d^{p-1} \equiv 1 \pmod{p}$。但是$P-1$是一个偶数，所以有

$(d^{ \frac{p-1}{2} } -1) \cdot (d^{ \frac{p-1}{2} }+1) \equiv 0 \pmod{p}$

$p$ 是一个素数，所以$d^{ \frac{p-1}{2} } -1$ 和 $d^{ \frac{p-1}{2} }+1$中必有一个是$P$ 的倍数。因此$d^{ \frac{p-1}{2} }$模$P$的余数必然是1或-1。

• 证明若$d$是模$p$二次剩余，则$d^{ \frac{p-1}{2}} \equiv 1 \pmod{p}$

若$d$是模$p$二次剩余，则存在 $x^2 \equiv d \pmod{p}$，$p$跟$d$和$x$ 互质。根据费马小定理得：

$d^{ \frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod{p}$

• 证明若$d^{ \frac{p-1}{2} } \equiv 1 \pmod{p}$，则$d$是模$p$的二次剩余

$p$ 是一个奇素数，所以关于$p$的原根存在。设$a$是$p$的一个原根，则存在$1 \le j \le p-1$使得$d=a^j$。于是

$d^{ \frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod{p}$

$a$是$p$的一个原根，因此$a$模$p$的指数是$p-1$，于是$p-1$整除 $\frac{ j(p-1) }{2}$ 。这说明$j$是一个偶数。令 $i = \frac{j}{2}$ ，就有 $(a^i)^2 =a^{2i} = d$ 。$d$是模$p$ 的二次剩余

定理2

二次同余式$x^2 \equiv c \pmod{p}$的解为：

​ $ x \equiv ±c^\frac{p+1}{4} \pmod{p} $

由于p是素数，显然a与p互素，再由欧拉判别定理， a是模p的平方剩余的充要条件是 ，

$(c^\frac{1}{2})^{φ(n)} \equiv 1\pmod{p}$

即$(c^\frac{1}{2})^{p-1} \equiv 1\pmod{p}$

带入原式，得$x^2 \equiv c·(c^\frac{1}{2})^{p-1} \equiv c^\frac{p+1}{2} \equiv (c^\frac{p+1}{4})^2$

则

$x \equiv ±c^\frac{p+1}{4} \pmod{p}$

定理3

如果整数$c$满足：

1） $c$为$p$的平方剩余

2） $c$为$q$的平方剩余

则：$ c$为$p*q$的平方剩余，解$x$为：

$x\equiv±(c^\frac{p+1}{4}\pmod{p})\cdot(q^{-1}\pmod{p})\cdot q ± (c^\frac{q+1}{4}\pmod{q})\cdot (p^{-1}\pmod{q})·p\pmod{p\cdot q}$

二次同余式： $x^2 \equiv c\pmod{p*q}$

等价于同余式组 ： $x^2 \equiv c \pmod{p}$ ①

​ $x^2 \equiv c\pmod{q}$ ②

由定理2

①式解为 $x \equiv ±c^\frac{p+1}{4} \pmod{p} $

②式解为 $x \equiv ±c^\frac{q+1}{4} \pmod{q}$

由CRT，解为 $x\equiv±(c^\frac{p+1}{4}\pmod{p})\cdot(q^{-1}\pmod{p})\cdot q ± (c^\frac{q+1}{4}\pmod{q})\cdot (p^{-1}\pmod{q})·p\pmod{p\cdot q}$

Rabin加密

选择两个大素数$p$和$q$做为私钥

计算$n = p * q$做为公钥

若明文为m，则密文为$c \equiv m^2 \pmod{n}$

Rabin解密

我们首先计算出x1和x2，使得

$x_1^2 \equiv c \pmod{p}$，①

$x_2^2 \equiv c \pmod q)$，②

由于$p$是素数，显然$c$与$p$互素，再由定理2

得

$x_1 \equiv ±c^\frac{p+1}{4} \pmod{p}$

$x_2 \equiv ±c^\frac{q+1}{4} \pmod{q}$

（一正一负，负的计算可简化为 模-正，如：$-x_1 \equiv p - x_1 \pmod{p}$）

从这里可以看出来如果$p$和$q$不是模$4$余$3$的话，c的指数就不是一个整数，也就不能用这个方法计算了

接着我们求出$p$在模$q$下的逆，设为$a$，即$a*p \equiv 1\pmod{q}$

然后我们求出$q$在模$p$下的逆，设为$b$，即$b*q \equiv 1 \pmod{p}$

求出来a，b用于中国剩余定理

带入 $x\equiv±(c^\frac{p+1}{4}\pmod{p})\cdot(q^{-1}\pmod{p})\cdot q ± (c^\frac{q+1}{4}\pmod{q})\cdot (p^{-1}\pmod{q})·p\pmod{p\cdot q}$

得 $x \equiv±(c^\frac{p+1}{4}\pmod{p})·b\cdot q ±(c^\frac{q+1}{4}\pmod{q})\cdot a·p \pmod{n}$

设$c^\frac{p+1}{4}\pmod{p} $为$cp$，$c^\frac{q+1}{4} \pmod{q}$为$cq$

$x_1 = (b \cdot q \cdot c_p+a \cdot p \cdot c_q ) \mod n$$-x_1 = n - x_1$$x_2= (b \cdot q \cdot c_p- a \cdot p \cdot c_q) \mod n$$-x_2 = n - x_2$

其中有一个为我们想要的明文m。

exp:

1234567891011121314151617181920

import gmpy2def n2s(x):    return hex(x)[2:].decode("hex")c = p = q = n = p*qc_p = pow(c,(p+1)/4,p)c_q = pow(c,(q+1)/4,q)a = gmpy2.invert(p,q)b = gmpy2.invert(q,p)x = (b*q*c_p+a*p*c_q)%ny = (b*q*c_p-a*p*c_q)%nprint n2s(x)print n2s(n-x)print n2s(y)print n2s(n-y)

这里涉及 Cipolla’s algorithm ，先知已经有一篇讲的不错的文章了

题目实例

UNCTF - 一句话加密

题目是给了一张图，隐写了一个模n

1

n = 0xc2636ae5c3d8e43ffb97ab09028f1aac6c0bf6cd3d70ebca281bffe97fbe30dd

可以发现n不大，直接用yafu分解可得

但是找不到e，最后试了试rabin，成功破解

exp用上面的那个就可

roarctf - babyrsa

1234567891011121314151617181920212223

import sympyimport randomdef myGetPrime():    A= getPrime(513)    print(A)    B=A-random.randint(1e3,1e5)    print(B)    return sympy.nextPrime((B!)%A)p=myGetPrime()#A1=#B1=q=myGetPrime()#A2=#B2=r=myGetPrime()n=p*q*r#n=c=pow(flag,e,n)#e=0x1001#c=#so,what is the flag?

加密中的(B!)%A的 ! 在这里是阶乘的意思，所以显然这里要用到威尔逊定理，不然这么大的一个数的阶乘，根本吃不消好吧

根据加密逻辑，这里是一个三素数系统，所以$φ(n) = (p-1)(q-1)(r-1)$，然后$r$肯定是要通过先求出$p，q$来得出

然后关于$p$和$q$，题目给的信息都一样，所以求$p$和求q的解法肯定是一样的，

所以题目简化为，根据A1,B1解p

而$p \equiv (B!) \pmod{A}$ （B是一个比A小的数）

虽然A，B均已给出且互素，但显然大数$B$的阶乘是不可能直接求得的，

所以要用威尔逊定理简化计算

简化过程如下：

已知 $B! \equiv P\pmod{A})$

由于A是素数，所以有： $(A-1)! \equiv -1 \pmod{A}$

​ 即$(A-1)(A-2)……(B+1)B! \equiv -1 \pmod{A}$

​ 根据已知$(A-1)(A-2)……(B+1)P \equiv -1 \pmod{A}$

​ 变形为$(A-2)……(B+1)P \equiv 1 \pmod{A}$

所以$p$即为$(A-2)(A-3)……(B+1)$ 在模$A $下的逆

exp

123456789101112131415161718192021222324252627

from gmpy2 import *import sympyA1=B1=A2=B2=n=e=0x1001c=a = 1for i in range(A1-2,B1,-1):    a = a*i % A1b = 1for i in range(A2-2,B2,-1):    b = b*i % A2p = sympy.nextprime(invert(a,A1))q = sympy.nextprime(invert(b,A2))r=n/p/qphi = (p-1)*(q-1)*(r-1)d = invert(e,phi)m=pow(c,d,n)print hex(m)[2:].decode('hex')

HECTF - easy_rsa

12345678910111213141516171819202122

from gmpy2 import *from Crypto.Util import number#e = have a tryp = number.getPrime(1024)q = number.getPrime(1024)nothing = 251560377963038761190200797029988859033 # getPrime(128)n = p*qfn = (p-1)*(q-1)d =inverse(e, fn)something=(p-1)*d+nothingenc = pow(flag, e, p*q)#n=#something=#enc=

题目给了，nothing（下面记为r），something（下面记为s），其中$ (p-1)*d= s - r$

目的很明确，就是分解大数n

这一题的思路就是利用$GCD$来约出$n$的因子

所以首先要获得一个$p$的倍数

根据费马小定理

$2^{p-1} \equiv 1 \pmod{p}$显然成立 (主要是为了利用题目中给出的$ (p-1)*d$）

所以设$A = 2^{p-1} - 1 = kp$

然后利用欧拉定理，我们直接利用上文中提到的RSA的解密证明中的结论

$(2^{p-1})^{ed} \equiv (2^{p-1}) \pmod{n}$

由题，$(p-1)d = s - r$

所以$A \equiv 2^{p-1} - 1 \equiv (2^{p-1})^{ed} - 1 \equiv 2^{es-er} - 1 \pmod{n}$

所以 $gcd( 2^{es-er} - 1 , n) $

即 $gcd(kp , pq) $

即可得到 $p$

exp:

1234567891011121314151617181920212223

import libnumfrom gmpy2 import *import sympyenc=n=something=nothing=e=1while(True):    try:        e=sympy.nextprime(e)        a=pow(2,e*something-e*nothing,n)-1        p=libnum.gcd(a,n)        q=n/p        fn=(p-1)*(q-1)        d=invert(e,fn)        flag=libnum.n2s(pow(enc,d,n))        if "hebtu" in flag:            print flag            breakexcept:    continue

构造GCD

可以看出，构造gcd来求大数n的因子以此来分解n是一种很好又很巧妙的方式,来看这一题

12345678910

from Crypto.Util.number import getPrime, isPrime, getRandomNBitIntegerp = getPrime(512)q = getPrime(512)n=p*qa=int(pow((q+p),2019,n))b=int(pow(p+2019,q,n))n=a=b=

这里，我们要通过已给出的a和b，来分解n

通过a，b和p，q的关系，我们要想办法用a,b凑出一个GCD来求出n的一个因子

解题过程如下：

由$ a \equiv (p+q)^{2019} \pmod{n}$

可得 $a \equiv (p+q)^{2019} \equiv p^{2019} \pmod{q}$ 【二项式展开定理】

由$ b \equiv (p+2019)^q \pmod{n}$

可得 $b \equiv (p+2019)^q \equiv p+2019 \pmod{q}$ 【费马小定理：$(p+2019)^q-1 \equiv 1 \pmod{q}$】

所以$ a \equiv (b - 2019)^{2019} \pmod{q}$

​ 即$ a = (b - 2019)^2019 + kq$

这样我们就可以凑出一个$GCD$

$GCD（ (b - 2019)^{2019}-a，n）= GCD（ Kq，n）= q$

解题完毕

总结

这一次学习了数论四大定理的证明、应用，以及rabin密码的解法。发现其实很多解法、攻击方法都是多种定理的结合运用，有时候还要引出各种推论，很灵活

参考

欧拉定理证明： https://www.cnblogs.com/wangxiaodai/p/9758242.html

中国剩余定理证明： https://blog.csdn.net/Rain722/article/details/53230707

威尔逊定理证明： https://www.cnblogs.com/Judge/p/10755703.html

Rabin算法： https://veritas501.space/2017/03/01/%E5%AF%86%E7%A0%81%E5%AD%A6%E7%AC%94%E8%AE%B0/

https://xz.aliyun.com/t/5113

https://en.wikipedia.org/wiki/Rabin_cryptosystem

https://blog.csdn.net/qq_24451605/article/details/45093911

最后感谢Lur大佬的一手指点

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 [email protected] - source:Van1sh的小屋