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等一系列操作
【2019 Roar CTF】baby RSA + 威尔逊定理 + python写脚本小结
原文：https://www.cnblogs.com/wayne-tao/p/11723494.html