密码学笔记之数论定理的应用

欧拉定理 : 若 $n,a$ 为正整数，且 $n,a$ 互素，即 $gcd(a,n)=1$，则 $a^φ(n) ≡ 1(mod$ $n)$

费马小定理（欧拉定理特殊型情况）: 对于质数p，任意整数a，均满足：$a^{p−1}≡1(mod$ $p)$ ，那么，$a^{p−2}$ 就是a在模p下的逆元了

中国剩余定理（CRT）

威尔逊定理： 当且仅当p为素数时有，$(p−1)!≡−1(mod$ $p)$ , $(p−2)!≡1(mod$ $p)$

案例

UNCTF 一句话加密(Rabin加密)

题目：

1
2
3
4
5


n = 0xc2636ae5c3d8e43ffb97ab09028f1aac6c0bf6cd3d70ebca281bffe97fbe30dd

c = pow(int(m.encode('hex'), 16),e,n)
c1:62501276588435548378091741866858001847904773180843384150570636252430662080263
c2:72510845991687063707663748783701000040760576923237697638580153046559809128516

用在线N分解网站获取p,q：factordb.com

1
2


p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239

这里 e 并没有给出，一般这样的话，e的值应该是常规值如： 65537、2、3、5

相关考点（低加密指数攻击、Rabin加密）

Rabin解密EXP：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


from gmpy2 import *
from libnum import *
from Crypto.Util.number import *

# c = 62501276588435548378091741866858001847904773180843384150570636252430662080263
c = 72510845991687063707663748783701000040760576923237697638580153046559809128516
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
n = p*q
c_p = pow(c,(p+1)//4,p)
c_q = pow(c,(q+1)//4,q)
a = invert(p,q)
b = invert(q,p)
x = (b*q*c_p+a*p*c_q)%n
y = (b*q*c_p-a*p*c_q)%n

# print(n2s(x))
# print(n2s(n-x))
# print(n2s(y))
# print(n2s(n-y))
print(long_to_bytes(x))
print(long_to_bytes(n-x))
print(long_to_bytes(y))
print(long_to_bytes(n-y))

unctf{412a1ed6d21e55191ee5131f266f5178}

Roarctf - babyrsa(威尔逊定理利用)

题目：

import sympy
import random

def myGetPrime():
    A= getPrime(513)
    print(A)
    B=A-random.randint(1e3,1e5)
    print(B)
    return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026

r=myGetPrime()

n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?

加密中的 (B!)%A 的 ! 在这里是阶乘的意思，所以显然这里要用到威尔逊定理，不然这么大的一个数的阶乘，解决的时间复杂度太大

根据加密逻辑，这里是一个三素数加密系统，即 $φ(n)=$ $(p-1) * (q-1) * (r-1)$ 。

已知条件：n，$n = p * q * r$

所以 r 的值肯定是要先通过求出 p,q 得到，关于 p ，q 获取方式都一样，所以解法也一样。

简化解题思路：

先根据 A1，B1 求出 p

而 $p ≡ B!$ $(mod A)$ ，$(B< A)$

虽然 B, A的值都给出了，但直接进行阶乘运算，显然是不可取的。所以需要用到威尔逊定理简化计算

简化计算：

已知 $B! ≡ P$ $(mod A)$

因为 A 是素数，根据威尔逊定理得到： $(A-1)! ≡ -1$ $(mod$ $A)$

即 $(A-1)(A-2)......(B+1)B! ≡ -1$ $(mod$ $A)$

由已知条件得到：$(A-1)(A-2)......(B+1)P ≡ -1$ $(mod$ $A)$

变形得到：$(A-2)......(B+1)P ≡ 1$ $(mod$ $A)$

所以 $P$ 就是 $(A-2)......(B+1)$ 在模 $A$ 下的逆

EXP：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


from gmpy2 import *
import sympy
from libnum import *


A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428

def get_p_q(A,B):
    tmp = 1
    for i in range(B+1,A-1):
        tmp *= i
        tmp %= A
    tmp_inv = invert(tmp,A)
    return tmp_inv

p = sympy.nextprime(get_p_q(A1,B1))
q = sympy.nextprime(get_p_q(A2,B2))
r = n//p//q

e=0x1001
phi = (p-1)*(q-1)*(r-1)
d = invert(e,phi)
m = pow(c,d,n)

print(n2s(m))

HECTF easy_rsa

from gmpy2 import *
from Crypto.Util import number

#e = have a try
p = number.getPrime(1024)
q = number.getPrime(1024)

nothing = 251560377963038761190200797029988859033 # getPrime(128)

n = p*q
fn = (p-1)*(q-1)
d =inverse(e, fn)
something=(p-1)*d+nothing
enc = pow(flag, e, p*q)

#n=
#something=
#enc=

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

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

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

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

根据费马小定理

$2^{p−1}≡1$ $(mod$ $p)$ 显然成立 主要是为了利用题目中给出的 $(p−1)∗d$

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

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

$(2p−1)^{ed} ≡$ $(2^{p−1})$ $(mod$ $n)$

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

所以$A≡2^{p−1}−1 ≡ (2^{p−1})^{ed}−1≡2^{es−er}−1(mod$ $n)$

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

即 $gcd(kp,pq)$

即可得到 $p$

EXP：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


import libnum
from gmpy2 import *
import sympy

enc=
n=
something=
nothing=
e=1
while(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
            break
	except:
    	continue

构造GCD

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger
p = getPrime(512)
q = getPrime(512)
n=p*q

a=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≡(p+q)^{2019}$ $(mod$ $n)$

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

由$b≡(p+2019)^q$ $(mod$ $n)$

可得 $b≡(p+2019)^q≡p+2019$ $(mod$ $q)$ 【费马小定理：$(p+2019)^q−1 ≡ $ $1(mod$ $q)$】

所以$a≡(b−2019)^{2019}$ $(mod$ $q)$

即$a=(b−2019)^{2019}+kq$

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

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

解题完毕

密码学笔记之数论定理的应用

数论四大重要定理的学习

学习文章：

四大定理：

案例

UNCTF 一句话加密(Rabin加密)

Rabin解密EXP：

Roarctf - babyrsa(威尔逊定理利用)

EXP：

HECTF easy_rsa

EXP：

构造GCD

密码学笔记之数论定理的应用

相关文章：