[RoarCTF2019]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?

此题有两种解法：
解法一：直接分解n的值，得到了p,q,r的值，分解方法有factor（网站：factordb.com）或者yafu工具

直接写求解RSA的代码：

import libnum
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
e = 4097    # 此处是将0x1001转为十进制数
p = 1276519424397216455160791032620569392845781005616561979809403385593761615670426423039762716291920053306063214548359656555809123127361539475238435285654851
q = 5057572094237208127867754008134739503717927865750318894982404287656747895573075881186030840558129423864679886646066477437020450654848839861455661385205433
r = 13242175493583584108411324143773780862426183382017753129633978933213674770487765387985282956574197274056162861584407275172775868763712231230219112670015751
n = p*q*r
phi = (p-1)*(q-1)*(r-1)
d = libnum.invmod(e,phi)
m =pow(c,d,n)
print(libnum.n2s(m))
# b'RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}'

解法二：虽然此题是给互素e的值，使其直接可以求出flag值，但是此题重点还是想考用p，q，r的生成方式，计算出p，q，r的值。

首先分析题目已知代码：

p=(B1!)%A1
q=(B2!)%A2

又已知由威尔逊定理得到：(A−1)!≡ −1 mod A

然后由题目代码B=A-random.randint(1e3,1e5)，很明显需要在B的前面给补上：(A−1)(A−2)(A−3)...(B+1) --> (A−1)(A−2)(A−3)...(B+1)∗(B!)%A=−1%A

最后我们化简整理得到：(A−2)(A−3)...(B+1)∗(B!)%A=1%A

这就可以知道由(A−2)(A−3)...(B+1)模A的逆元求得(B!)%A的值，再使用nextprime函数求p和q的值。

话不多说，直接写代码：

import libnum
import sympy
import gmpy2
A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
e = 4097  # 此处是将0x1001转为十进制数

def getp_q(A,B):
    k = 1
    for i in range(B+1,A-1):
        k *= i
        k %= A

    new = sympy.invert(k,A)
    flag = sympy.nextprime(new)
    return flag

p = getp_q(A1,B1)
q = getp_q(A2,B2)
r = n // p // q

d = libnum.invmod(e,(p-1)*(q-1)*(r-1))
m =pow(c,d,n)
print(libnum.n2s(m))
# b'RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}'

总结：此题主要考点是威尔逊定理(p-1)!+1=0 (mod p)。A和B很接近，而且A大于B，所以A！是包含B！的。