NKCTF2023

数字中国 Babysecret

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import *
from secrets import flag
assert len(flag) == 38
t = 30
p = getPrime(512)
x = getPrime(512)
while x > p:
    x = getPrime(512)
rs = []
cs = []
ss = []
for i in range(t):
    r = getPrime(512)
    s = getPrime(400)
    c = (r * x + s) % p
    rs.append(r)
    cs.append(c)
    ss.append(s)

enc = pow(x,flag,p)
print(f'p = {p}')
print(f'rs = {rs}')
print(f'cs = {cs}')
print(f'enc = {enc}')

# p = 6897108443075981744484758716081045417854227543713106404294789655180105457499042179717447342593790180943415014044830872925165163457476209819356694244840079
# rs = [12844634549263053228759749264403637022740290008286987401585068952741935277415527678380021212624846722242500708422759563558995936977274580301379494195702461, 12251634003683452916928102291170339939586644029776192301741341674585154859358419625191986830852794085541953563738986709807899575511700135958334229151930861, 7051370666077542197248638013011793824477073777322219545882367881807130066168444134964571398112151848834032654978368255218649720738040945429837692857031957, 9773046862351952930368505593284546267554571295872377323111558071278701231472975791962979256551519533723988556870551885073742407630481198192389750289392107, 8883776497660138308720006912582738672888752344326928153810910221453595077711284302041512529457450211602787210761461172326429880594024187025419873043435877, 12056735137145460036580841038332100311160368843873164649606343042416896898793233249873902218683966283969721460087390120622254758027779960740926123005377571, 8819958747150954554494406068232243249186433676383469322817152210037563032056202909377825740775383087605647374150477096718956454225946093710691864988563109, 12246023449098354751049599873213988024512286270964608502444597112110163392131757813461977030270733012385926751192637938686124570227538910606279104888073013, 11308837998867241929817950595621831002334468993828126438599805989088017326675963100044309448653090403889186401929445861220402556074702741108929442867300279, 9184622887414209361516593101129556569811888214607556630094969763910426953786020755838094184972397480276666170685926425137063559394969166216392939257091541, 12896400069515890897430087815982545671830645201023665112429779640768899091287291452408369445919464144390726200808875066389240126909811239597092893733457339, 11227025698697471809912850435140886785315702278826761054472525227951791647003561270585720797267604996360933395122286757099101227901032364782594523739698877, 8162123490656317490361880020667919072708091053716891870691544217490126444997503404094174246087938828993696335191488583306443577208796794274099282013427247, 13366989889442670291461262313757977600095962057470863475519088648267301129719953368943419562144276679400967122727554764013132918505564677243979978807323041, 9920857455945408588203972193444437533164351309299040911469275059092031755811492460585653948481522995557801781838215407648572999358456612525812067538372579, 7139402473546047825312503780125417567716958846513076797328672521987900978293260385267945187604725349720103672258987935569856239987227455748213833342843243, 13108142660294572752252393081421368493392921884487755391460006730258159004638343897340537616297811742032405724656497443006056456690449881719305597286675631, 13276762958403786077380090195631980415297280849950287990717193547481553124160398455403123819234755237450529090601858784999113026218918277529515287668651121, 12463094640052886550696551772104539361264529587569204472038955376345085195998921095774583176899949596998985033050547755235409943131811058035802010421860899, 11307743131694864808301935844724645695851330736969875190167422024500753079857478680029193758960169072890576310607053767920339034290416580654771095674487943, 10053742503547378455068966704402695956702795408343604912294923217443553169726438945982031485796964462946592530592946335569560364464958066521486506177193131, 9703695763451799125258961776229325510814289358679213305418559381901496449849584244211834872313767844996255556721041007654625153809128987422992102292472533, 8148189465927721940294369879439913703690047528695196368949823197675716174991296513758196009346701553643721225250628151384047219921709201619262393792138023, 9114150910964237818418367840207724528917302406836157928223872622442928604249864486858755737149640683259834299165900696585038569188627682022002709058902291, 12273514376180781903469287345188404399033432117915094289694407562166649079228640510678711431664410226301556172582177240184695103942141430877677144285616059, 8355005721684425514882933910286584148305344580589623112959517428993968438533866906223777778058096962333203237111245328436600994120168924143849685728268811, 8957883838807471492147480816683526636019698464133185237668243268667169800811696770484487123560197988448434475112352005768286417529319182162245840523697001, 12168542584724814356632409768687396920143300559579648963851924568387314914334359305942685551210180448419674060219496395116081866784918059237133414041227833, 12285935007930825571672128346804313607196190465690759870758278705086034778808662886056460827935986285259185071514490942831585313190946386878622608868345563, 7719913817859572377164973343651155934060296607908537845256755472465025202751239980758950094865067751407889569369974011139801401586939119147773466111699913]
# cs = [3911325901261770731066343727353093385607196883601022244426857460074338420692610012414571623512152485474248169220030587839849722757773859682519433853455847, 4198555117325325874584019691418573071733167640213933749582347442518997588452211673143722179281773602455507001395983681009769848414007206268682184816168744, 4422173666634983234895098798813962037875417568235708524339826709271381748884936178371767574064794177416615710120223914725873239836121654705208614576413533, 3540260422555697887869627546208164711550015909378340105077652177481959576550678379723450981807556863572610759824660630418670546203733170058626755080797998, 6451498467498935201092514865627931677091078787997097414208430992183264950579022373372254486595458117887305393317663712337699331503725124287017134808484874, 3439629581963524351810430910737336124616316641656190641248434504621774235943514617301857917041111617104850245148746427180069743940612560718213177903427306, 4279468191481832212496939242093486044278976937965085475567008228061184947513156012369586970486543083130565628906296600553024574099481246534878242920637212, 4102135455518061133919027670571325279976222647984452353051395864554309521223498761823084717077102213648612826513661629599971609555235760152049549057234342, 329051927890365028889097463563711966673066795688728876214731188783168691555262156515161429328581094087585127929869064685419149676592073496155898360311360, 1674347209896897571502352451063188834938904430329951752111921115230349947823188121972980025563878887201507629419811736910690965020923751424101521816057970, 4779084317811375050159574994746297486592271247137823471375199626788956576998627181220489952507937768042501203098391966702297812537463211799837921684467541, 5240331815784322792144549873873658636726233093228415489098002982220769676718681132737794994708716389174162820721646744776624413735318240597745363490427584, 2689716894922604875455207695253665212853470308341743040957367957727155614199743562225147359614514189877983156892749669804800163252617480446565479990148021, 449708769594599088851244243076921016853502252396793496349534051273454215985560340288452398756880916680293627457774430655982228613348249480600180821975835, 1584603978331289335352997151059666773277943458357161051278658090420067023680231414255557805410288144092653121568766136372728095300982743309696347031121424, 4874260053151700374809337053763032489184725334196495160358275038586824027920238733886703163018450814805937363825223459277373073591021082276610135118976834, 3524374131362906900545297291947110177298862564718451821839794960169356082042548386553363480921097452902723033854749443288682983558847052843293666815425196, 6544123591499569232021913370293570477776709315008783531720886545784773471486769240711262562401683145937715612435213816372680189321141928790509490282629891, 4873861166228118967099569086478548167127431415017791678812419676791754466935832034870862000658789609084166891933970013849850146718379819943737269970654866, 4100817874436703071716655163972145036104985973164830547825929590871920825981241934633977227547934514142660786061291026657802357404024236287955309372489516, 343238276681348130286495167739162902430650061145485619903964358840996341335935043000395056684771452815629410388891486531126938900311458948803147120186532, 2683710724350412998770392318832434885304538325033159937379489319924346689197445720734209841902612235485016866254994045969716413020197296428323832404151182, 5909464641105704179999104311562416363090166762341644691188169716182958971270396007422581429813172933930581475771306034495224054972725230757675444731953480, 105593489999747649490909471306354863316673821363863362258853043970534652401274789197677558215188249074837829003335733211890211648501689656345824858507373, 4992379366542645691375959247465888889778118153982142100956809440855745659745235576280578316185469306620017845690312554043770651058126536040173113949524396, 6533456398244789907636779407045515567135195474284185379689518387558345997627435421582437390053234675991361808532278264077968540197407743744279106871716267, 5169360398767270275853790242315213671633880428212603766301308853363063092609582572957561138022806887895634140899640025570759919257615537375706008159680239, 203310740924699994885931266978520636166917734618272844754878785050509801614513144739164450834936178065792112797202959106365282699245578309060905297742706, 3143563289239398127009575193211845399079310618985464994769603542400451633289266080869317336163844517539211542909055869608349639432145332113320465388067087, 4016252180207572047405081190649590978593306403200098541033213590567723751195926093369984531729148621419589009515870336049849542537363832071754623330736088]
# enc = 1315637864146686255246675143589215932218700984880749264689270214639479160648747323586062096067740047809798944996253169402675772469028914904598116394230426

\(enc=pow(x,flag,p)\),离散对数问题，p 是光滑的，后续可通过 PH 求解，但 x 未知

\(c=(rx+s)\;mod\;p\),c 和 r 是 30 位的向量，通过 LWE 求解 x 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

from sage.modules.free_module_integer import IntegerLattice
from Crypto.Util.number import *
import hashlib
row = 30
column = 1
p = 6897108443075981744484758716081045417854227543713106404294789655180105457499042179717447342593790180943415014044830872925165163457476209819356694244840079
rs = [12844634549263053228759749264403637022740290008286987401585068952741935277415527678380021212624846722242500708422759563558995936977274580301379494195702461, 12251634003683452916928102291170339939586644029776192301741341674585154859358419625191986830852794085541953563738986709807899575511700135958334229151930861, 7051370666077542197248638013011793824477073777322219545882367881807130066168444134964571398112151848834032654978368255218649720738040945429837692857031957, 9773046862351952930368505593284546267554571295872377323111558071278701231472975791962979256551519533723988556870551885073742407630481198192389750289392107, 8883776497660138308720006912582738672888752344326928153810910221453595077711284302041512529457450211602787210761461172326429880594024187025419873043435877, 12056735137145460036580841038332100311160368843873164649606343042416896898793233249873902218683966283969721460087390120622254758027779960740926123005377571, 8819958747150954554494406068232243249186433676383469322817152210037563032056202909377825740775383087605647374150477096718956454225946093710691864988563109, 12246023449098354751049599873213988024512286270964608502444597112110163392131757813461977030270733012385926751192637938686124570227538910606279104888073013, 11308837998867241929817950595621831002334468993828126438599805989088017326675963100044309448653090403889186401929445861220402556074702741108929442867300279, 9184622887414209361516593101129556569811888214607556630094969763910426953786020755838094184972397480276666170685926425137063559394969166216392939257091541, 12896400069515890897430087815982545671830645201023665112429779640768899091287291452408369445919464144390726200808875066389240126909811239597092893733457339, 11227025698697471809912850435140886785315702278826761054472525227951791647003561270585720797267604996360933395122286757099101227901032364782594523739698877, 8162123490656317490361880020667919072708091053716891870691544217490126444997503404094174246087938828993696335191488583306443577208796794274099282013427247, 13366989889442670291461262313757977600095962057470863475519088648267301129719953368943419562144276679400967122727554764013132918505564677243979978807323041, 9920857455945408588203972193444437533164351309299040911469275059092031755811492460585653948481522995557801781838215407648572999358456612525812067538372579, 7139402473546047825312503780125417567716958846513076797328672521987900978293260385267945187604725349720103672258987935569856239987227455748213833342843243, 13108142660294572752252393081421368493392921884487755391460006730258159004638343897340537616297811742032405724656497443006056456690449881719305597286675631, 13276762958403786077380090195631980415297280849950287990717193547481553124160398455403123819234755237450529090601858784999113026218918277529515287668651121, 12463094640052886550696551772104539361264529587569204472038955376345085195998921095774583176899949596998985033050547755235409943131811058035802010421860899, 11307743131694864808301935844724645695851330736969875190167422024500753079857478680029193758960169072890576310607053767920339034290416580654771095674487943, 10053742503547378455068966704402695956702795408343604912294923217443553169726438945982031485796964462946592530592946335569560364464958066521486506177193131, 9703695763451799125258961776229325510814289358679213305418559381901496449849584244211834872313767844996255556721041007654625153809128987422992102292472533, 8148189465927721940294369879439913703690047528695196368949823197675716174991296513758196009346701553643721225250628151384047219921709201619262393792138023, 9114150910964237818418367840207724528917302406836157928223872622442928604249864486858755737149640683259834299165900696585038569188627682022002709058902291, 12273514376180781903469287345188404399033432117915094289694407562166649079228640510678711431664410226301556172582177240184695103942141430877677144285616059, 8355005721684425514882933910286584148305344580589623112959517428993968438533866906223777778058096962333203237111245328436600994120168924143849685728268811, 8957883838807471492147480816683526636019698464133185237668243268667169800811696770484487123560197988448434475112352005768286417529319182162245840523697001, 12168542584724814356632409768687396920143300559579648963851924568387314914334359305942685551210180448419674060219496395116081866784918059237133414041227833, 12285935007930825571672128346804313607196190465690759870758278705086034778808662886056460827935986285259185071514490942831585313190946386878622608868345563, 7719913817859572377164973343651155934060296607908537845256755472465025202751239980758950094865067751407889569369974011139801401586939119147773466111699913]
cs = [3911325901261770731066343727353093385607196883601022244426857460074338420692610012414571623512152485474248169220030587839849722757773859682519433853455847, 4198555117325325874584019691418573071733167640213933749582347442518997588452211673143722179281773602455507001395983681009769848414007206268682184816168744, 4422173666634983234895098798813962037875417568235708524339826709271381748884936178371767574064794177416615710120223914725873239836121654705208614576413533, 3540260422555697887869627546208164711550015909378340105077652177481959576550678379723450981807556863572610759824660630418670546203733170058626755080797998, 6451498467498935201092514865627931677091078787997097414208430992183264950579022373372254486595458117887305393317663712337699331503725124287017134808484874, 3439629581963524351810430910737336124616316641656190641248434504621774235943514617301857917041111617104850245148746427180069743940612560718213177903427306, 4279468191481832212496939242093486044278976937965085475567008228061184947513156012369586970486543083130565628906296600553024574099481246534878242920637212, 4102135455518061133919027670571325279976222647984452353051395864554309521223498761823084717077102213648612826513661629599971609555235760152049549057234342, 329051927890365028889097463563711966673066795688728876214731188783168691555262156515161429328581094087585127929869064685419149676592073496155898360311360, 1674347209896897571502352451063188834938904430329951752111921115230349947823188121972980025563878887201507629419811736910690965020923751424101521816057970, 4779084317811375050159574994746297486592271247137823471375199626788956576998627181220489952507937768042501203098391966702297812537463211799837921684467541, 5240331815784322792144549873873658636726233093228415489098002982220769676718681132737794994708716389174162820721646744776624413735318240597745363490427584, 2689716894922604875455207695253665212853470308341743040957367957727155614199743562225147359614514189877983156892749669804800163252617480446565479990148021, 449708769594599088851244243076921016853502252396793496349534051273454215985560340288452398756880916680293627457774430655982228613348249480600180821975835, 1584603978331289335352997151059666773277943458357161051278658090420067023680231414255557805410288144092653121568766136372728095300982743309696347031121424, 4874260053151700374809337053763032489184725334196495160358275038586824027920238733886703163018450814805937363825223459277373073591021082276610135118976834, 3524374131362906900545297291947110177298862564718451821839794960169356082042548386553363480921097452902723033854749443288682983558847052843293666815425196, 6544123591499569232021913370293570477776709315008783531720886545784773471486769240711262562401683145937715612435213816372680189321141928790509490282629891, 4873861166228118967099569086478548167127431415017791678812419676791754466935832034870862000658789609084166891933970013849850146718379819943737269970654866, 4100817874436703071716655163972145036104985973164830547825929590871920825981241934633977227547934514142660786061291026657802357404024236287955309372489516, 343238276681348130286495167739162902430650061145485619903964358840996341335935043000395056684771452815629410388891486531126938900311458948803147120186532, 2683710724350412998770392318832434885304538325033159937379489319924346689197445720734209841902612235485016866254994045969716413020197296428323832404151182, 5909464641105704179999104311562416363090166762341644691188169716182958971270396007422581429813172933930581475771306034495224054972725230757675444731953480, 105593489999747649490909471306354863316673821363863362258853043970534652401274789197677558215188249074837829003335733211890211648501689656345824858507373, 4992379366542645691375959247465888889778118153982142100956809440855745659745235576280578316185469306620017845690312554043770651058126536040173113949524396, 6533456398244789907636779407045515567135195474284185379689518387558345997627435421582437390053234675991361808532278264077968540197407743744279106871716267, 5169360398767270275853790242315213671633880428212603766301308853363063092609582572957561138022806887895634140899640025570759919257615537375706008159680239, 203310740924699994885931266978520636166917734618272844754878785050509801614513144739164450834936178065792112797202959106365282699245578309060905297742706, 3143563289239398127009575193211845399079310618985464994769603542400451633289266080869317336163844517539211542909055869608349639432145332113320465388067087, 4016252180207572047405081190649590978593306403200098541033213590567723751195926093369984531729148621419589009515870336049849542537363832071754623330736088]
enc = 1315637864146686255246675143589215932218700984880749264689270214639479160648747323586062096067740047809798944996253169402675772469028914904598116394230426
ss=[1444695997149492190325503358748907180896428744501435959012446197804471238996228693169795874437240656170107638535797004901, 1710106002173551002425444054140394178956124023376657957303230765508377089074717746465653815466763654648249527857825569029, 2055313300434754785614061534661234769322543457763273072311107482412288908659564309179643251560799446038081677516598963457, 2529893752644237783483797815212946495982855556933204694011832676840091910035653685416019963608166318536749345810876453771, 2529138628117798443470937234045077945473928204906198619005287365776711527156367496383631463561676109741862230251586143377, 2262110335813452474430699656412885234503426852605393691899881796634211611052330735315181940758828054398894455017113733227, 2121889637450522029350552877626679809458662297228865521642554573119772081854990312156453774280770474194162502389497160327, 2529142548180563996394639773713532833480273727306125086719935756161917184911736806616267916075735106590544780324467585621, 1305329295536404276170448056500700469825272137020946460143963140200353157377196505556280067991447170875038122866415550101, 1552852098086060808737139123645915631099187828325664479373402352780546739207516108015428990851489119938061929818491926611, 1791104999803661806603955436215385390826508049741363470424060526111730352962999232609779584743853648363257676913487057757, 1899442479566327507595284152198923816070020299280413329026247522765072323119884753949208875377108001657197781777679291871, 1453541167592343188338822229691660044736912312708428492831729087255748263545506909467533920598337452593734393704376978807, 1839970255647517988033776502403781838348352314214922889121617450060735210741294955388142534936822274443404021805803333703, 1912160881436961130805854105580691921433605240682869508192604979038043884642959974735162453664737011078276186132003267537, 2543565462805293682479626661848772865479251641709980622442153819428251437133653745822570184749929330644293218076375940297, 2483083156651635774502843350477278413827965814754343098791424022880695703529884053363101276861390834327295178464586090169, 2003169101542395781256109850378099343661620656525906226012777618825679882882750121108967747380040440812305500025030472703, 1495306582962644344763635303973344887376634002664321023099433581011613385215984473933899539552759121449556619118213926953, 1475475640507405435263556560927151140961838107291429033550823738085598452588645697451453622811307836240178487270066202731, 1585296258758653869729779396633477768935787077644413518874111953612262499991020378795132976171831363612740565577673589949, 1751870981277054153889475362865184270808672777814739187606382420502953249942908536146994775691865449715881103437411562697, 2229385019858443633247567841668512226312552028112872103049568509800432132563139223600501334488455486995847787457023057543, 2509522757833822636876029295601980862244548996153272433687613093337042904569711801805004013230589715380175225102878772429, 1378538686540733061307578409608662896663843431656273949667551098986968433993734090533525999772678987014720821134447883279, 1615745464810222578868113006917238415594773977456189037245148298498578637163332628299020222221658719347173123797381998597, 2064151464294100789516756482456818746190321203565732371731029967136921201410297069827915522687620140104021460523804416353, 1711545496198775131056637405659683132417828376528113270088200929297233962942202546621239829931304134031695960814215807973, 1455761879282217336477189039622363054351048993520687962567785409775020556422692091664440576775863933336882803763246548923, 1880891423536411979565374334582143474888275578342367502429189125513290153271930355071969557105539679922217905887177950249]

prime=p
ma=rs
res = cs

W = matrix(ZZ, ma)
cc = vector(ZZ, res)
#LWE求解x
# Babai's Nearest Plane algorithm
def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(5):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -=  M[i] * c
    return target - small

A1 = matrix.identity(column)
Ap = matrix.identity(row) * prime
B = block_matrix([[Ap], [W]])
lattice = IntegerLattice(B, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, res)
re = Babai_closest_vector(lattice.reduced_basis, gram, target)
# print("Closest Vector: {}".format(re))

R = IntegerModRing(prime)
M = Matrix(R, ma)
M = M.transpose()

ingredients = M.solve_right(re)

#求出x后利用PH算法对flag进行还原，因为发现p-1可以分解，p是光滑阶
# x=6789891305297779556556571922812978922375073901749764215969003309869718878076269545304055843125301553103531252334876560433405451108895206969904268456786139
x=int(ingredients[0])
print(x)
m=x
c=enc
n=p

def r(h, g, N, p, qi):
    Zp = Zmod(p)
    h = pow(h, N//qi, p)
    g = pow(g, N//qi, p)
    ri = discrete_log(Zp(h), Zp(g))
    return int(ri)
m=x
c=enc
n=p

tmp_list=[2,3,193,877,2663,662056037,812430763,814584769,830092927,849943517,969016409,1000954193,1022090869,1048277339]

r_list = []
for qi in tmp_list:
    tmp = r(c,m,n-1,n,qi)
    print(tmp)
    r_list.append(tmp)
x = crt(r_list, tmp_list)

module = 1
for i in tmp_list:
    module *= i

while True:
    if int(x).bit_length()>304:
        print('fail')
        break
    if int(pow(m, x, n))==c:
        print('x =', x)
        print(long_to_bytes(x))
        break
    x += module
#b'flag{70b1b709ce431682addb581596320007}'

NKCTF2023

babyRSA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
nbit = 512
flag='****************************'

p=getPrime(nbit)
q=getPrime(nbit)
e=65537
n=p*q
m= bytes_to_long(bytes(flag.encode()))
P = pow(m,p,n)
Q = pow(m,q,n)
N=P*Q
phi_N=(P-1)*(Q-1)
d=inverse(e,phi_N)
dP=d%(P-1)
print('n = ',n)
print('N = ',N)
print('dP = ',dP)


n =  114101396033690088275999670914803472451228154227614098210572767821433470213124900655723605426526569384342101959232900145334500170690603208327913698128445002527020347955300595384752458477749198178791196660625870659540794807018881780680683388008090434114437818447523471527878292741702348454486217652394664664641
N =  1159977299277711167607914893426674454199208605107323826176606074354449015203832606569051328721360397610665453513201486235549374869954501563523028914285006850687275382822302821825953121223999268058107278346499657597050468069712686559045712946025472616754027552629008516489090871415609098178522863027127254404804829735621706042266140637592206366042515190385496909533329383212542170504864473944657824502882014292528444918055958758310544435120502872883857209880723535754528096143707324179005292445100655695427777453144657819474805882956064292780031599790769618615908501966912635232746588639924772530057835864082951499028
dP =  33967356791272818610254738927769774016289590226681637441101504040121743937150259930712897925893431093938385216227201268238374281750681609796883676743311872905933219290266120756315613501614208779063819499785817502677885240656957036398336462000771885589364702443157120609506628895933862241269347200444629283263

题目分析

题目后半部分是 dp 泄露，通过 N、e、dP 可求出 P、Q

1
2
3
4
5
6
7
for k in range(1,e):
    if (e*dP-1)%k == 0:
        P=(e*dP-1)//k + 1
        if N%P == 0:
            print(P)
            break
Q=N//P

法一

之后要通过\(P = m^p\;mod\;n\)与\(Q=m^q\; mod \;n\)来求解 m，下面进行一些数学推导

\[c_1^q=m^{pq}\;mod\;n\] \[c_1^{pq}=c_2^{p^2}\;mod\;n\] \[c_1^{pq}=c_2^{p^2}\;mod\;p\]

根据费马小定理转换可得

\[c_1^n=c_2^p\;mod\;p\] \[gcd(c_1^n-c_2,n)\;=\;p\]

求出 p 和 q 后，使用 crt 即可求得 m

1
2
3
4
5
6
7
8
c1=(pow(P,n,n)-Q)%n
p=GCD(c1,n)
q=n//p
mp=P%p
mq=Q%q
m=CRT([mp,mq],[p,q])
print(long_to_bytes(m))
# NKCTF{Th1S_a_babyRSA_y0u_are_tql!!!}

法二

通过推导将原式转换为

\[PQ=(k_1p+m)(k_2q+m)\] \[m(P+Q)=2m^2+(k_1p+k_2q)m\] \[PQ-m(P+Q)+m^2=k_1k_2n\] \[PQ-m(c_1+c_2)+m^2=0\;mod\;n\]

1
2
3
4
5
PR.<m> = PolynomialRing(Zmod(n))
f = P*Q-m^2-m*(P-m+Q-m)
f = f.monic()
m = f.small_roots(X=2^400, beta=0.4)
print(long_to_bytes(int(m[0])))

ezRSA

已知 phi 分解 n,后续同 babyRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from math import gcd
from math import isqrt
from random import randrange


def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if is_prime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if is_prime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return tuple(prime_factors)
e=65537
n = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505626165666334675100147790578546682128517668100858766784733351894480181877144793496927464058323582165412552970999921215333509253052644024478417393146000490808639363681195799826541558906527985336104761974023394438549055804234997654701266967731137282297623426318212701157416397999108259257077847307874122736921265599854976855949680133804464839768470200425669609996841568545945133611190979810786943246285103031363790663362165522662820344917056587244701635831061853354597
phi = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505622503351461565956106005118029537938273153581675065762015952483687057805462728186901563990429998916382820576211887477098611684072561849314986341226981300596338314989867731725668312057134075244816223120038573374383949718714549930261073576391501671722900294331289082826058292599838631513746370889828026039555245672195833927609280773258978856664434349221972568651378808050580665443131001632395175205804045958846124475183825589672204752895252723130454951830966138888560
a=factorize_multi_prime(n,phi)

ez_math

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from Crypto.Util.number import getPrime, bytes_to_long
from secret import BITS, hints, flag

p = getPrime(BITS)
q = getPrime(BITS)
n = p * q
print(f'n = {n}')

e = 0x10001
c = pow(bytes_to_long(flag), e, n)
print(f'c = {c}')

print('Give you some boring pows:')
for i in range(len(hints)):
    print(hints[i])

"""
n = 369520637995317866367336688225182965061898803879373674073832046072914710171302486913303917853881549637806426191970292829598855375370563396182543413674021955181862907847280705741114636854238746612618069619482248639049407507041667720977392421249242597197448360531895206645794505182208390084734779667749657408715621
c = 324131338592233305486487416176106472248153652884280898177125443926549710357763331715045582842045967830200123100144721322509500306940560917086108978796500145618443920020112366546853892387011738997522207752873944151628204886591075864677988865335625452099668804529484866900390927644093597772065285222172136374562043
Give you some boring pows:
pow(6, 42762902032363446334121451790132830028099011269558028556333775251728898854654431095595000922138958455510196735338223430882428451914478079186797153527810555787441234842366353864053114538165236037883914332840687123514412294276743506313011532002136735343280737244020115917460801848337792582496228600926958548903290, n) = 4
pow(6, 141997416965295486849546892322458652502850390670128808480582247784728456230996812361056958004801816363393016360646922983916999235770803618904474553309200419301820603229504955218189709387942156848904968053547462302189568831762401075340100029630332409419313772378068180267756675141584884876543484516408660699471038, n) = 9
pow(6, 163378867981477210016607618217525067516899896304907822758749135410592905658324027908854458465871295591148114728316034699358213461728042658497873130073105697195541220650688132150216266657024774867846925219967805863946774978900772828496605795631400777090954141000078238226487076065753781167791598816872139973922682, n) = 3
pow(5, 101651508435846472131121026992982127175369332865677196032272241712711171024515826370577416844824734811581351106736224929238579734879671732717639124571916168742336862493284572465162318403582113621582374924091725060981390318743531229548188092491836655143124663368239422819562367919547196053790207486164506763679128, n) = 4
pow(8, 7202269322818255506843028035725052687541091567764933235328308385449791332345247877549905289072216053144576876979686287212194040101112899704499548530779540409356827298148385589812450437990490353926475147376495772639210184768544932563432306664067058309318707174880146258394471096033723193568453520897758319446472, n) = 3
pow(6, 64144353048545169501182177685199245042148516904337042834500662877593348281981646643392501383208437683265295103007335146323642677871717118780195730291715833681161852263549530796079671807247854056825871499261030685271618441415115259469517298003205103014921105866030173876191202772506688873744342901390437823354935, n) = 8
pow(6, 21381451016181723167060725895066415014049505634779014278166887625864449427327215547797500461069479227755098367669111715441214225957239039593398576763905277893720617421183176932026557269082618018941957166420343561757206147138371753156505766001068367671640368622010057958730400924168896291248114300463479274451645, n) = 2
pow(4, 21606807968454766520529084107175158062623274703294799705984925156349373997035743632649715867216648159433730630939058861636582120303338699113498645592338621228070481894445156769437351313971471061779425442129487317917630554305634797690296919992201174927956121524640438775183413288101169580705360562693274958339416, n) = 9
pow(2, 21606807968454766520529084107175158062623274703294799705984925156349373997035743632649715867216648159433730630939058861636582120303338699113498645592338621228070481894445156769437351313971471061779425442129487317917630554305634797690296919992201174927956121524640438775183413288101169580705360562693274958339417, n) = 6
pow(4, 10803403984227383260264542053587579031311637351647399852992462578174686998517871816324857933608324079716865315469529430818291060151669349556749322796169310614035240947222578384718675656985735530889712721064743658958815277152817398845148459996100587463978060762320219387591706644050584790352680281346637479169708, n) = 3
pow(9, 3293982057350410278459882519024200329089724149803879577174733206141551016681048848343176690789446255513117465644006032807116613436995145441651711865811812905401261777042165657533800465011922458688696664211216129846590488003282750224539553623014598025837108471148806368738631086225250952573439068109703953523338, n) = 4
pow(2, 43213615936909533041058168214350316125246549406589599411969850312698747994071487265299431734433296318867461261878117723273164240606677398226997291184677242456140963788890313538874702627942942123558850884258974635835261108611269595380593839984402349855912243049280877550366826576202339161410721125386549916678832, n) = 9
pow(7, 156359509651684605051402965560382969488421316701585527115005130492947292379802933549188085059602557600903593831240316597311439285149968787780538126741092612405335349622445040578126369183536683733294143156965518222696624206221060030916594302284630706642066420353822195108928341123726471513256217857861184609387726, n) = 9
pow(7, 170559914324671769117535654836487226009685359320636182075960576764702323732727088502920021993271666209903403463612731506055433486417625242935904916789051793747298593847158174830184596554822038310041512771676833824200302666130102306284852931958549925702330464987955245647072909056824574486147965487598401928881026, n) = 3
pow(8, 123173545998439288789112229408394321687299601293124558024610682024304903390434162304434639284627183212602142063990097609866285125123521132060847804558007316726174558714580872721495215950738261924525921590925432950469320750692763054435407707754979429841729673081392197456811651326615118306026475411557079498916218, n) = 4
pow(2, 21606807968454766520529084107175158062623274703294799705984925156349373997035743632649715867216648159433730630939058861636582120303338699113498645592338621228070481894445156769437351313971471061779425442129487317917630554305634797690296919992201174927956121524640438775183413288101169580705360562693274958339416, n) = 3
pow(3, 6587964114700820556919765038048400658179448299607759154349466412283102033362097696686353381578892511026234931288012065614233226873990290883303423731623625810802523554084331315067600930023844917377393328422432259693180976006565500449079107246029196051674216942297612737477262172450501905146878136219407907046676, n) = 4
pow(7, 146900004342901005519726059203387905743111231159623333298786259340649199259667124880775175860427705602975071010583553281005991812801779033020769274211420710213704563866848310994325033574484679477677016014418321661821714582236428708141287327064859146436371562752616380650770729341741997594308364878898526065859626, n) = 4
pow(5, 172192380036714150788905270808196199818277334366508682218739812159577144024191963252552116624193235000074634457087111471641800814071769221933018962135503876997163938949365614056098717522475180216291316295788774044033481065993544994610614082708563841846852650913646728169671510827052772868386414581035580266356334, n) = 3
pow(8, 68789042322037899901399142739922213531190892214327212247633649397602243027562329029767224931385807659445647908974735092145336602662873465734923450809783198772444106655438821950560058413359621316189435942839212247873870560114926459781136160541556773230183543715576244986800296759341282346581691226676298068904581, n) = 6
pow(5, 159624441075769368394142197503800917105605266793330527400563601282696932962732683048452274321445695181246055818189076528484173940458256745774766217433996778905066039826859919029954611118842967545793750205189398662362981005947945407568116603784658538931110792205205160154125544664182868277733116044735541284338342, n) = 9
pow(8, 14404538645636511013686056071450105375082183135529866470656616770899582664690495755099810578144432106289153753959372574424388080202225799408999097061559080818713654596296771179624900875980980707852950294752991545278420369537089865126864613328134116618637414349760292516788942192067446387136907041795516638892944, n) = 9
"""

根据一个 hint 得到 \[8^x\;mod\;n=4\] \[2^{3x-2}=1\;mod\;n\] 由费马小定理得，3x-2=phi

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
import gmpy2
n = 369520637995317866367336688225182965061898803879373674073832046072914710171302486913303917853881549637806426191970292829598855375370563396182543413674021955181862907847280705741114636854238746612618069619482248639049407507041667720977392421249242597197448360531895206645794505182208390084734779667749657408715621
c = 324131338592233305486487416176106472248153652884280898177125443926549710357763331715045582842045967830200123100144721322509500306940560917086108978796500145618443920020112366546853892387011738997522207752873944151628204886591075864677988865335625452099668804529484866900390927644093597772065285222172136374562043
e=65537
x=123173545998439288789112229408394321687299601293124558024610682024304903390434162304434639284627183212602142063990097609866285125123521132060847804558007316726174558714580872721495215950738261924525921590925432950469320750692763054435407707754979429841729673081392197456811651326615118306026475411557079498916218
phi=3*x-2
print(long_to_bytes(pow(c,gmpy2.invert(e,phi),n)))
# b'NKCTF{d15cr373_L0g_15_R3DuC710n_f0R_f4C70r1nG}'

ez_polynomial

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#sage
from Crypto.Util.number import *
flag = list(bytearray(''))
p = getPrime(16)
R.<y> = PolynomialRing(GF(p))
while True:
    P1 = R.random_element(degree=(ZZ.random_element(len(flag), 2*len(flag))))
    Q1 = R.random_element(degree=(ZZ.random_element(len(flag), 2*len(flag))))
    if P1.is_irreducible() and Q1.is_irreducible():
        P = P1
        Q = Q1
        break
e = 65537
N = P*Q
S.<x> = R.quotient(N)
c = S(flag) ^ e
print("P:" + str(p) + "\n")
print("N:" + str(N) + "\n")
print("C:" + str(c))

#P:40031
#N:24096*y^93 + 38785*y^92 + 17489*y^91 + 9067*y^90 + 1034*y^89 + 6534*y^88 + 35818*y^87 + 22046*y^86 + 12887*y^85 + 445*y^84 + 26322*y^83 + 37045*y^82 + 4486*y^81 + 3503*y^80 + 1184*y^79 + 38471*y^78 + 8012*y^77 + 36561*y^76 + 19429*y^75 + 35227*y^74 + 10813*y^73 + 26341*y^72 + 29474*y^71 + 2059*y^70 + 16068*y^69 + 31597*y^68 + 14685*y^67 + 9266*y^66 + 31019*y^65 + 6171*y^64 + 385*y^63 + 28986*y^62 + 9912*y^61 + 10632*y^60 + 33741*y^59 + 12634*y^58 + 21179*y^57 + 35548*y^56 + 17894*y^55 + 7152*y^54 + 9440*y^53 + 4004*y^52 + 2600*y^51 + 12281*y^50 + 22*y^49 + 17314*y^48 + 32694*y^47 + 7693*y^46 + 6567*y^45 + 19897*y^44 + 27329*y^43 + 8799*y^42 + 36348*y^41 + 33963*y^40 + 23730*y^39 + 27685*y^38 + 29037*y^37 + 14622*y^36 + 29608*y^35 + 39588*y^34 + 23294*y^33 + 757*y^32 + 20140*y^31 + 19511*y^30 + 1469*y^29 + 3898*y^28 + 6630*y^27 + 19610*y^26 + 11631*y^25 + 7188*y^24 + 11683*y^23 + 35611*y^22 + 37286*y^21 + 32139*y^20 + 20296*y^19 + 36426*y^18 + 25340*y^17 + 36204*y^16 + 37787*y^15 + 31256*y^14 + 505*y^13 + 27508*y^12 + 20885*y^11 + 32037*y^10 + 31236*y^9 + 7929*y^8 + 27195*y^7 + 28980*y^6 + 11863*y^5 + 16025*y^4 + 16389*y^3 + 570*y^2 + 36547*y + 10451
#C:3552*x^92 + 6082*x^91 + 25295*x^90 + 35988*x^89 + 26052*x^88 + 16987*x^87 + 12854*x^86 + 25117*x^85 + 25800*x^84 + 30297*x^83 + 5589*x^82 + 23233*x^81 + 14449*x^80 + 4712*x^79 + 35719*x^78 + 1696*x^77 + 35653*x^76 + 13995*x^75 + 13715*x^74 + 4578*x^73 + 37366*x^72 + 25260*x^71 + 28865*x^70 + 36120*x^69 + 7047*x^68 + 10497*x^67 + 19160*x^66 + 17939*x^65 + 14850*x^64 + 6705*x^63 + 17805*x^62 + 30083*x^61 + 2400*x^60 + 10685*x^59 + 15272*x^58 + 2225*x^57 + 13194*x^56 + 14251*x^55 + 31016*x^54 + 10189*x^53 + 35040*x^52 + 7042*x^51 + 29206*x^50 + 39363*x^49 + 32608*x^48 + 38614*x^47 + 5528*x^46 + 20119*x^45 + 13439*x^44 + 25468*x^43 + 30056*x^42 + 19720*x^41 + 21808*x^40 + 3712*x^39 + 25243*x^38 + 10606*x^37 + 16247*x^36 + 36106*x^35 + 17287*x^34 + 36276*x^33 + 1407*x^32 + 28839*x^31 + 8459*x^30 + 38863*x^29 + 435*x^28 + 913*x^27 + 36619*x^26 + 15572*x^25 + 9363*x^24 + 36837*x^23 + 17925*x^22 + 38567*x^21 + 38709*x^20 + 13582*x^19 + 35038*x^18 + 31121*x^17 + 8933*x^16 + 1666*x^15 + 21940*x^14 + 25585*x^13 + 840*x^12 + 21938*x^11 + 20143*x^10 + 28507*x^9 + 5947*x^8 + 20289*x^7 + 32196*x^6 + 924*x^5 + 370*x^4 + 14849*x^3 + 10780*x^2 + 14035*x + 15327

题解

多项式 RSA，给定 n、e、c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
p=40031
P.<y>=PolynomialRing(Zmod(p))
x=y
N=24096*y^93 + 38785*y^92 + 17489*y^91 + 9067*y^90 + 1034*y^89 + 6534*y^88 + 35818*y^87 + 22046*y^86 + 12887*y^85 + 445*y^84 + 26322*y^83 + 37045*y^82 + 4486*y^81 + 3503*y^80 + 1184*y^79 + 38471*y^78 + 8012*y^77 + 36561*y^76 + 19429*y^75 + 35227*y^74 + 10813*y^73 + 26341*y^72 + 29474*y^71 + 2059*y^70 + 16068*y^69 + 31597*y^68 + 14685*y^67 + 9266*y^66 + 31019*y^65 + 6171*y^64 + 385*y^63 + 28986*y^62 + 9912*y^61 + 10632*y^60 + 33741*y^59 + 12634*y^58 + 21179*y^57 + 35548*y^56 + 17894*y^55 + 7152*y^54 + 9440*y^53 + 4004*y^52 + 2600*y^51 + 12281*y^50 + 22*y^49 + 17314*y^48 + 32694*y^47 + 7693*y^46 + 6567*y^45 + 19897*y^44 + 27329*y^43 + 8799*y^42 + 36348*y^41 + 33963*y^40 + 23730*y^39 + 27685*y^38 + 29037*y^37 + 14622*y^36 + 29608*y^35 + 39588*y^34 + 23294*y^33 + 757*y^32 + 20140*y^31 + 19511*y^30 + 1469*y^29 + 3898*y^28 + 6630*y^27 + 19610*y^26 + 11631*y^25 + 7188*y^24 + 11683*y^23 + 35611*y^22 + 37286*y^21 + 32139*y^20 + 20296*y^19 + 36426*y^18 + 25340*y^17 + 36204*y^16 + 37787*y^15 + 31256*y^14 + 505*y^13 + 27508*y^12 + 20885*y^11 + 32037*y^10 + 31236*y^9 + 7929*y^8 + 27195*y^7 + 28980*y^6 + 11863*y^5 + 16025*y^4 + 16389*y^3 + 570*y^2 + 36547*y + 10451
C=3552*x^92 + 6082*x^91 + 25295*x^90 + 35988*x^89 + 26052*x^88 + 16987*x^87 + 12854*x^86 + 25117*x^85 + 25800*x^84 + 30297*x^83 + 5589*x^82 + 23233*x^81 + 14449*x^80 + 4712*x^79 + 35719*x^78 + 1696*x^77 + 35653*x^76 + 13995*x^75 + 13715*x^74 + 4578*x^73 + 37366*x^72 + 25260*x^71 + 28865*x^70 + 36120*x^69 + 7047*x^68 + 10497*x^67 + 19160*x^66 + 17939*x^65 + 14850*x^64 + 6705*x^63 + 17805*x^62 + 30083*x^61 + 2400*x^60 + 10685*x^59 + 15272*x^58 + 2225*x^57 + 13194*x^56 + 14251*x^55 + 31016*x^54 + 10189*x^53 + 35040*x^52 + 7042*x^51 + 29206*x^50 + 39363*x^49 + 32608*x^48 + 38614*x^47 + 5528*x^46 + 20119*x^45 + 13439*x^44 + 25468*x^43 + 30056*x^42 + 19720*x^41 + 21808*x^40 + 3712*x^39 + 25243*x^38 + 10606*x^37 + 16247*x^36 + 36106*x^35 + 17287*x^34 + 36276*x^33 + 1407*x^32 + 28839*x^31 + 8459*x^30 + 38863*x^29 + 435*x^28 + 913*x^27 + 36619*x^26 + 15572*x^25 + 9363*x^24 + 36837*x^23 + 17925*x^22 + 38567*x^21 + 38709*x^20 + 13582*x^19 + 35038*x^18 + 31121*x^17 + 8933*x^16 + 1666*x^15 + 21940*x^14 + 25585*x^13 + 840*x^12 + 21938*x^11 + 20143*x^10 + 28507*x^9 + 5947*x^8 + 20289*x^7 + 32196*x^6 + 924*x^5 + 370*x^4 + 14849*x^3 + 10780*x^2 + 14035*x + 15327
e=65537

q1=N.factor()[0][0]
q2=N.factor()[1][0]
phi = (p**q1.degree() - 1) * (p**q2.degree() - 1)
assert gcd(e, phi) == 1
d = gmpy2.invert(e, phi)

m=pow(C,d,N)
print(m)
flag = ''.join([chr(i) for i in m])
print(flag)
# NKCTF{We_HaV3_n0th1ng_But_dr3amS}

CTF
NKCTF2023
https://sch01ar.github.io/2023/04/04/2023NKCTF/
作者
Roo1e
发布于
2023年4月4日
许可协议