【2019 Roar CTF】baby RSA + 威尔逊定理 + python写脚本小结

Baby RSA 题目内容：

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
#p=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140651
q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
#q=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351043
r=myGetPrime()
n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=38347207883249601033653636821391847544875416880619614342339765883967916960100888999916613942668007089161071995631543462301367053958077198225214363505024848543179161424532987598516195302155764378892435582732218546342964613797538210260769612972831286966696915391991999466554505813797987381860855552244138180628982832282918799144636417921948189345110125610972711494191577055380771099863428248761761388282714659239444209955862537018724141881150316760288205511447144
#so,what is the flag?

其实解题的关键位置就是在 sympy.nextPrime((B!)%A)

1. B是个大数

2. 阶乘之后更大，再取模很难算

综上，采用威尔逊定理：

定理的关键是对于q的阶乘模p，可以转换为q+1到p-2的连乘的积再模p

所以，脚本就成了如下：

import sympy
from gmpy2 import *
from Crypto.Util.number import long_to_bytes
A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e=4097
c=38347207883249601033653636821391847544875416880619614342339765883967916960100888999916613942668007089161071995631543462301367053958077198225214363505024848543179161424532987598516195302155764378892435582732218546342964613797538210260769612972831286966696915391991999466554505813797987381860855552244138180628982832282918799144636417921948189345110125610972711494191577055380771099863428248761761388282714659239444209955862537018724141881150316760288205511447144
def mod_wei(A,B):
 mod = 1
 x = A-1;
 y = B+1;
 for i in range(y,x):
  mod *= i
  mod %= A
 return mod

x1=mod_wei(A1,B1)
x2=mod_wei(A2,B2)
y1=invert(x1,A1)
y2=invert(x2,A2)
p=sympy.nextprime(y1)
q=sympy.nextprime(y2)
r=n/p/q
o_n=(r-1)*(p-1)*(q-1)
d=invert(e,o_n)

m=pow(c,d,n)
print m
print hex(m)[2:].decode('hex')
print long_to_bytes(m)

脚本小结：

1. for循环：像上题，从要想实现从B+1到A-2的连乘，range里就要写到A-1

2. long_to_bytes太好用了！！！完全代替了decode等一系列操作

最终flag