buu [RoarCTF2019]babyRSA 1

news/2024/4/26 3:53:28/文章来源:https://blog.csdn.net/XiongSiqi_blog/article/details/129214219

题目描述：

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

题目分析：

首先我们先看到 n = p * q * r （n 分解成了三个素数） ,而 e,c 都知道，所以要求明文 m = pow(c,d,n) 先要求出 d 来
而 d = gmpy2.invert(e,phi)
其中欧拉函数 phi = (p-1) * (q-1) * (r-1)
所以要求 d ,那么要求出 p 与 q
代码中 p = myGetPrime() = sympy.nextPrime((B!)%A)

sympy.nextprime(x) 是求小于x最近的质数

所以最终要求 (B!)%A，即B的阶乘模A，其中 A,B 都知道，那么B!（B的阶乘）怎么求呢？
有一个定理可以解决这个问题，即威尔逊定理

威尔逊定理

当且仅当p为素数时：( p -1 ) ! ≡ -1 ( mod p ) —> (p-1) ! +1=0 (mod p)

A = getPrime(513)，可知A为素数，又 B=A-random.randint(1e3,1e5)，通过威尔逊定理，可知(A-1) ! +1≡0 (mod A)，故B!(B+1)(B+2)…(A-1) ≡ -1 (mod A)，即B ! * C = ≡ -1 ( mod A )，其中C = (A - 1)! / (B) !，也就是B之后的数字之积
两边同时乘上C的逆元C1（C * C1 = 1），B ! = -1 * C1(mod A1)
B ! 求出来了，那么 p = myGetPrime() = sympy.nextPrime((B!)%A) 也就求出来了
如此，p,q 都求出来了，r = n // (p * q) ,自此p,q,r,都求出来了，最终flag也就出来了
代码如下：

import libnum
import sympy
import gmpy2A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
# e=0x1001，转十进制
e = 4097
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
def mydecryp(A,B):C1 = 1temp = pow(-1,1,A) # temp=-1 mod Afor i in range(B+1,A):C1 = (C1*gmpy2.invert(i,A))%A # C1是从B+1~A中每个数对A的逆元的乘积return sympy.nextprime((C1*temp)%A) # (C1*temp) = B!， (C1*temp)%A = (B!)%Ap = mydecryp(A1,B1)
q = mydecryp(A2,B2)
r = n//p//q
phi = (p-1)*(q-1)*(r-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(libnum.n2s(int(m)))