当前位置: article > 正文

2023 金砖ctf 密码wp_lcg 赛题 2023金砖

作者：我家自动化 | 2024-05-26 22:31:25

踩

lcg 赛题 2023金砖

题目如下


from Crypto.Util.number import *
from gmpy2 import *
from flag import flag
 
p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
e = 2023
 
a = pow(p+q, e, p*q)
b = pow(p+r, e, p*r)
c = pow(q+e, p, p*q)
d = pow(r+e, p, p*r)
print('a =', a)
print('b =', b)
print('c =', c)
print('d =', d)
 
phi = (p - 1)*(q - 1)*(r - 1)
n = p * q * r
e = e // gcd(e, phi)
pri = invert(e, phi)
plaintext = bytes_to_long(flag)
cipher = powmod(plaintext, e, n)
print('n =', n)
print('cipher =', cipher)
# a = 33022028261473232777495374489369984051173051765914698583738518002899904080523156837934749116742046277602367384435566675571554308103705904368259935553616909439053270303487771097937681411464233154789299798806729983958502682142190437300710333776343215351258409122741296694039365121701417931039351706449620933965
# b = 81094699539404597343145361125240498679809760332244536460451475832258379562399932681242912311485592104271252217309012830898060896041053659829385735202726553288600509493460180497835520339585127754273226762440611089795375598402111645618656148576588630597445547241467407938373779128315636192164727397109721371821
# c = 84271446189918339833844652348525276763886039158109929437916837238145526361383913885452712470249189911870483017509012824863702488719752612973997881394827167428837538802085223497834025041680433523842549305188960285145390142799963207261252716937469861672320881012026095221908641651584348583973984309599037601834
# d = 15123960887720641582473419411098607262340676763761583670149167561153634913307686118729176007021398862293975304379052309333724796000639317958549447559668843718134962233429595288688678289005300880495334503517799794958574524554067587882588738019194484329080120346211069604574355250202792739546620819511246051563
# n = 1305868362648956325108280699763961840235386671096061258456713954912731266673615837291582943747254404537935708260445169059805285844455841287219831463541106816288497639968189178634434642486867351457926262375796661302973440152867035648809800493109491306147763847782394757396926743318935458828143518191396384284418328375027978975482054453851125577336298275344893200656160561055796833366777132752509479244984517627109717567602238626834388842622601028046927506740105339
# cipher = 276625828551392451826511027008206245152906197958085623086229291363825163886169570753509917102894042740178793715930242597220990395554264570261869266530944288249880918648891613062189780553447229285518845120492754395430894258029324206721471149988053813319167588002898010914570319764757802782204461185081609022963705109732366715784498564685186711202882635722034792366950992854058484819139254900134224781513310691313446400801249008245006958186077485159435259984132664

a = pow(p+q, e, p*q)
b = pow(p+r, e, p*r)
c = pow(q+e, p, p*q)
d = pow(r+e, p, p*r)

题目的核心在于将这些式子联立，最终与n进行gcd 求出p

a = pow(p+q, e, p*q) $\rightarrow$ a $\equiv$ (p+q)^e%n

因为模n和模p一定是同余的(从别的师傅那问的)

所以可以得出a $\equiv$ (p+q)^e%p

进行一个二项是展开可以的到a $\equiv$ (q)^e%p

同里也可以对c进行同样的操作得到

c = pow(q+e, p, p*q) $\rightarrow$ c $\equiv$ (q+e)^p%p

由于欧拉定理可得c $\equiv$ (q+e)%p

所以a $\equiv$ ((c-e)^e)%p

所以可得gcd((a-(c-e)^e),n)=p

#p=9960273084392107672753408173717925902570408106372638927850338055098682523167049858267154607197113573840345304698630106571582758897437426803951229913557867

c $\equiv$ (q+e)%p $\rightarrow$ (c-e)%p=q%p

由于p已经求出可得q=k*p+(c-e)%p

由于p和q都是512为所以遍历一下即可的q，r自然就可以求出

最后即可正常的求出rsa解密即可

exp如下：


from gmpy2 import*
from Crypto.Util.number import*
a = 33022028261473232777495374489369984051173051765914698583738518002899904080523156837934749116742046277602367384435566675571554308103705904368259935553616909439053270303487771097937681411464233154789299798806729983958502682142190437300710333776343215351258409122741296694039365121701417931039351706449620933965
b = 81094699539404597343145361125240498679809760332244536460451475832258379562399932681242912311485592104271252217309012830898060896041053659829385735202726553288600509493460180497835520339585127754273226762440611089795375598402111645618656148576588630597445547241467407938373779128315636192164727397109721371821
c = 84271446189918339833844652348525276763886039158109929437916837238145526361383913885452712470249189911870483017509012824863702488719752612973997881394827167428837538802085223497834025041680433523842549305188960285145390142799963207261252716937469861672320881012026095221908641651584348583973984309599037601834
d = 15123960887720641582473419411098607262340676763761583670149167561153634913307686118729176007021398862293975304379052309333724796000639317958549447559668843718134962233429595288688678289005300880495334503517799794958574524554067587882588738019194484329080120346211069604574355250202792739546620819511246051563
n = 1305868362648956325108280699763961840235386671096061258456713954912731266673615837291582943747254404537935708260445169059805285844455841287219831463541106816288497639968189178634434642486867351457926262375796661302973440152867035648809800493109491306147763847782394757396926743318935458828143518191396384284418328375027978975482054453851125577336298275344893200656160561055796833366777132752509479244984517627109717567602238626834388842622601028046927506740105339
cipher = 276625828551392451826511027008206245152906197958085623086229291363825163886169570753509917102894042740178793715930242597220990395554264570261869266530944288249880918648891613062189780553447229285518845120492754395430894258029324206721471149988053813319167588002898010914570319764757802782204461185081609022963705109732366715784498564685186711202882635722034792366950992854058484819139254900134224781513310691313446400801249008245006958186077485159435259984132664
p=9960273084392107672753408173717925902570408106372638927850338055098682523167049858267154607197113573840345304698630106571582758897437426803951229913557867
e=2023
q=(c-e)%p+p
r=n//(p*q)
phi=(p-1)*(q-1)*(r-1)
e = e // gcd(e, phi)
d = invert(e, phi)
print(long_to_bytes(pow(cipher,d,n)))

可得flag

题目二


from secret import flag1, flag2
from gmpy2 import *
from Crypto.Util.number import *
 
m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)
 
def crypto1():
    length = m1.bit_length()
    a = getPrime(length)
    b = getPrime(length)
    m = getPrime(length)
    seed = m1
    output = []
    for i in range(10):
        seed = (a * seed + b) % m
        output.append(seed)
    print('output =', output)
 
def crypto2():
    m2_list = []
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 65537
    hint = powmod(2023 * q + 231103, p, n)
    c = []
    for i in range(len(m2_list)):
        c.append(int(powmod(m2_list[i], e, n)))
    print('c =', c)
    print('hint =', hint)
    print('nn =', n)
 
 
if __name__ == "__main__":
    crypto1()
    crypto2()
 
 
# output = [834653491090491712633760412777668482940684660, 963076666352276362933538153002557560276280585, 2680203877874696332529229520897896728035506440, 91858763922260510630160081492878643315221800, 179788783853351298046757117828345043944048910, 360189746914947261716838580980986928642259725, 1736536856400074029770851415755580673843781308, 1808021479900001497137673789265033052269563590, 1346369077150300179482561724405766566952716635, 2373070631657135370182962105386676320122698203]
# c = [25847117187564871147435977084310306888566983947533004007989507337302539448480660807400683631363037653323934655651536186195280144682282353338543988255095017564445193404201888360133098540124851755959520837089763142801881928435268639528998342405671374458752513354539623987641502292860424789824821508164066272325770454748703578945224156715971852577415342573152893595235493853234913150977184258529336202627461923875735036697841654561514417522586550567378435285727198208058151978028557619162834201070541097195611731200747178680644768761982034231425678341030415924899159928495497028791178552538387129954559459763486327397495, 2597993625898355131484686342642309548795549744986725437883422220238469085558875757418450133138609822456943968225927170364424344868040971841273067049081737515747884333142281160445801303333836123845195912632562871356499781514584148581245515233115435723319476908364475050944242999136486703821143769471968138440124145530159671206754459370985465492566841462887505700941413433303715576098224261742093505350242034497519349407497777840172671192513216651564778906388396162801076827093006861045453570939861667532351024688470022614391154946506206441355424901586644479443525206657200572321372868844771543146316459090158237181485, 2956527082066005164561821388448100413980058583346277188583843824057419295810072898451369974163664755524425406595092397181986202718599608676179025031672282789436288948166928300110786209041044643721963370664940963632603933877281404708280178459041841708863372035515895098193171794312771806822915232474821156532199456764289878170018358177794776126914245869062801083550971077561138689631826523106346667272445377205775932664350287319013373305343462758601941303804928455951370971893879093306929954617900630030164289394598699531267233453384013624287377087291174939289828864037772928737393008162118289258286909501985362295250, 24036359762192210612772216769280114763208471974956110358289952031832098084828316561012418821617228782053541665864931310703316886399402056757764367689999619081631788274207110438077894515491113950417695236611549302087737274711598540385232596160893200047079701589026141261112677074246250660711304079526781323031017830575312638032983137631928441724643068481283545018803215210820804425555615450341977378009083739669781292422413452909078695371859602951598617246723144643126038655203226020666569895519804781384684439089335013980271232648439988606125378545939020092644249623842729559919989410863356579288445314409370178474913, 3960363997589091480620107707211527346101509845142720321898628336810863500058399159107020570632760171583534173401747329014528165255811069267070342780557403219399202730513433346453017621259760388296924253978403037548122517473820088310735552144534877249705087543212438419537791801443623898662973517240548544630134753268280883355876468179760669428141037183575543020006316152289487999929337824359152627636004505961598612840979874902797770962325130525727812624140794438592392086716400523426505924643746377468358809269120102817977913346347887587250920306849645308740722351056575000057487879867306011223614731297637597389043, 19756293830168853506927251598786663302423547949939792595396365605557902176326841521914210558560101263240178286187344187007060920294606321179475442350736784741671759625019400592362483562240110524971943000520191614792589182461376693581255307965759647471787720229065051847213683029417007973713108156619851632918676731647220197394961430421738622620486859204140708188824209667620326849216032913138770508668745908255553971420899580341712899904058277264721198474032211468761694480952081632136747978707742286059674698424990033807956279371642269034887638278918724784178277289072578590524756705371433948355612999958351743990687, 17168619227875497909505939901538074210134896632967963453959488780245871108281300680739199130988768448884508766712433096659677272221474910220398498663465096600092751130706024334981335422994473791003403952348398712253381581055353963195606773755635837012381200529862673389537304536484437523586598301845411466647682253612584638116870758898534046313551493130902889215549744949455783525071657216963778321172413207671885400604972544452862110787806833176337316070491476202319472780767186730105114477599590013789692334667535406037577527189857145152460091371996475309191121964214791589876841386626445042490619304540000268744167]
# hint = 9338337483016165146898805881521198487541269309312832770436948511851832795941266791467994915578419649411572460435260271128921674759992557197545048249434470787607127732811475208233811711545397847068095165612619003606564161170506468897933819532076007793540250883667417425343082043376105603896166033385911408654609024224333133291817708574091425998982236982208848625894644349373591225115610127472627985717732283759324902607157365503370214811285637714767888436301307605770837070222961915979595273212415836871397473400733701288540538544080768855638638602293660616424571436692781529212135754748657495513441649887066399815641
# n = 26566298366382781281519125908424786963856550387674011415220761270178028565618620245185406648984634617854974445206610724734810892857339091633516947351741440994788700191189799988764343173914647096591779575666237861785163473720879395772744646178861521824163120894355954423163952598346158736490791956395261881103850207837298161904327244534821781661369671670803090335416464433768389172123558423828978582126115690776079581448080326998411708109024924484401975676011214124545502085738463524352787144445657656328837938664026202112240260840770445848444946039300979250933967179986200453997139662050410254918283621862756292376613

分析题目显然的第一段flag使用了lcg加密，套个模板脚本即可解密


from gmpy2 import*
from Crypto.Util.number import*
x = [834653491090491712633760412777668482940684660, 963076666352276362933538153002557560276280585, 2680203877874696332529229520897896728035506440, 91858763922260510630160081492878643315221800, 179788783853351298046757117828345043944048910, 360189746914947261716838580980986928642259725, 1736536856400074029770851415755580673843781308, 1808021479900001497137673789265033052269563590, 1346369077150300179482561724405766566952716635, 2373070631657135370182962105386676320122698203]
t = []
for i in range(1, len(x)):
    t.append(x[i] - x[i-1])
m = 0
for i in range(1, len(t)-1):
    m = GCD(t[i+1]*t[i-1] - t[i]*t[i], m)
print(m)
assert isPrime(m)
a = (x[2] - x[1]) * inverse(x[1] - x[0], m)
b = (x[1] - a*x[0]) % m
 
inva = inverse(a, m)
 
for i in range(2**16):
    x[0] = (x[0]-b)*inva % m
 
    flag = long_to_bytes(x[0])
    if b'flag' in flag:
        print(flag)

后一段flag

重点在于这个，hint = powmod(2023 * q + 231103, p, n)

h $\equiv$ (2023*q+231103)^p%q

h $\equiv$ (231103)^p%q

h^q $\equiv$ (231103)^n%q

h^q%q=(231103)^n%q

费马定理得

h=(231103)^n%q

h-(231103)^n=k*q

所以得gcd(h-(231103)^n,n)=q

后面即可正常求解

exp如下


c = [25847117187564871147435977084310306888566983947533004007989507337302539448480660807400683631363037653323934655651536186195280144682282353338543988255095017564445193404201888360133098540124851755959520837089763142801881928435268639528998342405671374458752513354539623987641502292860424789824821508164066272325770454748703578945224156715971852577415342573152893595235493853234913150977184258529336202627461923875735036697841654561514417522586550567378435285727198208058151978028557619162834201070541097195611731200747178680644768761982034231425678341030415924899159928495497028791178552538387129954559459763486327397495, 2597993625898355131484686342642309548795549744986725437883422220238469085558875757418450133138609822456943968225927170364424344868040971841273067049081737515747884333142281160445801303333836123845195912632562871356499781514584148581245515233115435723319476908364475050944242999136486703821143769471968138440124145530159671206754459370985465492566841462887505700941413433303715576098224261742093505350242034497519349407497777840172671192513216651564778906388396162801076827093006861045453570939861667532351024688470022614391154946506206441355424901586644479443525206657200572321372868844771543146316459090158237181485, 2956527082066005164561821388448100413980058583346277188583843824057419295810072898451369974163664755524425406595092397181986202718599608676179025031672282789436288948166928300110786209041044643721963370664940963632603933877281404708280178459041841708863372035515895098193171794312771806822915232474821156532199456764289878170018358177794776126914245869062801083550971077561138689631826523106346667272445377205775932664350287319013373305343462758601941303804928455951370971893879093306929954617900630030164289394598699531267233453384013624287377087291174939289828864037772928737393008162118289258286909501985362295250, 24036359762192210612772216769280114763208471974956110358289952031832098084828316561012418821617228782053541665864931310703316886399402056757764367689999619081631788274207110438077894515491113950417695236611549302087737274711598540385232596160893200047079701589026141261112677074246250660711304079526781323031017830575312638032983137631928441724643068481283545018803215210820804425555615450341977378009083739669781292422413452909078695371859602951598617246723144643126038655203226020666569895519804781384684439089335013980271232648439988606125378545939020092644249623842729559919989410863356579288445314409370178474913, 3960363997589091480620107707211527346101509845142720321898628336810863500058399159107020570632760171583534173401747329014528165255811069267070342780557403219399202730513433346453017621259760388296924253978403037548122517473820088310735552144534877249705087543212438419537791801443623898662973517240548544630134753268280883355876468179760669428141037183575543020006316152289487999929337824359152627636004505961598612840979874902797770962325130525727812624140794438592392086716400523426505924643746377468358809269120102817977913346347887587250920306849645308740722351056575000057487879867306011223614731297637597389043, 19756293830168853506927251598786663302423547949939792595396365605557902176326841521914210558560101263240178286187344187007060920294606321179475442350736784741671759625019400592362483562240110524971943000520191614792589182461376693581255307965759647471787720229065051847213683029417007973713108156619851632918676731647220197394961430421738622620486859204140708188824209667620326849216032913138770508668745908255553971420899580341712899904058277264721198474032211468761694480952081632136747978707742286059674698424990033807956279371642269034887638278918724784178277289072578590524756705371433948355612999958351743990687, 17168619227875497909505939901538074210134896632967963453959488780245871108281300680739199130988768448884508766712433096659677272221474910220398498663465096600092751130706024334981335422994473791003403952348398712253381581055353963195606773755635837012381200529862673389537304536484437523586598301845411466647682253612584638116870758898534046313551493130902889215549744949455783525071657216963778321172413207671885400604972544452862110787806833176337316070491476202319472780767186730105114477599590013789692334667535406037577527189857145152460091371996475309191121964214791589876841386626445042490619304540000268744167]
hint = 9338337483016165146898805881521198487541269309312832770436948511851832795941266791467994915578419649411572460435260271128921674759992557197545048249434470787607127732811475208233811711545397847068095165612619003606564161170506468897933819532076007793540250883667417425343082043376105603896166033385911408654609024224333133291817708574091425998982236982208848625894644349373591225115610127472627985717732283759324902607157365503370214811285637714767888436301307605770837070222961915979595273212415836871397473400733701288540538544080768855638638602293660616424571436692781529212135754748657495513441649887066399815641
n=26566298366382781281519125908424786963856550387674011415220761270178028565618620245185406648984634617854974445206610724734810892857339091633516947351741440994788700191189799988764343173914647096591779575666237861785163473720879395772744646178861521824163120894355954423163952598346158736490791956395261881103850207837298161904327244534821781661369671670803090335416464433768389172123558423828978582126115690776079581448080326998411708109024924484401975676011214124545502085738463524352787144445657656328837938664026202112240260840770445848444946039300979250933967179986200453997139662050410254918283621862756292376613
p=gcd((pow(231103,n,n)-hint),n)
q=n//p
 
phi=(p-1)*(q-1)
e=65537
d=invert(e,phi)
m=[]
for i in c:
    m1=int(pow(i,d,n))
    m.append(m1)
flag2=long_to_bytes(math.prod(m))
print(flag2)

最后两段flag拼接即可。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/628691