CTF-Crypto-RSA算法

先上一张图：

---

首先是两个比较大的质数一般记为p或者q（两者不能相等）  
然后还有个数是可以公开出来的。为N=p*q  
根据欧拉函数？质数的欧拉函数是φ(n)=n-1（φ(n)是一个函数，值的意义是与n互质的小于n的整数个数。）  
然后我们根据p和q可以得到一个关键数字r=φ(N)=φ(p)φ(q)=(p-1)*(q-1)  
然后任取一个小于r并且与r互质的整数e，这是可以公开出来的，是公钥(N,e)  
e关于r的模反元素d是私人所有的。私钥(N,d)  
p和q是应该被销毁的  
e*d-1=k*r(k为任意整数) or ed≡1(mod r) or e*d mod r≡1  
知道e和r求d的操作：d=gmpy2.invert(e,r)  
```
import gmpy2
#4*6 ≡ 1 (mod 23)
print(gmpy2.invert(4,23))       #6
```
加密的消息m应该满足m^e≡c (mod N)  c是加密后的密文
通过密文解密的话。c^d≡m (mod N)   m是原来的明文嘛
通过Python内置的脚本很容易实现。
加密：pow(m,e,N)
解密：pow(c,e,N)

逆元的定义：正整数 a, n，如果有 ax ≡ 1(mod n)，则称 x 的最小正整数解为 a 模 n的逆元。

Crypto-RSA加密
模反元素
逆元
gmpy2安装使用方法
gmpy2常见函数使用

<!--
-->

---

BUUCTF
Crypto-RSA
题目是这样的：

解题代码如下：掌握好RSA算法的基本原理就可以正常做出来了。
```

import gmpy2
# 4*6 ≡ 1 (mod 23)
# print(gmpy2.invert(4,23))
p=473398607161
q=4511491
e=17
r=(p-1)*(q-1)
d=gmpy2.invert(e,r)
print(d)


```



Crypto-rsarsa

```

import gmpy2
# 4*6 ≡ 1 (mod 23)
# print(gmpy2.invert(4,23))
p=9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q=11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
# p和q是两个大质数
N=p*q
e=65537
# e是公钥之一
r=(p-1)*(q-1)
d=gmpy2.invert(e,r)
# d是私钥之一
print(d)

c=83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
print(pow(c,d,N))


```


Crypto-RSA1
RSA密钥一般是1024位（安全）  
由p,q,dp,dq,c求明文的算法  
dp≡d mod(p-1)
dq≡d mod(q-1)
```
import gmpy2
I = gmpy2.invert(q,p)
mp = pow(c,dp,p)
mq = pow(c,dq,q)               #求幂取模运算

m = (((mp-mq)*I)%p)*q+mq       #求明文公式

print(hex(m))          #转为十六进制
```

Crypto-RSA1
完整代码如下。这个字节之类的处理一直不会。还有这个什么dp，dq推导结果的证明完全看不懂，摆大烂！！
```
import gmpy2
p=8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q=12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp=6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq=783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c=24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
I=gmpy2.invert(p,q)
mp=pow(c,dp,p)
mq=pow(c,dq,q)
m=(((mp-mq)*I)%p)*q+mq
m=hex(m)        
# 0x6e6f784354467b57333163306d335f37305f4368316e343730776e7d
a=bytes.fromhex(m[2:])
print(a)     #b'noxCTF{W31c0m3_70_Ch1n470wn}'


```
>参考资料
BUUCTF:RSA1
RSA加密算法详细解说
BUUCTF RSA题目全解1


Crypto-RSA2
```

import gmpy2
e=65537
n=248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp=905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c=140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
for i in range(1,e):
    if (dp*e)%i==1:
        if n%(((dp*e-1)//i)+1) == 0:
            p=((dp*e-1)//i)+1
            q=n//p
r=(p-1)*(q-1)
d=gmpy2.invert(e,r)
m=pow(c,d,n)
print(m)
print(bytes.fromhex(hex(m)[2:]))

```
>参考资料
RSA dp泄露的数学原理

Crypto-RSA3
```

import gmpy2
import libnum
def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291
s3,s1,s2=egcd(e1,e2)      # 取三个结果的后两个
if s1<0:
    s1 = - s1
    c1 = gmpy2.invert(c1, n)
elif s2<0:
    s2 = - s2
    c2 = gmpy2.invert(c2, n)
m=pow(c1,s1,n)*pow(c2,s2,n)%n
# print(type(m))      # <class 'mpz'>
print(libnum.n2s(int(m)))
# print(bytes.fromhex(hex(m)[2:]))


```
>参考资料
RSA共模攻击数学原理
libnum库的安装与使用

[NCTF2019]babyRSA

---

关键要素是e*d-1=k*r。而r=(p-1)*(q-1)。首先需要确定k的位数。然后通过爆破k来求解。。关键式也可写作e*d≡1 mod r

```

e=0x10001
d=19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c=5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804

import gmpy2
import sympy
ed1=e*d-1
for k in range(pow(2,15),pow(2,16)):    #16位数字？大概是
    if ed1%k==0:
        r=ed1//k
        p=sympy.prevprime(gmpy2.iroot(r,2)[0])
        q=sympy.nextprime(p)
        if (p-1)*(q-1)==r:
            break
n=p*q
m=pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))


```
比较常见的e的取值是：e=65537=2**16+1
二进制长度分别为a和b的数字相乘。结果的二进制位数为a+b-1和a+b
a位二进制长度的x与y相乘，所得结果的二进制位数为b位。那个y的二进制位数为b-a或b-a+1
n位二进制大于等于2的n-1次方小于2的n次方

```
# 计算一个十进制数的二进制位数
def bit_int(x):
  num=0
  while 1:
    if pow(2,num)<=x<pow(2,num+1):
      print(num+1)
      break
    else:
      num+=1
```
>参考资料
[NCTF2019]babyRSA
[NCTF2019]babyRSA
sympy库-GitHub

[BJDCTF2020]RSA

---

这题目条件好像给多了，方法应当不止一种。用RSA加密了两篇明文。第二篇中，明文m给了，密文c也给了，两个质数的乘积N也给了，然后e<100000。

于是根据等式c=pow(m,e,n)可以爆破出e
然后两篇加密的质数对中q还一样。两个N都给了，最大公约数就是q了，p也能根据n1算出来。然后r=(p-1)*(q-1)，知道e，r就可以根据逆元求d，d=gmpy2.invert(e,r)，然后此题就迎刃而解了
```

import gmpy2
import libnum
n1=13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
n2=12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
m2=libnum.s2n('BJD'*32)
c2=979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721
for e in range(10**4,10**5):        # 通过猜测进一步缩小e范围，e不会太小，所以舍弃了一部分
    if c2==pow(m2,e,n2):
        print(e)
        break
# 爆破得e=52361
q=gmpy2.gcd(n1,n2)
p=n1//q
r=(p-1)*(q-1)
d=gmpy2.invert(e,r)     # 第一篇加密的私钥d拿到
c=12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
m=pow(c,d,n1)
print(libnum.n2s(int(m)))


```
>参考资料
BUUCTF RSA题目全解2

[HDCTF2019]basic rsa

---

为数不多可以直接写出来的简单题

```

from gmpy2 import invert
import libnum
p=262248800182277040650192055439906580479
q=262854994239322828547925595487519915551
r=(p-1)*(q-1)
e=65533
d=invert(e,r)
c=27565231154623519221597938803435789010285480123476977081867877272451638645710
m=pow(c,d,p*q)
print(libnum.n2s(int(m)))


```
[BJDCTF2020]easyrsa

---

令人头秃，一堆不明所以的函数。。。
from fractions import Fraction中Fraction大概的作用就是输出一个最简分数
from sympy import Derivative中Derivative表示某函数关于某个变量的导数
用sympy中的diff函数可以进行求导操作，像这样：
```
import sympy
from sympy.abc import x
print(sympy.diff(sympy.atan(x),x))      # 1/(x**2 + 1)
```
然后百度了一下函数arth(x)的导数是1/(1-x**2)
所以z=p**2+q**2和n=p*q组成方程组求解就是了
```
from sympy import *
from gmpy2 import invert
import libnum
p=symbols('p')
q=symbols('q')
z=32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n=15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
ex_l=[p**2+q**2-z,p*q-n]   
end_data=solve(ex_l,[p,q])  # 有多组解，正负形式
for i in end_data:
    if i[0]>0 and i[1]>0:
        p=i[0]   
        q=i[0]   
        break               # 二元方程组会交换x，y的值再输出一遍，所以要break退出
e=65537
r=(p-1)*(q-1)
d=invert(e,int(r))
c=7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
m=pow(c,d,n)
print(libnum.n2s(int(m)))
```
>参考资料
arthx求导是什么
Python sympy.Derivative()用法及代码示例
Python 中fractions模块下Fraction函数使用方法
python求解多元多次方程组或非线性方程组

[NCTF2019]childRSA

---

我仿佛发现了什么绝妙的事情
```

from gmpy2 import invert
import libnum
p=178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139
q=184084121540115307597161367011014142898823526027674354555037785878481711602257307508985022577801782788769786800015984410443717799994642236194840684557538917849420967360121509675348296203886340264385224150964642958965438801864306187503790100281099130863977710204660546799128755418521327290719635075221585824217487386227004673527292281536221958961760681032293340099395863194031788435142296085219594866635192464353365034089592414809332183882423461536123972873871477755949082223830049594561329457349537703926325152949582123419049073013144325689632055433283354999265193117288252918515308767016885678802217366700376654365502867
r=(p-1)*(q-1)
e=0x10001
d=invert(e,r)
c=26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
m=pow(c,d,p*q)
print(libnum.n2s(int(m)))
```
至于这p和q咋来的，emmm，借助工具yafu
新建txt文件放入要进行因式分解的数，记得回车，键入命令后文本会被删除。。所以要做好备份
Windows终端输入`.\yafu-x64 "factor(@)" -batchfile 00.txt`
cmd命令行中输入`yafu-x64 "factor(@)" -batchfile n.txt`
数比较小的时候可以`yafu-x64 'factor(23333333333333)'`（受限于命令行输入限制）
>参考资料
BUUCTF RSA题目全解2
RSA因数分解工具yafu下载地址及使用方法介绍
工具yafu下载

---

后记：实际上大质数对乘积的分解还是很慢的。虽然不知道为什么这题目用yafu刚好很快就能算出结果来。也不知道yafu具体是怎样的一个算法。我用yafu试了一下上一道题目（[BJDCTF2020]easyrsa）的n的分解，目前跑了好几分钟还没有出结果。

[GWCTF 2019]BabyRSA

---

这题目给的大N可以直接用yafu-x64进行分解得到。总耗时13.4767 seconds。i5-1035G1，win11系统。

然后直接写代码就可以了。毕竟p和q都有了。
需要注意的是要用python写个二元的方程组求解。题目将flag分成了两个相等长度的字符串。
m1是两个字符串对应数字的和。m2是两个字符串对应数字的立方和
注意数据类型。剩下就都是以前的内容了
完整代码如下：
```
from gmpy2 import invert
from sympy import *
import libnum
p=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737
q=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
r=(p-1)*(q-1)
e=0x10001
d=int(invert(e,r))
# print(type(d))
c1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
c2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
m1=pow(c1,d,p*q)
m2=pow(c2,d,p*q)
x=symbols('x')
y=symbols('y')
ex_l=[x+y-m1,x**3+y**3-m2]  
data_xy=solve(ex_l,[x,y])
m1,m2=data_xy[0]  
print(libnum.n2s(int(m2))+libnum.n2s(int(m1)))     # b'GWHT{f709e0e2cfe7e530ca8972959a1033b2}'


```

[ACTF新生赛2020]crypto-rsa3

---

```

from gmpy2 import invert
import libnum
p=13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179293
q=13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179231
r=(p-1)*(q-1)
e=65537
d=int(invert(e,r))
c=1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049
m=pow(c,d,p*q)
print(libnum.n2s(m))


```

[NPUCTF2020]EzRSA

---

这题的n和gift都不太能用程序yafu进行质数分解。程序cpu的调度不是很激进，我挂后台一直算。大概有两个多小时，没有出结果

这题给了n。然后哦gift是两个素数（p，q）的欧拉函数的值（p-1和q-1）的最小公倍数
这个最小公倍数。很大。我们知道。两个数的最小公倍数和最大公约数的乘积是两个数的乘积（gcd(x,y)*lcm(x,y)=x*y）
所以最大公约数肯定不是特别大，就可以遍历暴力解决。目标应该是100以内差不多的样子
列方程组交给程序计算解决，然后p和q的值就都能求出来了。这里求解方程组还是用的sympy库
这题的坑点是，题目给的e不是素数！！

e=2∗27361

就tmd离谱哦。然后就出现e和r不互质的情况，正常些程序会报错e关于r的逆元不存在。
然后就需要用e//2来求那个d。所以就有c=pow(m,2*e,n)=pow(m**2,e,n)。所以就有m**2=pow(c,d,n)。求出来与明文有关的数字在进行字符串转换之前开个根号就是了
完整代码如下：
```

from sympy import *
from gmpy2 import invert,iroot
import libnum
x,y=symbols('x'),symbols('y')
n=17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
gift=2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104
for i in range(1,100):
    gcd_xy=i
    ex_l=[x*y-n,(x-1)*(y-1)-gift*gcd_xy
    jie=solve(ex_l,[x,y])
    if jie!=[]:
        # print(jie)
        # print(i)      # i=8,gcd_xy=8
        p,q=(int(i) for i in jie[0])
        break
e=54722
c=3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
r=(p-1)*(q-1)
d=invert(e//2,r)        # e不是素数
m=pow(c,d,n)
print(libnum.n2s(int(iroot(m,2)[0])))       # 数学变换


```

>参考资料
NPUCTF2020 EzRSA-cnblogs        注：不知道博客主给的gift的分解是怎么得到的

gmpy2常见函数使用