## 0. Introduction
:::success
:hatching_chick:
Xin chào tất cả mọi người, sau một thời gian vắng bóng ~~vì lười và gà~~ không tập trung vào viết wu crypto sau mỗi giải, giờ mình đã trở lại ~~và ngu hơn xưa~~. Giải này đánh thức con quái vật ||gà loz|| trong mình và tạo động lực cho mình try hard hơn. Dưới đây là thành tựu của team chúng mình và wu của toàn bộ challenge crypto của giải (trừ bài `Mask RSA` khó như ~~loz~~)
:::
## 1. ezcoppersmith
### Description
- Source:
```python=
import os
from Crypto.Util.number import bytes_to_long, getPrime
from random import getrandbits
from sympy import nextprime
flag = os.urandom(70)+b"CSCTF{fake_flag}"+os.urandom(70)
flag = bytes_to_long(flag)
e = 0x10001
p = getPrime(1024)
q = nextprime(p+getrandbits(512))
n = p*q
ct = pow(flag,e,n)
print(f"{n = }")
print(f"{ct = }")
"""
n = 18644771606497209714095542646224677588981048892455227811334258151262006531336794833359381822210403450387218291341636672728427659163488688386134401896278003165147721355406911673373424263190196921309228396204979060454870860816745503197616145647490864293442635906688253552867657780735555566444060335096583505652012496707636862307239874297179019995999007369981828074059533709513179171859521707075639202212109180625048226522596633441264313917276824985895380863669296036099693167611788521865367087640318827068580965890143181999375133385843774794990578010917043490614806222432751894223475655601237073207615381387441958773717
ct = 814602066169451977605898206043894866509050772237095352345693280423339237890197181768582210420699418615050495985283410604981870683596059562903004295804358339676736292824636301426917335460641348021235478618173522948941541432284037580201234570619769478956374067742134884689871240482950578532380612988605675957629342412670503628580284821612200740753343166428553552463950037371300722459849775674636165297063660872395712545246380895584677099483139705934844856029861773030472761407204967590283582345034506802227442338228782131928742229041926847011673393223237610854842559028007551817527116991453411203276872464110797091619
"""
```
### Solution
- Nhìn source có thể thấy rõ được hai hướng giải của bài này, một là coppersmith đơn thuần, hai là sử dụng `Fermat Attack` (Unintended).
#### Cách 1:
- Với cách này, nhận thấy khoảng `delta` giữa số `p` và `q` chỉ là 512 bit, xét trong `Zmod(n)` thì chỉ là 1/4, vậy nên `small_roots` hoàn toàn có thể giúp chúng ta tìm lại giá trị `delta` này.
- Một điều nữa, do hai số `p` và `q` khá gần nhau, nên mình sẽ define một số `tmp` là căn bậc 2 của `n` và tính:
```
p = tmp - delta
q = tmp + delta + 2 (số 2 chính là phần filler vì tmp**2 != n)
```
- Từ đây thành lập phương trình, ta dễ dàng giải ra `delta` và thu được `flag`:
```python=
from Crypto.Util.number import *
n = 18644771606497209714095542646224677588981048892455227811334258151262006531336794833359381822210403450387218291341636672728427659163488688386134401896278003165147721355406911673373424263190196921309228396204979060454870860816745503197616145647490864293442635906688253552867657780735555566444060335096583505652012496707636862307239874297179019995999007369981828074059533709513179171859521707075639202212109180625048226522596633441264313917276824985895380863669296036099693167611788521865367087640318827068580965890143181999375133385843774794990578010917043490614806222432751894223475655601237073207615381387441958773717
ct = 814602066169451977605898206043894866509050772237095352345693280423339237890197181768582210420699418615050495985283410604981870683596059562903004295804358339676736292824636301426917335460641348021235478618173522948941541432284037580201234570619769478956374067742134884689871240482950578532380612988605675957629342412670503628580284821612200740753343166428553552463950037371300722459849775674636165297063660872395712545246380895584677099483139705934844856029861773030472761407204967590283582345034506802227442338228782131928742229041926847011673393223237610854842559028007551817527116991453411203276872464110797091619
e = 0x10001
PR.<delta> = PolynomialRing(Zmod(n))
tmp = isqrt(n)
p = tmp - delta
q = tmp + delta + 2
f = p*q
f = f.monic()
sol = f.small_roots(X=2**512)
for s in sol:
if(int(s).bit_length() < 512): delta = s
p = ZZ(p(delta))
q = ZZ(q(delta))
assert p*q == n
m = long_to_bytes(int(pow(ct, inverse(e, (p-1)*(q-1)), n)))[70:-70]
print(m)
```
#### Cách 2:
- Nói tới `Fermat Attack` thì quá cơ bản đối với người học crypto rồi nên mình chỉ viết luôn code mà không giải thích gì thêm. Btw nếu thắc mắc tại sao lại dùng được thì trong [tài liệu này](https://fermatattack.secvuln.info/) đã nói rất rõ rằng
So yeah we could implement that attack and get the flag:
```python=
from Crypto.Util.number import *
from sympy.ntheory.primetest import is_square
from sympy import sqrt
n = 18644771606497209714095542646224677588981048892455227811334258151262006531336794833359381822210403450387218291341636672728427659163488688386134401896278003165147721355406911673373424263190196921309228396204979060454870860816745503197616145647490864293442635906688253552867657780735555566444060335096583505652012496707636862307239874297179019995999007369981828074059533709513179171859521707075639202212109180625048226522596633441264313917276824985895380863669296036099693167611788521865367087640318827068580965890143181999375133385843774794990578010917043490614806222432751894223475655601237073207615381387441958773717
ct = 814602066169451977605898206043894866509050772237095352345693280423339237890197181768582210420699418615050495985283410604981870683596059562903004295804358339676736292824636301426917335460641348021235478618173522948941541432284037580201234570619769478956374067742134884689871240482950578532380612988605675957629342412670503628580284821612200740753343166428553552463950037371300722459849775674636165297063660872395712545246380895584677099483139705934844856029861773030472761407204967590283582345034506802227442338228782131928742229041926847011673393223237610854842559028007551817527116991453411203276872464110797091619
e = 65537
def fermat(n):
a = int(sqrt(n))
b = a*a - n
while not is_square(b):
a += 1
b = a*a - n
else:
p = int(a - sqrt(b))
q = n//p
if(p*q == n): return p, q
p, q = fermat(n)
assert p*q == n
d = inverse(e, (p-1)*(q-1))
m = long_to_bytes(pow(ct, inverse(e, (p-1)*(q-1)), n))[70:-70]
print(m)
```
### Flag
> ~~`CSCTF{c0pp3rsm1th_1s_a_m4th_g0d_n0_d0ub7}`~~
---
## 2. flagprinter
### Description
- Challenge output:
```python=
enc = [65, 331, 1783, 6186, 6470, 17283, 25622, 49328, 75517, 80689, 148293, 164737, 256906, 285586, 529890, 453524, 486833, 612780, 995834, 1034513, 1164566, 1187257, 1195463, 1481795, 1456512, 2255447, 1918038, 2402807, 3279260, 2958036, 2881150, 3263588, 3820625, 4237730, 5185459, 5233235, 6049254, 6786968, 6183125, 8612625, 8897839, 8945969, 8548390, 9936098, 9754219, 10421226, 12312594, 13139249, 13528562, 13806877, 14378265, 14232673, 17206117, 17924517, 19586568, 21397250, 22214087, 25159893, 25280690, 27657640, 29296934, 29729604, 28262064, 32050040, 32629604, 33546289, 38222149, 38457097, 34401800, 39471481, 41751527]
R = [[1, 1, 2], [573, 229, 206], [10885, 41497, 160304], [8839119, 14295644, 29685237], [10280936393, 8467023078, 4707689596], [945960776097, 1031182232283, 69972907378], [137665703218004, 35525403452985, 138350929229224], [122336169683982108, 59224551586149213, 118549674466202725], [13626900512752906569, 3897136862695780183, 35076404995397046345], [163593922657921448706, 2585968319357630198594, 6996211172572711470196], [1433471461923638870900801, 327749274075770619032029, 392888374649818189286143], [19744782485775287314957049, 460634978666194064781998391, 31659469833364582430102473], [6307006601660265171992374053, 98623451654268880809155078560, 64233892285570757739641890442], [29154577259006185142961063158052, 9914420641115443182131036644284, 7279481296300468961689254189816], [1558076296273259698341440069238056, 4310691260512125134140007179935352, 4980109395532057935132560488460615], [1405212213206399714548754108042831062, 147404700816591482365933597995505421, 1687342229905046884455484428290534831], [178231026292428921004703562165525411894, 412963066680488665482944489625497608212, 70340936836695689283893473181751382743], [56698349585950537262338505181144336979587, 52217406711284315435595033610018391654195, 62108893391408870656968514251159189194521], [23893381410382084563262913681592457710903753, 22212431596810321024205206524427117951881276, 19989366146226118433589584982546380299442529], [2889511959527885324209305298200285677701094725, 2606035783027360737177505608659564857175468342, 912571494124990709836860172316232544276438933], [1228504793022169504797984188122406171358072857562, 1363360236293969893605831020276765744813251042404, 297563475302044806097863947023814157856389926467], [175608219147292209879121072264875458914106479644056, 315961037093380016583816358395509380577071641993080, 239337133002097856335802829217431187967280790555618], [86907177537979343798282102958682278554281933300161219, 64317934619982444261646548589166853140812442454915939, 88018844277704099677399755876858185474535387410720445], [7578403250388931197644961338635760720785818764109837460, 3274632430417597288151262115132742324278216710102859849, 21631882539927419463654991077819010737499996516834371896], [1784005907786440158922591109117656913793076162623216189690, 584544132694337139275683959718819628005872667061541957378, 468567183178097211759022580480616535344925394592430209347], [729938520575815549919101929342052441361022063727469070145908, 274550060366659698888268478648666070589265337265466015158929, 816678505785021313430715270084566186204139128920927645737535], [106419295808981221951748024239581079670028738895932201279327601, 228539844398841595052385901358010923608064510380402434702609661, 273988143389250335223734499597874248431371549060210491714569562], [49610527461979411507467246924089752425201348016881391697347424513, 69137173214147289942692162771140621271832934031257876965711710949, 62730418740220882006739225333147856993853932330719923493210890436], [16851730736657444946446580883690706974734423996859949550565127900099, 17020082067082804201146138962045534353417049142267440365496556106646, 8425831360975428058545914350645398599666494245768262308563962500419], [1744457135330206658118333956018617505833961797560206981881297005844650, 2488272677039458908993320500395188112777156174503950549584903141127805, 2025261799014127885373424699982740002932128127330675129998065148842076], [911346406564292964244181957884281723110968676471292861562401898225344617, 515016108655135831997810719937894761768485489577746685305628286718842981, 529790162728531781327256209611140765345349305272432962612449845910133431], [188862868604458670709430534588424053453382627459433615665235632604774195105, 159265669796915366090971144664529549841435257409990033156402470728739515566, 60682317875971312140589380343235690226249919927211583007002668602340443573], [55193706264542603342210130740272648982338137150197933176657775220529084548357, 27195911554042477052963544743968295593780567038751440659821492286699921720191, 29560858927273910749887729332550032054935265811253142815881982028400038247319], [7967504222642156771288173955589952284643390129548188481154174503319661178503072, 1359513209197691298598578835648210368417270153147787219079370527092612752268982, 9230224122977955411941024673666600930203300543850914931726268334960580194164492], [831700796347413410615911772707996893565701575245034815476696517314277469580570895, 348270496636109272924978536225447046371768965881221748966431208037510608509018947, 1374142394998218750798266411208358766099463968207325565770298390782412190916814310], [728134218644001393441390399108789642515528723649320724369274506318570415182986524315, 742827622102241979512100045719273776927502266118292292534558855112165931221386202274, 834896424809769450256618602072325069420072099322355588900296733100469513421816291082], [66657521960797189904538245565000331457185183590890330549573802546986185313721475396700, 156009195280892389693769014846212616019395180017555815307430719390512302340174696802961, 200597453219232827796159650057256671048223063579900089130489322256618558160451930790328], [29037802387828000295889248231258384842641658132563570380131111284295279711886813738722877, 19026977082052219356279509080995574655135318523161839766669049352934239566123435130632269, 39761369983488555876764613607529231297124885693027657193256415982138011913990538842193676], [12561577796321365976754879894302013598558663721653793677134296816829605195336351648166256979, 12838267657320533157115690870383947765475624026880560207257146094964304690365021016825129853, 7495910847481301240802133743653617325920902801350946983901641264085048246865582593139729403], [3041492422855245745694700380550203206979029337703391421024168530121179356261997345191319516771, 640848136862288646629516649150957018999642176847724807173173190110594937936496769080786522049, 2969396567186077593954887271522825649221970125735131131175295619859668697895377679704620087889], [81093296695439965954342113512388849103885378349927499243812089963712022532857570393423108003659, 207270172491583465284894346681199376583340220798632240230546015429407709634891762897301883017884, 190032100106748542252716447896640624640777006597630648586475349805342010386746524668165629317161], [32533344401268273967114633758559931826617665158198522614215035245432490850547861982523840145942074, 63037110804852476247528611221542679314242047661614004564491126914186621243875589339803531182020426, 124951290010810803694525061731704200016278732642269550252996419375511248225453431694350800495944347], [35137716753067452090927097050636563619547995454738820278063768022488025199701346321134314448841872794, 12985633921598678956642044617726801111706054490973834029123104709195008027204480882797267867341064476, 5305727297771409651023243066103178878140492848258919185568928165081859031657272186995329239806104118], [3762249421419366884537098419354305781080227852906891797970952858114351664324268703722577235910347584304, 1550561491002149215075653857319603880429910437941882645815693111090526036411984733619993307966461840126, 9381201201142531265853888435902828303237464579889417263110360168656884858562872253087408205544357087306], [2056899273710648314295675026370994461871817025547273056051947505619792320735406178540815338367649803736698, 2400734502375026278495337239471134511733068748104902082380177269089395799760690047001894688755690156943965, 1732882327457919111959549262162185466220677456316057330624797413276486794416719248300528086966180252303114], [652896416106612920827629685957065255447694536466438605951176120897225559332173369105354682171886992371096271, 454656456599989954897128567415348109820116193092249211381080865675729251399216425900943035094745504751551478, 313462687528796654990235524389154265472701132978608107344549946439400139763799796696708655697709590458851693], [104545083165292290401534689701271365665130721684233823742393188465642248906869971808131422905737188031748198141, 143435659999076222337918882839514881215221734734388221592284254721485478080813955224165205293052195097128579855, 40702920019369144545229507759809584949672965917473112280581406604369595519129367208280022299388654288711154666], [38503581328033455359533847919966468672140392024444493807653196910126532016690751491942280634907485938880904383892, 18884661042488142899588244068961327261179761242819343293800084248732455991582145396596568605394801002264811582913, 9384187667567328792366639242333135973520260966794149958963790153859412473452108461030094493051859371952206600103], [1324740544139254318273253770332855107671134390702432855738006366746449029576545099512912405134518891320718185169513, 303109855383738809002288742946345379428808745080383659457773592835713207285305179350437080179436990935112214270665, 1624316398491836088831202617387140081826145335528105327252325808416312557534737052667304856958627845436851248489907], [1401688155035324575988216421089538478215416341501120197948850057036940982809195355604792139051606198616259749003767965, 2048526767570983439518103534423786218930891544461790174537795037321458400711335285803377717794909411012955744133476255, 1762727028524336180955903313027800157402368747053245589279568985101199159336178410704769284913872366668626620722820001], [50297209609059623442815521181722350352719290856519522344205021656047917502237970917310786375279675448048523557477430805, 15857002182452297197982329375111053201349508644473177012866786518888614594064540203474772864651339444396084341878515576, 403895394397791973760362815402896437377344978600840941064554187621230430084298005374238342732262063840044910975524068949], [20927895257497747238986668613021753703988641935802190249109474260700254931957028009020124444515606174885105200514424695082, 98413334887257200681733050277146006881243886515744398160788872174047591102175251363062934975915162936537446741657116020142, 78051558442599615087309433778145628490452507646127324484751553881813231026055047222156670588293781138503172604228380321976], [16192599784864691180295806644680526068139201230224367938291307055217817451931595148327785761709610349158459120162594696721314, 25611869083247087245152286117827285218210603087717473516754579003267021231851741943325038005987943686029851783456188413428074, 25992180689931116336143095391720658271235318487491891937170995569452091167110261435363933440750176011418320077925229437139441], [1486065074770625241543033346926580865585132960697717056411171079869255497066621227141079321338459582851303823888054029997147496, 3245525951376819329573085322535606750874380802419239054828998013409477579195505568845403155178550250571620183484642153687084244, 112418439871405702093723993558148045955947964355568790237500341233964777308030963124075783317247912243584957552429165175567188], [554414264583315659699674517123338050716408838397305952512626047866746893643260154358369760406409101186772630676890380049965307590, 1043200414999535582462864439522105588377941946109653277868282881800541041225127481024498906645711562172897887223370490480497681412, 1871431105609054802663860414521114349131507818555644333411481724711171594958225200659513765626347213458290656339411867664235748235], [109230492350394219294209686711480148111959062898867460819812302521395700744999727865321098736169431939787056320261942410874757468733, 10946993578608042700991075540593043447808613562525646016983180580734427427599503571629298569725315601140135266559866649733843666727, 246030677678827748651446732888780806311392020007912976339004498361198715345773486325046589103993759763143866861161592823427071675783], [101248109580616294936240676346296891730712143388596188295797877367588968569639645896673577202008557062368850136081432452565741764481780, 72117245758610730163502698117383423435096962164217931641814611037828628449683172552024006212893710709568092586830060674702530720630838, 34156236014950110786479179647875910303316921242375549800567936108514427153840347644258274879993941142366793077681295934860378594097995], [15990838065899635329967108817549304489054566867252353907331052546852811551057811982388652520412231526149334610863159737956306990396908939, 13877638546016696452612797658463979632180424075209018025216464738606223836856974888899865627240196446658442424067555529584318542068829304, 12677775392542654738129436028991703771671470731367401228424534633630663828784099080524940674805885560927768192511268731112718248394226507], [4296188317596592605354429710403045587794207218497978126733577807175844533640562786210144572543925369843724531281548656552721224871306408934, 285081536544994597260307396740776857794705257501212064846291286514459078443374031927697656139361855500907534462182310648076485673416888921, 520400706696766574333742507514386230765824087521995208501834759618645877986879790251385446075750614955038875512629839250118760269191026622], [723122593616548907044099469723004726497190485559641744410070335219249336116342743215201071639802723683990761587106342365181354592623344218801, 1153081974669760235610536228156857408078008322403018213105375405360329083793186764164405226051712297309391269434496643454473313250671026317128, 1045323654864427173281766234316255577186878737208078652772060147922139057153363756199552977634641592432020342677714487371354351937732515340769], [286030080032157831584122660246587223893513399286538292684484068916231408017197370416498756180333020768698170404223092800960480629708274198357766, 100459558673910591509973452243869469674982609364866947220110101686698490657211631881397783562822118029166972210922055667458687955478399421168073, 312292327459064171357951759470882292390813169506242332753018135455390262583056880515441693426982451446980584789275705862372219996047882719285468], [76023080448832255495664889576818310445911073068838354851978140354392238188416337217228905387684862369127475726687990437747210819206251364663178366, 79909535960128750054208617904939309393169970650206619816849976160579698275180034617070788991315683797824856913928470939644467300086993321201275631, 12836987084929344870134687159309348060974294106220115465827408756433486147899850505008319816817057038378975905890624567608788056817845202397527597], [11279020797227306692073405567334400908025941871799432354659652341662205110177284358626006856443935763650221701010232939257999415323818219101323774121, 20701716847360264680448441409193277773473820912500811296314617325114135630274188720845655325935966413579156878391231036040452436356525182168927455769, 11662490076049426720444287570232288256606203670569001212826141005750817611908212326773163654541321013641063180589777301351375281786680265675242915490], [3664976056843244899046405770495243971851225829858688853727255965918845526037369928043768545436855691031033629075777959837838040026954342398365868203284, 4303664923255399627145773380664312302061180145098884815650431155840108262865380991633139788830947418042382178669502102253270206161944686126778721177256, 1329888344611251607206799678158068345794425334107811143951615318094938592491017133110084673083835131542105919726637023746895921675774269854930747391813], [27526396919462446400199857855946211084417698150345843381184345248429342915256383060323038929143521278663384600451962926565632962402403286747322866933186, 832473066824718090282351924757867347117523355595408205531707129191210904495622372227106712804655676416188547356217198716998980216027824443061970459017213, 739285279997382078166992780609222700401048107660954429292420131543662494886151464036035917462960151020457777790199766047230392831072294938389838019192375], [241604036983256570910237563151583734634247804014729497396976621887556420166938734129084585512496813488556852332626724956813515081301022211288671489609624726, 232918625432663776612980648646547430425799068288725384437941544591137340240225694513718939585866852521983294039207611429584316281048886496760692847238475958, 330280356821375777416141788080009583520428720186288496589338440210000394525310148011506810729947920712589385371511611188538783776067961774123574958402713416], [37917177921557913063797063712175107470400149903365012052437848627624556178462092849875066084483410175131191909488280543701737678455574966120683361771538984869, 82285213220068552502977130984079405256046284613100219448045047718647214635424915048365233181766026879765932575837957606566968808956187850661636939764713829757, 54862629754020461190972199219422809877737510603527851047197196675006832975655107720818914451383313987635699626910019975156748775680769393491662354129665564665], [10176770592061494683902022210595838961181896347187166561115555380150487550055091054691083781753046719620211182526622568190117287871224755124378960411817051522347, 20391437792952018079898899709442083666375852061962519735185961685298641965953456220963572734830150545534613384697719780482366933145736561569104130664654552711112, 5184672887185762911825431869653048673959736811735614638077371148686297384863233976741655920190695071107226141719503919502011593827206165497631320711901861412505], [2773806845979032590669908316758838167490410534429658877076115296219751182626553934482865930802051989491312042105845829522334288803990327629270690684487381035735068, 4313397356511833703919769030365821724752420735506938177875096936636635640237756238703789233649487006170963871514071797499791012862391242439315785734249060209905870, 1384521522113584419234026605710886691198760220478447038149301773862983248614505122442941228842319360170622150894552550565168083692478460245750070200793173355915110], [977605605346967027884157812086795195281198128843588844802255600782574072246322450726753867594904637719389010883656117163446600576421636602802273450819657911229092739, 1077122028153411402864595787831545281960357301948562230974263019017587247307938796068349770175005165754271751912679139878240066950583364300243665524428812156594708658, 381071794273313233090141046983124159496192143355842855513220907221649906653471651139682409544512356167912597901893098050357507457603299288858937833673078904758920182], [67062212236285997924209614787534890751009288135227553165998196811919096000885310832052245686810617894345398300182072193678864438410618886008897981904472885367476211057, 159854276414635686128310856355014729303536467044176101830252797765797010129021499806804246440506719099238942904835227939207035449129236215655107335852262007504926605969, 250442077587466213725605597489854467254423721041651218597587608844522479925489283592286145881313894977088155508712509697027472708345579764134359861134589340933375529074]]
```
- Challenge source:
```python=
from out import enc, R
from math import prod
flag = ''
a = [0]
for i in range(355):
b = [_+1 for _ in a]
c = [_+1 for _ in b]
a += b + c
if i%5 == 0:
flag += chr(enc[i//5] ^ prod([a[_] for _ in R[i//5]]))
print(flag)
```
### Solution
- How the fuck Connor give that, challenge của chúng ta chính là source luôn. Tuy nhiên nhìn vào output khủng bố kia và cách mà source gen ra các mảng `a, b, c` thì thực sự laptop sẽ nổ ngay lập tức vì quá tải.
- Đây là một bài khá dễ (cho vào crypto thì hơi sú :penguin:) vì chúng ta chỉ cần optimize đoạn code trên là dễ dàng lấy được flag. Tóm lại source sẽ gen ra mảng `a, b, c` là các mảng tăng dần và số lượng của các mảng là một bội số của 3. Mình sẽ không đưa ví dụ vào ~~vì nó dài vcl~~ mà chỉ đưa ra cách giải:
```python=
from out import *
from math import prod
def find(n):
s = 0
while(n):
s += n % 3
n //= 3
return s
flag = ''
for i in range(355 // 5):
c = prod([find(n) for n in R[i]])
flag += chr(enc[i] ^ c)
print(flag)
```
### Flag
> ~~`CSCTF{2441d2f22fa1d5b9fc0a850dcfbbccf608cafbc22a1beaae0ac328ff6d218781}`~~
---
## 3. trendy windy trigonity
### Description
- Challenge source:
```python=
from Crypto.Util.number import bytes_to_long
flag = REDACTED
print(len(flag))
R = RealField(1000)
a,b = bytes_to_long(flag[:len(flag)//2]),bytes_to_long(flag[len(flag)//2:])
x = R(0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557302303874143106908193100)
enc = a*cos(x)+b*sin(x)
#38
#2.78332652222000091147933689155414792020338527644698903976732528036823470890155538913578083110732846416012108159157421703264608723649277363079905992717518852564589901390988865009495918051490722972227485851595410047572144567706501150041757189923387228097603575500648300998275877439215112961273516978501e45
```
### Solution
- Chall này khá thú vị vì liên quan đến phương trình lượng giác (điều mình thấy khá hiếm trong CTF). Phương trình được cho là:
```
a*sin(x) + b*cos(x) = c
```
yêu cầu tìm `a, b` với góc `x` cho trước nên phương trình lượng giác trở thành phương trình bậc nhất hai ẩn.
- Phương trình này có vô số nghiệm, tuy nhiên chúng ta chỉ cần tìm nghiệm nhỏ nhất, điều này đưa mình tới ý tưởng sử dụng LLL (lattice) để giải. Nhưng do `a` và `b` đều là các số khá lớn (vì là `long_to_bytes()` của hai phần flag 38 bytes) nên chúng ta sẽ cần thêm trọng số vào trong lattice (càng lớn càng tốt nhưng `2**1000` là đủ vì chúng ta đang sử dụng tập số thực `R` với độ chính xác 1000).
- Biến đổi phương trình, ta được:
```python
c - a*sin(x) - b*cos(x) = 0
```
nên lattice có dạng:
```python=
L = [ w*c 1 0 0]
[w * -sin(x) 0 1 0]
[w * -cos(x) 0 0 1]
```
- Áp dụng LLL vào lattice L ta nhận được hai số `a`, `b` là hai phần tử cuối cùng của hàng đầu tiên. Giải thích: do vector ngắn nhất sau khi LLL nhận được có dạng `[garbage1, garbage2, a, b]` theo chứng minh của [Theblupper (cũng là author của giải này luôn)](https://theblupper.github.io/blog/posts/lattices/)
- Code:
```python=
from Crypto.Util.number import *
R = RealField(1000)
x = R(0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557302303874143106908193100)
c = 2.78332652222000091147933689155414792020338527644698903976732528036823470890155538913578083110732846416012108159157421703264608723649277363079905992717518852564589901390988865009495918051490722972227485851595410047572144567706501150041757189923387228097603575500648300998275877439215112961273516978501e45
w = 2**1000
L = matrix(QQ, [
[w * c , 1, 0, 0],
[w * -R(sin(x)), 0, 1, 0],
[w * -R(cos(x)), 0, 0, 1]
])
sol = L.LLL()[0]
a, b = int(sol[-1]), int(sol[-2])
assert a*cos(x) + b*sin(x) == c
flag = long_to_bytes(a) + long_to_bytes(b)
print(flag)
```
### Flag
> ~~`CSCTF{Trigo_453_Tr3ndy_FuN_Th35e_D4Y5}`~~
### Note
- Bài này là một introduction khá tốt cho mọi người muốn học về lattice và LLL, những tài liệu và challenge về vấn đề tương tự mình sẽ để ở [đây(lattice training)](https://ur4ndom.dev/static/files/latticetraining/practical_lattice_reductions.pdf) và [đây(eprint)](https://eprint.iacr.org/2023/032.pdf)
---
## 4. super-fnv
### Description
- Challenge source:
```python=
from pwn import xor
from random import randint
from hashlib import sha256
from FLAG import flag
cc = [randint(-2**67, 2**67) for _ in range(9)]
key = sha256("".join(str(i) for i in cc).encode()).digest()
enc = xor(key, flag)
def superfnv():
x = 2093485720398457109348571098457098347250982735
k = 1023847102938470123847102938470198347092184702
for c in cc:
x = k * (x + c)
return x % 2**600
print(f"{enc.hex() = }")
print(f"{superfnv() = }")
# enc.hex() = '4ba8d3d47b0d72c05004ffd937e85408149e13d13629cd00d5bf6f4cb62cf4ca399ea9e20e4227935c08f3d567bc00091f9b15d53e7bca549a'
# superfnv() = 2957389613700331996448340985096297715468636843830320883588385773066604991028024933733915453111620652760300119808279193798449958850518105887385562556980710950886428083819728334367280
```
### Solution
### Flag
> ~~``~~
---
## 5. Connorsmith
### Description
- Challenge source:
```python=
m = int.from_bytes(b'CSCTF{redacted}')
p = random_prime(2**1024)
q = random_prime(2**1024)
N = p*q
d = randint(0, int(N**0.35))
e = pow(d, -1, (p-1)*(q-1))
print(f'{N = }')
print(f'{e = }')
print(f'c = {pow(m, e, N)}')
print(f'hint = {(p+q) >> 795}')
"""
N = 7552253013225223212686972759229408890943243937848116869511428282592494711559240135372705736006054353083281103140787662239958191241833157109597880624454796412006762881501916845155158694626704629051045217266597685547634722763704638532067409306181328833329683262904207364205190648604464680961179156366009048508124744257064547090561236984730817200175311749708243086463240602718911105727107075971987228340827791295829216059926076767577606528647738447725195880791137450082195604212374273765390335921438605358227547423468794396280894150559661664635540689602987474623120205743645087417873312711804245504568677508120251077973
e = 3972273176912267799970180147678020025192175195982968793722693097132970664724388722714705209022371322943558028173459714967997171817396680330435643595109433373306392229639747130134793710239081601404067602930871254806754684103349829634489509031907387929080189489106215966862642406152181674399593026117258657690036458955106821789654735855538375273851668820461621159458690509295524433242439365251850800232909323376356116251835554606066609685882803255427299046970093232995420925951786433206910901590576814359503385919307570360242528454529766855342865079257244016304989185569117193284115242278439808082079787893597831292429
c = 6722063431743120124281037577917473736384734002344400102535470664988199976365033546621632487383386053044468700113542626459908567596300577088705896140930724832695917664482501591801075560437336915520962349830960551339852803481367045861684404716913927870231244602348980596739084252620702852351036834534769613031735817640709051052713694452907186969900542466747407949270228341375666775282809021111998328175103742416108902755346724742467339317044645243210574003890806923017769148711785248795287760426567277473640239499920974270994457112678786022613046685998793486144172215215581287541508145268729387185453679039441575292812
hint = 891237814844096809623936988168241703768093224718029580247856301709140
"""
```
### Solution
- Bài này là một trong hai bài khô nhất của mình, và cũng là bài khá thú vị. Nhìn vào source, ta có thể dễ dàng nhận ra `d < N^0.35`, đây là thứ giúp remind lại về các cách tấn công RSA với `small private exponent` mà tiêu biểu trong đó là `Weiner Attack` hoặc cao cấp hơn là `Boneh Durfee Attack`. Tuy nhiên cả hai cách tấn công trên chỉ thực hiện được khi mà `d < N^0.292`. Với bài này chúng ta cần phải sử dụng thêm `hint` để recover lại `d`
- Mình đã tham khảo cryptohack về [Boneh-Durfee Attack](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/boneh-durfee-attack) để thành lập phương trình hai ẩn trên trường `Zmod(e)`, cụ thể như sau:
```python=
PR = PolynomialRing(Zmod(e), names=('x', 'k'))
x, k = PR.gens()
sh = hint << 795
A = (N+1) // 2
s = -(sh + x) // 2
f = k*(A + s) - 1
```
- Tại đây chúng ta có thể sử dụng `Coppersmith` để tìm lại nghiệm của phương trình. Có rất nhiều tools `Coppersmith` được viết trên github, mình đã thử cả `defund` và `kiona` nhưng chỉ có `kiona` thành công. Author cũng giải thích rằng thuật toán giải sử dụng trong `defund` là `Groebner basis` trong khi `kiona` sử dụng `Jacobian-Newton's method`. Bên cạnh đó Connor cũng suggest rằng chúng ta nên giải phương trình hai ẩn bằng `Resultant` để đạt hiệu quả cao nhất.
- Tóm lại chall này không có gì quá phức tạp, straight-forward idea, right? :monkey_face:. Btw, implementing `kiona's coppersmith` is a little bit crazy and not easy, here is the [link](https://github.com/kionactf/coppersmith).
```python=
import sys
sys.path.append("/mnt/c/Users/ADMIN/CryptoTools/coppersmith") #Path to kiona's tools directory
sys.set_int_max_str_digits(5000)
from Crypto.Util.number import *
from coppersmith_multivariate_heuristic import coppersmith_multivariate_heuristic
# Params
N = 7552253013225223212686972759229408890943243937848116869511428282592494711559240135372705736006054353083281103140787662239958191241833157109597880624454796412006762881501916845155158694626704629051045217266597685547634722763704638532067409306181328833329683262904207364205190648604464680961179156366009048508124744257064547090561236984730817200175311749708243086463240602718911105727107075971987228340827791295829216059926076767577606528647738447725195880791137450082195604212374273765390335921438605358227547423468794396280894150559661664635540689602987474623120205743645087417873312711804245504568677508120251077973
e = 3972273176912267799970180147678020025192175195982968793722693097132970664724388722714705209022371322943558028173459714967997171817396680330435643595109433373306392229639747130134793710239081601404067602930871254806754684103349829634489509031907387929080189489106215966862642406152181674399593026117258657690036458955106821789654735855538375273851668820461621159458690509295524433242439365251850800232909323376356116251835554606066609685882803255427299046970093232995420925951786433206910901590576814359503385919307570360242528454529766855342865079257244016304989185569117193284115242278439808082079787893597831292429
c = 6722063431743120124281037577917473736384734002344400102535470664988199976365033546621632487383386053044468700113542626459908567596300577088705896140930724832695917664482501591801075560437336915520962349830960551339852803481367045861684404716913927870231244602348980596739084252620702852351036834534769613031735817640709051052713694452907186969900542466747407949270228341375666775282809021111998328175103742416108902755346724742467339317044645243210574003890806923017769148711785248795287760426567277473640239499920974270994457112678786022613046685998793486144172215215581287541508145268729387185453679039441575292812
hint = 891237814844096809623936988168241703768093224718029580247856301709140
# Define
PR = PolynomialRing(Zmod(e), names=('x', 'k'))
x, k = PR.gens()
un = 795
sh = hint << un
A = (N + 1) // 2
s = -(sh + x) // 2
f = k*(A + s) - 1
# Solve
tmp = coppersmith_multivariate_heuristic(f, [2**un, 2**711], beta = 1)[0]
xx = tmp[0]
kk = tmp[1]
assert f(x = xx, k=kk) == 0
s = sh + xx
phi = N + 1 - s
d = inverse(e, int(phi))
m = int(pow(c, d, N))
m = long_to_bytes(m)
print(m)
```
### Flag
> ~~`CSCTF{37c37f30fc67f98f376a1c30b25b3969}`~~
---
## 6. Two many hints
### Description
- Challenge source:
```python=
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad,unpad
from secret import flag
# PARAMETERS
q = 3329
k = 2
sigma = 2.5
n = 256
K = CyclotomicField(n,'z')
OK = K.OK()
OKq= OK.quotient(q,'y')
A = matrix(K, k,k, [K(random_vector(ZZ,n//2,x=-q//2,y=q//2).list()) for _ in k*k*"_"]).lift_centered()
s = matrix(K, [K(random_vector(ZZ,n//2,sigma,distribution="gaussian").list()) for __ in k*"_"] )
e = matrix(K, [K(random_vector(ZZ,n//2,sigma,distribution="gaussian").list()) for __ in k*"_"] )
b = (s*A +e ).change_ring(OKq)
H = matrix(k,k,[ OK(list(random_vector(ZZ,n))) for _ in k*k*"_"] )
l = s*H # I won't give you this 3:)
h = floor(.25*n/2)
l2 = matrix([l[0,0] , OK(l[0,1].list()[:-h]) ])
key = sha256(str(s).encode()).digest()[:16]
iv = sha256(str(e).encode()).digest()[:16]
cipher= AES.new(key,AES.MODE_CBC,iv=iv)
enc = cipher.encrypt(pad(flag,16))
#Printing
print(f"A = {A.coefficients()}")
print(f"b = {b.coefficients()}")
print(f"H = {H.coefficients()}")
print(f"l2 = {l2.coefficients()}")
print("enc = ", enc.hex())
```
- Challenge output:
```python=
A = [-1052*z^127 + 566*z^126 + 1032*z^125 + 1260*z^124 + 1379*z^123 + 395*z^122 - 929*z^121 - 1350*z^120 + 1535*z^119 + 72*z^118 + 262*z^117 - 669*z^116 + 1141*z^115 + 1076*z^114 - 200*z^113 + 1453*z^112 - 1492*z^111 - 1165*z^110 - 599*z^109 + 990*z^108 - 207*z^107 + 1014*z^106 + 1230*z^105 + 125*z^104 + 369*z^103 - 1073*z^102 - 741*z^101 + 1349*z^100 + 459*z^99 + 51*z^98 - 616*z^97 - 1491*z^96 - 310*z^95 - 975*z^94 + 580*z^93 - 1371*z^92 + 291*z^91 - 904*z^90 - 989*z^89 - 1007*z^88 - 1525*z^87 + 1548*z^86 + 885*z^85 - 671*z^84 - 406*z^83 - 1164*z^82 + 1600*z^81 + 438*z^80 + 1079*z^79 - 15*z^78 + 1027*z^77 + 1263*z^76 + 1307*z^75 + 1250*z^74 - 1347*z^73 - 1003*z^72 - 1444*z^71 - 1174*z^70 + 1117*z^69 + 159*z^68 - 1555*z^67 + 1035*z^66 - 1167*z^65 + 326*z^64 - 362*z^63 - 1377*z^62 + 152*z^61 + 934*z^60 + 1120*z^59 - 155*z^58 - 797*z^57 - 379*z^56 + 501*z^55 - 958*z^54 - 577*z^53 - 836*z^52 + 663*z^51 - 550*z^50 - 442*z^49 + 1271*z^48 + 1200*z^47 - 454*z^46 + 1164*z^45 - 505*z^44 - 1571*z^43 + 1480*z^42 + 113*z^41 - 36*z^40 + 821*z^39 - 1456*z^38 + 1475*z^37 + 325*z^36 + 525*z^35 - 481*z^34 + 1586*z^33 - 139*z^32 - 950*z^31 - 277*z^30 - 389*z^29 + 653*z^28 - 1526*z^27 - 645*z^26 + 438*z^25 - 904*z^24 - 1272*z^23 - 28*z^22 + 848*z^21 - 206*z^20 - 918*z^19 + 1311*z^18 - 1544*z^17 - 760*z^16 - 755*z^15 + 837*z^14 + 1258*z^13 + 659*z^12 + 405*z^11 + 1208*z^10 - 1168*z^9 - 422*z^8 + 356*z^7 - 1398*z^6 - 1632*z^5 + 862*z^4 - 166*z^3 + 391*z^2 + 1229*z - 369, -374*z^127 - 587*z^126 - 509*z^125 + 570*z^124 - 728*z^123 + 999*z^122 + 1375*z^121 - 103*z^120 + 1335*z^119 - 600*z^118 - 91*z^117 + 292*z^116 - 51*z^115 + 140*z^114 - 30*z^113 - 1085*z^112 + 1125*z^111 - 780*z^110 - 1305*z^109 - 715*z^108 - 1403*z^107 - 518*z^106 + 11*z^105 - 936*z^104 + 544*z^103 - 1190*z^102 + 1407*z^101 + 1079*z^100 + 325*z^99 + 278*z^98 + 788*z^97 - 236*z^96 - 1304*z^95 - 1385*z^94 + 1484*z^93 - 771*z^92 - 15*z^91 - 195*z^90 - 799*z^89 - 772*z^88 - 1269*z^87 - 716*z^86 + 1201*z^85 - 199*z^84 + 900*z^83 - 593*z^82 - 1512*z^81 - 1019*z^80 + 1379*z^79 - 753*z^78 + 892*z^77 + 1000*z^76 - 848*z^75 + 41*z^74 + 611*z^73 + 456*z^72 + 1624*z^71 + 262*z^70 + 1112*z^69 - 1527*z^68 - 438*z^67 + 902*z^66 - 1338*z^65 - 1350*z^64 - 1014*z^63 + 1085*z^62 + 511*z^61 - 1236*z^60 + 887*z^59 + 784*z^58 - 966*z^57 - 1174*z^56 - 1236*z^55 + 1206*z^54 - 597*z^53 - 1004*z^52 - 941*z^51 - 1251*z^50 - 543*z^49 - 529*z^48 - 443*z^47 + 796*z^46 - 814*z^45 - 1347*z^44 + 1469*z^43 + 406*z^42 - 551*z^41 + 1408*z^40 + 1605*z^39 + 1481*z^38 + 829*z^37 - 917*z^36 - 1527*z^35 - 1469*z^34 - 1533*z^33 + 143*z^32 - 1221*z^31 - 887*z^30 - 1653*z^29 + 315*z^28 - 125*z^27 - 1373*z^26 + 1026*z^25 - 234*z^24 + 1380*z^23 - 1019*z^22 + 817*z^21 + 716*z^20 - 53*z^19 - 215*z^18 + 1355*z^17 - 184*z^16 - 1364*z^15 + 1269*z^14 - 1402*z^13 - 771*z^12 + 672*z^11 + 66*z^10 - 846*z^9 - 1208*z^8 + 563*z^7 - 1457*z^6 + 259*z^5 + 1486*z^4 - 556*z^3 + 622*z^2 - 164*z + 550, 59*z^127 - 782*z^126 - 80*z^125 - 426*z^124 - 1524*z^123 + 138*z^122 - 646*z^121 + 192*z^120 + 1125*z^119 + 845*z^118 + 948*z^117 - 503*z^116 + 721*z^115 + 158*z^114 + 1543*z^113 - 1638*z^112 - 197*z^111 + 1577*z^110 + 1585*z^109 + 1389*z^108 - 106*z^107 + 1612*z^106 - 289*z^105 - 365*z^104 + 101*z^103 + 354*z^102 - 1037*z^101 + 1388*z^100 - 592*z^99 + 181*z^98 + 454*z^97 - 702*z^96 + 501*z^95 + 904*z^94 - 133*z^93 - 1644*z^92 + 1446*z^91 + 917*z^90 + 1520*z^89 + 1620*z^88 + 971*z^87 + 1398*z^86 - 1386*z^85 + 1130*z^84 + 862*z^83 + 88*z^82 - 1083*z^81 + 782*z^80 - 1138*z^79 + 845*z^78 - 1318*z^77 - 769*z^76 - 226*z^75 + 311*z^74 - 536*z^73 + 287*z^72 + 47*z^71 + 547*z^70 + 249*z^69 - 1470*z^68 + 683*z^67 - 152*z^66 - 1430*z^65 - 147*z^64 + 388*z^63 + 1145*z^62 + 99*z^61 - 646*z^60 - 942*z^59 + 1472*z^58 + 225*z^57 - 412*z^56 - 243*z^55 + 1642*z^54 - 51*z^53 + 1028*z^52 - 1476*z^51 + 1375*z^50 + 938*z^49 - 1304*z^48 - 120*z^47 - 123*z^46 - 1479*z^45 - 1338*z^44 + 257*z^43 + 1562*z^42 - 1413*z^41 - 730*z^40 - 1024*z^39 - 1134*z^38 + 963*z^37 + 142*z^36 - 147*z^35 - 1292*z^34 - 1295*z^33 - 387*z^32 + 1447*z^31 + 1182*z^30 + 10*z^29 - 1656*z^28 - 110*z^27 - 592*z^26 - 1454*z^25 - 328*z^24 - 1001*z^23 - 751*z^22 - 127*z^21 - 467*z^20 - 583*z^19 - 909*z^18 - 122*z^17 - 177*z^16 - 1503*z^15 + 1409*z^14 - 1343*z^13 - 715*z^12 + 1261*z^11 + 1100*z^10 - 929*z^9 - 1314*z^8 + 1207*z^7 + 1474*z^6 + 590*z^5 - 1302*z^4 - 1233*z^3 + 862*z^2 + 354*z - 1358, 511*z^127 + 892*z^126 + 786*z^125 + 1358*z^124 + 301*z^123 + 620*z^122 - 481*z^121 + 1353*z^120 + 408*z^119 - 732*z^118 + 879*z^117 - 779*z^116 + 974*z^115 - 1417*z^114 - 255*z^113 - 1183*z^112 - 593*z^111 - 271*z^110 - 1592*z^109 + 1552*z^108 + 1482*z^107 - 1574*z^106 + 77*z^105 + 219*z^104 + 1193*z^103 + 1598*z^102 + 40*z^101 - 677*z^100 + 978*z^99 - 900*z^98 + 1323*z^97 - 176*z^96 - 1091*z^95 - 299*z^94 + 616*z^93 - 1060*z^92 + 671*z^91 + 786*z^90 + 1123*z^89 + 1547*z^88 + 1214*z^87 - 1076*z^86 - 1463*z^85 - 1201*z^84 - 488*z^83 - 584*z^82 - 530*z^81 + 145*z^80 + 327*z^79 - 964*z^78 + 868*z^77 - 1112*z^76 - 939*z^75 - 955*z^74 + 851*z^73 - 1030*z^72 - 992*z^71 - 1560*z^70 + 488*z^69 - 372*z^68 - 157*z^67 + 382*z^66 - 364*z^65 + 1348*z^64 - 417*z^63 + 262*z^62 + 991*z^61 - 1471*z^60 + 803*z^59 - 1000*z^58 + 1616*z^57 + 1485*z^56 - 963*z^55 - 1020*z^54 + 1381*z^53 - 1048*z^52 + 130*z^51 + 1528*z^50 + 986*z^49 + 1239*z^48 - 1454*z^47 + 1095*z^46 - 639*z^45 - 190*z^44 - 689*z^43 - 1351*z^42 - 1242*z^41 - 550*z^40 - 1180*z^39 - 761*z^38 - 1067*z^37 - 1565*z^36 + 404*z^35 - 821*z^34 + 1449*z^33 - 1377*z^32 + 507*z^31 - 691*z^30 + 604*z^29 - 1649*z^28 + 350*z^27 - 1568*z^26 - 872*z^25 - 944*z^24 - 242*z^23 + 84*z^22 + 240*z^21 + 646*z^20 - 1513*z^19 + 40*z^18 + 266*z^17 - 1232*z^16 - 56*z^15 + 800*z^14 + 1335*z^13 + 1472*z^12 - 1042*z^11 + 636*z^10 - 1620*z^9 + 780*z^8 - 158*z^7 + 818*z^6 - 911*z^5 - 498*z^4 - 1380*z^3 - 1287*z^2 + 820*z - 335]
b = [-395*z^127 - 347*z^126 + 654*z^125 - 1469*z^124 + 318*z^123 + 325*z^122 - 20*z^121 - 516*z^120 + 159*z^119 + 102*z^118 + 825*z^117 - 943*z^116 - 767*z^115 - 1662*z^114 - 1556*z^113 + 1638*z^112 - 103*z^111 + 1408*z^110 + 1047*z^109 + 169*z^108 - 1205*z^107 - 1025*z^106 - 128*z^105 - 391*z^104 + 1653*z^103 + 441*z^102 - 1430*z^101 + 187*z^100 - 417*z^99 + 468*z^98 + 635*z^97 + 816*z^96 - 1590*z^95 - 822*z^94 - 626*z^93 + 73*z^92 - 206*z^91 + 573*z^90 + 81*z^89 - 620*z^88 - 764*z^87 - 831*z^86 + 1356*z^85 - 106*z^84 - 950*z^83 + 664*z^82 + 453*z^81 - 1663*z^80 - 1410*z^79 + 1243*z^78 + 213*z^77 - 55*z^76 + 814*z^75 - 81*z^74 - 1272*z^73 + 1513*z^72 + 687*z^71 + 519*z^70 + 55*z^69 + 1540*z^68 - 1234*z^67 - 1046*z^66 - 1049*z^65 - 1479*z^64 - 302*z^63 - 496*z^62 + 1586*z^61 - 825*z^60 - 123*z^59 - 1020*z^58 - 1416*z^57 + 623*z^56 - 615*z^55 + 760*z^54 + 1155*z^53 - 1143*z^52 + 1037*z^51 - 478*z^50 - 531*z^49 + 1380*z^48 + 1111*z^47 - 258*z^46 + 884*z^45 - 1491*z^44 + 1132*z^43 - 1184*z^42 - 1397*z^41 + 238*z^40 - 128*z^39 + 642*z^38 + 763*z^37 + 927*z^36 + 1121*z^35 - 441*z^34 + 22*z^33 + 1167*z^32 + 1512*z^31 - 402*z^30 + 1261*z^29 + 750*z^28 - 1469*z^27 - 931*z^26 + 616*z^25 + 229*z^24 + 517*z^23 + 145*z^22 - 112*z^21 + 493*z^20 - 981*z^19 + 796*z^18 - 1196*z^17 + 702*z^16 + 1423*z^15 + 978*z^14 + 1312*z^13 - 183*z^12 - 386*z^11 + 585*z^10 + 1473*z^9 - 1137*z^8 + 918*z^7 + 1539*z^6 - 193*z^5 + 861*z^4 - 315*z^3 - 529*z^2 + 866*z + 1234, -1263*z^127 + 785*z^126 - 515*z^125 - 1149*z^124 - 1165*z^123 - 1111*z^122 - 628*z^121 + 962*z^120 - 1277*z^119 + 1546*z^118 - 13*z^117 + 1237*z^116 + 1397*z^115 - 1056*z^114 - 172*z^113 - 1048*z^112 - 782*z^111 + 430*z^110 - 881*z^109 + 566*z^108 + 67*z^107 - 29*z^106 - 889*z^105 + 1233*z^104 - 1208*z^103 + 497*z^102 - 416*z^101 + 653*z^100 + 1639*z^99 + 516*z^98 - 65*z^97 - 1068*z^96 - 799*z^95 + 324*z^94 + 302*z^93 + 382*z^92 - 123*z^91 - 158*z^90 + 279*z^89 - 896*z^88 + 329*z^87 - 696*z^86 + 1240*z^85 + 315*z^84 + 1113*z^83 - 741*z^82 + 178*z^81 + 186*z^80 - 1171*z^79 + 1126*z^78 - 908*z^77 - 1643*z^76 + 193*z^75 + 1372*z^74 - 793*z^73 + 1544*z^72 - 1330*z^71 + 295*z^70 + 1172*z^69 - 1159*z^68 + 696*z^67 - 718*z^66 - 1587*z^65 + 1007*z^64 - 323*z^63 - 258*z^62 - 125*z^61 - 704*z^60 - 375*z^59 + 1362*z^58 + 97*z^57 - 512*z^56 + 785*z^55 + 1398*z^54 + 1048*z^53 - 926*z^52 + 121*z^51 + 1559*z^50 + 308*z^49 - 72*z^48 - 1050*z^47 + 190*z^46 + 868*z^45 - 1248*z^44 - 1498*z^43 - 658*z^42 + 228*z^41 + 661*z^40 - 670*z^39 - 500*z^38 - 594*z^37 + 1495*z^36 - 194*z^35 - 1119*z^34 + 1139*z^33 + 1268*z^32 - 1589*z^31 + 1133*z^30 - 123*z^29 + 93*z^28 - 859*z^27 - 1547*z^26 + 1274*z^25 - 695*z^24 - 1250*z^23 + 1406*z^22 - 1548*z^21 - 949*z^20 - 566*z^19 + 1542*z^18 + 96*z^17 + 195*z^16 + 149*z^15 - 1152*z^14 + 204*z^13 + 1202*z^12 + 505*z^11 - 1213*z^10 - 575*z^9 - 942*z^8 - 923*z^7 - 503*z^6 + 801*z^5 + 637*z^4 - 1143*z^3 - 506*z^2 + 138*z + 900]
H = [z^127 - z^126 - z^125 + z^124 + 9*z^123 - z^122 - z^121 + 2*z^120 - 98*z^118 + 8*z^117 + 5*z^115 + 11*z^114 - 2*z^113 - z^111 + 10*z^110 - z^108 + z^106 - z^105 - 4*z^104 - z^103 - z^102 - 3*z^101 + 7*z^100 + z^99 + 50*z^98 + 17*z^97 - 3261*z^96 + z^94 + 2*z^93 + z^92 - z^91 + 14*z^90 + z^89 - z^88 + 4*z^87 - 51*z^86 + 7*z^85 - z^84 + z^83 - z^82 + 2*z^81 - 8*z^80 - z^79 + z^78 + 2*z^76 - 6*z^75 - z^74 - 2*z^73 - z^72 - 2*z^71 - z^69 - z^68 - 2*z^67 - 5*z^66 - 3*z^65 - 30*z^64 + 5*z^63 + z^62 - 4*z^61 - 2*z^60 - 9*z^59 + z^58 - 5*z^57 + 3*z^56 + 6*z^55 - 4*z^54 - z^53 - 3*z^52 - z^51 + 2*z^50 - 13*z^49 + 2*z^47 + z^46 - z^45 - 2*z^44 + 5*z^43 - z^42 + 5*z^41 - z^39 + z^37 - z^35 + z^34 - 3*z^33 + 6*z^32 - 2*z^31 - z^30 - 6*z^28 - z^26 + z^25 - z^24 + 3*z^23 - 8*z^21 - 10*z^20 - 17*z^19 + z^18 - z^16 - 2*z^15 + z^14 + z^13 + z^12 + z^11 + 10*z^10 - z^9 - z^8 - z^7 - 2*z^6 + z^5 - z^3 - z^2 + 12*z, z^126 + z^125 - 4*z^124 + z^123 + z^122 + z^121 - 4*z^119 + z^118 + z^117 - 19*z^116 - z^115 + 3*z^114 - 2*z^113 + z^112 + 5*z^111 + 3*z^110 + z^107 - z^106 - z^105 - 5*z^104 + 2*z^103 - z^102 - 3*z^100 - 8*z^99 + 4*z^98 + 2*z^95 + 13*z^94 - 2*z^93 + z^92 - z^90 - 3*z^88 + z^87 - z^86 + z^85 + z^84 - 2*z^83 - 6*z^81 - 5*z^78 - z^77 + z^76 + z^75 - z^74 - 2*z^73 + z^72 + 8*z^71 + z^70 + 3*z^69 - z^68 - 5*z^66 - z^64 - z^63 - 2*z^62 - 2*z^61 - 16*z^60 + z^59 + 8*z^58 - z^57 - z^56 - z^55 + z^54 + 3*z^53 + z^52 + 5*z^51 - z^50 - 3*z^49 - 4*z^47 + z^46 - z^45 + 5*z^43 + z^40 + z^39 + 2*z^38 - z^37 - z^36 + z^35 - z^34 - 2*z^33 + z^32 + z^31 - z^30 - z^29 + z^27 - 4*z^26 + 2*z^24 + z^23 + 2*z^22 + z^21 + 22*z^19 - z^18 + 2*z^16 + z^15 - z^14 + z^12 - 10*z^11 + z^10 - z^9 + z^8 - z^7 - z^6 - z^3 + z^2, -3*z^124 + 2*z^123 + 2*z^122 + z^121 - 67*z^120 + 2*z^119 + 2*z^118 + z^117 + 55*z^116 - 4*z^115 + z^114 - z^113 - 2*z^112 + 17*z^111 + 4*z^110 - z^109 + z^108 + z^107 + z^106 + z^104 + z^103 + 2*z^102 - z^101 - z^100 - z^99 + z^98 - 6*z^97 - z^96 - z^95 + z^92 - z^91 - z^90 + z^89 - 54*z^88 - z^86 - z^85 - z^84 - z^83 + z^82 + 3*z^81 + z^79 + z^77 - z^76 - 2*z^75 + 2*z^74 - z^73 - 2*z^72 + 2*z^71 - z^70 - z^69 - z^68 + z^67 - z^66 - 3*z^65 + z^64 - z^63 + z^62 + 48*z^60 - z^58 - 3*z^57 - 2*z^56 - z^54 - 4*z^53 + 8*z^52 - 3*z^51 - 56*z^50 + 3*z^49 - z^48 + z^45 + 24*z^44 - z^43 - 3*z^42 + z^40 + z^39 - z^38 + 2*z^37 - z^35 - z^34 - 3*z^33 + 2*z^31 - 42*z^29 - z^28 - 10*z^26 + z^25 + z^24 + 8*z^23 - z^22 + z^21 + 3*z^19 - 6*z^18 + 2*z^16 - z^15 - z^14 - z^13 + z^12 + 6*z^11 - 3*z^10 + z^8 + z^7 + 2*z^6 + 2*z^5 + z^4 + z^3 - 3*z^2 - 1, -z^127 + 2*z^126 - 16*z^125 - z^123 + z^122 + z^121 - 23*z^120 + z^119 + z^118 + 2*z^117 + z^116 + 5*z^115 + 8*z^114 - 5*z^113 + z^112 - z^111 + 5*z^110 + 2*z^108 + z^107 + 24*z^105 + 3*z^104 + z^103 - z^102 + 26*z^101 - 3*z^100 + 3*z^99 - z^98 + 3*z^97 + z^96 - z^94 - z^93 + z^92 - 4*z^90 - 3*z^88 - z^87 + 2*z^86 - 3*z^85 - 2*z^84 + z^83 - 2*z^82 + 6*z^80 + z^79 - z^78 + 8*z^77 - 2*z^76 - 3*z^75 - 2*z^74 - 2*z^73 + 3*z^71 + z^70 + z^69 - 2*z^67 - z^66 - 72*z^64 + 5*z^62 + 5*z^61 - 9*z^60 - z^59 + z^55 + z^54 - z^53 + z^52 + 3*z^51 + 15*z^50 + 3*z^49 - 3*z^48 - z^47 - z^45 - 7*z^44 - z^43 - 3*z^42 + 17*z^41 - z^37 - 3*z^36 + z^35 - 3*z^34 + z^32 - z^31 - z^30 + z^29 + 2*z^28 - z^26 + 2*z^25 + z^24 - 3*z^23 - 2*z^22 + 4*z^20 - 2*z^19 - z^18 + 2*z^17 + 6*z^15 - z^14 - z^13 - 2*z^12 - 2*z^11 + 2*z^9 + z^8 - 3*z^6 - 3*z^5 - z^4 - 4*z^3 + 2*z^2 - z]
l2 = [-6125*z^127 - 2822*z^126 - 92*z^125 - 9474*z^124 - 2842*z^123 + 6910*z^122 - 4249*z^121 + 4443*z^120 - 6752*z^119 - 3199*z^118 - 6560*z^117 + 3735*z^116 + 10442*z^115 - 6547*z^114 - 3302*z^113 - 9315*z^112 + 6096*z^111 + 2825*z^110 + 8951*z^109 - 307*z^108 + 9340*z^107 - 2962*z^106 + 13486*z^105 + 3908*z^104 + 10228*z^103 - 6813*z^102 + 5772*z^101 + 12398*z^100 + 3491*z^99 + 13448*z^98 + 3687*z^97 - 748*z^96 - 361*z^95 + 7100*z^94 - 3617*z^93 + 6460*z^92 + 3983*z^91 + 7359*z^90 - 12602*z^89 - 3562*z^88 - 26786*z^87 - 280*z^86 - 3294*z^85 - 6302*z^84 - 6502*z^83 + 9983*z^82 + 6643*z^81 + 6723*z^80 - 10252*z^79 - 3047*z^78 - 665*z^77 + 10404*z^76 + 6441*z^75 - 6583*z^74 - 5947*z^73 + 9607*z^72 - 12514*z^71 + 131*z^70 - 3517*z^69 - 3115*z^68 + 13435*z^67 - 12509*z^66 - 6094*z^65 - 12622*z^64 + 2840*z^63 + 3166*z^62 + 2622*z^61 + 3362*z^60 - 3041*z^59 + 7126*z^58 - 3046*z^57 - 3350*z^56 - 432*z^55 + 6468*z^54 - 2885*z^53 + 470*z^52 - 3109*z^51 - 6331*z^50 - 3812*z^49 + 6021*z^48 - 3058*z^47 - 4180*z^46 + 3159*z^45 + 19359*z^44 - 6450*z^43 - 6568*z^42 - 13101*z^41 + 6179*z^40 - 13210*z^39 - 2478*z^38 - 3550*z^37 + 6556*z^36 + 3405*z^35 + 309*z^34 + 3076*z^33 + 9636*z^32 - 467*z^31 + 2596*z^30 + 13554*z^29 - 6653*z^28 - 16341*z^27 - 12422*z^26 + 10044*z^25 - 19304*z^24 - 6484*z^23 - 5988*z^22 - 3026*z^21 - 2853*z^20 - 3058*z^19 - 12863*z^18 - 537*z^17 + 2784*z^16 + 804*z^15 - 271*z^14 - 9575*z^13 + 13044*z^12 - 6387*z^11 - 464*z^10 - 10906*z^9 - 6056*z^8 + 137*z^7 - 12311*z^6 - 6797*z^5 + 111*z^4 + 9323*z^3 - 16100*z^2 - 3241*z + 216, 169*z^95 - 237*z^94 - 287*z^93 + 535*z^92 - 142*z^91 - 257*z^90 + 132*z^89 + 61*z^88 + 214*z^87 - 69*z^86 + 154*z^85 - 102*z^84 + 413*z^83 + 166*z^82 + 547*z^81 + 2*z^80 - 88*z^79 - 215*z^78 - 467*z^77 - 167*z^76 - 467*z^75 + 164*z^74 - 120*z^73 - 304*z^72 + 144*z^71 + 282*z^70 - 277*z^69 - 27*z^68 + 41*z^67 + 111*z^66 - 549*z^65 + 636*z^64 - 46*z^63 + 328*z^62 - 65*z^61 + 149*z^60 - 137*z^59 - 130*z^58 - 116*z^57 + 113*z^56 - 150*z^55 - 187*z^54 - 29*z^53 + 422*z^52 - 421*z^51 + 149*z^50 + 236*z^49 + 149*z^48 - 232*z^47 - 336*z^46 - 278*z^45 - 155*z^44 + 135*z^43 - 393*z^42 - 31*z^41 + 358*z^40 + 51*z^39 - 6*z^38 - 47*z^37 + 345*z^36 + 66*z^35 + 243*z^34 - 263*z^33 + 76*z^32 - 120*z^31 - 85*z^30 + 120*z^29 + 99*z^28 - 288*z^27 + 209*z^26 + 178*z^25 + 32*z^24 - 368*z^23 + 148*z^22 - 262*z^21 + 141*z^20 - 357*z^19 + 94*z^18 - 207*z^17 + 205*z^16 + 27*z^15 + 25*z^14 + 62*z^13 - 250*z^12 - 234*z^11 - 36*z^10 + 101*z^9 + 520*z^8 + 200*z^7 - 279*z^6 - 60*z^5 + 369*z^4 - 81*z^3 + 133*z^2 - 330*z + 227]
enc = 0c8850f11526011aad008ba5fdb4335ea1985d2212bd017fd00dce2eae58b1fb46a65644768718d34bd67c921eb278e419c025b7f0ffbb6b24123946908dd4cb
```
### Solution
- Khi đọc source và output bài này mình đã quá sốc vì có quá nhiều kiến thức mới. Tóm tắt lại thì chall này đặt chúng ta vào trường `Cyclotomic Field` với thương số `q`. Sau đó chall gen ra ma trận `A`, secret vector `s`, noise vector `e` và vector kết quả `b = s*A + e`, đây chính là mô hình LWE điển hình. Bên cạnh đó còn một ma trận `H` cùng cỡ với `A`, tính `l = s*H` và hint `l2 = matrix([l[0,0] , OK(l[0,1].list()[:-h])])`.
- Tên challenge đưa chúng ta tới một docs được đăng tải năm 2023, về việc sử dụng LLL để giải mã LWE: [Too many hints](https://eprint.iacr.org/2023/777.pdf)
- Về các định nghĩa và kiến thức nêu trong tài liệu trên là rất nhiều, mình đã mất khoảng 1 ngày chỉ để hiểu tương đối nó. Tóm lại, vấn đề đặt ra trong chall này là `LWE: Perfect Hints`, nằm trong mục `4. Integrating Perfect Hints` của doc.
- Lời giải:
#### Extract data from output file:
- Do ma trận và trường được sử dụng trong tài liệu là `ZZ`, trong khi chúng ta đang ở `CyclotomicField` nên cần đưa tất cả các `output` về đúng trường.
- Code:
```python=
def get(data):
data = data.split("= ")[1].replace("^", "**")
return eval(data)
def from_poly_to_mat(m):
m = [[coef.matrix() for coef in row] for row in m.rows()]
return block_matrix(ZZ, m)
def from_poly_to_vec(v):
v = v[0].list() + v[1].list()
return vector(v)
gets = open("output.txt", "r").readlines()
A = from_poly_to_mat(A_temp)
b = from_poly_to_vec(b_temp)
H = from_poly_to_mat(matrix(K, k, k, get(gets[2])))
l2 = from_poly_to_vec(vector(K, k, get(gets[3])))
```
#### Building lattices:
- Chúng ta đang tham khảo tài liệu ở mục `4` nên đầu tiên cần xây dựng một ma trận `B (Hint Lattice)` như sau:
:::info
:bulb:
Ở đây chúng ta có:
- `q` là thương số đã cho
- `A` và `b` đã cho
- `Im` và `In` là các ma trận đơn vị cỡ `m` và `n`, trong chall này thì m = n = 256 (chính là size của ma trận `A`)
- `V` và `l` lần lượt là ma trận `H` và `l2` đã được extract ở trên
:::
- Vậy lattice `B` sẽ có dim là `m+n+1 = 513`, code:
```python=
B = []
B.append([q*I, 0*I, transpose(matrix([0] * 256))])
V = H[:, :-h]
B.append([A, V.augment(I[:, -h:]), transpose(matrix([0] * 256))])
B.append([matrix(b), matrix(l2), matrix([1])])
B = block_matrix(ZZ, B)
assert B.nrows() == B.ncols() == 513
```
- Lưu ý, các kí hiệu trong chall khá khác so với document: `V` và `l` trong doc là `H` và `l2` trong chall.
#### Construct Sublattice and Reducing:
- Chúng ta sẽ áp dụng thuật toán được gợi ý trong doc như sau:
- Tóm lại mình sẽ tạm gọi phần `(V, l)` (theo doc) hay `(H, l2)` (theo chall) là `H_right`, chúng ta cần `Construct sublattice` này với số `c` là `scaling parameter` quan trọng tính bằng công thức:
:::info
:bulb:
Trong đó
- `n, m, k` thỏa `n = m = 256`, `k = 2`
- `detL(v1, . . . , vk)` là định thức của lattice, được tính theo công thức:
:::
- Thực hiện đúng theo thuật toán, chúng ta có code:
```python=
# Construct Sublattice
H_left = B[256:513, 256:-32]
# Scaling Param
c = sqrt( (n+m+1-k) / (2*pi*exp(1)) )
c *= ( sqrt( det(H_left.T*H_left) ) ) ** (1 / (n+m+1-k))
c *= 2^((n+m+1)/2)
H_right = B[n:, n:]
H_right[:, :k] *= ceil(c)
```
#### LLL and Recovering:
- Chúng ta có một lưu ý quan trọng ở đây
- Thực hiện theo guide thui:
```python=
# Lattice then LLL
print("LLL...")
res, tmp = H_right.LLL(transformation=1)
print("LLL done...")
# Solve 2 parts of s using l2 and H -> Recover s
ss = -res[0]
ss01 = ss[-h-1:-1]
tmp_mat = H[:-h, :-h]
tmp_vec = (l2 - ss[:-1]*H)[:-h]
ss00 = tmp_mat.solve_left(tmp_vec)
ss = vector(list(ss00) + list(ss01))
s = vector([K(list(ss[:n//2])),K(list(ss[n//2:]))])
# Recover e
ee = (b_temp - s*A_temp)
e = ee.change_ring(OKq)
```
- Phần `ss` kia mình đã đọc trong doc nhưng không hiểu lắm về ý tưởng nên phải check lại rất nhiều với file `Test` của mình để recover lại vector `s` và `e` :crying_cat_face:, but finally it's done. Có vẻ như nó ở phần này:
#### Decoding:
- Code:
```python=
key = sha256(str(matrix(s)).encode()).digest()[:16]
iv = sha256(str(matrix(e)).encode()).digest()[:16]
cipher= AES.new(key,AES.MODE_CBC,iv=iv)
enc = bytes.fromhex(gets[-1].split("= ")[1])
flag = unpad(cipher.decrypt(enc),16).decode()
print(flag)
```
- Vậy là xong, chúng ta lấy được `flag`
### Flag
> ~~`CSCTF{wh4t_1f_my_h1nt_i5_4lgbr4!c????0x54763498142}`~~
### Note
- Full script:
```python=
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
# From challenge
q = 3329
k = 2
n = 256
h = 32
K = CyclotomicField(n, "z")
OK = K.OK()
OKq = OK.quotient(q, "y")
z = K.gen()
def get(data):
data = data.split("= ")[1].replace("^", "**")
return eval(data)
def from_poly_to_mat(m):
m = [[coef.matrix() for coef in row] for row in m.rows()]
return block_matrix(ZZ, m)
def from_poly_to_vec(v):
v = v[0].list() + v[1].list()
return vector(v)
# Import data then save two values of A and b for computing later
gets = open("output.txt", "r").readlines()
A_temp = matrix(K, k, k, get(gets[0]))
b_temp = vector(K, k, get(gets[1]))
A = from_poly_to_mat(A_temp)
b = from_poly_to_vec(b_temp)
H = from_poly_to_mat(matrix(K, k, k, get(gets[2])))
l2 = from_poly_to_vec(vector(K, k, get(gets[3])))
assert A.nrows() == A.ncols() == n
m = n
I = identity_matrix(n)
# Block Matrix from document
B = []
B.append([q*I, 0*I, transpose(matrix([0] * 256))])
V = H[:, :-h]
B.append([A, V.augment(I[:, -h:]), transpose(matrix([0] * 256))])
B.append([matrix(b), matrix(l2), matrix([1])])
B = block_matrix(ZZ, B)
assert B.nrows() == B.ncols() == 513
# Construct Sublattice
H_left = B[256:513, 256:-32]
# Scaling Param
c = sqrt( (n+m+1-k) / (2*pi*exp(1)) )
c *= ( sqrt( det(H_left.T*H_left) ) ) ** (1 / (n+m+1-k))
c *= 2^((n+m+1)/2)
H_right = B[n:, n:]
H_right[:, :k] *= ceil(c)
# Lattice then LLL
print("LLL...")
res, tmp = H_right.LLL(transformation=1)
print("LLL done...")
# Solve 2 parts of s using l2 and H -> Recover s
ss = -res[0]
ss01 = ss[-h-1:-1]
tmp_mat = H[:-h, :-h]
tmp_vec = (l2 - ss[:-1]*H)[:-h]
ss00 = tmp_mat.solve_left(tmp_vec)
ss = vector(list(ss00) + list(ss01))
s = vector([K(list(ss[:n//2])),K(list(ss[n//2:]))])
# Recover e
ee = (b_temp - s*A_temp)
e = ee.change_ring(OKq)
# Have double checked that using my "Test_output" so don't worry about that
key = sha256(str(matrix(s)).encode()).digest()[:16]
iv = sha256(str(matrix(e)).encode()).digest()[:16]
cipher= AES.new(key,AES.MODE_CBC,iv=iv)
enc = bytes.fromhex(gets[-1].split("= ")[1])
flag = unpad(cipher.decrypt(enc),16).decode()
print(flag)
```
Sign in with Wallet
Connect another wallet