RSA数论合集
题目-1
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
flag = "******"
e = 65537
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m, e, n)
hint = pow(2025 * p + 114514, q, n)
print("n =",n)
print("c =",c)
print("hint =",hint)
"""
n = 16424239302340955387862050329463308924648129588882906961772049940910037565420816272539693065728959547323880652178860068400621815213066789286978516457054723083188713494314542868491165337122492361221396030563451750104982561848545159852192164627168202009698162269975689552602886494778668537452967836770257917647341484785398045004982781618073719820649377220959440378673557066864191240734776357511608649230606325975010543181655546794723388678505127265797095215011470094099605236108170748884264890636167714143368272725898015519824530585278788005826945310433188903230059691490523881360414184871282847626976579925213959555553
c = 13838356945888210116011004644343565367202153766573634269175020737677381455152711896489133258090744204587580613298484055754389031598038328114501008944943438878142581894202416918737392508134449644574468691237037473600935223114770348933813008219275996814918471712220063341472083558279532591252182343717542367588579635717061551707120891711534343333594313376926197607544416351288665003994633549253447256192271627827844500571390502242201953263275248784446546433729218679108020819638890571999577127759411732118436300207189633997165805245018586264551649978164336676117680468323308841800795530841317945349730464909187592182222
hint = 10011920465853899201833186656022447035612931813999145983965135485208588109154235030606164170627001061949087940537746179537518196036243834496778762986726242407813418722121070844827026254201836020192132664666136114726908625043899818906791283743727000499479048011585751410564335483747838251747570544498669240868445876059317285109966133255283293867527101301812599290480927568925517338882657349371616003247300970216051190084469363644986486298699980311717636494588032997458038135861717437952962139745076501567795028485426981061417912656932316865497844046838926054860553523491592498256870154598863220290673481363886570740206
"""思路
- @@ 费马小定理:如果 $p$ 是一个素数,且 $a$ 是一个整数,满足 $a$ 不能被 $p$ 整除(即 $a$ 和 $p$ 互素),那么有 $a^{p-1} \equiv \pmod p$
- 已知
hint = (2025*p + 114514)^q mod p - 由于
2025*p是p的倍数,所以2025*p ≡ 0 mod p - 根据费马小定理得
hint = 114514^q + k1*p - 则
114514^q = hint - k1*p - 两边同时乘
p的幂(114514^q)^p = (hint - k1*p)^p 114514^n = p*(.....) + hint^p => 114514^n = hint^p mod p = hint- 假设
114514^n ≡ hint mod p,这意味着p整除114514^n−hint,如果我们进一步假设114514^n ≡ hint mod q,那么q也整除114514^n−hint,因此,n=p*q也整除114514^n−hint - 所以
GCD(pow(114514,n,n)−hint,n),我们实际上是在寻找n和114514^n−hint的最大公约数,由于n整除114514^n−hint,这个最大公约数至少是p或q中的一个
解答-1
from Crypto.Util.number import *
from gmpy2 import *
n = 16424239302340955387862050329463308924648129588882906961772049940910037565420816272539693065728959547323880652178860068400621815213066789286978516457054723083188713494314542868491165337122492361221396030563451750104982561848545159852192164627168202009698162269975689552602886494778668537452967836770257917647341484785398045004982781618073719820649377220959440378673557066864191240734776357511608649230606325975010543181655546794723388678505127265797095215011470094099605236108170748884264890636167714143368272725898015519824530585278788005826945310433188903230059691490523881360414184871282847626976579925213959555553
c = 13838356945888210116011004644343565367202153766573634269175020737677381455152711896489133258090744204587580613298484055754389031598038328114501008944943438878142581894202416918737392508134449644574468691237037473600935223114770348933813008219275996814918471712220063341472083558279532591252182343717542367588579635717061551707120891711534343333594313376926197607544416351288665003994633549253447256192271627827844500571390502242201953263275248784446546433729218679108020819638890571999577127759411732118436300207189633997165805245018586264551649978164336676117680468323308841800795530841317945349730464909187592182222
hint = 10011920465853899201833186656022447035612931813999145983965135485208588109154235030606164170627001061949087940537746179537518196036243834496778762986726242407813418722121070844827026254201836020192132664666136114726908625043899818906791283743727000499479048011585751410564335483747838251747570544498669240868445876059317285109966133255283293867527101301812599290480927568925517338882657349371616003247300970216051190084469363644986486298699980311717636494588032997458038135861717437952962139745076501567795028485426981061417912656932316865497844046838926054860553523491592498256870154598863220290673481363886570740206
e = 65537
p = GCD(pow(114514, n, n) - hint, n)
q = n // p
d = inverse(e, (p - 1) * (q - 1))
flag = long_to_bytes(pow(c, d, n))
print(flag)
#qqqy{d0_y0u_like_th1S_ferm4t_th1nKing?}题目-2
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
flag = "******"
e = 65537
m = bytes_to_long(flag.encode())
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m, e, n)
hint = pow(1234 * p + 14723333, e, n)
print("n =", n)
print("c =", c)
print("hint =", hint)
"""
n = 21563748218649522293515458416300844508649432411194562048776696617037098337786871975314008116724088874944622354907335208152199845597235576952219057728628348296526373113909683233675251171684719578502863977765773467315186165700924613275161151242934919456515005432062607123880568384913305467286377842926240014379444989779943840802547873724941397202008993345358505607018180524796892666811959504916496694315491406923426424004857659404371687191818417147067023242708678847271091652667261349191206260760005439197063265422606209444937539304759062043997939121804681827501736683404527934457987220269157282566292328379350083406723
c = 19975345430162252289239628687704846844292439201301981636174554075191968786420819803191837624049548476640021286249879622872050008540089941885072624195559076050100284821542047130690088670449651535047189624369653369894492000010200613095537236682732539890391548835519670384016401642487364592932054739669385496156461820263228775518082444608622351000523582534189735835583371403873993488431358569523688907388525458106154227849288805474790649366618367804315266589755847817259786848281333568062762416922069930219158201605637168744408943006373814146224528082926865097625670298358627575869602969871167375445828391890774496005015
hint = 1915330880182243444603869091210811267520377135663756420146968183966218753804613947507356809874462006272517685871046960089033580747143048214739290440618792352076015562022459223773623041155653494552585115481711825183116198817882740362683677622637196277040567737602279166014858546656163265624678568138459250221544484427437686585614844009508150958201904801356328466875151496446736655433378156579012049512170004927415581306213091680509183748182783784930260367458776303133356532912108154950249008326287395235105289974144421001362612341955791032997816703116525796420144176365375374290555777259149975478821111992389187254628
"""思路
- 相较于上一题这里就是把
hint = pow(a * p + b, q, n)中的q换成了e
解答-2
from Crypto.Util.number import *
from gmpy2 import *
n = 21563748218649522293515458416300844508649432411194562048776696617037098337786871975314008116724088874944622354907335208152199845597235576952219057728628348296526373113909683233675251171684719578502863977765773467315186165700924613275161151242934919456515005432062607123880568384913305467286377842926240014379444989779943840802547873724941397202008993345358505607018180524796892666811959504916496694315491406923426424004857659404371687191818417147067023242708678847271091652667261349191206260760005439197063265422606209444937539304759062043997939121804681827501736683404527934457987220269157282566292328379350083406723
c = 19975345430162252289239628687704846844292439201301981636174554075191968786420819803191837624049548476640021286249879622872050008540089941885072624195559076050100284821542047130690088670449651535047189624369653369894492000010200613095537236682732539890391548835519670384016401642487364592932054739669385496156461820263228775518082444608622351000523582534189735835583371403873993488431358569523688907388525458106154227849288805474790649366618367804315266589755847817259786848281333568062762416922069930219158201605637168744408943006373814146224528082926865097625670298358627575869602969871167375445828391890774496005015
hint = 1915330880182243444603869091210811267520377135663756420146968183966218753804613947507356809874462006272517685871046960089033580747143048214739290440618792352076015562022459223773623041155653494552585115481711825183116198817882740362683677622637196277040567737602279166014858546656163265624678568138459250221544484427437686585614844009508150958201904801356328466875151496446736655433378156579012049512170004927415581306213091680509183748182783784930260367458776303133356532912108154950249008326287395235105289974144421001362612341955791032997816703116525796420144176365375374290555777259149975478821111992389187254628
e = 65537
p = gcd(pow(14723333,e,n)-hint,n)
phi = (p-1)*(n // p-1)
d = inverse(e,phi)
flag = long_to_bytes(pow(c, d, n))
print(flag)
#qqqy{D0_y0U_l1kE_th1S_f\xcf\x86rm4t_pro_th1nkIng?}
#qqqy{D0_y0U_l1kE_th1S_fφrm4t_pro_th1nkIng?}题目-3
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
flag = '******'
m = bytes_to_long(flag.encode())
p = getPrime(1024)
q = getPrime(1024)
n = p * q
hint1 = pow(m, p, n)
hint2 = pow(m, q, n)
print("n =", n)
print("hint1 =", hint1)
print("hint2 =", hint2)
"""
n = 22298541722045020729319440426369433596799307987762344185862716383431376538967811698202949575549360749626221935332806097505158938090923071438645599291030495034203094087097312185806556069059569633738070693997409308709231580218238225538543307992988182395961766558478322196641333531638190964618176277251206183437791565196115139402911558725264751216576620594866002551939872338386604325059715119828401498698494745435763618295783469906759854637564589207411725948033500924093549789353761050278471358887490128731198345292641427028788639525231951638189707419039581304799962829378237703109454472110823449125524221126567905775963
hint1 = 15821652379078695857111146401130092201656370213247671354989815334385534623458867920262190085707681497166385000409185727894496687159339471243597036591102906040630980987178129520499083699877031503988667007914612504036011545303286704046027037097108539301511170352290662170479937690860141646397490868928090883176133282575506966365751603787820285939425103536667349104914371410466626082740343997894676281629895944437954136697495521068024992537938169231133282239396136137411011138438810930513734196924433577263207605684514853232383231314170488993873140144838962070628453059382322056902445122664041287174355223774507577068507
hint2 = 3621257637932239525203884275810195823723844807080238450686435723973333370935233264321518005102584782808412330392389285423730793823453389019228215683334181053141594950746200839470020360785327887726286981541583348515749727928242993306108653737461558969692030259008959367832264894584664141645273295076083724662378007430806070522623535015543735649784796967290421810802334037147094746532335291247234119124925343221443628343685379351143218723796833585641809642590313670530705506056930689366122192837356187462137250752795946183581425071480751332763429816223575210766161317751099248127510774237957350209870398735718485069287
"""思路
- 费马定理约约约
- 最后CRT求解明文
解答-3-1
from Crypto.Util.number import *
from gmpy2 import *
n = 22298541722045020729319440426369433596799307987762344185862716383431376538967811698202949575549360749626221935332806097505158938090923071438645599291030495034203094087097312185806556069059569633738070693997409308709231580218238225538543307992988182395961766558478322196641333531638190964618176277251206183437791565196115139402911558725264751216576620594866002551939872338386604325059715119828401498698494745435763618295783469906759854637564589207411725948033500924093549789353761050278471358887490128731198345292641427028788639525231951638189707419039581304799962829378237703109454472110823449125524221126567905775963
hint1 = 15821652379078695857111146401130092201656370213247671354989815334385534623458867920262190085707681497166385000409185727894496687159339471243597036591102906040630980987178129520499083699877031503988667007914612504036011545303286704046027037097108539301511170352290662170479937690860141646397490868928090883176133282575506966365751603787820285939425103536667349104914371410466626082740343997894676281629895944437954136697495521068024992537938169231133282239396136137411011138438810930513734196924433577263207605684514853232383231314170488993873140144838962070628453059382322056902445122664041287174355223774507577068507
hint2 = 3621257637932239525203884275810195823723844807080238450686435723973333370935233264321518005102584782808412330392389285423730793823453389019228215683334181053141594950746200839470020360785327887726286981541583348515749727928242993306108653737461558969692030259008959367832264894584664141645273295076083724662378007430806070522623535015543735649784796967290421810802334037147094746532335291247234119124925343221443628343685379351143218723796833585641809642590313670530705506056930689366122192837356187462137250752795946183581425071480751332763429816223575210766161317751099248127510774237957350209870398735718485069287
p = gcd(pow(hint1,n,n)-hint2, n)
q = n // p
def CRT(hint1, hint2, p, q):
n = p * q
a = hint1 % p
b = hint2 % q
p_inv_mod_q = inverse(p, q)
q_inv_mod_p = inverse(q, p)
m = (a * q * q_inv_mod_p + b * p * p_inv_mod_q) % n
return m
m = CRT(hint1, hint2, p, q)
flag = long_to_bytes(m)
print(flag)
#qqqy{D0_y0U_l1kE_th1S_ferm4t_pro_m4x_th1nkIng?_hahaha1145141919810}解答-3-2
$c1=pow(m,p,n)=m^p \bmod (pq)$ , $c2=pow(m,q,n)=m^q \bmod (pq)$
由费马小定理: $a^{(p-1)}≡1 \bmod p$ 进一步推导可得 $a^p≡a \bmod p$
则 $m^p≡m \bmod p$ , $m^q≡m \bmod q$ ,那么有
$m^p=m+k1p$ $m^q=m+k2q$
进而有
$c1=m^p \bmod (pq)=(m+k1p) \bmod (pq)=m+k1p+k3pq$
$c2=m^q \bmod (pq)=(m+k2q) \bmod (pq)=m+k2q+k4pq$
可以构造
$c1+c2=m+k1p+k3pq+m+k2q+k4pq=2m+(k1p+k3pq+k2q+k4pq)$
$c1c2=(m+k1p+k3pq)(m+k2q+k4pq)=m^2+(k1p+k3pq+k2q+k4pq)m+(k1p+k3pq)(k2q+k4pq)$
$(c1+c2)m=2m^2+(k1p+k3pq+k2q+k4pq)m$
则有
$c1c2-(c1+c2)m=-m^2+(k1p+k3pq)(k2q+k4pq)$ => $m^2-(c1+c2)m+c1c2=(k1p+k3pq)(k2q+k4pq)$
至此,我们构成了模多项式 $m^2-(c1+c2)m+c1c2$
from Crypto.Util.number import long_to_bytes
c1 = 15821652379078695857111146401130092201656370213247671354989815334385534623458867920262190085707681497166385000409185727894496687159339471243597036591102906040630980987178129520499083699877031503988667007914612504036011545303286704046027037097108539301511170352290662170479937690860141646397490868928090883176133282575506966365751603787820285939425103536667349104914371410466626082740343997894676281629895944437954136697495521068024992537938169231133282239396136137411011138438810930513734196924433577263207605684514853232383231314170488993873140144838962070628453059382322056902445122664041287174355223774507577068507
c2 = 3621257637932239525203884275810195823723844807080238450686435723973333370935233264321518005102584782808412330392389285423730793823453389019228215683334181053141594950746200839470020360785327887726286981541583348515749727928242993306108653737461558969692030259008959367832264894584664141645273295076083724662378007430806070522623535015543735649784796967290421810802334037147094746532335291247234119124925343221443628343685379351143218723796833585641809642590313670530705506056930689366122192837356187462137250752795946183581425071480751332763429816223575210766161317751099248127510774237957350209870398735718485069287
n = 22298541722045020729319440426369433596799307987762344185862716383431376538967811698202949575549360749626221935332806097505158938090923071438645599291030495034203094087097312185806556069059569633738070693997409308709231580218238225538543307992988182395961766558478322196641333531638190964618176277251206183437791565196115139402911558725264751216576620594866002551939872338386604325059715119828401498698494745435763618295783469906759854637564589207411725948033500924093549789353761050278471358887490128731198345292641427028788639525231951638189707419039581304799962829378237703109454472110823449125524221126567905775963
PR.<m> = PolynomialRing(Zmod(n))
f = m^2-(c1+c2)*m+c1*c2
x0 = f.small_roots(X=2^535)
print(x0)
#[99681815868725503471927605308712871349467969282956996980489165777622113777147715733156420694651307076913359009165173559761967019247931654984900533054018581246077]
print(long_to_bytes(int(x0[0])))
#qqqy{D0_y0U_l1kE_th1S_ferm4t_pro_m4x_th1nkIng?_hahaha1145141919810}题目-4
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
flag = '******'
m = bytes_to_long(flag.encode())
p = getPrime(1024)
q = getPrime(1024)
e = 65537
n = p*q
hint1 = pow(2025*p+2024*q, 1140, n)
hint2 = pow(2024*p+2025*q, 5140, n)
c = pow(m, e, n)
print("n =", n)
print("c =", c)
print("hint1 =", hint1)
print("hint2 =", hint2)
"""
n = 26601860753512582644521788861211507464857025777305967483443237218482913123624339698252520560929143417687962914590510743868795842955437526899764917011644002303366616355906264113683450437362198255748657014391308415847921128961375264362691493181906066619794112799308024513672228138395822888371235336459797462984348981879775439486172476857393893279009825373781820869318142473401187282160933057166976490254754188166397173581901999799417805809151440970722846936696316789830389418053172432146556013029515653061238296053774789312417000010410319995038994209977315853478743364494214025090679505819412374295813469102726093005679
c = 1691507981973025375530919247330700310897951983770012688942983782563981419174950233586519702824663477642719864292562003317515466995418187393362570600583794831093165991997026328585907806310474606499092966020109041719241992876734091586854637763363629011381704594140443541561063678797789714693637539131443956967040090361567724663680119694577570782784657088032952824849076725840870308908288147377569944978348585450905077311616384563360505620381520673944785079802919825846410398348369154652312854223489663876095735952970141764394997989683479516914741154244723325049099612472204934986860064724278729881794745118367496791814
hint1 = 21201327117676904720045132915983802738525010763693881767339395453523890072335129057766736861243571091353909371022104321476639417918705909061232710321939002407979929100496213849490299883206901522991611887382115189849615192818926384663984435331927792669193804702271066361667925198968895100939133247420796138224799821378653170934462230817060953532184024168106429086149800856398030429897301921294889337575013299223994689986374361156908232698053146616877198267139755577837645706145181398584585055185345924339769051284132878545188557813123656429077856687731027784075468399752750085148999073331475064395294551226908948726721
hint2 = 20359677991122628886246843451991462318260549672910971418858580857777170995572510452288238565445539266511545071236507666704446050130903503364274990336083571321707059076364832555629954910120215850595565753328442061497526032616139003944508070129664650293123793984170917884470936013229095795238414928905579908135588501049540136500148552178958544464866611232256547741180045324906493226180619001361198251781168983942569702089485047442808875223604918172413057015760327820514116085525430403721170621147114074052186939903945669151692019886231672436594407230036828887303742969084685554445653362423854655392613322470309085295269
"""思路
- 大胆约分!
- 核心思想依旧参考第一个的费马小定理
解答-4
from Crypto.Util.number import *
from gmpy2 import *
n = 26601860753512582644521788861211507464857025777305967483443237218482913123624339698252520560929143417687962914590510743868795842955437526899764917011644002303366616355906264113683450437362198255748657014391308415847921128961375264362691493181906066619794112799308024513672228138395822888371235336459797462984348981879775439486172476857393893279009825373781820869318142473401187282160933057166976490254754188166397173581901999799417805809151440970722846936696316789830389418053172432146556013029515653061238296053774789312417000010410319995038994209977315853478743364494214025090679505819412374295813469102726093005679
c = 1691507981973025375530919247330700310897951983770012688942983782563981419174950233586519702824663477642719864292562003317515466995418187393362570600583794831093165991997026328585907806310474606499092966020109041719241992876734091586854637763363629011381704594140443541561063678797789714693637539131443956967040090361567724663680119694577570782784657088032952824849076725840870308908288147377569944978348585450905077311616384563360505620381520673944785079802919825846410398348369154652312854223489663876095735952970141764394997989683479516914741154244723325049099612472204934986860064724278729881794745118367496791814
hint1 = 21201327117676904720045132915983802738525010763693881767339395453523890072335129057766736861243571091353909371022104321476639417918705909061232710321939002407979929100496213849490299883206901522991611887382115189849615192818926384663984435331927792669193804702271066361667925198968895100939133247420796138224799821378653170934462230817060953532184024168106429086149800856398030429897301921294889337575013299223994689986374361156908232698053146616877198267139755577837645706145181398584585055185345924339769051284132878545188557813123656429077856687731027784075468399752750085148999073331475064395294551226908948726721
hint2 = 20359677991122628886246843451991462318260549672910971418858580857777170995572510452288238565445539266511545071236507666704446050130903503364274990336083571321707059076364832555629954910120215850595565753328442061497526032616139003944508070129664650293123793984170917884470936013229095795238414928905579908135588501049540136500148552178958544464866611232256547741180045324906493226180619001361198251781168983942569702089485047442808875223604918172413057015760327820514116085525430403721170621147114074052186939903945669151692019886231672436594407230036828887303742969084685554445653362423854655392613322470309085295269
e = 65537
kq = pow(2025, 1140 * 5140, n)*pow(hint2, 1140, n) - pow(2024, 1140 * 5140, n)*pow(hint1, 5140, n)
q = gcd(kq, n)
phi = (q - 1) * (n // q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#qqqy{d0_YoU_L1kE_Th15_ferm4t_prO_MAX_Ultr4_th1nkIng?_clx(Z51)}题目-5
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
flag="******"
m = bytes_to_long(flag.encode())
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
M = 2025 * m * 5202 * p
c = pow(M,e,n)
print('c =',c)
print('n =',n)
'''
c = 15078515245173533989657997953126994539772196781684668696473708214369797328819315589725685481469201279669776887187974179463866017302106600417464318582930433286473078640667107972074325035317761256817589163479445872422831666364602990727216559809099990199040944425235742916615076737732277246774322736162989433178783810153225888473399818063828824691811491957160579470290053967575045520007195347455944955901408826846538313011478816218826474871102659647268875201229646337822445145926368588805750579436953373238191906852446926045125287861161146836140737171625078171179604070335098276889575163999828471394777707470201216141521
n = 15322272212735350583630656956849788767557816261451276606126655490671547645090195767321995274956834278205170493308077101667903197693638025255834670553666202140296272141229231610687364013328949784429440542409036037896945255565851887406988287570391982459438193193424075852393394197396518036802912563346646607600590001358848556761273388103331259687461065291064140642734342415813599880317328301015095829452739540323870738420591179951496780115595461274525286565040995485119519627357413603923885798242267310864496365149627782683591003948367498280561484842151200003157997627658165367189995930841250484111112116483610630063381
'''思路
n与c有公因子p- gcd即可
解答-5
from Crypto.Util.number import *
from gmpy2 import *
c = 15078515245173533989657997953126994539772196781684668696473708214369797328819315589725685481469201279669776887187974179463866017302106600417464318582930433286473078640667107972074325035317761256817589163479445872422831666364602990727216559809099990199040944425235742916615076737732277246774322736162989433178783810153225888473399818063828824691811491957160579470290053967575045520007195347455944955901408826846538313011478816218826474871102659647268875201229646337822445145926368588805750579436953373238191906852446926045125287861161146836140737171625078171179604070335098276889575163999828471394777707470201216141521
n = 15322272212735350583630656956849788767557816261451276606126655490671547645090195767321995274956834278205170493308077101667903197693638025255834670553666202140296272141229231610687364013328949784429440542409036037896945255565851887406988287570391982459438193193424075852393394197396518036802912563346646607600590001358848556761273388103331259687461065291064140642734342415813599880317328301015095829452739540323870738420591179951496780115595461274525286565040995485119519627357413603923885798242267310864496365149627782683591003948367498280561484842151200003157997627658165367189995930841250484111112116483610630063381
e = 65537
p = gcd(n, c)
q = n // p
n = p * q
phi = (p - 1) * (q - 1)
d = invert(e, phi)
M = pow(c, d, n)
m = M // (2025 * 5202 * p)
print(long_to_bytes(m))
#qqqy{p=gcd(n,c)_hahahahahahaha}题目-6
- ! HGAME2024-week2-babyRSA
from Crypto.Util.number import *
from secret import flag,e
m=bytes_to_long(flag)
p=getPrime(64)
q=getPrime(256)
n=p**4*q
k=getPrime(16)
gift=pow(e+114514+p**k,0x10001,p)
c=pow(m,e,n)
print(f'p={p}')
print(f'q={q}')
print(f'c={c}')
print(f'gift={gift}')
"""
p=14213355454944773291
q=61843562051620700386348551175371930486064978441159200765618339743764001033297
c=105002138722466946495936638656038214000043475751639025085255113965088749272461906892586616250264922348192496597986452786281151156436229574065193965422841
gift=9751789326354522940
"""思路
- 已知
gift=pow(e+114514+p**k,0x10001,p) - 因为
p的幂次方模p就等于0 - 所以就剩下
e+114514,把他当成要求的m直接求解即可 - 然后我们发现
e与p-1,phi不互素 有限域开方+CRTe太大了……
解答-6-1
p=14213355454944773291
q=61843562051620700386348551175371930486064978441159200765618339743764001033297
c=105002138722466946495936638656038214000043475751639025085255113965088749272461906892586616250264922348192496597986452786281151156436229574065193965422841
gift=9751789326354522940
n = p**4*q
d = inverse_mod(65537,p-1)
mm = pow(gift,d,p)
e = mm - 114514
print(e)
#73561
phi = p**3*(p-1)*(q-1)
#GCD(e,phi)
#73561
res = Zmod(n)(c).nth_root(e, all=True)
for m in res:
try:
flag = bytes.fromhex(hex(m)[2:])
if b"hgame" in flag:
print(flag)
break
except ValueError:
continue
#hgame{Ad1eman_Mand3r_Mi11er_M3th0d}解答-6-2
p = 14213355454944773291
q = 61843562051620700386348551175371930486064978441159200765618339743764001033297
c = 105002138722466946495936638656038214000043475751639025085255113965088749272461906892586616250264922348192496597986452786281151156436229574065193965422841
gift = 9751789326354522940
n = p**4*q
d = inverse_mod(65537,p-1)
mm = pow(gift,d,p)
e = mm - 114514
print(e)
#73561
for mp in GF(p)(c).nth_root(e, all=True):
for mq in GF(q)(c).nth_root(e, all=True):
m = crt([ZZ(mp), ZZ(mq)], [p, q])
try:
res = bytes.fromhex(hex(m)[2:])
if res.isascii():
print(res)
except:
pass
#hgame{Ad1eman_Mand3r_Mi11er_M3th0d}题目-7
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
import hint
flag="******"
m = bytes_to_long(flag.encode())
e = 0x10001
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m, e, n)
x = getPrime(1024)
assert hint + x == x * p
print("n =", n)
print("c =", c)
print("hint =", hint)
'''
n = 15976809040711879471281731539856761604380576125028511883839879356245576856888369298458933538045322312928348121229144001321215501200523808376448554983699823608775114551139841018886908673439790613819399710574534587115695195116321805453143389429734986092801845888787500324238469989388829407654468454460856567278861786137435617130945283785050463059663327919970870438524485917591998775840103212924291249615845320422416660683510065647412178413983811999433675979112579201382338443856115272449608980061816627806074449134565559244073320244265273384754838349324942393866603176942263056807614767893928795708766754973852104447753
c = 8275226470633011867735807927026142131653175242892102286334954874753153557541211557166831259391614876018788339764040561079880385233613466834706228097855091567130862164921634639331134637645587281471276806240369426002092292101399592342527471742658841386046348881222566288642003086455731070934953796155722306182865125169970874219660634388109782203969599135023796034011209285180751962674417136584654237708364570669506145772411802898803018017805545314742060641114139951206724165206584637945420542236234529917975308087376344515935532814849370099088221841207979285033322690236838222029450530342042251505928060278259383517530
hint = 14581409386445283346438463479014278225787343506308938880936562171635019506485618274110431105797239018229016591806931161853859900151573220938558792970374693052290981284831706398415858721854573194172669259212485776873002047124377558967043980931981523718465288574647357881010685858510463076895057353584323904563406998593442100795383533617037462640986904103608378230226794115249277132181562582924922278548350800954501539483865846393098237532858000494625030432329543759184569083562269906963392985597364246020187304490502358492233932603492062235030229418462986205498523465621165322212578806252178919809287789484599677700190
'''思路
- 费马推导
- 其中
c一直是一个与p互质的常数 - 解答1是通过推定出的
c^hint-1 ≡ (k-aq)p mod p判断其模解一定为p的倍数,那么搞多组倍数解求其最大公约数不正是p的值 - 解答2则是通过推定出的
c^hint-1 ≡ (k-aq)p mod p判断其模解一定为p的倍数,但是没有取多组解求gcd,而是和n进行gcd,一样可以求(不过需要注意的是如果x不是一个素数或者由多个素数相乘,那么第二种方法需要将hint除以这些数留下唯一素数,而第一种方法通过多组模p解已经可以将这些多余数约掉)
解答-7-1
from Crypto.Util.number import *
from gmpy2 import *
n = 15976809040711879471281731539856761604380576125028511883839879356245576856888369298458933538045322312928348121229144001321215501200523808376448554983699823608775114551139841018886908673439790613819399710574534587115695195116321805453143389429734986092801845888787500324238469989388829407654468454460856567278861786137435617130945283785050463059663327919970870438524485917591998775840103212924291249615845320422416660683510065647412178413983811999433675979112579201382338443856115272449608980061816627806074449134565559244073320244265273384754838349324942393866603176942263056807614767893928795708766754973852104447753
c = 8275226470633011867735807927026142131653175242892102286334954874753153557541211557166831259391614876018788339764040561079880385233613466834706228097855091567130862164921634639331134637645587281471276806240369426002092292101399592342527471742658841386046348881222566288642003086455731070934953796155722306182865125169970874219660634388109782203969599135023796034011209285180751962674417136584654237708364570669506145772411802898803018017805545314742060641114139951206724165206584637945420542236234529917975308087376344515935532814849370099088221841207979285033322690236838222029450530342042251505928060278259383517530
hint = 14581409386445283346438463479014278225787343506308938880936562171635019506485618274110431105797239018229016591806931161853859900151573220938558792970374693052290981284831706398415858721854573194172669259212485776873002047124377558967043980931981523718465288574647357881010685858510463076895057353584323904563406998593442100795383533617037462640986904103608378230226794115249277132181562582924922278548350800954501539483865846393098237532858000494625030432329543759184569083562269906963392985597364246020187304490502358492233932603492062235030229418462986205498523465621165322212578806252178919809287789484599677700190
e = 0x10001
tmp1 = pow(2, hint, n) - 1
tmp2 = pow(3, hint, n) - 1
x = gcd(tmp1, tmp2)
y = n // x
phi = (x-1) * (y-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#qqqy{hint + x == x * p_then_what_is_x_and_hint???_i_know_hint_is_very_big}解答-7-2
from Crypto.Util.number import *
from gmpy2 import *
n = 15976809040711879471281731539856761604380576125028511883839879356245576856888369298458933538045322312928348121229144001321215501200523808376448554983699823608775114551139841018886908673439790613819399710574534587115695195116321805453143389429734986092801845888787500324238469989388829407654468454460856567278861786137435617130945283785050463059663327919970870438524485917591998775840103212924291249615845320422416660683510065647412178413983811999433675979112579201382338443856115272449608980061816627806074449134565559244073320244265273384754838349324942393866603176942263056807614767893928795708766754973852104447753
c = 8275226470633011867735807927026142131653175242892102286334954874753153557541211557166831259391614876018788339764040561079880385233613466834706228097855091567130862164921634639331134637645587281471276806240369426002092292101399592342527471742658841386046348881222566288642003086455731070934953796155722306182865125169970874219660634388109782203969599135023796034011209285180751962674417136584654237708364570669506145772411802898803018017805545314742060641114139951206724165206584637945420542236234529917975308087376344515935532814849370099088221841207979285033322690236838222029450530342042251505928060278259383517530
hint = 14581409386445283346438463479014278225787343506308938880936562171635019506485618274110431105797239018229016591806931161853859900151573220938558792970374693052290981284831706398415858721854573194172669259212485776873002047124377558967043980931981523718465288574647357881010685858510463076895057353584323904563406998593442100795383533617037462640986904103608378230226794115249277132181562582924922278548350800954501539483865846393098237532858000494625030432329543759184569083562269906963392985597364246020187304490502358492233932603492062235030229418462986205498523465621165322212578806252178919809287789484599677700190
e = 0x10001
a = 2
x = pow(a, hint, n)
p = gcd(x - 1, n)
q = n // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#qqqy{hint + x == x * p_then_what_is_x_and_hint???_i_know_hint_is_very_big}题目-8
- ! energyCTF2025-NumberTheory
from Crypto.Util.number import *
import hint
flag=b'xxx'
e=65537
p=getPrime(512)
q=getPrime(512)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
k=getPrime(1024)
assert hint + 233 * k == 233 * k * p
print(n)
print(c)
print(hint)
# 113310007043671810845854958178261892350466329031075849658400622797220639822165853920670375240421584770086737199174179404426269461807205919265215015318558583279307342189066142674684812629436201594710931246023579402265860654799773575870718232197419475376859857859160478517321102794376573133320398421013885294803
# 71140184512977657248678802858923889906469994653365050397942639686285067049311597229075083243014006139628135512648917088910957708595173169740778384396383007676160125041429483214711040860094456744628950189892189206308633008723823236088821678663574778449944147445444557428696970338207423613161971095287158528268
# 304302625376181653586904104401793052942691958380766622476796502085769101118223423483198426870687288772995446524917404481734386549400612667029785738864459729312716240418284186683690152478372081937338184159203750009565388703480806423176123558900518577576731229725343401015296144240503499943327828404875279740222104515371853890423856666710430710428991178833598803175224026696772717334264841725910496575249477684269365734094608409667005577061258227602330654989600297462思路
- 这里的
233需要约掉,其他的和上一题一样 - 此事在上一题亦有记载
解答-8-1
from Crypto.Util.number import *
from gmpy2 import *
n = 113310007043671810845854958178261892350466329031075849658400622797220639822165853920670375240421584770086737199174179404426269461807205919265215015318558583279307342189066142674684812629436201594710931246023579402265860654799773575870718232197419475376859857859160478517321102794376573133320398421013885294803
c = 71140184512977657248678802858923889906469994653365050397942639686285067049311597229075083243014006139628135512648917088910957708595173169740778384396383007676160125041429483214711040860094456744628950189892189206308633008723823236088821678663574778449944147445444557428696970338207423613161971095287158528268
hint = 304302625376181653586904104401793052942691958380766622476796502085769101118223423483198426870687288772995446524917404481734386549400612667029785738864459729312716240418284186683690152478372081937338184159203750009565388703480806423176123558900518577576731229725343401015296144240503499943327828404875279740222104515371853890423856666710430710428991178833598803175224026696772717334264841725910496575249477684269365734094608409667005577061258227602330654989600297462
e = 65537
kp = hint // 233
a = 2
x = pow(a, kp, n)
p = gcd(x - 1, n)
q = n // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#flag{d0bafb7185f2acfd371c566cbae25af9}解答-8-2
from Crypto.Util.number import *
from gmpy2 import *
n = 113310007043671810845854958178261892350466329031075849658400622797220639822165853920670375240421584770086737199174179404426269461807205919265215015318558583279307342189066142674684812629436201594710931246023579402265860654799773575870718232197419475376859857859160478517321102794376573133320398421013885294803
c = 71140184512977657248678802858923889906469994653365050397942639686285067049311597229075083243014006139628135512648917088910957708595173169740778384396383007676160125041429483214711040860094456744628950189892189206308633008723823236088821678663574778449944147445444557428696970338207423613161971095287158528268
hint = 304302625376181653586904104401793052942691958380766622476796502085769101118223423483198426870687288772995446524917404481734386549400612667029785738864459729312716240418284186683690152478372081937338184159203750009565388703480806423176123558900518577576731229725343401015296144240503499943327828404875279740222104515371853890423856666710430710428991178833598803175224026696772717334264841725910496575249477684269365734094608409667005577061258227602330654989600297462
e = 65537
tmp1 = pow(2, hint, n) - 1
tmp2 = pow(3, hint, n) - 1
x = gcd(tmp1, tmp2)
y = n // x
phi = (x-1) * (y-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#flag{d0bafb7185f2acfd371c566cbae25af9}题目-9
- ! 2019-AceBear Security Contest-babyRSA
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c = pow(m, e, n)
print(n)
print(c)
print(pow(p+q, 2019, n)
print(pow(p+2019, q, n))
#132991872691788324082134861997953579720626276400340540687013665099477551458348129102088618361745158673111757871083783880384786818716675179609957267487624993539275409316283860268944400754318665280566429956092526555947286266806591767802818223484766666271142927737412289284611614382748008696676464334157695348471
#51298575439582965784709335152059190835305126166438646589369499569428503835480418841408132266294091481013029021796067865137829386370176771358549523435135941877535688535317287350930103706346511719290416785053872504275498831270025102211793188751664805369414883387849038010293938521738911310864582949611581363258
#116622952696503724444465816906812927416603315297598995734109952470693593204299624097288573735780464942963720997719694033378973971604112334413336782598075611956878592757766346915810900585142701963781432186914454664547551508332077962977944352243565906344660561255453917679867097810681750809061744116605905787747
#46935581819524717607675319301313485106684889957138298327245990937934310422542055504175491111118389178173005337213903985686712577881019021348501335888175248295397612880683801733649468701485843002169345784241756189697901370624950199354359977266595488202827970067500373575114835718127956891051157026649793602861思路
- 费马费马!
解答-9
from Crypto.Util.number import *
from gmpy2 import *
e = 65537
n = 132991872691788324082134861997953579720626276400340540687013665099477551458348129102088618361745158673111757871083783880384786818716675179609957267487624993539275409316283860268944400754318665280566429956092526555947286266806591767802818223484766666271142927737412289284611614382748008696676464334157695348471
c = 51298575439582965784709335152059190835305126166438646589369499569428503835480418841408132266294091481013029021796067865137829386370176771358549523435135941877535688535317287350930103706346511719290416785053872504275498831270025102211793188751664805369414883387849038010293938521738911310864582949611581363258
h1 = 116622952696503724444465816906812927416603315297598995734109952470693593204299624097288573735780464942963720997719694033378973971604112334413336782598075611956878592757766346915810900585142701963781432186914454664547551508332077962977944352243565906344660561255453917679867097810681750809061744116605905787747
h2 = 46935581819524717607675319301313485106684889957138298327245990937934310422542055504175491111118389178173005337213903985686712577881019021348501335888175248295397612880683801733649468701485843002169345784241756189697901370624950199354359977266595488202827970067500373575114835718127956891051157026649793602861
p = gcd(h1 - pow(h2 - 2019, 2019, n), n)
q = n // p
n = p * q
phi = (p - 1)*(q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#AceBear{1_Hop3_1t_w4s_n0t_t00_34sy_f0r_U}题目-10
from Crypto.Util.number import *
from sympy import *
from flag import secret
m = b'***'
flag = bytes_to_long(m)
p = getPrime(1024)
q = nextprime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(flag, e, n)
print(f'd =',d)
print(f'c =',c)
#d = 23146692831807292160283075033846897149306878921088969315437456757340187413559018143046133850228053385487698301669169519237157100086166892816330573134508870936518925483344579936687911347144932691356699823826922419750209161148318217844945779980063757263819151621487352332815090544951662892902347720704617631467144703816876287302850179125812239738598608518351770619410140450498592254802746341127421147090803856558897044127032657884006230160735932856565656682135072602312809844025276409068965697038394294259190882349073308237700511657608611983154619403845162590637719457136520942423334407612566629628629701765946820960289
#c = 28742924229392087466182548771679429476075478097233732222881336576802186500509338902254171523721474125064472440904690237917127948284117223469126994889423945074509741819912621716859903540548051980552377594955346185872874090733691738619233268685844092651530186839595758908001471093400671254065369293833294026733246065426849761147915823486668385266805963259432785473241951598165014242278297278691658878893552953185661894332546686173559051935051386688155320835275074361867533385599286739181003471084061428317806192389997024395165436234041262603883418056265619060914858793173871296504362995603050087131552197307988519432102思路
- 给了
d,没给n,但p,q是相邻素数 - 那我们现在考虑
e*d-1,他一定是phi的倍数 p,q都是1024位,所以(p-1)(q-1)是2048位,那么e*d-1大概是2064位- 也就是说
(e*d-1)/phi≈k,其中k约为65536(2^16) - 那我们尝试找到一个
k可以刚好除尽(e*d-1) - 然后再对这个可能得
phi开方,因为p,q是相邻素数，所以稍微遍历一下就能找到p和q - 随后就可以求解出明文了(IlIIIIllIlIIllIIIlIllIIIIlIlIIllIlIIIIlI)
解答-10
from Crypto.Util.number import *
import gmpy2
c = 28742924229392087466182548771679429476075478097233732222881336576802186500509338902254171523721474125064472440904690237917127948284117223469126994889423945074509741819912621716859903540548051980552377594955346185872874090733691738619233268685844092651530186839595758908001471093400671254065369293833294026733246065426849761147915823486668385266805963259432785473241951598165014242278297278691658878893552953185661894332546686173559051935051386688155320835275074361867533385599286739181003471084061428317806192389997024395165436234041262603883418056265619060914858793173871296504362995603050087131552197307988519432102
d = 23146692831807292160283075033846897149306878921088969315437456757340187413559018143046133850228053385487698301669169519237157100086166892816330573134508870936518925483344579936687911347144932691356699823826922419750209161148318217844945779980063757263819151621487352332815090544951662892902347720704617631467144703816876287302850179125812239738598608518351770619410140450498592254802746341127421147090803856558897044127032657884006230160735932856565656682135072602312809844025276409068965697038394294259190882349073308237700511657608611983154619403845162590637719457136520942423334407612566629628629701765946820960289
e = 0x10001
kphi = d*e - 1
mayphi = []
for k in range(2**15, 2**17):
if kphi % k == 0:
mayphi.append(kphi // k)
def fact(phi):
for a in range(gmpy2.iroot(phi, 2)[0], gmpy2.iroot(phi, 2)[0]+3000):
if phi % a == 0:
b = phi // a
if gmpy2.is_prime(a+1) and gmpy2.is_prime(b+1):
return (a+1, b+1)
#a=p-1, b=q-1
pq = []
for a in mayphi:
res = fact(a)
if res:
pq.append(res)
p, q = pq[0]
m = pow(c, d, p*q)
print(long_to_bytes(m))
#qqqy{y0u_kNow_[(e*d-1)%phi==k]_IlIIIIllIlIIllIIIlIllIIIIlIlIIllIlIIIIlI}题目-11
- ! [祥云杯 2022]little little fermat
from Crypto.Util.number import *
from random import *
from libnum import *
import gmpy2
from secret import x
flag = b'?????????'
m = bytes_to_long(flag)
def obfuscate(p, k):
nbit = p.bit_length()
while True:
#getRandomRange是指在-1到1的范围中获取一个数 左闭右开 只可能是-1或0
l1 = [getRandomRange(-1, 1) for _ in '_' * k]
l2 = [getRandomRange(100, nbit) for _ in '_' * k]
l3 = [getRandomRange(10, nbit//4) for _ in '_' * k]
l4 = [getRandomRange(2, 6) for _ in '_' *k]
#sum是求和函数 把列表中的数值加起来
A = sum([l1[_] * 2 ** ((l2[_]+l3[_])//l4[_]) for _ in range(0, k)])
q = p + A
if isPrime(q) * A != 0:
return q
p = getPrime(512)
q = obfuscate(p, 5)
e = 65537
n = p*q
print(f'n = {n}')
assert 114514 ** x % p == 1 # 根据断言语句获得x的值
m = m ^ (x**2)
c = pow(m, e, n)
print(f'c = {c}')
'''
n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
'''思路
- 看着麻烦其实 $q$ 就是 $p$ 的附近的一个值,可以直接分解
- 又根据
费马小定理,如果 $p$ 是素数,且114514不是 $p$ 的倍数(即114514 % p ≠ 0),那么有:114514^(p-1) ≡ 1 (mod p)这意味着当x = p-1时,114514^x % p = 1成立
解答-11
from Crypto.Util.number import *
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
p = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734648016476153593841839977704512156756634066593725142934001
q = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734646483980612727952939084061619889139517526028673988305393
x = p - 1
phi = (p-1)*(q-1)
e = 65537
n = p * q
d = inverse(e, phi)
m = pow(c,d,n)
m = (m ^ (x**2))
print(long_to_bytes(m))
#b'flag{I~ju5t_w@nt_30_te11_y0u_how_I_@m_f3ll1ng~}45108#@7++3@79?3328?!!@08#712/+963-60#9-/83#+/1@@=59!/84@?3#4!4=-9542/##'题目-12
- ! GHCTF2025-EZ_Fermat
from Crypto.Util.number import getPrime, bytes_to_long
from secret import f
flag = b'NSSCTF{test_flag}'
p = getPrime(512)
q = getPrime(512)
n = p*q
m = bytes_to_long(flag)
e = 65537
c = pow(m,e,n)
R.<x> = ZZ[]
f = R(str(f))
w = pow(2,f(p),n)
print(f'{n = }\n')
print(f'{e = }\n')
print(f'{c = }\n')
print(f'{f = }\n')
print(f'{w = }\n')
'''
n = 101780569941880865465631942473186578520071435753163950944409148606282910806650879176280021512435190682009749926285674412651435782567149633130455645157688819845748439487113261739503325065997835517112163014056297017874761742768297646567397770742374004940360061700285170103292360590891188591132054903101398360047
e = 65537
c = 77538275949900942020886849496162539665323546686749270705418870515132296087721218282974435210763225488530925782158331269160555819622551413648073293857866671421886753377970220838141826468831099375757481041897142546760492813343115244448184595644585857978116766199800311200819967057790401213156560742779242511746
f = 2*x^332 - x^331 + x^329 + 3*x^328 - x^327 - 3*x^325 + x^323 - 3*x^322 - x^321 - 3*x^320 + x^319 + 2*x^318 - 4*x^317 - 3*x^315 - 2*x^314 + x^313 + x^312 + 2*x^311 + 2*x^309 + 2*x^308 + 5*x^307 + 2*x^306 + 3*x^305 + 5*x^304 + 4*x^303 + x^302 - x^301 - x^300 - 2*x^299 - 2*x^298 + x^297 + 3*x^296 - x^295 - 4*x^292 - x^290 + 4*x^289 - x^287 - 3*x^286 + x^285 - 2*x^284 + x^283 - x^282 - 2*x^281 + x^280 - 2*x^279 + x^278 + 2*x^277 - 3*x^276 - x^275 - 4*x^274 - 3*x^273 - 5*x^272 - 2*x^271 - 3*x^270 + 2*x^269 + 2*x^268 - x^267 - 2*x^266 + x^265 + x^264 - 3*x^262 - 3*x^259 + 2*x^258 - x^257 + 2*x^256 + 2*x^255 - x^254 - 2*x^253 - x^252 + 2*x^251 - x^250 + x^249 + 2*x^247 + 2*x^246 + 2*x^245 - 2*x^244 - 3*x^243 + 2*x^242 - 3*x^241 - x^240 - 3*x^239 - x^236 - 3*x^235 - 2*x^234 - x^233 - 2*x^232 - x^231 - 3*x^230 - 2*x^229 - 4*x^228 - 2*x^227 - 3*x^226 + 2*x^225 + x^224 - x^223 - 2*x^221 + 3*x^219 - x^217 - 2*x^216 + x^215 + 2*x^213 - x^212 + 3*x^211 + x^210 + 4*x^209 + x^208 - x^206 - x^205 - x^204 + 2*x^203 - 3*x^202 + 2*x^199 - x^198 + 2*x^196 - 2*x^195 + 3*x^194 + 3*x^193 - x^192 + 4*x^191 + 2*x^189 + x^186 - x^185 - x^184 + 3*x^183 + x^182 + 2*x^181 - 2*x^180 + x^177 + x^175 - x^173 + 3*x^172 + x^170 + x^169 - x^167 - 2*x^166 - x^165 - 4*x^164 - 2*x^163 + 2*x^162 + 4*x^161 - 2*x^160 - 3*x^159 - 2*x^158 - 2*x^157 + x^156 - x^155 + 3*x^154 - 4*x^153 + x^151 + 2*x^150 + x^149 - x^148 + 2*x^147 + 3*x^146 + 2*x^145 - 4*x^144 - 4*x^143 + x^142 - 2*x^140 - 2*x^139 + 2*x^138 + 3*x^137 + 3*x^136 + 3*x^135 + x^134 - x^133 + 2*x^132 + 3*x^130 - 3*x^129 - 2*x^128 - x^127 - 2*x^126 + x^125 + x^124 - 2*x^123 + x^122 - x^121 + 3*x^120 - x^119 - 2*x^118 - x^117 - x^116 - 2*x^115 + 2*x^114 + 2*x^113 - 3*x^112 - x^111 - 4*x^110 + x^109 + x^108 + x^106 - 4*x^105 + x^104 - x^103 - x^101 + x^100 - 2*x^99 + x^98 - x^97 + 3*x^96 + 3*x^94 - x^93 - x^92 + x^91 - 2*x^90 + x^89 - x^88 + x^87 - x^86 + x^85 + x^84 - x^83 + x^79 - 3*x^78 - 2*x^77 + x^74 + 3*x^73 - x^72 - 3*x^71 - 2*x^70 + x^69 - 3*x^66 + x^65 + x^64 - 4*x^62 - x^61 + x^60 - x^59 + 3*x^58 - x^57 - x^54 + 3*x^53 + x^51 - 3*x^50 - x^49 + 2*x^47 - x^46 - x^44 + x^43 - x^42 - 4*x^41 - 3*x^39 - x^37 - x^36 - 3*x^35 + x^34 + x^33 - 2*x^32 + 2*x^31 - x^30 + 2*x^29 - 2*x^28 - 2*x^27 - x^24 + x^22 - 5*x^21 + 3*x^20 + 2*x^19 - x^18 + 2*x^17 + x^16 - 2*x^15 - 2*x^14 + x^13 + x^12 + 2*x^11 - 3*x^10 + 3*x^9 + 2*x^8 - 4*x^6 - 2*x^5 - 4*x^4 + x^3 - x^2 - 1
w = 32824596080441735190523997982799829197530203904568086251690542244969244071312854874746142497647579310192994177896837383837384405062036521829088599595750902976191010000575697075792720479387771945760107268598283406893094243282498381006464103080551366587157561686900620059394693185990788592220509670478190685244
'''思路
- 题目给出了 $2^{f(p)} \bmod n=w$ ,根据中国剩余定理,很明显对于模 $p$ 和模 $q$ 同样成立
- 同时根据费马小定理 $2^{f(p)}=1 \bmod p$ ,我们可以化简为 $2^{f(p) \bmod (p-1)} \bmod p = w$
- 那么如何求 $f(p) \bmod (p-1)$ 呢
- $p \equiv 1 \bmod (p−1)$ ,即 $p$ 除以 $p−1$ 的余数为 $1$
- 因此,对于任意正整数 $k$ ,有: $p^k \equiv 1^k \equiv 1 \bmod (p−1)$ ,将 $p \equiv 1 \bmod (p−1)$ 代入 $f(p)$ ,得到的正是 $f(1)$ 的值,即 $f(p) \bmod (p-1)=f(1) \bmod (p-1)$
- 再将指数转为 $f(1)$ ,即可得到 $2^{f(1)} \bmod n=w$ ,即 $2^{f(1)}-w=0 \bmod n$
- 将 $1$ 代入多项式求解后取 $\gcd(2^{f(1)}-w,n)$ 即可得到 $p$ ,随后正常求解
rsa即可
解答-12-1
from Crypto.Util.number import *
n = 101780569941880865465631942473186578520071435753163950944409148606282910806650879176280021512435190682009749926285674412651435782567149633130455645157688819845748439487113261739503325065997835517112163014056297017874761742768297646567397770742374004940360061700285170103292360590891188591132054903101398360047
e = 65537
c = 77538275949900942020886849496162539665323546686749270705418870515132296087721218282974435210763225488530925782158331269160555819622551413648073293857866671421886753377970220838141826468831099375757481041897142546760492813343115244448184595644585857978116766199800311200819967057790401213156560742779242511746
w = 32824596080441735190523997982799829197530203904568086251690542244969244071312854874746142497647579310192994177896837383837384405062036521829088599595750902976191010000575697075792720479387771945760107268598283406893094243282498381006464103080551366587157561686900620059394693185990788592220509670478190685244
R.<x> = PolynomialRing(ZZ)
f = 2*x^332 - x^331 + x^329 + 3*x^328 - x^327 - 3*x^325 + x^323 - 3*x^322 - x^321 - 3*x^320 + x^319 + 2*x^318 - 4*x^317 - 3*x^315 - 2*x^314 + x^313 + x^312 + 2*x^311 + 2*x^309 + 2*x^308 + 5*x^307 + 2*x^306 + 3*x^305 + 5*x^304 + 4*x^303 + x^302 - x^301 - x^300 - 2*x^299 - 2*x^298 + x^297 + 3*x^296 - x^295 - 4*x^292 - x^290 + 4*x^289 - x^287 - 3*x^286 + x^285 - 2*x^284 + x^283 - x^282 - 2*x^281 + x^280 - 2*x^279 + x^278 + 2*x^277 - 3*x^276 - x^275 - 4*x^274 - 3*x^273 - 5*x^272 - 2*x^271 - 3*x^270 + 2*x^269 + 2*x^268 - x^267 - 2*x^266 + x^265 + x^264 - 3*x^262 - 3*x^259 + 2*x^258 - x^257 + 2*x^256 + 2*x^255 - x^254 - 2*x^253 - x^252 + 2*x^251 - x^250 + x^249 + 2*x^247 + 2*x^246 + 2*x^245 - 2*x^244 - 3*x^243 + 2*x^242 - 3*x^241 - x^240 - 3*x^239 - x^236 - 3*x^235 - 2*x^234 - x^233 - 2*x^232 - x^231 - 3*x^230 - 2*x^229 - 4*x^228 - 2*x^227 - 3*x^226 + 2*x^225 + x^224 - x^223 - 2*x^221 + 3*x^219 - x^217 - 2*x^216 + x^215 + 2*x^213 - x^212 + 3*x^211 + x^210 + 4*x^209 + x^208 - x^206 - x^205 - x^204 + 2*x^203 - 3*x^202 + 2*x^199 - x^198 + 2*x^196 - 2*x^195 + 3*x^194 + 3*x^193 - x^192 + 4*x^191 + 2*x^189 + x^186 - x^185 - x^184 + 3*x^183 + x^182 + 2*x^181 - 2*x^180 + x^177 + x^175 - x^173 + 3*x^172 + x^170 + x^169 - x^167 - 2*x^166 - x^165 - 4*x^164 - 2*x^163 + 2*x^162 + 4*x^161 - 2*x^160 - 3*x^159 - 2*x^158 - 2*x^157 + x^156 - x^155 + 3*x^154 - 4*x^153 + x^151 + 2*x^150 + x^149 - x^148 + 2*x^147 + 3*x^146 + 2*x^145 - 4*x^144 - 4*x^143 + x^142 - 2*x^140 - 2*x^139 + 2*x^138 + 3*x^137 + 3*x^136 + 3*x^135 + x^134 - x^133 + 2*x^132 + 3*x^130 - 3*x^129 - 2*x^128 - x^127 - 2*x^126 + x^125 + x^124 - 2*x^123 + x^122 - x^121 + 3*x^120 - x^119 - 2*x^118 - x^117 - x^116 - 2*x^115 + 2*x^114 + 2*x^113 - 3*x^112 - x^111 - 4*x^110 + x^109 + x^108 + x^106 - 4*x^105 + x^104 - x^103 - x^101 + x^100 - 2*x^99 + x^98 - x^97 + 3*x^96 + 3*x^94 - x^93 - x^92 + x^91 - 2*x^90 + x^89 - x^88 + x^87 - x^86 + x^85 + x^84 - x^83 + x^79 - 3*x^78 - 2*x^77 + x^74 + 3*x^73 - x^72 - 3*x^71 - 2*x^70 + x^69 - 3*x^66 + x^65 + x^64 - 4*x^62 - x^61 + x^60 - x^59 + 3*x^58 - x^57 - x^54 + 3*x^53 + x^51 - 3*x^50 - x^49 + 2*x^47 - x^46 - x^44 + x^43 - x^42 - 4*x^41 - 3*x^39 - x^37 - x^36 - 3*x^35 + x^34 + x^33 - 2*x^32 + 2*x^31 - x^30 + 2*x^29 - 2*x^28 - 2*x^27 - x^24 + x^22 - 5*x^21 + 3*x^20 + 2*x^19 - x^18 + 2*x^17 + x^16 - 2*x^15 - 2*x^14 + x^13 + x^12 + 2*x^11 - 3*x^10 + 3*x^9 + 2*x^8 - 4*x^6 - 2*x^5 - 4*x^4 + x^3 - x^2 - 1
f1 = f(1)
print("f(1) =", f1)
k = pow(2, f1, n)
g = gcd(k - w, n)
print("gcd =", g)
q = n // p
d = inverse(e, phi)
print(long_to_bytes(pow(c,d,n)))
'''
f(1) = -57
gcd = 10369947696097707510769809078424403635336089844072313788886920079212917663690503014328582816890429888540698699892682697716174207561536836918335963753124197
b'NSSCTF{8d1e3405044a79b23a44a43084bd994b}'
'''解答-12-2
from Crypto.Util.number import long_to_bytes, inverse
from gmpy2 import gcd
x = var('x')
n = 101780569941880865465631942473186578520071435753163950944409148606282910806650879176280021512435190682009749926285674412651435782567149633130455645157688819845748439487113261739503325065997835517112163014056297017874761742768297646567397770742374004940360061700285170103292360590891188591132054903101398360047
e = 65537
c = 77538275949900942020886849496162539665323546686749270705418870515132296087721218282974435210763225488530925782158331269160555819622551413648073293857866671421886753377970220838141826468831099375757481041897142546760492813343115244448184595644585857978116766199800311200819967057790401213156560742779242511746
f = 2*x^332 - x^331 + x^329 + 3*x^328 - x^327 - 3*x^325 + x^323 - 3*x^322 - x^321 - 3*x^320 + x^319 + 2*x^318 - 4*x^317 - 3*x^315 - 2*x^314 + x^313 + x^312 + 2*x^311 + 2*x^309 + 2*x^308 + 5*x^307 + 2*x^306 + 3*x^305 + 5*x^304 + 4*x^303 + x^302 - x^301 - x^300 - 2*x^299 - 2*x^298 + x^297 + 3*x^296 - x^295 - 4*x^292 - x^290 + 4*x^289 - x^287 - 3*x^286 + x^285 - 2*x^284 + x^283 - x^282 - 2*x^281 + x^280 - 2*x^279 + x^278 + 2*x^277 - 3*x^276 - x^275 - 4*x^274 - 3*x^273 - 5*x^272 - 2*x^271 - 3*x^270 + 2*x^269 + 2*x^268 - x^267 - 2*x^266 + x^265 + x^264 - 3*x^262 - 3*x^259 + 2*x^258 - x^257 + 2*x^256 + 2*x^255 - x^254 - 2*x^253 - x^252 + 2*x^251 - x^250 + x^249 + 2*x^247 + 2*x^246 + 2*x^245 - 2*x^244 - 3*x^243 + 2*x^242 - 3*x^241 - x^240 - 3*x^239 - x^236 - 3*x^235 - 2*x^234 - x^233 - 2*x^232 - x^231 - 3*x^230 - 2*x^229 - 4*x^228 - 2*x^227 - 3*x^226 + 2*x^225 + x^224 - x^223 - 2*x^221 + 3*x^219 - x^217 - 2*x^216 + x^215 + 2*x^213 - x^212 + 3*x^211 + x^210 + 4*x^209 + x^208 - x^206 - x^205 - x^204 + 2*x^203 - 3*x^202 + 2*x^199 - x^198 + 2*x^196 - 2*x^195 + 3*x^194 + 3*x^193 - x^192 + 4*x^191 + 2*x^189 + x^186 - x^185 - x^184 + 3*x^183 + x^182 + 2*x^181 - 2*x^180 + x^177 + x^175 - x^173 + 3*x^172 + x^170 + x^169 - x^167 - 2*x^166 - x^165 - 4*x^164 - 2*x^163 + 2*x^162 + 4*x^161 - 2*x^160 - 3*x^159 - 2*x^158 - 2*x^157 + x^156 - x^155 + 3*x^154 - 4*x^153 + x^151 + 2*x^150 + x^149 - x^148 + 2*x^147 + 3*x^146 + 2*x^145 - 4*x^144 - 4*x^143 + x^142 - 2*x^140 - 2*x^139 + 2*x^138 + 3*x^137 + 3*x^136 + 3*x^135 + x^134 - x^133 + 2*x^132 + 3*x^130 - 3*x^129 - 2*x^128 - x^127 - 2*x^126 + x^125 + x^124 - 2*x^123 + x^122 - x^121 + 3*x^120 - x^119 - 2*x^118 - x^117 - x^116 - 2*x^115 + 2*x^114 + 2*x^113 - 3*x^112 - x^111 - 4*x^110 + x^109 + x^108 + x^106 - 4*x^105 + x^104 - x^103 - x^101 + x^100 - 2*x^99 + x^98 - x^97 + 3*x^96 + 3*x^94 - x^93 - x^92 + x^91 - 2*x^90 + x^89 - x^88 + x^87 - x^86 + x^85 + x^84 - x^83 + x^79 - 3*x^78 - 2*x^77 + x^74 + 3*x^73 - x^72 - 3*x^71 - 2*x^70 + x^69 - 3*x^66 + x^65 + x^64 - 4*x^62 - x^61 + x^60 - x^59 + 3*x^58 - x^57 - x^54 + 3*x^53 + x^51 - 3*x^50 - x^49 + 2*x^47 - x^46 - x^44 + x^43 - x^42 - 4*x^41 - 3*x^39 - x^37 - x^36 - 3*x^35 + x^34 + x^33 - 2*x^32 + 2*x^31 - x^30 + 2*x^29 - 2*x^28 - 2*x^27 - x^24 + x^22 - 5*x^21 + 3*x^20 + 2*x^19 - x^18 + 2*x^17 + x^16 - 2*x^15 - 2*x^14 + x^13 + x^12 + 2*x^11 - 3*x^10 + 3*x^9 + 2*x^8 - 4*x^6 - 2*x^5 - 4*x^4 + x^3 - x^2 - 1
w = 32824596080441735190523997982799829197530203904568086251690542244969244071312854874746142497647579310192994177896837383837384405062036521829088599595750902976191010000575697075792720479387771945760107268598283406893094243282498381006464103080551366587157561686900620059394693185990788592220509670478190685244
for i in f.list()[1::]:
w *= 2 ^ (-ZZ(i))
w %= n
p = gcd(w * 2 - 1, n)
q = n // p
print(long_to_bytes(pow(c, inverse(e, (p - 1) * (q - 1)), n)))
#NSSCTF{8d1e3405044a79b23a44a43084bd994b}题目-13
- ! GHCTF2025-EZ_Fermat_bag_PRO
from Crypto.Util.number import getPrime, bytes_to_long
from random import *
from secret import f, flag
assert len(flag) == 88
assert flag.startswith(b'NSSCTF{')
assert flag.endswith(b'}')
p = getPrime(512)
q = getPrime(512)
n = p*q
P.<x,y> = ZZ[]
f = P(str(f))
w = pow(2,f(p,q),n)
assert all(chr(i) in ''.join(list(set(str(p)))) for i in flag[7:-1:])
c = bytes_to_long(flag) % p
print(f'{n = }\n')
print(f'{f = }\n')
print(f'{w = }\n')
print(f'{c = }\n')
'''
n = 95656952327201449381426394713246214670537600365883923624876350719801926817916514429721785287844335184715049179879891389941974481490433975689601829920289485889138252888029716516069912637121531561601839948367426922036690701168975937162280451323099126372019216020898338909808577022618554997063496690156977790629
f = x^31 - x^30*y - 2*x^29*y^2 + 7*x^28*y^3 + 2*x^27*y^4 - 4*x^24*y^7 + 3*x^23*y^8 - x^20*y^11 - 4*x^19*y^12 + x^18*y^13 - 5*x^17*y^14 - 4*x^16*y^15 - x^15*y^16 + x^14*y^17 + x^13*y^18 + x^12*y^19 - 2*x^11*y^20 - 3*x^9*y^22 + 5*x^7*y^24 + x^6*y^25 + 6*x^4*y^27 + x^3*y^28 + 2*x*y^30 + y^31 - 2*x^30 - 3*x^29*y + 2*x^28*y^2 + 2*x^27*y^3 - x^26*y^4 - x^25*y^5 - 2*x^24*y^6 - 3*x^23*y^7 - 3*x^22*y^8 - 3*x^20*y^10 - 4*x^19*y^11 + 2*x^18*y^12 + x^15*y^15 - x^14*y^16 - 2*x^12*y^18 - 3*x^11*y^19 - x^10*y^20 + x^9*y^21 + 2*x^8*y^22 + x^7*y^23 + x^5*y^25 - x^4*y^26 - 2*x^3*y^27 - 2*x^2*y^28 - y^30 - 2*x^29 - x^28*y + 3*x^26*y^3 - x^25*y^4 - 2*x^24*y^5 + x^23*y^6 - x^22*y^7 - x^20*y^9 + 2*x^19*y^10 + 2*x^18*y^11 + x^16*y^13 + x^15*y^14 + x^14*y^15 + x^13*y^16 + x^12*y^17 + 5*x^11*y^18 - x^9*y^20 - 2*x^8*y^21 - 5*x^7*y^22 - 2*x^6*y^23 + 3*x^5*y^24 - 5*x^3*y^26 - x^2*y^27 + 2*x*y^28 - y^29 + 3*x^28 + 3*x^27*y - 2*x^26*y^2 + x^25*y^3 + 2*x^24*y^4 - x^23*y^5 - 2*x^22*y^6 - 3*x^20*y^8 - 3*x^19*y^9 + 4*x^17*y^11 - x^16*y^12 - 3*x^15*y^13 - 2*x^14*y^14 + x^13*y^15 + 2*x^12*y^16 - 2*x^11*y^17 + x^10*y^18 - 2*x^9*y^19 + x^8*y^20 - 2*x^7*y^21 - x^6*y^22 + x^5*y^23 - x^4*y^24 + x^3*y^25 + x^2*y^26 - x*y^27 - y^28 + x^27 + x^26*y - 2*x^24*y^3 + x^23*y^4 - 3*x^22*y^5 - 2*x^21*y^6 - 2*x^20*y^7 - 5*x^19*y^8 + 2*x^18*y^9 - 5*x^17*y^10 + x^16*y^11 - 3*x^15*y^12 - 4*x^14*y^13 - x^13*y^14 + x^12*y^15 + 3*x^11*y^16 + 2*x^10*y^17 - 4*x^9*y^18 - 2*x^6*y^21 + x^5*y^22 + 4*x^3*y^24 + 2*x^2*y^25 + 2*x*y^26 - 2*y^27 + x^25*y + x^24*y^2 + x^23*y^3 + 5*x^22*y^4 + x^20*y^6 - 3*x^19*y^7 + x^18*y^8 - x^17*y^9 + 2*x^15*y^11 - x^14*y^12 + 2*x^13*y^13 - x^12*y^14 + 4*x^11*y^15 - x^10*y^16 - 2*x^6*y^20 - x^5*y^21 + 3*x^3*y^23 + x^2*y^24 - 3*x*y^25 - 3*y^26 + 3*x^25 - 2*x^23*y^2 - x^21*y^4 + x^17*y^8 + 2*x^16*y^9 - x^15*y^10 - 2*x^14*y^11 - x^13*y^12 + 2*x^12*y^13 - 2*x^11*y^14 - x^9*y^16 - x^8*y^17 - x^6*y^19 - x^5*y^20 + x^4*y^21 + x^3*y^22 + 5*x*y^24 - 2*y^25 - x^24 + 2*x^23*y + x^22*y^2 - x^21*y^3 - x^19*y^5 + x^18*y^6 - x^17*y^7 + 2*x^16*y^8 - 4*x^15*y^9 - x^14*y^10 - x^13*y^11 - x^12*y^12 + 4*x^10*y^14 + 2*x^9*y^15 - x^8*y^16 - 2*x^7*y^17 - 2*x^6*y^18 + 4*x^5*y^19 + x^4*y^20 + 2*x^2*y^22 - 5*x*y^23 - y^24 + x^23 - x^22*y + 2*x^21*y^2 - x^20*y^3 - x^18*y^5 - x^17*y^6 - 5*x^15*y^8 + x^14*y^9 - 3*x^13*y^10 + 3*x^12*y^11 + 2*x^11*y^12 - 2*x^10*y^13 - 2*x^9*y^14 - x^8*y^15 + 2*x^7*y^16 - 2*x^6*y^17 - 4*x^5*y^18 - 5*x^3*y^20 - x^2*y^21 - x*y^22 - 4*y^23 - x^22 + 2*x^21*y - 2*x^20*y^2 - 2*x^19*y^3 - 3*x^17*y^5 - x^16*y^6 - x^15*y^7 + 4*x^13*y^9 + 2*x^12*y^10 + 3*x^11*y^11 + 2*x^10*y^12 - x^9*y^13 - x^7*y^15 + 2*x^6*y^16 + x^3*y^19 + 2*x^2*y^20 + 2*x*y^21 + 3*y^22 - 3*x^21 - x^20*y - x^19*y^2 + 2*x^17*y^4 - x^16*y^5 - x^15*y^6 + x^14*y^7 - 5*x^12*y^9 - 2*x^11*y^10 + x^10*y^11 + x^6*y^15 + x^5*y^16 + x^4*y^17 - 3*x^2*y^19 - 2*x*y^20 - 2*y^21 + x^20 + 2*x^19*y - 2*x^17*y^3 + 2*x^16*y^4 - 3*x^15*y^5 + 4*x^14*y^6 + 2*x^13*y^7 - x^12*y^8 - 2*x^11*y^9 + x^10*y^10 + 6*x^9*y^11 + x^8*y^12 + x^7*y^13 + 2*x^5*y^15 + 4*x^4*y^16 + x^3*y^17 - x^2*y^18 + 3*x*y^19 - x^17*y^2 + 2*x^16*y^3 + 3*x^14*y^5 - x^13*y^6 + 2*x^11*y^8 + x^10*y^9 + 3*x^9*y^10 - x^7*y^12 - x^6*y^13 + 3*x^5*y^14 - 4*x^4*y^15 + x^2*y^17 + 2*y^19 - x^18 - x^16*y^2 - 2*x^14*y^4 - 2*x^13*y^5 - 2*x^12*y^6 + 2*x^11*y^7 + 3*x^9*y^9 + 3*x^8*y^10 + x^6*y^12 - x^4*y^14 + 2*x^3*y^15 + 2*x^2*y^16 - 2*x*y^17 - x^17 - 4*x^16*y - 2*x^15*y^2 + 2*x^14*y^3 - x^13*y^4 + x^12*y^5 - 2*x^11*y^6 - 3*x^10*y^7 - x^9*y^8 - 5*x^8*y^9 + 2*x^7*y^10 + 2*x^6*y^11 - x^5*y^12 + x^4*y^13 - 3*x^2*y^15 + x*y^16 - 3*x^16 + x^15*y - 3*x^14*y^2 - x^13*y^3 - x^12*y^4 + 2*x^11*y^5 - x^10*y^6 + 5*x^8*y^8 + 3*x^7*y^9 + 3*x^6*y^10 + 2*x^5*y^11 + 4*x^4*y^12 + 2*x^3*y^13 + x^2*y^14 - 3*x*y^15 - x^15 + 3*x^14*y + x^13*y^2 - x^12*y^3 - 3*x^11*y^4 + x^10*y^5 - x^9*y^6 + 2*x^8*y^7 - x^7*y^8 + 4*x^5*y^10 - 2*x^4*y^11 + x^3*y^12 - x^14 + x^13*y + 2*x^12*y^2 + x^11*y^3 - 5*x^10*y^4 - x^9*y^5 - 3*x^8*y^6 - 2*x^7*y^7 + x^6*y^8 + 3*x^5*y^9 + x^4*y^10 + 2*x^3*y^11 - x^2*y^12 - 4*x*y^13 + 3*y^14 + x^12*y - 2*x^11*y^2 - x^9*y^4 - x^8*y^5 + 5*x^7*y^6 - 4*x^6*y^7 + 3*x^5*y^8 + 4*x^4*y^9 - 3*x^3*y^10 - x^2*y^11 - 2*x*y^12 - 3*y^13 + 3*x^12 + x^11*y + x^10*y^2 + x^9*y^3 + x^8*y^4 - x^6*y^6 - x^5*y^7 - 4*x^3*y^9 - x^2*y^10 - 3*x*y^11 - 2*y^12 + x^10*y + 5*x^9*y^2 + x^8*y^3 + 3*x^5*y^6 + x^4*y^7 + 2*x^3*y^8 - 4*x^2*y^9 + 2*x*y^10 + 3*y^11 - x^10 - 2*x^9*y - 2*x^7*y^3 - x^6*y^4 + x^5*y^5 + 3*x^4*y^6 - 2*x^2*y^8 - x*y^9 + 4*x^9 - 3*x^8*y - 3*x^6*y^3 + x^5*y^4 - x^4*y^5 - 2*x^3*y^6 - 2*x^2*y^7 + x*y^8 + 4*y^9 + 2*x^8 - x^7*y - 2*x^5*y^3 - 4*x^4*y^4 + 3*x^3*y^5 + 4*x^2*y^6 + 2*x*y^7 - 2*y^8 + 2*x^7 + 3*x^5*y^2 + 3*x^2*y^5 - x*y^6 - 4*x^6 + 6*x^3*y^3 + 2*x^2*y^4 - 2*x*y^5 - 3*y^6 + x^5 - 3*x^4*y + x^3*y^2 + x^2*y^3 - 2*x*y^4 + 2*x^4 - 2*x^3*y + 6*x^2*y^2 - 3*x*y^3 - 2*y^4 - 5*x^3 - 2*x^2*y - 2*x*y^2 + 3*y^3 + 2*x^2 - x*y + y^2 - 2*x + 2*y - 2
w = 12796020294902567574981427270787776254781813995526831579805652479456168245098217943847166109912113827479436654134179666391771173421469188197935460525521295192736123648410762964187396897298542198935971755852754544978564521188423737649175136194386664628304164316905741781089536713701674793641345344818309314224
c = 10266913434526071998707605266130137733134248608585146234981245806763995653822203763396430876254213500327272952979577138542487120755771047170064775346450942
'''思路
- 这次题目中有两个未知数了,想办法消去一个,只要给原版的多项式乘上 $x^{32} (p^{32})$ ,就可以消掉全部的 $y (q)$
- 也可以把 $y$ 写成 $n//x$ ,然后 $x=1$ 代入多项式方程组,然后就都是根据费马定理解了
- 然后就是求 $flag$ ,其中 $flag$ 大于 $p$ ,且大于的较多所以没办法爆破求解,同时 $flag$ 具有一定特殊性
- 最后就是
easy_mod[[easy_mod]] - @ 2024-NSSCTF-密码工坊非官方dlc-wp-crypto | 糖醋小鸡块的blog
解答-13
把y写成n//x
from sympy import symbols, sympify
from Crypto.Util.number import *
n = 95656952327201449381426394713246214670537600365883923624876350719801926817916514429721785287844335184715049179879891389941974481490433975689601829920289485889138252888029716516069912637121531561601839948367426922036690701168975937162280451323099126372019216020898338909808577022618554997063496690156977790629
w = 12796020294902567574981427270787776254781813995526831579805652479456168245098217943847166109912113827479436654134179666391771173421469188197935460525521295192736123648410762964187396897298542198935971755852754544978564521188423737649175136194386664628304164316905741781089536713701674793641345344818309314224
f = '''x^31 - x^30*y - 2*x^29*y^2 + 7*x^28*y^3 + 2*x^27*y^4 - 4*x^24*y^7 + 3*x^23*y^8 - x^20*y^11 - 4*x^19*y^12 + x^18*y^13 - 5*x^17*y^14 - 4*x^16*y^15 - x^15*y^16 + x^14*y^17 + x^13*y^18 + x^12*y^19 - 2*x^11*y^20 - 3*x^9*y^22 + 5*x^7*y^24 + x^6*y^25 + 6*x^4*y^27 + x^3*y^28 + 2*x*y^30 + y^31 - 2*x^30 - 3*x^29*y + 2*x^28*y^2 + 2*x^27*y^3 - x^26*y^4 - x^25*y^5 - 2*x^24*y^6 - 3*x^23*y^7 - 3*x^22*y^8 - 3*x^20*y^10 - 4*x^19*y^11 + 2*x^18*y^12 + x^15*y^15 - x^14*y^16 - 2*x^12*y^18 - 3*x^11*y^19 - x^10*y^20 + x^9*y^21 + 2*x^8*y^22 + x^7*y^23 + x^5*y^25 - x^4*y^26 - 2*x^3*y^27 - 2*x^2*y^28 - y^30 - 2*x^29 - x^28*y + 3*x^26*y^3 - x^25*y^4 - 2*x^24*y^5 + x^23*y^6 - x^22*y^7 - x^20*y^9 + 2*x^19*y^10 + 2*x^18*y^11 + x^16*y^13 + x^15*y^14 + x^14*y^15 + x^13*y^16 + x^12*y^17 + 5*x^11*y^18 - x^9*y^20 - 2*x^8*y^21 - 5*x^7*y^22 - 2*x^6*y^23 + 3*x^5*y^24 - 5*x^3*y^26 - x^2*y^27 + 2*x*y^28 - y^29 + 3*x^28 + 3*x^27*y - 2*x^26*y^2 + x^25*y^3 + 2*x^24*y^4 - x^23*y^5 - 2*x^22*y^6 - 3*x^20*y^8 - 3*x^19*y^9 + 4*x^17*y^11 - x^16*y^12 - 3*x^15*y^13 - 2*x^14*y^14 + x^13*y^15 + 2*x^12*y^16 - 2*x^11*y^17 + x^10*y^18 - 2*x^9*y^19 + x^8*y^20 - 2*x^7*y^21 - x^6*y^22 + x^5*y^23 - x^4*y^24 + x^3*y^25 + x^2*y^26 - x*y^27 - y^28 + x^27 + x^26*y - 2*x^24*y^3 + x^23*y^4 - 3*x^22*y^5 - 2*x^21*y^6 - 2*x^20*y^7 - 5*x^19*y^8 + 2*x^18*y^9 - 5*x^17*y^10 + x^16*y^11 - 3*x^15*y^12 - 4*x^14*y^13 - x^13*y^14 + x^12*y^15 + 3*x^11*y^16 + 2*x^10*y^17 - 4*x^9*y^18 - 2*x^6*y^21 + x^5*y^22 + 4*x^3*y^24 + 2*x^2*y^25 + 2*x*y^26 - 2*y^27 + x^25*y + x^24*y^2 + x^23*y^3 + 5*x^22*y^4 + x^20*y^6 - 3*x^19*y^7 + x^18*y^8 - x^17*y^9 + 2*x^15*y^11 - x^14*y^12 + 2*x^13*y^13 - x^12*y^14 + 4*x^11*y^15 - x^10*y^16 - 2*x^6*y^20 - x^5*y^21 + 3*x^3*y^23 + x^2*y^24 - 3*x*y^25 - 3*y^26 + 3*x^25 - 2*x^23*y^2 - x^21*y^4 + x^17*y^8 + 2*x^16*y^9 - x^15*y^10 - 2*x^14*y^11 - x^13*y^12 + 2*x^12*y^13 - 2*x^11*y^14 - x^9*y^16 - x^8*y^17 - x^6*y^19 - x^5*y^20 + x^4*y^21 + x^3*y^22 + 5*x*y^24 - 2*y^25 - x^24 + 2*x^23*y + x^22*y^2 - x^21*y^3 - x^19*y^5 + x^18*y^6 - x^17*y^7 + 2*x^16*y^8 - 4*x^15*y^9 - x^14*y^10 - x^13*y^11 - x^12*y^12 + 4*x^10*y^14 + 2*x^9*y^15 - x^8*y^16 - 2*x^7*y^17 - 2*x^6*y^18 + 4*x^5*y^19 + x^4*y^20 + 2*x^2*y^22 - 5*x*y^23 - y^24 + x^23 - x^22*y + 2*x^21*y^2 - x^20*y^3 - x^18*y^5 - x^17*y^6 - 5*x^15*y^8 + x^14*y^9 - 3*x^13*y^10 + 3*x^12*y^11 + 2*x^11*y^12 - 2*x^10*y^13 - 2*x^9*y^14 - x^8*y^15 + 2*x^7*y^16 - 2*x^6*y^17 - 4*x^5*y^18 - 5*x^3*y^20 - x^2*y^21 - x*y^22 - 4*y^23 - x^22 + 2*x^21*y - 2*x^20*y^2 - 2*x^19*y^3 - 3*x^17*y^5 - x^16*y^6 - x^15*y^7 + 4*x^13*y^9 + 2*x^12*y^10 + 3*x^11*y^11 + 2*x^10*y^12 - x^9*y^13 - x^7*y^15 + 2*x^6*y^16 + x^3*y^19 + 2*x^2*y^20 + 2*x*y^21 + 3*y^22 - 3*x^21 - x^20*y - x^19*y^2 + 2*x^17*y^4 - x^16*y^5 - x^15*y^6 + x^14*y^7 - 5*x^12*y^9 - 2*x^11*y^10 + x^10*y^11 + x^6*y^15 + x^5*y^16 + x^4*y^17 - 3*x^2*y^19 - 2*x*y^20 - 2*y^21 + x^20 + 2*x^19*y - 2*x^17*y^3 + 2*x^16*y^4 - 3*x^15*y^5 + 4*x^14*y^6 + 2*x^13*y^7 - x^12*y^8 - 2*x^11*y^9 + x^10*y^10 + 6*x^9*y^11 + x^8*y^12 + x^7*y^13 + 2*x^5*y^15 + 4*x^4*y^16 + x^3*y^17 - x^2*y^18 + 3*x*y^19 - x^17*y^2 + 2*x^16*y^3 + 3*x^14*y^5 - x^13*y^6 + 2*x^11*y^8 + x^10*y^9 + 3*x^9*y^10 - x^7*y^12 - x^6*y^13 + 3*x^5*y^14 - 4*x^4*y^15 + x^2*y^17 + 2*y^19 - x^18 - x^16*y^2 - 2*x^14*y^4 - 2*x^13*y^5 - 2*x^12*y^6 + 2*x^11*y^7 + 3*x^9*y^9 + 3*x^8*y^10 + x^6*y^12 - x^4*y^14 + 2*x^3*y^15 + 2*x^2*y^16 - 2*x*y^17 - x^17 - 4*x^16*y - 2*x^15*y^2 + 2*x^14*y^3 - x^13*y^4 + x^12*y^5 - 2*x^11*y^6 - 3*x^10*y^7 - x^9*y^8 - 5*x^8*y^9 + 2*x^7*y^10 + 2*x^6*y^11 - x^5*y^12 + x^4*y^13 - 3*x^2*y^15 + x*y^16 - 3*x^16 + x^15*y - 3*x^14*y^2 - x^13*y^3 - x^12*y^4 + 2*x^11*y^5 - x^10*y^6 + 5*x^8*y^8 + 3*x^7*y^9 + 3*x^6*y^10 + 2*x^5*y^11 + 4*x^4*y^12 + 2*x^3*y^13 + x^2*y^14 - 3*x*y^15 - x^15 + 3*x^14*y + x^13*y^2 - x^12*y^3 - 3*x^11*y^4 + x^10*y^5 - x^9*y^6 + 2*x^8*y^7 - x^7*y^8 + 4*x^5*y^10 - 2*x^4*y^11 + x^3*y^12 - x^14 + x^13*y + 2*x^12*y^2 + x^11*y^3 - 5*x^10*y^4 - x^9*y^5 - 3*x^8*y^6 - 2*x^7*y^7 + x^6*y^8 + 3*x^5*y^9 + x^4*y^10 + 2*x^3*y^11 - x^2*y^12 - 4*x*y^13 + 3*y^14 + x^12*y - 2*x^11*y^2 - x^9*y^4 - x^8*y^5 + 5*x^7*y^6 - 4*x^6*y^7 + 3*x^5*y^8 + 4*x^4*y^9 - 3*x^3*y^10 - x^2*y^11 - 2*x*y^12 - 3*y^13 + 3*x^12 + x^11*y + x^10*y^2 + x^9*y^3 + x^8*y^4 - x^6*y^6 - x^5*y^7 - 4*x^3*y^9 - x^2*y^10 - 3*x*y^11 - 2*y^12 + x^10*y + 5*x^9*y^2 + x^8*y^3 + 3*x^5*y^6 + x^4*y^7 + 2*x^3*y^8 - 4*x^2*y^9 + 2*x*y^10 + 3*y^11 - x^10 - 2*x^9*y - 2*x^7*y^3 - x^6*y^4 + x^5*y^5 + 3*x^4*y^6 - 2*x^2*y^8 - x*y^9 + 4*x^9 - 3*x^8*y - 3*x^6*y^3 + x^5*y^4 - x^4*y^5 - 2*x^3*y^6 - 2*x^2*y^7 + x*y^8 + 4*y^9 + 2*x^8 - x^7*y - 2*x^5*y^3 - 4*x^4*y^4 + 3*x^3*y^5 + 4*x^2*y^6 + 2*x*y^7 - 2*y^8 + 2*x^7 + 3*x^5*y^2 + 3*x^2*y^5 - x*y^6 - 4*x^6 + 6*x^3*y^3 + 2*x^2*y^4 - 2*x*y^5 - 3*y^6 + x^5 - 3*x^4*y + x^3*y^2 + x^2*y^3 - 2*x*y^4 + 2*x^4 - 2*x^3*y + 6*x^2*y^2 - 3*x*y^3 - 2*y^4 - 5*x^3 - 2*x^2*y - 2*x*y^2 + 3*y^3 + 2*x^2 - x*y + y^2 - 2*x + 2*y - 2'''
x, y = symbols('x y')
f_expr = sympify(f)
f_substituted = f_expr.subs(y, n // x)
f1 = int(f_substituted.subs(x, 1))
#print("f(1) =", f1)
v = pow(2, f1, n)
p = GCD(n, v - w)
print(p)
#12887845651556262230127533819087214645114299622757184262163859030601366568025020416006528177186367994745018858915213064803349065489849643880676026721892753乘以p^32
N = 95656952327201449381426394713246214670537600365883923624876350719801926817916514429721785287844335184715049179879891389941974481490433975689601829920289485889138252888029716516069912637121531561601839948367426922036690701168975937162280451323099126372019216020898338909808577022618554997063496690156977790629
w = 12796020294902567574981427270787776254781813995526831579805652479456168245098217943847166109912113827479436654134179666391771173421469188197935460525521295192736123648410762964187396897298542198935971755852754544978564521188423737649175136194386664628304164316905741781089536713701674793641345344818309314224
P.<n,p> = PolynomialRing(ZZ)
n, p = P.gens()
f = n**31*p + 2*n**30*p**3 - n**30*p**2 - n**29*p**3 + n**28*p**7 - 2*n**28*p**6 + 2*n**28*p**5 - n**28*p**4 + 6*n**27*p**9 - 2*n**27*p**8 - n**27*p**7 - n**27*p**6 - 2*n**27*p**5 - n**26*p**10 - 5*n**26*p**9 + n**26*p**8 + 2*n**26*p**7 - 3*n**26*p**6 + n**25*p**13 + n**25*p**12 + n**25*p**10 + 2*n**25*p**9 - 3*n**25*p**8 - 2*n**25*p**7 + 5*n**24*p**15 + 3*n**24*p**13 - n**24*p**12 + 4*n**24*p**11 + n**24*p**10 + 5*n**24*p**9 - n**24*p**8 + n**23*p**16 - 2*n**23*p**15 + n**23*p**14 + 3*n**23*p**12 - 5*n**23*p**10 - 4*n**23*p**9 - 3*n**22*p**19 + 2*n**22*p**18 - 5*n**22*p**17 - n**22*p**16 + n**22*p**15 + n**22*p**13 + 2*n**22*p**12 - n**22*p**11 + 3*n**22*p**10 + n**21*p**20 - 2*n**21*p**19 - 2*n**21*p**18 - 2*n**21*p**17 - n**21*p**16 + n**21*p**15 - n**21*p**13 + 2*n**21*p**12 - 2*n**21*p**11 - 2*n**20*p**23 - n**20*p**22 - n**20*p**21 + n**20*p**20 - 2*n**20*p**18 - n**20*p**17 + n**20*p**16 - 5*n**20*p**15 + 2*n**20*p**14 - 2*n**20*p**13 + n**19*p**25 - 3*n**19*p**24 - 2*n**19*p**22 - n**19*p**19 + 4*n**19*p**18 + n**19*p**16 - 3*n**19*p**15 + 3*n**19*p**14 + 2*n**19*p**13 + n**18*p**27 - 2*n**18*p**26 + 5*n**18*p**25 + n**18*p**24 - 4*n**18*p**23 - 2*n**18*p**20 - 4*n**18*p**19 - n**18*p**16 + n**17*p**29 + n**17*p**27 - 2*n**17*p**26 + 2*n**17*p**25 - n**17*p**23 - 2*n**17*p**22 - 2*n**17*p**21 + n**17*p**19 + n**17*p**18 + n**17*p**17 - 2*n**17*p**16 - n**16*p**31 - n**16*p**30 + n**16*p**29 + 2*n**16*p**28 + 3*n**16*p**27 - n**16*p**26 - n**16*p**25 - n**16*p**24 + 2*n**16*p**23 + 2*n**16*p**22 + n**16*p**21 + 4*n**16*p**20 + 2*n**16*p**18 + n**16*p**17 - 4*n**15*p**33 + n**15*p**32 + n**15*p**31 + n**15*p**30 + n**15*p**29 + 4*n**15*p**28 + 2*n**15*p**26 - n**15*p**25 - n**15*p**24 + n**15*p**23 + 2*n**15*p**22 - 4*n**15*p**21 + 2*n**15*p**20 - 3*n**15*p**19 - 3*n**15*p**18 - 5*n**14*p**35 + n**14*p**33 - 2*n**14*p**32 - n**14*p**31 - n**14*p**30 - 2*n**14*p**29 + 4*n**14*p**28 - 2*n**14*p**27 + 3*n**14*p**23 - n**14*p**22 + n**14*p**20 + 3*n**14*p**18 + n**13*p**37 + n**13*p**35 - 3*n**13*p**34 - 4*n**13*p**33 + 2*n**13*p**32 + 2*n**13*p**31 - 2*n**13*p**29 - n**13*p**28 + n**13*p**26 - n**13*p**25 + n**13*p**23 + 2*n**13*p**22 - 4*n**13*p**20 - 3*n**13*p**19 - 4*n**12*p**39 + 2*n**12*p**38 - n**12*p**36 - 3*n**12*p**35 - n**12*p**34 - n**12*p**33 - n**12*p**32 + 2*n**12*p**31 + 2*n**12*p**30 + n**12*p**28 - n**12*p**27 + n**12*p**26 - n**12*p**25 + 4*n**12*p**24 + n**12*p**23 - n**12*p**22 - 2*n**12*p**21 - 2*n**12*p**20 - n**11*p**41 - 4*n**11*p**40 + 2*n**11*p**39 + 4*n**11*p**38 + n**11*p**37 + 2*n**11*p**36 - 2*n**11*p**35 - n**11*p**34 + 3*n**11*p**33 + 3*n**11*p**32 + n**11*p**31 + 6*n**11*p**30 + 2*n**11*p**27 + 2*n**11*p**26 - 2*n**11*p**25 + 2*n**11*p**24 - n**11*p**23 - 3*n**11*p**22 + 3*n**11*p**21 - 3*n**10*p**42 + 2*n**10*p**41 - 5*n**10*p**39 - n**10*p**37 - n**10*p**36 - 3*n**10*p**35 + 2*n**10*p**34 - 2*n**10*p**33 + n**10*p**32 + 3*n**10*p**31 + 3*n**10*p**30 + 2*n**10*p**29 + 3*n**10*p**28 + 4*n**10*p**27 + n**10*p**26 - 3*n**10*p**25 - n**10*p**24 + 2*n**10*p**23 - n**9*p**43 - 3*n**9*p**42 + 2*n**9*p**41 - n**9*p**40 + 2*n**9*p**39 - 4*n**9*p**38 + n**9*p**37 + 4*n**9*p**36 - 5*n**9*p**35 - 2*n**9*p**34 + n**9*p**33 + 3*n**9*p**32 - 5*n**9*p**31 + 3*n**9*p**30 + 3*n**9*p**28 + 4*n**9*p**27 - 4*n**9*p**26 - 4*n**9*p**25 - n**9*p**24 + 4*n**9*p**23 + 3*n**8*p**47 - 3*n**8*p**46 - 3*n**8*p**44 - 5*n**8*p**43 + n**8*p**42 + n**8*p**41 + 2*n**8*p**40 - 5*n**8*p**39 - n**8*p**36 + 2*n**8*p**35 - n**8*p**33 + 5*n**8*p**32 - n**8*p**31 + n**8*p**30 + 3*n**8*p**29 + 2*n**8*p**27 - 2*n**8*p**26 + n**8*p**25 - 2*n**8*p**24 - 4*n**7*p**49 - 3*n**7*p**48 - n**7*p**47 - 2*n**7*p**45 - 3*n**7*p**44 - n**7*p**42 - n**7*p**40 + n**7*p**39 + 2*n**7*p**38 + 2*n**7*p**36 - 3*n**7*p**35 + 2*n**7*p**33 - 2*n**7*p**32 - 4*n**7*p**31 - n**7*p**30 + n**7*p**29 - 2*n**7*p**27 + 2*n**7*p**26 - 2*n**6*p**50 + n**6*p**49 - 2*n**6*p**48 - 2*n**6*p**47 + n**6*p**46 + n**6*p**44 - n**6*p**43 - n**6*p**42 - n**6*p**41 + 4*n**6*p**40 - n**6*p**39 - 2*n**6*p**38 - 2*n**6*p**37 - n**6*p**36 - n**6*p**35 - 3*n**6*p**34 + 5*n**6*p**33 - n**6*p**32 + 3*n**6*p**31 + 3*n**6*p**30 - 2*n**6*p**29 + 4*n**6*p**28 - n**6*p**27 - 3*n**6*p**26 - n**5*p**52 - 2*n**5*p**51 - n**5*p**50 - 3*n**5*p**49 - n**5*p**46 - n**5*p**45 - 3*n**5*p**44 - n**5*p**43 - 3*n**5*p**42 + 3*n**5*p**41 - 2*n**5*p**40 + n**5*p**39 + 2*n**5*p**38 + n**5*p**37 - n**5*p**36 - n**5*p**35 + n**5*p**32 - n**5*p**31 + 3*n**5*p**30 + 3*n**5*p**29 - 2*n**5*p**28 + 2*n**4*p**55 - n**4*p**54 - n**4*p**53 + 2*n**4*p**52 + n**4*p**51 + 5*n**4*p**50 - n**4*p**49 + 2*n**4*p**45 + 2*n**4*p**44 - 2*n**4*p**42 - n**4*p**41 - n**4*p**40 - 3*n**4*p**39 - 5*n**4*p**38 - n**4*p**37 + n**4*p**36 - n**4*p**34 + n**4*p**33 - 4*n**4*p**32 + 2*n**4*p**30 - 2*n**4*p**29 - 2*n**4*p**28 + 7*n**3*p**57 + 2*n**3*p**56 + 3*n**3*p**55 + n**3*p**54 - 2*n**3*p**53 + n**3*p**52 - n**3*p**50 - n**3*p**49 - 2*n**3*p**48 - 2*n**3*p**46 + 2*n**3*p**45 + 2*n**3*p**43 - n**3*p**42 - n**3*p**41 + n**3*p**40 + n**3*p**38 + n**3*p**37 - 2*n**3*p**36 - 3*n**3*p**35 - 2*n**3*p**34 + 6*n**3*p**32 + n**3*p**31 - 3*n**3*p**30 + 3*n**3*p**29 - 2*n**2*p**59 + 2*n**2*p**58 - 2*n**2*p**56 + n**2*p**54 - 2*n**2*p**53 + n**2*p**52 + 2*n**2*p**51 - 2*n**2*p**50 - n**2*p**49 - n**2*p**47 - n**2*p**46 - 2*n**2*p**45 - 3*n**2*p**44 + n**2*p**43 + 2*n**2*p**42 - 2*n**2*p**41 + n**2*p**40 + 5*n**2*p**39 + 3*n**2*p**35 + n**2*p**33 + 6*n**2*p**32 - 2*n**2*p**31 + n**2*p**30 - n*p**61 - 3*n*p**60 - n*p**59 + 3*n*p**58 + n*p**57 + n*p**56 + 2*n*p**54 - n*p**53 + 2*n*p**52 - n*p**51 + 2*n*p**50 - 4*n*p**47 + n*p**46 + 3*n*p**45 + n*p**44 + n*p**43 + n*p**42 + n*p**41 - 2*n*p**40 - 3*n*p**39 - n*p**38 - 3*n*p**35 - 2*n*p**34 - 2*n*p**33 - n*p**32 + 2*n*p**31 + p**63 - 2*p**62 - 2*p**61 + 3*p**60 + p**59 + 3*p**57 - p**56 + p**55 - p**54 - 3*p**53 + p**52 - p**50 - p**49 - 3*p**48 - p**47 - p**46 + 3*p**44 - p**42 + 4*p**41 + 2*p**40 + 2*p**39 - 4*p**38 + p**37 + 2*p**36 - 5*p**35 + 2*p**34 - 2*p**33 - 2*p**32
for i, j in zip(f.monomials(), f.coefficients()):
w *= pow(2, -ZZ(j) * i.subs(p = 1, n = N), N)
w %= N
p = gcd(w - 1, N)
print(p)
#12887845651556262230127533819087214645114299622757184262163859030601366568025020416006528177186367994745018858915213064803349065489849643880676026721892753最终的easy_mod
from Crypto.Util.number import *
p = 12887845651556262230127533819087214645114299622757184262163859030601366568025020416006528177186367994745018858915213064803349065489849643880676026721892753
c = 10266913434526071998707605266130137733134248608585146234981245806763995653822203763396430876254213500327272952979577138542487120755771047170064775346450942
prefix = b"NSSCTF{"
suffix = b"}"
length = 88 - len(prefix) - len(suffix)
c -= 256^(len(suffix) + length) * bytes_to_long(prefix)
c -= bytes_to_long(suffix)
c = c * inverse(256,p) % p
L = Matrix(ZZ,length+2,length+2)
for i in range(length):
L[i,i] = 1
L[i,-1] = 256^i
c -= 256^i*48
L[-2,-2] = 5
L[-2,-1] = -c
L[-1,-1] = p
L[:,-1:] *= p
res = L.BKZ()
flag = ""
for i in res[:-1]:
if(abs(i[-2]) == 5 and all(abs(j) < 10 for j in i[:-2])):
for j in i[:-2][::-1]:
flag += chr(48 + abs(j))
print(flag)
#38886172735077060750460332815973614272222523052135584902884007925985948919714862
#NSSCTF{38886172735077060750460332815973614272222523052135584902884007925985948919714862}题目-14
import os
from Crypto.Util.number import *
flag=b"NSSCTF{xxxxxxxxxxxxxxxxxxx}"
p = getPrime(2048)
q = getPrime(2048)
n = p*q
g = n+1
flag = flag + os.urandom(256)
m = bytes_to_long(flag)
assert m < n
c=(pow(g,p,n*n)*pow(m,n,n*n))%(n*n)
print(f"c={str(c)}")
print(f"n={str(n)}")
print(f"hint={str(pow(m,n,n*n))}") 参数
# c=218076151021560547051903316719541222512040541728274127251955864973204319200312422995983092104505370830336341646283643290975865810979693431665790610118752578450560322701464606111124759353729454729357651736630354926734261137232304018105525402480409214739463624926019853406667257471858400554068936984966255122726345392299611192889869061539625603262461395069803838256649227551122691722958477064737646079234633593322257264277828874899605785719884582898801922036376706945214557655573105936069927519342707813584133447394527727777145289236041783964596526172298751923527410923728437653793368452092818162677292173126395038239746952564824349029187021070624008127312777783389153721156471730690460245726539173442219919067086198412985379251064006364545842890512676104195964096685904104471607447579133813262242889948684214615216415152003486684332654021763372875688811108164167029372542655680239691864011325001804416649090546652965592245015233937378914902555020997254559783431091213187054225512285704706127222748135840936979571164239968858574619878355623067035562073147836429462588372618500946665592533980646179287203705864082701267348885216165672773119373427706470575290690902668785242467233967870570261108990892859880739698792351646244754952340844420919259404502699266393058426943569348443212550646905609608670176752388829848639990144513783071090027192962534454341704209113094332822171724354423757760205937173503650126923081671379294681026909824698111163520911268295889474804858820122835834292711776643387277793548733641809948674628119693459864760337483163877679917119388740268787073315582536101385769332216844206772200893152057186765390268976281904057200764887141067277637744939424349347335952574178492737111320884889894593413406720620482887249419382551684677812936351975305964980443771310389160311391859989139144435489943187361252326617436405569045786172471146825826484820533463066934499480104433398977611810330276369147938097117995654985458513989302241106332776904067311803420489090552556891879767682415265560743407340298578130798877648570926192953127574474259716781135801273211777116319348356510073635809816358623224620898024473581877733194648312939500788032519396047197931401057492369464362250728505049498537131676040902419082386902837490490020207391112191256297932073021141841637862479797419191517126847743253818063471644376196087415026020405982443713386674133996026381008967344619818015476575693412862275373303754013892689230528546297224836909468991043799205998787941893011
# n=508649864931677614732467390772427961758931524996950943172348989353779413500135745017318030372818346445171787306774776609051270954621980771071637593801560166625137373096310055034937710873339570248386417692379532713565448110999149898224125057983565314582568870217037082321220190178702247284057805478222196862321877126877541221804916630403210745798454726695767965708773814502024042373335280648703042654755304969849832318086242798067639199224298659205981289856966590499810461072473369452077687615913217546268362501813809748922922532657782215807173319693469430751556310985767810712372068465527832726893651833030643914873945580271625080157996808574695857605733101549978621472016493582602814890278818563043847095493265778824174731054566468708287724290549925230267719117266452407869862605078436659020887227224470196270187491398217001451889275579626459491632506953638949085966203707446055610214983015428316166700670710716910016807567113694397559364621848368518820842900845963635710936101678917277407976769668789284143702572735353391307624460327339616496606065042109014043456540221432729574605562610831787594345569772727113605355252600129915926507232161710531913156415953128254338208741867773085355435238760994755555830964013004019492562245961
# hint=218453179086923289943807203202770838925178689627774745147232020515098516891161432630028304346664762962142685215503546042472463188085210756898964960254583869432945520650866749585786670220495127010275938757711518963512690357966318771229029024139860779906436335668507703089169058834533472932888386221671186182247869434699020350251916212956639268455849140594527951127570312231046210122761381292092058171708887595484453711631828228850043342993869671675498781490707220852504338423236844200845629493885003815571053367960570828719514793961666314203716137708394529735950110878173175859966298104855781891314256393660478947857997049309347664916363312769426872393903240797057291513182057786294193463281179876929436423970304992964378978343703058273610599094670858299390115880959442514513002687898361714995376183382702580310860520166550246905769724461107221385567718477106980293610194354260662299313387637029454859051754049141731708862005007657254777005078937290648653252057172789665484106225904252249322285164277069353595858401391763857781471982430400812430485462777863701578165740021651239264400111602346875691919587562776319002092593590043298682899772829734368041057265219520645505796166918571599787733464916168997021422429642875880015201743138557239246816614645961943942384226721696842364578221142494114967457346538723563534281835490913459152865031135512888020156712332950698315471031328945767161582387501768383019764191345069522790270253976284543970378444427727423121536104008553289510510497088596599741651012409020454471902200942494893254608355219933431097693790764370965829619433976045850073467615077879096698409574487772631069225578624386542659818683559823001358916184145187794138636007200677181455572920942709512649217555102476437241677652845050079961562071604521307752725300453167225947534296744839161286409625003203181858982730609149419917332043428767843293277924022007390853988328511663307394805322715579362345649842431371200748639996476587970393904239732072852670279076966635546790856059886353247283187091483814130965265452117641315707359747672993447721009270939662160468115475733881984431822454194850017395548046798675473636140217840418467588166347095543815767317284635513061287105795015042775738353765062476084211922890124244419037796630154403434882572164730631883001098922170198642065216541425903144234820480236095640278292837060194123091442480170728800340689332104613912950234195039809087610879082689821270573215009809335626725761798981628604037461376378712686098思路
类似于Paillier加密系统
- 已知参数
- $p$ , $q$ , $n = p*q$ , $g = n + 1$
- $c = (g^p \bmod n^2) * (m^n \bmod n^2) \bmod n^2$
- $hint = m^n \bmod n^2$
- 分解
p和q- 由加密公式 $c = (g^p * hint) \bmod n^2$ ,两边乘以 $hint$ 的逆元 $inv_h \bmod n^2$
- 可得: $T = (c * inv_h) \bmod n^2 = g^p \bmod n^2$
- 因为 $g = n + 1$ ,根据二项式展开: $(n+1)^p = 1 + C(p,1)n + C(p,2)n^2 + … + n^p$
- 对 $n^2$ 取模时, $n^2$ 及更高次项都会被消去,因此: $g^p \bmod n^2 = 1 + p*n$
- 因此 $T = 1 + p*n$ ,整理得: $p = (T – 1) // n$
- 从
hint还原明文m- 对质数 $p$ ,根据费马小定理:对 $m < p$ , $m^{(p-1)} \equiv 1 \bmod p$
- 由于 $n = pq$ ,则 $n \equiv q \bmod (p-1)$ (因为 $p \equiv 1 \bmod (p-1)$ ,所以 $pq \equiv 1*q \bmod (p-1)$ )
- 因此 $m^n \bmod p = m^q \bmod p$ ,即 $hint \bmod p = m^q \bmod p$ (记为 $h_p$ )
- 同理, $hint \bmod q = m^p \bmod q$ (记为 $h_q$ )
- 对 $h_p = m^q \bmod p$ ,需找 $q$ 的逆元 $d_p$ (模 $p-1$ ),使得 $q*d_p \equiv 1 \bmod (p-1)$ ,此时 $m \bmod p = h_p^{d_p} \bmod p$ (记为 $m_p$ )
- 对 $h_q = m^p \bmod q$ ,同理找 $p$ 的逆元 $d_q$ (模 $q-1$ ),得 $m \bmod q = h_q^{d_q} \bmod q$ (记为 $m_q$ )
- 最后用
CRT合并结果 - 已知 $m \equiv m_p \bmod p$ 和 $m \equiv m_q \bmod q$ ,需找 $m$ 满足: $m = m_p + k*p$ ( $k$ 为整数)
- 代入第二个式子得: $m_p + k*p \equiv m_q \bmod q$ ,解得 $k \equiv (m_q – m_p) * inv_p \bmod q$ ( $inv_p$ 是 $p$ 模 $q$ 的逆元)
- 最终 $m = m_p + p*k$ ,模 $n$ 后即为明文
解答-14
from Crypto.Util.number import *
c = 218076151021560547051903316719541222512040541728274127251955864973204319200312422995983092104505370830336341646283643290975865810979693431665790610118752578450560322701464606111124759353729454729357651736630354926734261137232304018105525402480409214739463624926019853406667257471858400554068936984966255122726345392299611192889869061539625603262461395069803838256649227551122691722958477064737646079234633593322257264277828874899605785719884582898801922036376706945214557655573105936069927519342707813584133447394527727777145289236041783964596526172298751923527410923728437653793368452092818162677292173126395038239746952564824349029187021070624008127312777783389153721156471730690460245726539173442219919067086198412985379251064006364545842890512676104195964096685904104471607447579133813262242889948684214615216415152003486684332654021763372875688811108164167029372542655680239691864011325001804416649090546652965592245015233937378914902555020997254559783431091213187054225512285704706127222748135840936979571164239968858574619878355623067035562073147836429462588372618500946665592533980646179287203705864082701267348885216165672773119373427706470575290690902668785242467233967870570261108990892859880739698792351646244754952340844420919259404502699266393058426943569348443212550646905609608670176752388829848639990144513783071090027192962534454341704209113094332822171724354423757760205937173503650126923081671379294681026909824698111163520911268295889474804858820122835834292711776643387277793548733641809948674628119693459864760337483163877679917119388740268787073315582536101385769332216844206772200893152057186765390268976281904057200764887141067277637744939424349347335952574178492737111320884889894593413406720620482887249419382551684677812936351975305964980443771310389160311391859989139144435489943187361252326617436405569045786172471146825826484820533463066934499480104433398977611810330276369147938097117995654985458513989302241106332776904067311803420489090552556891879767682415265560743407340298578130798877648570926192953127574474259716781135801273211777116319348356510073635809816358623224620898024473581877733194648312939500788032519396047197931401057492369464362250728505049498537131676040902419082386902837490490020207391112191256297932073021141841637862479797419191517126847743253818063471644376196087415026020405982443713386674133996026381008967344619818015476575693412862275373303754013892689230528546297224836909468991043799205998787941893011
n = 508649864931677614732467390772427961758931524996950943172348989353779413500135745017318030372818346445171787306774776609051270954621980771071637593801560166625137373096310055034937710873339570248386417692379532713565448110999149898224125057983565314582568870217037082321220190178702247284057805478222196862321877126877541221804916630403210745798454726695767965708773814502024042373335280648703042654755304969849832318086242798067639199224298659205981289856966590499810461072473369452077687615913217546268362501813809748922922532657782215807173319693469430751556310985767810712372068465527832726893651833030643914873945580271625080157996808574695857605733101549978621472016493582602814890278818563043847095493265778824174731054566468708287724290549925230267719117266452407869862605078436659020887227224470196270187491398217001451889275579626459491632506953638949085966203707446055610214983015428316166700670710716910016807567113694397559364621848368518820842900845963635710936101678917277407976769668789284143702572735353391307624460327339616496606065042109014043456540221432729574605562610831787594345569772727113605355252600129915926507232161710531913156415953128254338208741867773085355435238760994755555830964013004019492562245961
hint = 218453179086923289943807203202770838925178689627774745147232020515098516891161432630028304346664762962142685215503546042472463188085210756898964960254583869432945520650866749585786670220495127010275938757711518963512690357966318771229029024139860779906436335668507703089169058834533472932888386221671186182247869434699020350251916212956639268455849140594527951127570312231046210122761381292092058171708887595484453711631828228850043342993869671675498781490707220852504338423236844200845629493885003815571053367960570828719514793961666314203716137708394529735950110878173175859966298104855781891314256393660478947857997049309347664916363312769426872393903240797057291513182057786294193463281179876929436423970304992964378978343703058273610599094670858299390115880959442514513002687898361714995376183382702580310860520166550246905769724461107221385567718477106980293610194354260662299313387637029454859051754049141731708862005007657254777005078937290648653252057172789665484106225904252249322285164277069353595858401391763857781471982430400812430485462777863701578165740021651239264400111602346875691919587562776319002092593590043298682899772829734368041057265219520645505796166918571599787733464916168997021422429642875880015201743138557239246816614645961943942384226721696842364578221142494114967457346538723563534281835490913459152865031135512888020156712332950698315471031328945767161582387501768383019764191345069522790270253976284543970378444427727423121536104008553289510510497088596599741651012409020454471902200942494893254608355219933431097693790764370965829619433976045850073467615077879096698409574487772631069225578624386542659818683559823001358916184145187794138636007200677181455572920942709512649217555102476437241677652845050079961562071604521307752725300453167225947534296744839161286409625003203181858982730609149419917332043428767843293277924022007390853988328511663307394805322715579362345649842431371200748639996476587970393904239732072852670279076966635546790856059886353247283187091483814130965265452117641315707359747672993447721009270939662160468115475733881984431822454194850017395548046798675473636140217840418467588166347095543815767317284635513061287105795015042775738353765062476084211922890124244419037796630154403434882572164730631883001098922170198642065216541425903144234820480236095640278292837060194123091442480170728800340689332104613912950234195039809087610879082689821270573215009809335626725761798981628604037461376378712686098
n_2 = n * n
inv_h = pow(hint, -1, n_2)
T = (c * inv_h) % n_2
p = (T - 1) // n
q = n // p
h_p = hint % p
h_q = hint % q
d_p = pow(q, -1, p-1)
d_q = pow(p, -1, q-1)
m_p = pow(h_p, d_p, p)
m_q = pow(h_q, d_q, q)
inv_p = pow(p, -1, q)
m = (m_p + p * ((m_q - m_p) * inv_p % q)) % n
print(long_to_bytes(m))
#NSSCTF{937dc8be-8348-4925-ad7e-06b91aed8171}\xaf\xb2\xc9\xde\x90\xed\xa7\xaf-\rz`\xa4\'\xc8@\xcdp}\x00}Q{#\x8b\x13\x15F\xd8\x9cB\xd5Y\xc5U\x16\xefw\xb2\x15}\xf1\xac`w\x9a\xa2Hz:$\xed\x18P\xd0)\xce\xc8\xca5\xb3\xe6@\xd1\xcd\x15\xdf\xfa\xf7WtI}xG@\xdb4:\xa8\xff\xc0\xb6\xac\xefT\x97\xa7\xfe\x82C"\\M\xe7\xcc\x06k\xbeK\xc0\x1bV\xbd@\xd5\x92\xf5\xea\x88\x19\x84\xdaV\xdb\x10\\e \xedH\xa2%\xcfO\xe9=3\xd4,\x96`m\xb7\x04\xb8\x1a[\xeeyO\xaa\x9e(\x80\x04S\x93:\xda\x80\xa7\xbdq\xcc\x97\x17k\x02\xd4\xc8\x03\xb8\x1b\xc8[R\xbcv\xe2\x9c\x075\xa4\xf2\x8d\x00\xe0\t\x1d\xaaT\xf0.Sk\xa9\x15\x98`\x846c\xbcY\x18~X\x1b(\xfa\xefJw\x14\x05m\xf0o\xf5\x05\xbfb\xc7>\xd4\xf8\x84\xc7@\x96\x1bL~f\x96\x87[\xe6Q\x19])\xaa\xac\x9e\x86G\xc8\xae\x8d,\x82\xa7\x9dL\x1c\xd7"\x81\x0f1W\xab\xe2&
#NSSCTF{937dc8be-8348-4925-ad7e-06b91aed8171}题目-15
- ! 安恒四月春季战-not_RSA
from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse
from secret import flag,p,q
from sympy import isprime,nextprime
import random
m=bytes_to_long(flag)
n=p*q
g=n+1
r=random.randint(1,n)
c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n)
print "c=%d"%(c)
print "n=%d"%(n)
'''
c=29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
n=6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
'''思路
- 加密流程
- 选择两个大素数 $p$ , $q$ 使得 $\gcd(pq,(p-1)(q-1)) =1$
- $n=pq \quad and \quad \lambda =lcm(p-1,q-1)$
- 随机选择一个 $g$ 使得 $g \in Z_{n^2}^*$
- $\mu = (L(g^\lambda\mod n^2))^{-1}\mod n$ ,其中 $L(x) = \frac{x-1}{n}$
- 公钥为 $(n,g)$ ,私钥为 $(\lambda,\mu)$
- 随机选择 $r$ 使得 $r\in Z_n^ \quad and \quad \gcd(r,n) = 1$
- 密文为 $c=g^m r^n \mod n^2$
- $n$ 直接分解出来
解答-15-1
from Crypto.Util.number import *
from gmpy2 import *
#加密参考https://zhuanlan.zhihu.com/p/557034854
#解密参考https://zhuanlan.zhihu.com/p/259282416
p = 80006336965345725157774618059504992841841040207998249416678435780577798937819
q = 80006336965345725157774618059504992841841040207998249416678435780577798937447
n = 6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
c = 29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
lam = lcm(p-1,q-1)
g = n + 1
def L(x,n):
return (x - 1) // n
mu = pow(L(pow(g,lam,n**2),n),-1,n)
flag = (L(pow(c,lam,n**2),n) * mu) % n
print(long_to_bytes(flag))
#flag{5785203dbe6e8fd8bdbab860f5718155}
#或者
'''
lcm = ((p - 1) * (q - 1)) // gcd(p - 1,q - 1)
a = (pow(c,lcm,n * n) - 1) // n
b = (pow(n + 1,lcm,n * n) - 1) // n
print(long_to_bytes((a * inverse(b,n)) % n))
'''解答-15-2
from Crypto.Util.number import *
c=29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
n=6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
p=80006336965345725157774618059504992841841040207998249416678435780577798937819
q=80006336965345725157774618059504992841841040207998249416678435780577798937447
phi=(p-1)*(q-1)
c1=pow(c,phi,n*n)-1
c2=c1//n
m=(c2*inverse(phi,n))%n
print(long_to_bytes(m))
#flag{5785203dbe6e8fd8bdbab860f5718155}题目-16
- ! LitCTF2025-math
from Crypto.Util.number import *
from enc import flag
m = bytes_to_long(flag)
e = 65537
p,q = getPrime(1024),getPrime(1024)
n = p*q
noise = getPrime(40)
tmp1 = noise*p+noise*q
tmp2 = noise*noise
hint = p*q+tmp1+tmp2
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint = {hint}")
'''
n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141
e = 65537
c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196
hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164
'''思路
- 已知 $hint=p*q+tmp1+tmp2$
- 则 $hint-n=tmp1+tmp2=(p+q+noise)*noise$
- 直接分解 $hint-n$ 就可以得到 $noise$
解答-16
from Crypto.Util.number import *
import gmpy2
n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141
e = 65537
c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196
hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164
noise = 942430120937
sum_pq = ((hint - n) // noise) - noise
discriminant = sum_pq ** 2 - 4 * n
sqrt_discriminant = gmpy2.isqrt(discriminant)
p = (sum_pq + sqrt_discriminant) // 2
q = (sum_pq - sqrt_discriminant) // 2
print("p:", p)
print("q:", q)
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#LitCTF{db6f52b9265971910b306754b9df8b76}题目-17
- ! RoarCTF2020-EASYRSA
from Crypto.Util.number import *
from gmpy2 import *
from secret import *
assert(flag.startwith('flag{')) and (flag.endwith('}'))
assert(is_prime(beta) and len(bin(beta)[2:]) == 512)
assert(len(bin(x)[2:]) == len(bin(y)[2:]))
# This is tip!!!
assert(tip == 2*x*y*beta + x + y)
p = 2*x*beta + 1
q = 2*y*beta + 1
assert(is_prime(p) and is_prime(q))
n = p*q
e = 65537
m = bytes_to_long(flag)
enc = powmod(m,e,n)
#n=17986052241518124152579698727005505088573670763293762110375836247355612011054569717338676781772224186355540833136105641118789391002684013237464006860953174190278718294774874590936823847040556879723368745745863499521381501281961534965719063185861101706333863256855553691578381034302217163536137697146370869852180388385732050177505306982196493799420954022912860262710497234529008765582379823928557307038782793649826879316617865012433973899266322533955187594070215597700782682186705964842947435512183808651329554499897644733096933800570431036589775974437965028894251544530715336418443795864241340792616415926241778326529055663
#e=65537
#enc=10760807485718247466823893305767047250503197383143218026814141719093776781403513881079114556890534223832352132446445237573389249010880862460738448945011264928270648357652595432015646424427464523486856294998582949173459779764873664665361437483861277508734208729366952221351049574873831620714889674755106545281174797387906705765430764314845841490492038801926675266705606453163826755694482549401843247482172026764635778484644547733877083368527255145572732954216461334217963127783632702980064435718785556011795841651015143521512315148320334442235923393757396733821710592667519724592789856065414299022191871582955584644441117223
#beta=11864389277042761216996641604675717452843530574016671576684180662096506094587545173005905433938758559675517932481818900399893444422743930613073261450555599思路
- 已知 $tip=2xybeta+x+y$ , $p=2xbeta+1$ , $q=2y*beta+1$
- 可以推出 $n=pq=[4xybeta^2+2(x+y)*beta+1]$
- 所以 $tip=(n-1)//2*beta$
- 再根据模运算我们给 $tip$ 模一个 $beta$ 得到的就是 $x+y$ ,需要注意的是如果 $x+y$ 大于 $beta$ 那么取模可能会变小,需要 $+ beta * i$ 遍历一下
- 现在就可以求出 $xy$ 了, $xy=[tip-(x+y)]//2*beta$
- 最后用韦达定理求 $x$ 和 $y$
解答-17
from Crypto.Util.number import *
import gmpy2
n = 17986052241518124152579698727005505088573670763293762110375836247355612011054569717338676781772224186355540833136105641118789391002684013237464006860953174190278718294774874590936823847040556879723368745745863499521381501281961534965719063185861101706333863256855553691578381034302217163536137697146370869852180388385732050177505306982196493799420954022912860262710497234529008765582379823928557307038782793649826879316617865012433973899266322533955187594070215597700782682186705964842947435512183808651329554499897644733096933800570431036589775974437965028894251544530715336418443795864241340792616415926241778326529055663
e = 65537
enc = 10760807485718247466823893305767047250503197383143218026814141719093776781403513881079114556890534223832352132446445237573389249010880862460738448945011264928270648357652595432015646424427464523486856294998582949173459779764873664665361437483861277508734208729366952221351049574873831620714889674755106545281174797387906705765430764314845841490492038801926675266705606453163826755694482549401843247482172026764635778484644547733877083368527255145572732954216461334217963127783632702980064435718785556011795841651015143521512315148320334442235923393757396733821710592667519724592789856065414299022191871582955584644441117223
beta = 11864389277042761216996641604675717452843530574016671576684180662096506094587545173005905433938758559675517932481818900399893444422743930613073261450555599
tip = (n - 1) // (2 * beta)
for i in range(1000):
try:
x_y = tip % beta + beta * i
xy = (tip - x_y) // (2 * beta)
delta = x_y ** 2 - 4 * xy
sqrt_delta = gmpy2.isqrt(delta)
x = (x_y + sqrt_delta) // 2
y = (x_y - sqrt_delta) // 2
p = 2*x*beta + 1
q = 2*y*beta + 1
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(enc, d, n)
flag = long_to_bytes(m)
if b'flag{' in flag:
print(flag)
break
except:
continue
#flag{21824349-25bb-4f7f-b551-f13d4abba2e2}题目-18
- ! LitCTF2025-ez_math
from sage.all import *
from Crypto.Util.number import *
from uuid import uuid4
flag = b'LitCTF{'+ str(uuid4()).encode() + b'}'
flag = bytes_to_long(flag)
len_flag = flag.bit_length()
e = 65537
p = getPrime(512)
P = GF(p)
A = [[flag, getPrime(len_flag)],
[getPrime(len_flag), getPrime(len_flag)]]
A = matrix(P, A)
B = A ** e
print(f"e = {e}")
print(f"p = {p}")
print(f"B = {list(B)}".replace('(', '[').replace(')', ']'))
# e = 65537
# p = 8147594556101158967571180945694180896742294483544853070485096002084187305007965554901340220135102394516080775084644243545680089670612459698730714507241869
# B = [[2155477851953408309667286450183162647077775173298899672730310990871751073331268840697064969968224381692698267285466913831393859280698670494293432275120170, 4113196339199671283644050914377933292797783829068402678379946926727565560805246629977929420627263995348168282358929186302526949449679561299204123214741547], [3652128051559825585352835887172797117251184204957364197630337114276860638429451378581133662832585442502338145987792778148110514594776496633267082169998598, 2475627430652911131017666156879485088601207383028954405788583206976605890994185119936790889665919339591067412273564551745588770370229650653217822472440992]]思路
- 还是求 $phi=(p-1)$ , $d=e^{-1} \bmod phi$ ,不过对象是矩阵
解答-18
from Crypto.Util.number import *
e = 65537
p = 8147594556101158967571180945694180896742294483544853070485096002084187305007965554901340220135102394516080775084644243545680089670612459698730714507241869
B = [[2155477851953408309667286450183162647077775173298899672730310990871751073331268840697064969968224381692698267285466913831393859280698670494293432275120170, 4113196339199671283644050914377933292797783829068402678379946926727565560805246629977929420627263995348168282358929186302526949449679561299204123214741547], [3652128051559825585352835887172797117251184204957364197630337114276860638429451378581133662832585442502338145987792778148110514594776496633267082169998598, 2475627430652911131017666156879485088601207383028954405788583206976605890994185119936790889665919339591067412273564551745588770370229650653217822472440992]]
phi=p-1
d=inverse(e,phi)
P = GF(p)
B = matrix(P, B)
B =B ** d
print(long_to_bytes(int(B[0][0])))
#LitCTF{13dd217e-9a67-4093-8a1b-d2592c45ba82}题目-19
from Crypto.Util.number import *
from secret import flag
flag = b'qqqy{******}'
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
hint = pow(p + q, 2, n)
print(f'{n = }')
print(f'{c = }')
print(f'{hint = }')
'''
n = 76020466822456310884617974442149344673146982570325063127362255136870486628004398357898337643130692449143060346686808591020982993885441016972172751152349567557320114450245422870534961279639539904142973004902745429939780362855221593504681864612140468360381576935698641786837296966706600682387896997138453513771
c = 37487513414707375812445645078504470210533889513472111583843715084448961721162828867908670893334259654681058740344809192130385146865408520120584295737550360475161735267024492815581846573973869607965563003023041467118163111859760478080704149764561318795235428902163604403484275649269893770991321555950908087753
hint = 15485328737055540959221056196406184440098293880348574585177218216536432761437856593906393232054099724808247596696224862618129731577503310290680602087381600539139806961834392836258719233667577942475884836759735801070444229045163224329976095546175166303813982595335341043497631832194347491196314875327613622500
'''思路
- 这个
hint是 $(p+q)^2 \bmod n$ 的值,那么 $hint-n$ 就是 $(p^2+q^2) \bmod n$ ,但因为其对 $n$ 取余了,所以 $hint$ 比 $n$ 小 - 那我们尝试 $xn + hint$ 再开平方得到 $p+q$ ,最后 $hint-4n$ 开方得到 $p-q$ 即可求解
解答-19
from gmpy2 import *
from Crypto.Util.number import *
n = 76020466822456310884617974442149344673146982570325063127362255136870486628004398357898337643130692449143060346686808591020982993885441016972172751152349567557320114450245422870534961279639539904142973004902745429939780362855221593504681864612140468360381576935698641786837296966706600682387896997138453513771
c = 37487513414707375812445645078504470210533889513472111583843715084448961721162828867908670893334259654681058740344809192130385146865408520120584295737550360475161735267024492815581846573973869607965563003023041467118163111859760478080704149764561318795235428902163604403484275649269893770991321555950908087753
hint = 15485328737055540959221056196406184440098293880348574585177218216536432761437856593906393232054099724808247596696224862618129731577503310290680602087381600539139806961834392836258719233667577942475884836759735801070444229045163224329976095546175166303813982595335341043497631832194347491196314875327613622500
e = 65537
for x in range(10000):
ss = x*n + hint #(p+q)^2
s = gmpy2.isqrt(ss) #p+q
if s * s != ss:
continue
D = s * s - 4 * n #(p-q)^2
if D < 0:
continue
sqrt_D = gmpy2.isqrt(D) #p-q
p = (s + sqrt_D) // 2
q = (s - sqrt_D) // 2
assert p * q == n
#print(f"x = {x}")
#4
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)
break
#qqqy{this_is_easy_square_root}题目-20
- ! m0lec0nCTF2024-Quadratic Leak
from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes, bytes_to_long
flag = b'ptm{REDACTED}'
flag = bytes_to_long(flag)
key = RSA.generate(2048)
n = key.n
e = key.e
p, q = key.p, key.q
leak = (p**2 + q**2 - p - q)%key.n
ciph = pow(flag, key.e, key.n)
ciph = long_to_bytes(ciph)
print(f'{n = }')
print(f'{e = }')
print(f'{ciph = }')
print(f'{leak = }')
'''
n = 18981841105895636526675685852772632158842968216380018810386298633786155635996081803989776444322885832862508871280454015266715098097212762303823817669399277859053310692838636039765017523835850272300243126797277954387477501506925762258179024160726332434715115654485883242651742714579029928789693932848304595300833348009779987606253681750351002940239431890559231554840489325837351081804589516122959648786979395257143753954514874848903523580352634665455711644772319481340052722305319056316013353993453687301538982087215697860640865435677605005049256026879380517059221652220476972139202570771113865372482940490650024591211
e = 65537
ciph = b'/>\xf0a\xe4\x95a\xb8!h\x11[\xa01\xa2\x08\xd2\xa0\xd7G\xb0CU`\x97\xc7\xa2\xe9\x94\x10=\xf7\xd6y{\x01u\xcbl\xe1\x7f\x8d\xa0\xd8_\xba\x8a\xd9\x85\xc1\xcc\rK\xc7\xb6\xfb.(\x99%\x1f\x0b\xeci\nR\x8b\xcc>\x86\x18\xe1ie\x19\x9dI\xda\x9bNh8N\xe5\xf2\xf3kP\xeb\x02d\xdei\xadd\xa0\x17WKs~3ohp\xeb\x83\x17>[\x87K\xd1\x0e>\xf6\xeeR\x08\xc4y\x9c\xc7\xbf\xdaq\x9a\xff\x99EQSg\x04"H\xc0=\xfc\x1b\xdcA\x95\xb9\x15m\xe6\x04N\x81%\xda\xa5\xb2P\x02\xbb\xb9\x83\xbf\xcfR\xffe\x0fT\xd9=f\xc1\xab\xd3:\xfb\xf8k\xc0\xd1]V\xc6pK\x86T\xfe\xd5\xadb\x7f\x1b\xb1\x9d9\xe51\xb8\'BY\xcb\x934\x1e\xfb\xc8\x96V4\x0f\xb3\xe4\xd9\x92e;v\x88\x8e\x16\x14?\xe9ew\x95\x8c\xa2\xfc\xc3\xf7,\xd50\xc3@\x11|\x8a\xe0\xee\xf3u\xa0\x8a_?A2[\xad\x8e\x81\x99\xf0\r'
leak = 110277838449088002585424592968018361142419851286027284241723700708406129526007148628583636124051067276081936889565484783806534793568491888186904160969266846545579940493300734427497600123059580090561311191997050900418560468769108541786093143743441372956591688646550593311523980201035231511541259853198512190703006995530566933548862787123808685889850952840156903871573965022335639190635103252052979042642912530238710466180279568731038056810280199578414064760950459385877300845399348928704648108281000674478903445454838155321984920936780746021819652974978142789457099370813760033995294668404782700700352547809925049256
'''思路
- 已知 $p^2+q^2-(p+q) \bmod n$ ,跟上题一样遍历其模 $n$ 真实值
- 因为 $p^2 + q^2 = (p+q)^2 – 2pq = s^2 – 2n$ ,所以 $ss=s^2-2n-s$
- 当 $s$ 较大时(RSA中 $p$ , $q$ 都是大素数, $s = p+q$ 必然很大), $s^2 – s ≈ s^2$ ($s$ 相对于 $s^2$ 可以忽略),因此 $s^2 ≈ ss + 2n$
- $+2n$ 开方再 $+1$ 得到 $p+q$ ,剩下的步骤同上题
解答-20
from gmpy2 import *
from Crypto.Util.number import *
n = 18981841105895636526675685852772632158842968216380018810386298633786155635996081803989776444322885832862508871280454015266715098097212762303823817669399277859053310692838636039765017523835850272300243126797277954387477501506925762258179024160726332434715115654485883242651742714579029928789693932848304595300833348009779987606253681750351002940239431890559231554840489325837351081804589516122959648786979395257143753954514874848903523580352634665455711644772319481340052722305319056316013353993453687301538982087215697860640865435677605005049256026879380517059221652220476972139202570771113865372482940490650024591211
e = 65537
ciph = b'/>\xf0a\xe4\x95a\xb8!h\x11[\xa01\xa2\x08\xd2\xa0\xd7G\xb0CU`\x97\xc7\xa2\xe9\x94\x10=\xf7\xd6y{\x01u\xcbl\xe1\x7f\x8d\xa0\xd8_\xba\x8a\xd9\x85\xc1\xcc\rK\xc7\xb6\xfb.(\x99%\x1f\x0b\xeci\nR\x8b\xcc>\x86\x18\xe1ie\x19\x9dI\xda\x9bNh8N\xe5\xf2\xf3kP\xeb\x02d\xdei\xadd\xa0\x17WKs~3ohp\xeb\x83\x17>[\x87K\xd1\x0e>\xf6\xeeR\x08\xc4y\x9c\xc7\xbf\xdaq\x9a\xff\x99EQSg\x04"H\xc0=\xfc\x1b\xdcA\x95\xb9\x15m\xe6\x04N\x81%\xda\xa5\xb2P\x02\xbb\xb9\x83\xbf\xcfR\xffe\x0fT\xd9=f\xc1\xab\xd3:\xfb\xf8k\xc0\xd1]V\xc6pK\x86T\xfe\xd5\xadb\x7f\x1b\xb1\x9d9\xe51\xb8\'BY\xcb\x934\x1e\xfb\xc8\x96V4\x0f\xb3\xe4\xd9\x92e;v\x88\x8e\x16\x14?\xe9ew\x95\x8c\xa2\xfc\xc3\xf7,\xd50\xc3@\x11|\x8a\xe0\xee\xf3u\xa0\x8a_?A2[\xad\x8e\x81\x99\xf0\r'
leak = 110277838449088002585424592968018361142419851286027284241723700708406129526007148628583636124051067276081936889565484783806534793568491888186904160969266846545579940493300734427497600123059580090561311191997050900418560468769108541786093143743441372956591688646550593311523980201035231511541259853198512190703006995530566933548862787123808685889850952840156903871573965022335639190635103252052979042642912530238710466180279568731038056810280199578414064760950459385877300845399348928704648108281000674478903445454838155321984920936780746021819652974978142789457099370813760033995294668404782700700352547809925049256
for x in range(1000):
ss = leak + x * n #p^2+q^2-(p+q)
s = isqrt(ss + 2 * n) + 1 #p+q
if s * s - 4 * n < 0:
continue
sqrt_D = isqrt(s * s - 4 * n) #isqrt((p-q)^2)=p-q
if sqrt_D * sqrt_D != s * s - 4 * n:
continue
p = (s + sqrt_D) // 2
q = (s - sqrt_D) // 2
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(long_to_bytes(pow(bytes_to_long(ciph), d, n)))
break
#ptm{Nonlinear_Algebra_Preserved_Over_Large_Integers}
