CTF BUUOJ [DASCTF X CBCTF 2022九月挑战赛]easySignin Writeup

CTF BUUOJ [DASCTF X CBCTF 2022九月挑战赛]easySignin Writeup

题目信息

• 题目名称：easySignin
• 来源：DASCTF X CBCTF 2022九月挑战赛
• 分类：Crypto

题目分析

题目给出了一个 Python 脚本 easySignIn.py。

核心代码逻辑

from Crypto.Util.number import *
import libnum
from random import randint
from secret import flag
p = getPrime(512)
d = getPrime(40) # 注意：d是一个40位的素数，这是解题的关键线索
m = libnum.s2n(flag)
a = randint(2,p)
b = randint(2,p)
c = randint(2,p)
g = d
# 核心加密循环
for i in range(10):
g = (c*d^2 + b*g + a)%p # 注：原代码中的^在Python中是异或，但在数理逻辑上应为乘方**
a = (a*b – c) % p
b = (b*c – a) % p # 这里的a已经是更新后的a
c = (c*a – b) % p # 这里的a,b已经是更新后的值
t = (m+d)^2 %p # 同理，理解为 (m+d)^2
# 输出参数
print('p=',p)
print('a=',a) # 最终状态参数
print('b=',b)
print('c=',c)
print('g=',g) # 最终状态g
print('t=',t)

破题切入点

解题步骤

第一步：逆向恢复参数序列

题目给出了循环结束后的 $a,b,c$。我们需要推导循环过程中的参数。
观察正向更新逻辑（注意赋值的依赖关系）：

# Step i -> i+1
a_next = (a * b – c) % p
b_next = (b * c – a_next) % p # 使用了更新后的 a_next
c_next = (c * a_next – b_next) % p # 使用了更新后的 a_next, b_next

我们可以推导逆向逻辑（从 $i+1$ 推回 $i$）：

第二步：构建关于 $d$ 的多项式

$g$ 的更新公式为：$g_{next}=c\cdot d^2+b\cdot g+a$。
由于 $d$ 是常数，我们可以将 $g$ 始终看作关于 $d$ 的二次多项式：
$$g_i=A_i{d}^2+B_{i}d+C_i$$
初始状态：
$g_0=d$，故初始系数为 $A_0=0,B_0=1,C_0=0$。
迭代推导：
代入 $g_i$ 到更新公式中：
$$\begin{array}{rl}{g}_{i+1}& =c_i{d}^2+b_i(A_i{d}^2+B_{i}d+C_i)+a_i\\ & =(c_i+b_i{A}_i)d^2+(b_i{B}_i)d+(b_i{C}_i+a_i)\end{array}$$
由此得到系数的递推公式：
$$\{\begin{array}{l}{A}_{i+1}=c_i+b_i{A}_i\\ B_{i+1}=b_i{B}_i\\ C_{i+1}=b_i{C}_i+a_i\end{array}$$
利用第一步恢复出的参数序列，正向计算 10 轮，得到最终的 $A_{10},B_{10},C_{10}$。

第三步：求解二次方程得到 $d$

经过迭代，我们有等式：
$$g_{final}\equiv A_{10}{d}^2+B_{10}d+C_{10}(\mathrm{mod}p)$$
移项整理得标准的二次方程形式：
$$A_{10}{d}^2+B_{10}d+(C_{10}-g_{final})\equiv 0(\mathrm{mod}p)$$
这是一个模 $p$ 下的二次方程。由于 $p$ 是素数且 $p\equiv 3(\mathrm{mod}4)$，我们可以利用 Tonelli-Shanks 算法（或简单的 Euler 准则公式）计算判别式的平方根，进而利用求根公式解出 $d$。
得到两个解后，利用 $d$ 是 40 位素数 这一条件进行筛选。

第四步：还原 Flag

得到 $d$ 后，利用题目给出的 $t$：
$$t\equiv (m+d{)}^2(\mathrm{mod}p)$$
$$m\equiv \sqrt{t}-d(\mathrm{mod}p)$$
计算 $t$ 的模平方根，减去 $d$，将结果转为字节串即可得到 flag。

完整 Exploit 代码

import gmpy2
from gmpy2 import mpz, invert, isqrt, is_prime
import libnum # 提前导入，避免作用域问题

# 题目数据（保持不变）
p = 7591656713055743077369340861541583433090841738590989539280316533530045331013958613146671718809022799047779468311222607020894006899032327866283558110087799
a_final = 4392865163304254999527172406061971162689920565151840813033448791785156740502864894051809689255751412382468345217962713758808061870635744521996229554057672
b_final = 2119856022628544669301306700581535843188073099896481101405665476192582614655960576092254118367775147735092457551317887281026710342124525625026559538165667
c_final = 3370586754351688470908526079815435343732016329743637661764947106415792049906966624513736208696137655804912688128186282852926377345819134856707156640355705
g_final = 2221154642536617375933147254663757148609834736621720750750043572054496685087600339999953459509198087870095805651320901316659013390557077204194753685935362
t = 6426975621182152052236088849377616252912408340750729257254509090637526282051064469268808395760737262115678691330037039061905028548054911000486882481093832

# ========== 新增：调试输出函数 ==========
def debug_print(msg, value=None):
print(f"[DEBUG] {msg}: {value if value else 'OK'}")

# 1. 逆向恢复 a, b, c 序列
debug_print("开始逆向推导参数")
params = []
a_curr, b_curr, c_curr = a_final, b_final, c_final

for i in range(10):
a_next, b_next, c_next = a_curr, b_curr, c_curr

# 逆向公式（先保留原公式，后续验证）
c_prev = (c_next + b_next) * invert(a_next, p) % p
b_prev = (b_next + a_next) * invert(c_prev, p) % p
a_prev = (a_next + c_prev) * invert(b_prev, p) % p

params.append((a_prev, b_prev, c_prev))
debug_print(f"第{i+1}轮逆向结果", (a_prev, b_prev, c_prev))
a_curr, b_curr, c_curr = a_prev, b_prev, c_prev

params = params[::–1]
debug_print("逆向参数列表（index对应i）", params[:2]) # 只打印前2个，避免刷屏

# 2. 前向计算多项式系数 A, B, C
debug_print("开始正向构建多项式")
A, B, C = 0, 1, 0

for i in range(10):
ai, bi, ci = params[i]
A_new = (ci + bi * A) % p
B_new = (bi * B) % p
C_new = (bi * C + ai) % p
A, B, C = A_new, B_new, C_new
debug_print(f"第{i}轮多项式系数", (A, B, C))

# 3. 求解二次方程
debug_print("开始求解二次方程")
delta_c = (C – g_final) % p
D = (B * B – 4 * A * delta_c) % p
debug_print("判别式D", D)

# 验证p%4是否为3（确认平方根算法正确）
debug_print("p % 4", p % 4)
sqrt_D = gmpy2.powmod(D, (p + 1) // 4, p)
debug_print("sqrt(D) mod p", sqrt_D)

inv_2A = invert(2 * A, p)
debug_print("inv(2A) mod p", inv_2A)

d1 = (–B + sqrt_D) * inv_2A % p
d2 = (–B – sqrt_D) * inv_2A % p
debug_print("d1值", d1)
debug_print("d2值", d2)
debug_print("d1的位数", d1.bit_length())
debug_print("d2的位数", d2.bit_length())
debug_print("d1是否为素数", is_prime(d1))
debug_print("d2是否为素数", is_prime(d2))

# 4. 恢复 m
sqrt_t = gmpy2.powmod(t, (p + 1) // 4, p)
debug_print("sqrt(t) mod p", sqrt_t)
debug_print("-sqrt(t) mod p", (–sqrt_t) % p)

def check_and_print(d_val):
debug_print(f"检查d值: {d_val}")
if d_val.bit_length() <= 45 and is_prime(d_val):
debug_print(f"d={d_val} 满足位数和素数条件")
for root in [sqrt_t, –sqrt_t % p]:
m_val = (root – d_val) % p
debug_print(f"尝试root={root}, m_val={m_val}")
try:
flag_bytes = libnum.n2s(int(m_val))
debug_print(f"m转字节串", flag_bytes)
if b'DASCTF' in flag_bytes or b'flag' in flag_bytes:
print(f"\\n===== 找到flag ======")
print(f"Found d: {d_val}")
print(f"Flag: {flag_bytes.decode()}")
return True
except Exception as e:
debug_print(f"转换字节串出错: {e}")
continue
else:
debug_print(f"d={d_val} 不满足条件（位数：{d_val.bit_length()}，素数：{is_prime(d_val)}）")
return False

# 执行检查
debug_print("检查d1")
check_and_print(d1)
debug_print("检查d2")
check_and_print(d2)

运行结果

运行脚本后，成功获取 Flag：

[DEBUG] 开始逆向推导参数: OK
[DEBUG] 第1轮逆向结果: (mpz(1558327918173916685276061896009146814462087603675562547749464338567789777526157067883836812063086030139306395351744800560094726977076742887829461268635558), mpz(4514148881631515061858934147505049323883430087629553393687379588421262903144178261541888640294288831031133809383907481714613701220966378839463140096771142), mpz(6852227333661582809040997504319324351902752602498116902003495662316181290311509340056889282031693078153608180707421739904104897716102066595433625160283868))
[DEBUG] 第2轮逆向结果: (mpz(4234783580347301415219055168004953720021990043845525530978728641401141280688765768255841044951798583995682343024907380189589165570451045720056452326485618), mpz(5718235690118251228617104726479064921991314663732805083156370432971341367382827271609557691898846816407222614032051075708178029254271041725207957347236569), mpz(6011203979414507997009462186342176669941053585431071624148473597721460653407597205937696793979140839505480847287174278929294086631363969339351348575352856))
[DEBUG] 第3轮逆向结果: (mpz(1276816869879639977990203528882856601012474784947810512487591115574428646605781380422735500626575579669016136844540271053533311757951144082015936557489087), mpz(1239916973932615451066506751318691392204788751681844835551848034385300794677700028988929557778553964903346405673924363004228948262352704973820706023958891), mpz(2285860412837188443208576330203052996086133758687332958176255791492234226477257282920036027518499672369420512593972418102867910390592209259341791773808425))
[DEBUG] 第4轮逆向结果: (mpz(750395498918226777040527843867196113458405311943647981774216787181612352604554317713785604945826407015377270019505130311300614336277162115563565360618478), mpz(4840449299234867971000534596756931162830835855867819145058680308392558160966470220222109505723871889664721592993291696185055331584842480392441058196006436), mpz(5412702039966146294395879633578487882240433694451709440397732707557193056889334787123501521744362953062885714266204930622216103885338311445206792741932999))
[DEBUG] 第5轮逆向结果: (mpz(6787260216003704037436828249042950501442135219256212863721237923906944473725953011789953225572229483386321885419169052842430604831287326826367535177852053), mpz(7289837746969742837562254130441459418716174243333286884721893365447520299330685353689480042055570758502172720594554142917472501623012005474566631566544775), mpz(6581191704328187480538895638259936434391238929209425408851189613318327811764420001620980504352179287185565444922372294504832272119209006602669933898480878))
[DEBUG] 第6轮逆向结果: (mpz(7103657963548914558151473809474075771611185618134380111586031973749843445270500043215388123926986228575345423314499611151032605087785285456086954143332795), mpz(2437090089471763281003268510083600543608846252680223991273908345135602309589620097292474114081336144065225051782014698516867570373062887759704073445145766), mpz(7263633592969865940568162914112873033425552832716604041970494862239901164707781850676711734033552643405919601738169630448608427244505351343621156673841732))
[DEBUG] 第7轮逆向结果: (mpz(599541426740541398930281198217219002055776031533759543636607757629213787169680162194126045830416834733408242600490845122211014165748273997720985171688041), mpz(5957207859384881463025007501710389658802332383558267293322714086358938193388741893071655615153092025747579772703124512208782459441100652478549738180467978), mpz(4682713376946075123598629989240562117774633362251661889503646233262116515006093065833206615375846947185403405658122109052452004335578521197128755538142562))
[DEBUG] 第8轮逆向结果: (mpz(5342408465355821539357986311892676556199271023491659460379476187712977833146964566593532451072939601789180818278583745555483090452024642159007064165800081), mpz(3283554726718737444389729631016035434015751338535189074295640854481651942378365746643274759572464743981861848971330295577364787640389158084889350283978821), mpz(3140055548802978995474977115602107560914575889710138407298306721971016304575233705366565976404902888283840198356431969988949513149516351192261087493740890))
[DEBUG] 第9轮逆向结果: (mpz(2563221664374872663278726447352893822468787748826688543449083601814070735291152495522031395953021486479126489409553661909467374804495083097067023461101241), mpz(6566088464708310995642409028807288393979344735404620168989682843309896029461182739839950463522656561353959979803920824844492121990544498716716047723977910), mpz(130057529710426488213137583219999255587156240884036482222085445611551740946428211680329413666239014546023650006579524537602274302379152576119520068108319))
[DEBUG] 第10轮逆向结果: (mpz(184972745971509494177749002438471045142431744349694071290568699875759696273259964144195521605616391458033949428260257403866133106081122954953351131066266), mpz(5203346575880216155246099170513405396695418799624477309823705848477387257144158566705537881272662895232085767641640102113789121259979434162072009911706202), mpz(5128252735042950570541661862704057778697777367682675179255508249069206116108008236364688726497066420198915103127328652153920791569475715644224564332100639))
[DEBUG] 逆向参数列表（index对应i）: [(mpz(184972745971509494177749002438471045142431744349694071290568699875759696273259964144195521605616391458033949428260257403866133106081122954953351131066266), mpz(5203346575880216155246099170513405396695418799624477309823705848477387257144158566705537881272662895232085767641640102113789121259979434162072009911706202), mpz(5128252735042950570541661862704057778697777367682675179255508249069206116108008236364688726497066420198915103127328652153920791569475715644224564332100639)), (mpz(2563221664374872663278726447352893822468787748826688543449083601814070735291152495522031395953021486479126489409553661909467374804495083097067023461101241), mpz(6566088464708310995642409028807288393979344735404620168989682843309896029461182739839950463522656561353959979803920824844492121990544498716716047723977910), mpz(130057529710426488213137583219999255587156240884036482222085445611551740946428211680329413666239014546023650006579524537602274302379152576119520068108319))]
[DEBUG] 开始正向构建多项式: OK
[DEBUG] 第0轮多项式系数: (mpz(5128252735042950570541661862704057778697777367682675179255508249069206116108008236364688726497066420198915103127328652153920791569475715644224564332100639), mpz(5203346575880216155246099170513405396695418799624477309823705848477387257144158566705537881272662895232085767641640102113789121259979434162072009911706202), mpz(184972745971509494177749002438471045142431744349694071290568699875759696273259964144195521605616391458033949428260257403866133106081122954953351131066266))
[DEBUG] 第1轮多项式系数: (mpz(7056540433291547105379421474365647448354632427499275440381996278513634448175944957829667711531961156615613891189262650046871828247158090921956908809223391), mpz(3081713841236294043319612488565500603761911735191847227672323629067187425322837685217426217834348735734551054189329492359309838345677284016139987579982480), mpz(155553405667526884128409674827967720405382765124034219189597864576524298905720607478118400825103674541009786099122399007130965480451421438136318303700206))
[DEBUG] 第2轮多项式系数: (mpz(7351452739469247898933724214335630148173510607082079253265111905719628351825938831413065209518822821120439084124556080593406887885364021429040909722529477), mpz(3614092245722791229213608791726590760356622653808625011491336778901152562857258817082811751898212920346286640789711073019733885582470333578905644716793820), mpz(1951326650691790731867401101083652748738420892092603148954305515978439417035304178186198470316142078309045688483194307704925110572188525611930562409421810))
[DEBUG] 第3轮多项式系数: (mpz(189760589722789642251436852458338686965433992221135945475854487360477640240156197937265439365905316150251999992242976426709082547852969206087273345109835), mpz(3948867414184514694653811609355088107275149193559427328573309775393116224931034536812940948253817811154677346678733681818327662678524282808467187029229637), mpz(360360911521453968124638882337247577036891228650123311741057088252616055403340393559907633764705298271744806280321486074549214156916099021903998882477445))
[DEBUG] 第4轮多项式系数: (mpz(1268738680391355410059467298967441110523158868985945478728254327069585832928970846899726671004000072189825765269904507707349435743954180674617686152869832), mpz(7152731010608783206001849105552890272658422050629573894019563945039159149975062057323897314139400971944297445208592362595476943621994220680472654907902579), mpz(4613019741111845221513900022363292721311127745523798105069077872566606730432997889965455646392529520848844521762821150598191471578621645758925481092895772))
[DEBUG] 第5轮多项式系数: (mpz(4115867201190204765427789986881061018619428869416053528571593353562863311566215252546308533567865456974980497169708049600988303396508680320626996903710575), mpz(3519716180554947716543257894369816669862089708761421300994428722647372636739419991839208314176160399172748962372277544756708720935571131699425090915890232), mpz(2752721941848363771264658156861253369354129477235416934899483857444462980299364320606095238738621263801194386286933208734517358070951775419376958641159769))
[DEBUG] 第6轮多项式系数: (mpz(6917541650363525125469920445180759106001776150906576525918376632419289151558898987352948379834485931364159260502576609563369050892847159038721718478793029), mpz(638859381677056145616063931554914251715047833531812731870218730629788995490770039989164902027474792152671749969888741880946342595932987734716568116778291), mpz(2700702415686226886636961515493339118067752993424024062537915602583783532207199717691473516951557858254937105446295365183760922310465141293609248320114295))
[DEBUG] 第7轮多项式系数: (mpz(2564732284779826484395624797009062352884508221426328534856240413564296323976130981995022088675621167539861556461967489179033030949766225701917073874276440), mpz(329439979599827162276277967425222696084427185792867528921498091438070833609246236125492678491632210851035811725958466636437827960580355156700258752356409), mpz(3229420499044121013638093163443410183327442804720862615649805956475480668988088514727442341226212585971956943804772006464283653443818098640899469579630806))
[DEBUG] 第8轮多项式系数: (mpz(1760648086534993937402581641462327321195989946870480350225063539318770316405299174790181088958345565797386572339859859490817573155213286776040785510267276), mpz(3166169624047192755254375996368280521405881948677863515319327067254587627120057560155864807529279326806817145892138710728362076238019179865475006520411083), mpz(397510509939515269098385952086960952233814461949350546661508235468156783184000645448547703648278584316753810876061721769445221883503828323385987149623723))
[DEBUG] 第9轮多项式系数: (mpz(596133050004585865345117708558237037160534486241265084699224056239599954780652773516391059421728791733204672187788345531957456448174307218858919303904863), mpz(6507260534156605589831863894111212693990718727458127819656315179778367782855231389046167541115862480226521943539610867856172849186902375173620370475574618), mpz(3897035633910380379212903870816929202987360196557403448404254744799932723751160939406714973233171696870713807378919548076646376512935671860330511540776796))
[DEBUG] 开始求解二次方程: OK
[DEBUG] 判别式D: 416691664659706157270659067880415445440089334509688236798648911207936042133903346873159247934169027396657416180349376944278501268459207279304153189471727
[DEBUG] p % 4: 3
[DEBUG] sqrt(D) mod p: 4334302755708777392149852014612559261930029923849000171310182085372217458041200456685581329838020495487675155122969726752023877614089691975654531900876317
[DEBUG] inv(2A) mod p: 6928892362557825503137888086754357484013485127659362326945564193552675833549122068183127840202264020404515214025035767250659522728029270929682886634400969
[DEBUG] d1值: 3807215909035989795536872811930149940528089123015269988976547876480129486123396973291313982543531301902195293729435310996431335855905236294657804664410724
[DEBUG] d2值: 793009095377
[DEBUG] d1的位数: 511
[DEBUG] d2的位数: 40
[DEBUG] d1是否为素数: OK
[DEBUG] d2是否为素数: True
[DEBUG] sqrt(t) mod p: 7591656713055743077369340861541583433090841738590989539280316533529914669358031382351028958377643759269145794938649787861165963022699333466670422633862441
[DEBUG] -sqrt(t) mod p: 130661655927230795642760431379039778633673372572819159728043876332994399613135476225358
[DEBUG] 检查d1: OK
[DEBUG] 检查d值: 3807215909035989795536872811930149940528089123015269988976547876480129486123396973291313982543531301902195293729435310996431335855905236294657804664410724: OK
[DEBUG] d=3807215909035989795536872811930149940528089123015269988976547876480129486123396973291313982543531301902195293729435310996431335855905236294657804664410724 不满足条件（位数：511，素数：False）: OK
[DEBUG] 检查d2: OK
[DEBUG] 检查d值: 793009095377: OK
[DEBUG] d=793009095377 满足位数和素数条件: OK
[DEBUG] 尝试root=7591656713055743077369340861541583433090841738590989539280316533529914669358031382351028958377643759269145794938649787861165963022699333466670422633862441, m_val=7591656713055743077369340861541583433090841738590989539280316533529914669358031382351028958377643759269145794938649787861165963022699333466669629624767064: OK
[DEBUG] m转字节串: b"\\x90\\xf3>\\xbb$\\x8b{\\x9b>4\\xe0\\xaf\\x81{m'W\\x91;\\xbb\\x0b\\x86\\x1f\\xfd~\\xda\\xff\\x8a\\xb0\\xaa\\xce\\xd9\\xe2\\xdeM\\xb4f\\xae\\xa0\\xce\\xfc\\x99A\\xe0\\xd2\\x81\\x81\\xe9\\r,\\xdf6\\x1e1^\\xee\\xdf\\xb6\\x8f[\\xa73RX"
[DEBUG] 尝试root=130661655927230795642760431379039778633673372572819159728043876332994399613135476225358, m_val=130661655927230795642760431379039778633673372572819159728043876332994399612342467129981: OK
[DEBUG] m转字节串: b'CBCTF{cjx_H0pe_that_love_1s_forever}'

总结

这道题虽然代码不长，但考察了几个关键点：