下载py文件,代码如下:

 1 import sympy
 2 import random
 3 
 4 def myGetPrime():
 5     A= getPrime(513)
 6     print(A)
 7     B=A-random.randint(1e3,1e5)
 8     print(B)
 9     return sympy.nextPrime((B!)%A)
10 p=myGetPrime()#93811
11 #A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
12 #B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
13 
14 q=myGetPrime()#67901
15 #A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
16 #B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
17 
18 r=myGetPrime()
19 
20 n=p*q*r
21 #n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
22 c=pow(flag,e,n)
23 #e=0x1001
24 #c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
25 #so,what is the flag?

代码逻辑不难,就是通过自定义的myGetPrime()函数获得三个大质数p,q,r,再加密,重点在于函数的返回值 sympy.nextPrime((B!)%A),返回了B!%A的下一个素数,B!代表B的阶乘。这里看到!就想到了威尔逊定理:(p-1)!+1=0 (mod p),其中p为素数

解题思路如下:

①首先要知道p,q,r,通过这三个数算出n的欧拉函数phi,p和q可以通过威尔逊定理求出,p和q出来了,r也可求出

②通过威尔逊定理,可知(A-1)!+1≡0 (mod A),故B!*(B+1)*(B+2)*...*(A-1) ≡ -1 (mod A),故只要求出(B+1)*(B+2)*...*(A-1)在模数A下的逆(这里设为C1),即

B!≡-1*C1 (mod A),那么B!%A的值就可以求出,也可以得出sympy.nextPrime((B!)%A)

③求出私钥d,解出密文

脚本如下:

from libnum import *
from Crypto.Util.number import *
import sympy
import gmpy2

def wilison(b,a): p=1 b=b+1 while b<a: p*=b p=p%a b=b+1 return p A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407 B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596 A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927 B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026 n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733 e=0x1001 c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428 invert1=1 invert2=1 invert1=invmod(wilison(B1,A1),A1) invert2=invmod(wilison(B2,A2),A2) p=gmpy2.next_prime((invert1*(-1))%A1) q=gmpy2.next_prime((invert2*(-1))%A2) print(p,q) r=n//p//q print("r:",r) phi=(p-1)*(q-1)*(r-1) d=invmod(e,phi) s=pow(c,d,n) print(long_to_bytes(s))

运行结果如下:

root@kali:~/桌面/Crypto# python3.7 rebabyrsa_roar_10_8.py 
1276519424397216455160791032620569392845781005616561979809403385593761615670426423039762716291920053306063214548359656555809123127361539475238435285654851 13242175493583584108411324143773780862426183382017753129633978933213674770487765387985282956574197274056162861584407275172775868763712231230219112670015751
r: 5057572094237208127867754008134739503717927865750318894982404287656747895573075881186030840558129423864679886646066477437020450654848839861455661385205433
b'RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}'

得到flag!!!

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/jane315/p/13805724.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!