[roarctf2019] babyrsa Wilson theorem

1. Title code

# 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)
# #
# #c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
# #so,what is the flag?

2. Reappear

Direct decomposition p,q,r. It is found that it can be decomposed .

import gmpy2
import libnum
import sympy
import math

n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
p=1276519424397216455160791032620569392845781005616561979809403385593761615670426423039762716291920053306063214548359656555809123127361539475238435285654851
q=5057572094237208127867754008134739503717927865750318894982404287656747895573075881186030840558129423864679886646066477437020450654848839861455661385205433
r=13242175493583584108411324143773780862426183382017753129633978933213674770487765387985282956574197274056162861584407275172775868763712231230219112670015751
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
phi=(p-1)*(q-1)*(r-1)
e=0x1001
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
flag=libnum.n2s(int(m))
print(flag)
# b'RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}'

  But this question should not be for this , We should use p,q,r How to generate , Work out p,q,r.

The key is sympy.nextPrime((B!)%A),B,A We all know , Find out B!%A That's all right. , But it can't be counted directly , because B It's too big .

Check here for Wilson's theorem :(p-1)!+1=0 (mod p).A,B Very similar , and A Greater than B, therefore A！ Is included B！ Of .

(B-1)!+10(mod B)

(A-1)!+10(mod A)->B!*(B+1)......(A-1)+10 mod A->B!*(B+1)......(A-1)-1 mod A

Therefore, only (B+1)(B+2)…*(A-1) In module A Inverse of down （ Set here as C1）, namely

B!≡-1*C1 (mod A), that B!%A You can find the value of

import gmpy2
import libnum
import sympy
A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
e=0x1001
def getprime(A,B):
    c=1
    for i in range(B+1,A):
        c=(c*gmpy2.invert(i,A))%A
    c=c*(A-1)%A
    return sympy.nextprime(c)
p=getprime(A1,B1)
q=getprime(A2,B2)
r=n//p//q
phi=(p-1)*(q-1)*(r-1)
d=gmd=gmpy2.invert(e,phi)
m=pow(c,d,n)
flag=libnum.n2s(int(m))
print(flag)
# b'RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}'