简单的模运算：

题面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from Crypto.Util.number import *
from libnum import *
from gmpy2 import *


flag = b'DASCTF{******}'
m1 = s2n(flag[0:21])
m2 = s2n(flag[21:])
# challenge_1
p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1*q1
e1 = getPrime(10)
e2 = getPrime(10)
c1=pow(m1,65537,n1)
hint1 = pow(e1*p1+q1,e2,n1)
hint2 = pow(p1+q1,e1,n1)

# challenge_2
p2 = getPrime(5120)
q2 = getPrime(512)
r = getPrime(512)
n2 = p2*q2*r
hint3 = pow((p2*q2**3 + r), p2, n2)
hint4 = pow(q2 + r,p2,n2)
hint5 = pow(r**2+1,m2,r**3)


print('n1 = ',n1)
print('e1 = ',e1)
print('e2 = ',e2)
print('c1 = ',c1)
print('hint2 = ',hint2)
print('hint1 = ',hint1)
print('n2 = ',n2)
print('hint3 = ',hint3)
print('hint4 = ',hint4)
print('hint5 = ',hint5)

'''
n1 =  59291291447490366931525634934604732490686993375526804349191888372804657968568621876626267171031639542229776816809231575682674990669907844507573323062869697381007018170369953528533225693260962158277876389797698421883811693774623191453338343873376809325940622690724742325375260783954612111771505452790833107433
e1 =  1009
e2 =  661
c1 =  42985353077188042701858678659683858628193880095538312019081971299029326751867795460043384534976482867850898695817341887974850615883707385265375936859975562647458644154098813749248370155445911231152202411316142174083125556302740642264129017638217154099365335103116579136478977445028803457714891387414804454563
hint2 =  40507463249661310357827794806044375677878316124571340628557074423085821966799760539750240709046644351970536177027127843527257097695964926292300842488261880439240179761636200128317742727421272586463218228015921971356760958631902559531017704907319793768862467740343002694370348402368271531907359292269313167594
hint1 =  1271005879853316066661199285969179445258555468409602536767308127422453124456569166278548456389424001236622134198431700958874184560969387121822195176467698604581027381830540104701755158555395105056691597754287953054854072522855420859550987917092786677237411037800799757596145745139003994853090852244952501770
n2 =  18907964900655384324579822409386633636878766956056871585535362235214353767231073564264059287914388330411792102199606677008933621408085966756951588469677351070820733406746369679198435269992553170199992317543151904463295431360000467944654613563212110648427484740736780335622922770497302516605477200091994280170659051797483082932715112295285374951466772664058673174457133774539371864037823431076085535646866492867565053211399132137624309571702027870497719709848105717638061824558263209029252939242634210549580025431343041421766587111257036497372428545483704784943228958032869014014563237034417269447643411742587366522581092247139356905151503074118950953726319892565456479517718514001822091970116274032235077283171573739409327260871369017093426482435098823654221146125974831336950435699141428482689352594911360748437075413924102074118643817682988301168832491421799525827632647293700871699768251822202064478207264310344710162587091114198326722398521534722836191900118919600325987668228334387274131745452370144048469165896152934265086085786170745300044244328435656038364921390878141315764940004361350568616343868964642155971232793094529961537868556317288317761237430569785361173933724010332338240102029231307867651913780873895463922404696220328907265969090667253011075715302423364798124784791540343259221981176571491275777227356362593241763735078774750032170810209648159443012857333801615838630780060716065099646497273032317098446052746729617067928763959393487041510168193671378036773409927475705441371588922269531683087325413686315760604906941830110671649667896262119795185372459800672732201403353796496975239081396680894282951703497436899157694531797901273547022181574313676236049710129802224469486290831758140772148263506850711301689866687921384434558768919627058698246307704127709329632785782812326088967419473252484748677712381933762265715476433475653
hint3 =  9939018467626296300864549557153960485816202060115441771858993139956001568094397129213688325169848929397519454556265038265085753791012239390847499832076142790537570688728474176390891119329028306138917962137940523721411683756694953004757356322832322272044727574511946615053360780724964403109981221038321150251912087095566788471973368735984926133539004913163814796547521685779553548417828006578689568287135076606657942555780079060666398892624634539284576783451146414121481315811210373744629102035041262128288541384833388244359092650525684510233998198648220188818529696044589322103131713532522087913277853687802387823370812184861308056607206704924142111163623647400386387795315156552323415775302567837608141240660791558895222250523472575523943334805729177781503647940132538364353380916295244903544529895988952519161034077133368918033027698840291604695794239996491625350827193007237672555853711676946280455422865857083520387962904612732978811244632662722516874510663815000407442709650546583427701935634421822920667340400344464560819496241832753100346158973730178944583819434570015364985334123682718945396012714833234814138060680879946683598382558581755464432848629830671740874556822495651590292355132309556201503702994218748824342270746121842337819752324099307642066174745872761074064496053960340396957873940843698476902239785513353538575271300199803656708789414583304212919858466476111752009816249691548012011325635726932007337584928654763601504911235883280784689919453164650180423494792012285026508211938647974660637499188015435581876228505538395991613265963363970634342709084117396030961729066498695271401095219781344237736883159601430790828530656828799412179649742014177933116928065839153385688599329261957525423958781720021524864279277040500534782586037303978447982579881703150864520067784227584088469267877647284326147128663307302461696049106379396
hint4 =  11497927853957540365332790665731275206952151206861039571536392062632509295957449992678521695139160324432572043863866571073273424766195027066994928026020365890447586873438730677930838694248463784234422970896904779315141100899548415386962349420861970235250438845409060098489028828677789310690303276268227293420117427555062211347687022376226002772552572846005575907377875069559346178573605837280707896716903996273437999304784804469148200034055401729899984732371826562249893238400736560876412526076698397150716407768045925783960626076975474775287357623238930181817744888057241082587725853888247069373763616410186825446631363893872367121719099675878971215427631753890480342562281509217650841316549477101278836516712239644946591434882047908159355119724740895836970093220436696609508084144405957119864577550601265078506824881563233145601502789276574964256487656042156050790935757687533400014492738943377035151940053902285169162559415884261670006407914345470020985548114750984409094762491065523701667910143102554492295526746294891248183460488516919232107982441935261002056298051839186448002917036315086702724337403007094283544108605752353892969499338937456927473502637574082273446631592875576206457590873417790534425052375523311069970894661662935504029122498888677579838832589434264156033809784824308541883139057067073172969579383284214906496081973100504512465134008311849499410830926217663692810810073433508445528894019031624950077917834721653995486872359322444973369269957808220204120434820049177595069822767774880891475045042506316778272385296785381694201967451988353025446019210309412684814041807087081841227290094176745748423008005181412793105824372881451510867905760386180468940263583834371726883151840358399349831450242497969453799407724511831157375792268531837507107779497339624673256413930993867285692700231244480782493119378673295412687014852050209
hint5 =  734693499178140709107482184121639881311481497449164451247514670640712514605734040224535011153519609835276802031782238154113623838563165860055971999265801692161249909520059287311664417036724025637099701450424590923727907132999019020950844342934742235333060614209179570928227493575110697506644022234765949969346518432653798426853947974772328105759741384608693269694

'''

分析：

第一部分：
$$
hint1 = (e1*p1+q1)^{e2}\ mod\ n1\
hint2 = (p1+q1)^{e1}\ mod\ n1
$$

$$
先二项式展开得到：\
hint1 = (e1p1)^{e2}+(q1)^{e2}\ mod\ n1\
hint2 = (p1)^{e1}+(q1)^{e1}\ mod\ n1\
凑项：\
hint1^{e1} = (e1p1)^{e1e2}+(q1)^{e1e2}\ mod\ n1\
hint2^{e2} = (p1)^{e1e2}+(q1)^{e1e2}\ mod\ n1\
e1^{e1e2 }hint2^{e1}=(e1p1)^{e1e2}+(e1q1)^{e1e2}\ mod\ n1\
则有：
e1^{e1e2 }hint2^{e1}-hint1^{e1}=0\mod\ q
$$

第二部分：
$$
hint3 = (p2*{q2}^3+r)^{p2}\ mod\ n2\
hint4 = (q2+r)^{p2}\ mod\ n2\
hint5 = (r^2+1)^{m2}\ mod\ r^3
$$

$$
先用费马小定理简化：\
hint3=r\ \ mod\ p2\
hint4=q2+r\ \ mod\ p2\
则有：\
hint4-hint3=0 \ mod\ q2
$$

$$
且有hint4-hint3-q2=0 \ mod\ p2\
这里与n2取最大公因数发现得到的是p2*q2\
r = n2//p2//q2\
对于hint5 = (r^2+1)^{m2}\ mod\ r^3\
直接二项式展开：\
(r^2+1)^{m2}=\sum_{k=0}^{m2}\begin{pmatrix}m2\k\end{pmatrix}(r^2)^{m2-k}1^k=\sum_{k=0}^{m2}\begin{pmatrix}m2\k\end{pmatrix}r^{2(m2-k)}\
因为在模r^3这个原则下，我们仅保留r^0,r^1,r^2的系数，\因此，我们需要计算2(m2-k)小于或等于2时的项\
(1)当k=m2时，2(m2-m2)=0,得到常数项1\
(2)当k=m2-1时，2（m2-(m2-1))=2，我们得到r^2的系数位为\begin{pmatrix}m2\k\end{pmatrix}=m2\
所以得到最终结果：\
(r^2+1)^{m2}\ \ mod\ r^3 = 1+m_2r^2
$$

所以：
$$
m2 = (hint5-1)//r^2
$$

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import *
from tqdm import *
from gmpy2 import *

n1 =  59291291447490366931525634934604732490686993375526804349191888372804657968568621876626267171031639542229776816809231575682674990669907844507573323062869697381007018170369953528533225693260962158277876389797698421883811693774623191453338343873376809325940622690724742325375260783954612111771505452790833107433
e1 =  1009
e2 =  661
c1 =  42985353077188042701858678659683858628193880095538312019081971299029326751867795460043384534976482867850898695817341887974850615883707385265375936859975562647458644154098813749248370155445911231152202411316142174083125556302740642264129017638217154099365335103116579136478977445028803457714891387414804454563
hint2 =  40507463249661310357827794806044375677878316124571340628557074423085821966799760539750240709046644351970536177027127843527257097695964926292300842488261880439240179761636200128317742727421272586463218228015921971356760958631902559531017704907319793768862467740343002694370348402368271531907359292269313167594
hint1 =  1271005879853316066661199285969179445258555468409602536767308127422453124456569166278548456389424001236622134198431700958874184560969387121822195176467698604581027381830540104701755158555395105056691597754287953054854072522855420859550987917092786677237411037800799757596145745139003994853090852244952501770
n2 =  18907964900655384324579822409386633636878766956056871585535362235214353767231073564264059287914388330411792102199606677008933621408085966756951588469677351070820733406746369679198435269992553170199992317543151904463295431360000467944654613563212110648427484740736780335622922770497302516605477200091994280170659051797483082932715112295285374951466772664058673174457133774539371864037823431076085535646866492867565053211399132137624309571702027870497719709848105717638061824558263209029252939242634210549580025431343041421766587111257036497372428545483704784943228958032869014014563237034417269447643411742587366522581092247139356905151503074118950953726319892565456479517718514001822091970116274032235077283171573739409327260871369017093426482435098823654221146125974831336950435699141428482689352594911360748437075413924102074118643817682988301168832491421799525827632647293700871699768251822202064478207264310344710162587091114198326722398521534722836191900118919600325987668228334387274131745452370144048469165896152934265086085786170745300044244328435656038364921390878141315764940004361350568616343868964642155971232793094529961537868556317288317761237430569785361173933724010332338240102029231307867651913780873895463922404696220328907265969090667253011075715302423364798124784791540343259221981176571491275777227356362593241763735078774750032170810209648159443012857333801615838630780060716065099646497273032317098446052746729617067928763959393487041510168193671378036773409927475705441371588922269531683087325413686315760604906941830110671649667896262119795185372459800672732201403353796496975239081396680894282951703497436899157694531797901273547022181574313676236049710129802224469486290831758140772148263506850711301689866687921384434558768919627058698246307704127709329632785782812326088967419473252484748677712381933762265715476433475653
hint3 =  9939018467626296300864549557153960485816202060115441771858993139956001568094397129213688325169848929397519454556265038265085753791012239390847499832076142790537570688728474176390891119329028306138917962137940523721411683756694953004757356322832322272044727574511946615053360780724964403109981221038321150251912087095566788471973368735984926133539004913163814796547521685779553548417828006578689568287135076606657942555780079060666398892624634539284576783451146414121481315811210373744629102035041262128288541384833388244359092650525684510233998198648220188818529696044589322103131713532522087913277853687802387823370812184861308056607206704924142111163623647400386387795315156552323415775302567837608141240660791558895222250523472575523943334805729177781503647940132538364353380916295244903544529895988952519161034077133368918033027698840291604695794239996491625350827193007237672555853711676946280455422865857083520387962904612732978811244632662722516874510663815000407442709650546583427701935634421822920667340400344464560819496241832753100346158973730178944583819434570015364985334123682718945396012714833234814138060680879946683598382558581755464432848629830671740874556822495651590292355132309556201503702994218748824342270746121842337819752324099307642066174745872761074064496053960340396957873940843698476902239785513353538575271300199803656708789414583304212919858466476111752009816249691548012011325635726932007337584928654763601504911235883280784689919453164650180423494792012285026508211938647974660637499188015435581876228505538395991613265963363970634342709084117396030961729066498695271401095219781344237736883159601430790828530656828799412179649742014177933116928065839153385688599329261957525423958781720021524864279277040500534782586037303978447982579881703150864520067784227584088469267877647284326147128663307302461696049106379396
hint4 =  11497927853957540365332790665731275206952151206861039571536392062632509295957449992678521695139160324432572043863866571073273424766195027066994928026020365890447586873438730677930838694248463784234422970896904779315141100899548415386962349420861970235250438845409060098489028828677789310690303276268227293420117427555062211347687022376226002772552572846005575907377875069559346178573605837280707896716903996273437999304784804469148200034055401729899984732371826562249893238400736560876412526076698397150716407768045925783960626076975474775287357623238930181817744888057241082587725853888247069373763616410186825446631363893872367121719099675878971215427631753890480342562281509217650841316549477101278836516712239644946591434882047908159355119724740895836970093220436696609508084144405957119864577550601265078506824881563233145601502789276574964256487656042156050790935757687533400014492738943377035151940053902285169162559415884261670006407914345470020985548114750984409094762491065523701667910143102554492295526746294891248183460488516919232107982441935261002056298051839186448002917036315086702724337403007094283544108605752353892969499338937456927473502637574082273446631592875576206457590873417790534425052375523311069970894661662935504029122498888677579838832589434264156033809784824308541883139057067073172969579383284214906496081973100504512465134008311849499410830926217663692810810073433508445528894019031624950077917834721653995486872359322444973369269957808220204120434820049177595069822767774880891475045042506316778272385296785381694201967451988353025446019210309412684814041807087081841227290094176745748423008005181412793105824372881451510867905760386180468940263583834371726883151840358399349831450242497969453799407724511831157375792268531837507107779497339624673256413930993867285692700231244480782493119378673295412687014852050209
hint5 =  734693499178140709107482184121639881311481497449164451247514670640712514605734040224535011153519609835276802031782238154113623838563165860055971999265801692161249909520059287311664417036724025637099701450424590923727907132999019020950844342934742235333060614209179570928227493575110697506644022234765949969346518432653798426853947974772328105759741384608693269694

kq1 = pow(e1,e1*e2)*pow(hint2,e2)-pow(hint1,e1)
q1 = GCD(kq1,n1)

q1 = 7917962325456189465321175948354190952370872015463405092526291425554667011157024195680710886921609504823633281750265733453692080653143784217220777931558171
p1 = n1//q1
phi1 = (p1-1)*(q1-1)
d1 = invert(65537,phi1)

m1 = pow(c1,d1,n1)

print(long_to_bytes(m1))

q2 = GCD(hint4-hint3,n2)
p2 = GCD(hint4-hint3-q2,n2)//q2
print(isPrime(p2))

r = n2//p2//q2
m2 = (hint5-1)//r**2
print(long_to_bytes(m2))
#DASCTF{0e88f0e0-f18d-11ee-a56a-38f3abddb69b}