HTB University CTF 2023: Brains and Bytes
Table of Contents
I played HTB University CTF 2023 with my university team @Wanna.W1n and my team solved all crypto challenges. Here is my writeup for two challenges I solved: Mayday Mayday and Zombie Rolled
Mayday Mayday
After successfully obtaining the research papers by extracting the encryption key, a new obstacle arises. The essential information regarding potential cures, including formulas and test results, is shielded by another layer of encryption. Can you overcome this additional challenge to reveal the final formula, enabling you to initiate the cure creation process?
source.py
from Crypto.Util.number import getPrime, GCD, bytes_to_long
from secret import FLAG
from random import randint
class Crypto:
def __init__(self, bits):
self.bits = bits
self.alpha = 1/9
self.delta = 1/4
self.known = int(self.bits*self.delta)
def keygen(self):
while True:
p, q = [getPrime(self.bits//2) for _ in '__']
self.e = getPrime(int(self.bits*self.alpha))
φ = (p-1)*(q-1)
try:
dp = pow(self.e, -1, p-1)
dq = pow(self.e, -1, q-1)
self.n = p*q
break
except:
pass
return (self.n, self.e), (dp, dq)
def encrypt(self, m):
return pow(m, self.e, self.n)
rsa = Crypto(2048)
_, (dp, dq) = rsa.keygen()
m = bytes_to_long(FLAG)
c = rsa.encrypt(m)
with open('output.txt', 'w') as f:
f.write(f'N = 0x{rsa.n:x}\n')
f.write(f'e = 0x{rsa.e:x}\n')
f.write(f'c = 0x{c:x}\n')
f.write(f'dp = 0x{(dp >> (rsa.bits//2 - rsa.known)):x}\n')
f.write(f'dq = 0x{(dq >> (rsa.bits//2 - rsa.known)):x}\n')
output.txt
N = 0x78fb80151a498704541b888b9ca21b9f159a45069b99b04befcb0e0403178dc243a66492771f057b28262332caecc673a2c68fd63e7c850dc534a74c705f865841c0b5af1e0791b8b5cc55ad3b04e25f20dedc15c36db46c328a61f3a10872d47d9426584f410fde4c8c2ebfaccc8d6a6bd1c067e5e8d8f107b56bf86ac06cd8a20661af832019de6e00ae6be24a946fe229476541b04b9a808375739681efd1888e44d41196e396af66f91f992383955f5faef0fc1fc7b5175135ab3ed62867a84843c49bdf83d0497b255e35432b332705cd09f01670815ce167aa35f7a454f8b26b6d6fd9a0006194ad2f8f33160c13c08c81fe8f74e13e84e9cdf6566d2f
e = 0x4b3393c9fe2e50e0c76920e1f34e0c86417f9a9ef8b5a3fa41b381355
c = 0x17f2b5a46e4122ff819807a9d92b6225c483cf93c9804381098ecd6b81f4670e94d8930001b760f1d26bc7aa7dda48c9e12809d20b33fdb4c4dd9190b105b7dab42e932b99aaff54023873381e7387f1b2b18b355d4476b664d44c40413d82a10635fe6e7322543943aed2dcfbe49764b8da70edeb88d6f63ee47f025be5f2f38319611ab74cd5db6f90f60870ecbb57a884f821d873db06aadf0e61ff74cc7d4c8fc1e527dba9b205220c6707f750822c675c530f8ad6956e41ab80911da49c3d6a7d27e93c44ba5968f2f47a9c5a2694c9d6da245ceffe9cab66b6043774f446b1b08ee4739d3cc716b87c8225a84d3c4ea2fdf68143d09f062c880a870554
dp = 0x59a2219560ee56e7c35f310a4d101061aa61e0ae4eae7605eb63784209ad488b4ed161e780811edd61bf593e2d385beccfd255b459382d8a9029943781b540e7
dq = 0x39719131fbfd8afbc972ca005a430d080775bf1a5b3e8b789aba5c5110a31bd155ff13fba1019bb6cb7db887685e34ca7966a891bfad029b55b92c11201559e5
In this challenge, we are given 512 MSB of $d_p = d \mod p-1$ and $d_q = d \mod q-1$. This kind of challenge is similar to a challenge that i solved in BauhiniaCTF 2023 (this writeup is written in Vietnamese). I followed this and solved this challenge, and I will explain what i did.
Finding k, l
Let rewrite $d_p$ and $d_q$:
$$\begin{aligned}d_p &= d_p^{(M)} * 2^{512} + d_p^{(L)} \newline d_q &= d_q^{(M)} * 2^{512} + d_q^{(L)}\end{aligned}$$
Where $d_p^{(M)}, d_q^{(M)}$ is MSBs and $d_p^{(L)}, d_q^{(L)}$ is LSBs. We already have $d_p^{(M)}, d_q^{(M)}$, so our problem is finding LSBs
With $d_p$ and $d_q$, we have:
$$\begin{aligned}ed_p &= k(p-1) + 1 \newline ed_q &= l(p-1) + 1\end{aligned}$$
Rewrite it:
$$\begin{aligned}kp = k - 1 + ed_p \newline lq = l - 1 + ed_q\end{aligned}$$
Multiply $kp$ with $lq$ and we will have:
$$klN = (k - 1)(l - 1) + ed_p(l - 1) + ed_q(k - 1) + e^2d_pd_q \ (1)$$
Now, let
$$A = {2^{1024}e^2d_pd_q \over N}$$
And by Lemma 1 in the paper, we have $\lceil A \rceil = kl$
If we have $kl$, then equation $(1)$ become:
$$k+l = 1 - kl(N - 1) \mod e$$
Now we have $k + l$ and $kl$, and we can use Vieta’s formulas over $\mathbb{Z}_e$ to find $k$ and $l$
Factoring N
In previous part, we have two equations: $ed_p = k(p-1) + 1$ and $d_p = d_p^{(M)} * 2^{512} + d_p^{(L)}$
We already know $k$ and $d_p^{(M)}$, so we can combine two equations and get:
$$ed_p^{(L)} + ed_p^{(M)}*2^i + k - 1 = kp$$
This equation yields a polynomial $f(x) = x + a \mod kp$ where $a = (ed_p^{(M)}*2^i + k - 1)(e^-1 \mod kN)$. By using Coppersmith’s algorithm, we can get a small root $x_0 = d_p^{(L)}$ of $f(x)$. After that, we can factor $N$ by calculate $gcd(N, f(x_0))$
solve.sage
from Crypto.Util.number import *
from sage.all import *
N = ..
e = ..
c = ..
dp = ..
dq = ..
A = (2**1024*e**2*dp*dq)//N + 1
x = PolynomialRing(Zmod(e), 'x').gen()
f = x^2 - (1 - A*(N - 1))*x + A
k, l = [int(c[0]) for c in f.roots()]
x = PolynomialRing(Zmod(k*N), 'x').gen()
a = ((e*dp*2^512 + k - 1) * pow(e, -1, k * N)) % (k * N)
g = x + a
dp_low = int(g.small_roots(X=2**512, beta=0.5)[0])
kp = int(g(dp_low))
p = gcd(kp, N)
q = N // p
assert p * q == N
d = pow(e, -1, (p - 1)*(q - 1))
m = pow(c, d, N)
from Crypto.Util.number import *
print(long_to_bytes(int(m)))
flag: HTB{f4ct0r1ng_w1th_just_4_f3w_b1ts_0f_th3_CRT_3xp0n3nts!https://eprint.iacr.org/2022/271.pdf}
Zombie Rolled
With the formula now in your team’s possession, you face a significant challenge. The formula is constructed upon an exceedingly advanced equation that surpasses your current comprehension of mathematics. A note suggests a flaw, but the intricacies appear much too complex. It’s crucial for the equation to be genuinely secure and not break in edge cases. Can you analyze this complex equation to bring an end to this tragic situation once and for all?
source.py
from Crypto.Util.number import getPrime, bytes_to_long
from fractions import Fraction
from math import prod
from hashlib import sha256
from secrets import randbelow
# I hope no one cares about Kerckhoff's principle :)
from secret import derive_public_key, FLAG
def fraction_mod(f, n):
return f.numerator * pow(f.denominator, -1, n) % n
class PublicKey:
def __init__(self, pub):
self.pub = pub
self.f = self.magic(pub)
self.nb = (self.f.denominator.bit_length() + 7) // 8
def encrypt(self, m):
return pow(m, self.f.numerator, self.f.denominator)
def verify(self, m, sig):
s1, s2 = sig
h = bytes_to_long(sha256(m.to_bytes(self.nb, "big")).digest())
a, b = m, h
r = self.encrypt(s1)
c = self.encrypt(s2)
return fraction_mod(self.magic((a, b, c)), self.f.denominator) == r
@staticmethod
def magic(ar):
a, b, c = ar
return Fraction(a, b) + Fraction(b, c) + Fraction(c, a)
class PrivateKey(PublicKey):
def __init__(self, priv, pub):
super().__init__(pub)
if self.magic(priv) != self.f:
raise ValueError("Invalid key pair")
self.priv = priv
self.d = pow(self.f.numerator, -1, prod([x - 1 for x in priv]))
def decrypt(self, c):
return pow(c, self.d, self.f.denominator)
def sign(self, m):
h = bytes_to_long(sha256(m.to_bytes(self.nb, "big")).digest())
a, b = m, h
c = randbelow(1 << self.nb)
r = fraction_mod(self.magic((a, b, c)), self.f.denominator)
s1 = self.decrypt(r)
s2 = self.decrypt(c)
return s1, s2
@staticmethod
def generate(nbits):
while True:
try:
priv = tuple([getPrime(nbits) for _ in range(3)])
pub = derive_public_key(priv)
return PrivateKey(priv, pub)
except ValueError:
pass
def main():
assert len(FLAG) <= 64
m = bytes_to_long(FLAG)
key = PrivateKey.generate(1024)
data = f"pub = {key.pub}\n"
# make sure it really works
enc = key.encrypt(m)
assert key.decrypt(enc) == m
sig = key.sign(m)
assert key.verify(m, sig)
# mixing them :)
mix = [sig[0] + sig[1], sig[0] - sig[1]]
mix = [key.encrypt(x) for x in mix]
data += f"mix = {mix}"
with open("output.txt", "w") as f:
f.write(data)
if __name__ == "__main__":
main()
output.txt
pub = (-679149827688896546432684514781159016843208241259733038415608446794483893865137935606244643075224614588255514670703135466975466970913232919448971056463765967267932205245723609028669700790327888053737513173004906874791948794706164874163000233242663467112356684022940655151358257782991132383407917101800634477163967250047209128395271227452766580073122831277123102243705154267181506512402418039719173720827696442606604970528063168565779813124052546633103006687964589521475168208905582555230534709754318532234948569155566965251016769141273474050547777208930826949494111933369822606247918218189742785296490363879808413854798453415486721083351760540440727104905848109665720749305468099771944894375713469720303756620101486771358570935901473647573434771209918671576552610105681029288935780171889489032033021940200657122568137703155744190258342713712412791279147013204380608939099412456303268575877533613186703629403608506029153274825614231950222036769768440858686468414798013424323765200986740221652787739657510451377763752151261173701557996570807100005672113902309356835881522886670894124683065117547063607171455016275575226133973000898546626428525316423640294588059582425678225307973026140509236726222895277593502658123536454581741258241350319709620218946214665277722917625163484143287737560990362641167985157948128093478633332215687808673326510025966928820082371826010204772434810834908522239370003521927141674940923107924718589020116481655436804371698576313448620651274568714018039959665606305466508336068792512300330447079049391998121903628542300433666064229921580215835067999800174889123776199641564914760737600821953293714498453721075798275047009255942697608822458887368884228615671991262750899422262693397993810261279502497616420217291365257434988696383465213630804193810674969275499135895349396517300341694326130217329147937575188985044945549854453507141533817669145401648967346307076924815850188448842044898686784928539015228772201838211426957234107261809629639488140342429501192224120877838900600824055655563831019772958581350347081393942024086716044621385448218128870528968546874044728000006962970494893355352673283507468842799994294656025864551101856509528014985899203160260433154506345617010883888392862375738238905192516684056280710225432696655387350661830299769543107006018477779636761481812001885777307338070488998064732654317341303970152707374877928275562177058710127753099319277046999346991319018270073503529254012239006330090621492580837121246383935, -62076393535220713230211372773016154819776973272085279510651810925567779949353129946722665324346680014266486318715153201960740792449256110092242298637141869182191301801348471698842750492673269805386405258903922775271516275959471007270470783319809938344980989030858451767810558937769006054050097442784355926821230070379192555314422288851726919132047206078443630648828611342794053179031715333055698280449463491394083273880477510623203232349139229518535496279365263598613132079698328994631219260929529014155663831397189773051194410051588749692352737665469175569662944453505412436038259868251153299961933349760369897472364513246615362132669886696823052680175413762753451532554603896709930434997447861155715656069046149639262746319959746238179869888630675350046188185867904504017641487194302334327723755607524433514488406681046596968802669158589535873655500657057147028422069215178280598799698023523842357762349312690981167196137904038634376059163646848305423446194854985523208266633269733804799399607579721802215740994923964998077749276376011664190442983045021233328860583431325491398740404717916957583624416525249155775990424790364048060223994351310834002052812950138181225201366866314173709814344726454058400929651246654127831150461139153521780070432541564467256212600334416658092578286615407601260752708323965051595729545763555521745630970189873094019504197470499857463907805936270010647572788276449685684281797985033841971693243345694540270555091524839897049609610694927649006414175285808616559721550306026476105719357460921592355959150692653059587214522745084239909633381558412919917765258331958067109432311999676460754436818201240023311791169802096388297862219517745888298152485206376817292783209092101414045488990410966964411575840592166475524123368782667715013887175556663844953274929494297381264202051980047425186510319292378252632808136510156368067796082090881873863176619957188519245758562409606283750005034060349233190765189422774601110274372976258448740486162640303554541285690390642874100570657406690134508272681549727638076837266298852607372446728482637226932907561200761597573567176950238238261414346592107964949875193908993522612254840698757416962124520050724327233377985303460697496676181895430294259015494830416056429816116680627673230428123227550005209799526871524994673920145445281764352654447538983391735348123813851971146216997750793741632897137346289689048299843427272709114665386119324590006011517253390435055796456069897547662246663469050, 7830486145829508377558227408290134666403414818680891369176645894657730719560462345413647777035691365258303368067215176543275998927964954949936712360465415742305180023074796925974228987920346807337046972890048193675380148777690313974213732587383856306544481992804522271933234142582135631837143021763752036371144162337258022513117655962693146611295672219977744995976478481618309460588961678471875936477345228279163041888319063508894362501867902730894177063341454634424454782062634032617628985824505983759212857299828749995752235758280573881085074326788874659358083585790319249788052723728978677280818302159890013608215097544022503686764809254320162354127388898310054146477537454655331114752144580956313131601466170634129721047436217501010686515461442226299103956329529388095001070391385189826814864746360320333918929686149324974844514612649731799514398645742580625276435924292653289878873850265379360271050603859206438004883855432886650553014115919828422317294957226985270768975519537120458232477529774162488973095316791366021139626153997771391194348622350835846276300080551743631687665470499546808409919692234446116541139972549724015591941496221132694347053824568526998941915494190313922421141792712177850635304804853629529860738709134170021521102700328604628927875567294032063066171031633521264813050524393039049915547228949811888603458908961700972119089383547482638110428947454915597289453149684921808588155575892869551719408017163519505152564311034805403584244791464453674297092713220925531618514351406361895037695504970845118751396728421079695580995084470838685511076186640881628743480208128654755986540162228797182203097429878571055580982419910698271318560371375725624590383889293031827343721601921283218257563981664825233636121202430668321472633600201081855377049584327600961474706457007803948936824801776548939412019028877381656854352042881659133167174502453362966793813997989646037370005971535903722675701268453950616768210577721799262016472978512795971976360288455246627122308235526400041892494207712587655624310348101802715615388185255043745377008056152447575197765696754537890671347192620664952431667401070828663411172784617836559669320812607668877073449814900939924918858434664371233944816438544081459935797541138873496291375791704149531348074915907756350500006241339201669154574473335111528050064627331874217370202929428747238792910498913366471880111057711710182734506773946328772476941505432386559666283038340899500750365525879310436221464632932)
mix = [320097670159304209872309549471930993417143388077612479497520462342663934977666619462544724222917378443968580805422580825361629081490271425796180005007150747981294833573665302687843134857904098195466433204039058015530152552325684827139190765614362244643766711802006240778166882116884363374725459551909065104305033828828854239454604753713577854447476580313858442898211797176449603725270483947895282965175447381948570185109212852155846189091780576621552251326144055737198080348963003230356855332599698331598994549981281612662608348841085666739363070407550100107611043508427316142601784200258788876751333421411315222696828075445887895455540798110282831853710380354729703219505108629359197051336831375142595785378662848001960222878291497005997865756885831339332471275732796885611507451753622271015336628712225776167393560183733898486530850953580390452793438185371865569655507768389802668508433717577899938841236692983646823027361, 349362680724100439001784418744128033820777004106762219940030797663423035126842789961301765825984790980690057949860749399355278228450692377224412215897507215190015109832483673402204604232784701242900565985678019980900605960003183528535025133581067044874804468687010880739758605406077761031350401248992459970793003097988643424534679899913404629630391199540164124586883472387639995010304310446530364782969667797609685774685940403053235307671556459857310584515167273597080744839887558160920716970032955099943334650018552259294137522684003806871855045036984303040298988654317845297423677227040203951111165862748444474516781528350286768742283071330157900311167729282004019891879048809487509974878771126244472706852271120669147203065908414503160273025384004067262219422586521719641783916408458322110103608436662590492232330298616191719127365835397875038644290248233827642595125378514596518087399154247594983235918109876187387712452]
A challenge with weird encryption and signing method! In this challenge, the source code is mentioned to Kerckhoff’s principle, and we have everything except private_key. We are also given mix, which is the list contain encrypted sig[0] + sig[1] and sig[0] - sig[1], where sig[0], sig[1] is the result of signing flag
From an equation to an elliptic curve :astonished:
In this challenge, the $public\_key = (a_1, b_1, c_1)$ and $private\_key = (a_2, b_2, c_2)$ have a relationship
$$f = magic(a_1, b_1, c_1) = magic(a_2, b_2, c_2) = {fn \over fd}$$
where $$magic(a, b, c) = {a \over b} + {b \over c} + {c \over a}$$ With a strange equation, I try to google to have some ways to deal with it, after about one hours, I find this one: https://mathoverflow.net/questions/27107/transforming-a-diophantine-equation-to-an-elliptic-curve
It looks like a magic !
We will using the $public\_key$ and the result in the site. Let:
$$\begin{aligned}u &= 3*{f^2z - 12x \over z} \newline v &= 108*{2xy-fxz+z^2 \over z^2}\end{aligned}$$
Then $(u, v)$ is a rational point on the elliptic curve $(E_f): v^2 = u^3 + Au + B$ with $A = 27f(24 - f^3)$ and $B = 54(216 - 36f^3 + f^6)$
With this way, we can generate many tuples $(a_i, b_i, c_i)$ that satisfy $magic(a_i, b_i, c_i) = f$ and vice versa, with a tuple $(x, y, z)$ that satisfy the equation $magic(x, y, z) = f$, we can construct a point $G(u, v)$ that lying on $(E_f)$
Finding private key
With the relationship we have found, we will treat $privatekey$ as a point $G_{priv}$ in $(E_f)$. Because this challenge has a hidden function derive_public_key(), so I guess $G_{priv}$ generates the $public\_key$ as a point $G_{pub}$ by some method
If we read the code carefully, we will see that $0 < a_2, b_2, c_2 < 2^{1024}$, when $a_1, b_1, c_1 \approx 2^{8192}$, so we need to find a way to decrease the point $G_{pub}$. And surprisingly, SageMath has a magical method .division_point(). When we use that method to calculate $\frac{1}{2}G_{pub}$, we will have the point $G_{priv}!$
This part is a little bit confused, maybe because I solved this part with a guessy way.
Finding the signature
When we have $private_key$, we can find the signature
Reading the source code, we have
$$\begin{aligned}mix_0 &= key.encrypt(sig_0 + sig_1) \newline mix_1 &= key.encrypt(sig_0 - sig_1)\end{aligned}$$
where $$\begin{aligned}sig_0 &= \Big({flag \over sha256(flag)} + {sha256(flag) \over c} + {c \over flag}\Big)^d \newline sig_1 &= c^d\end{aligned}$$
and $d$ can calculate from $private_key$
(Remember $sig_0$ and $sig_1$ are in $GF(fd)$) Because we have $private_key$, we can decrypt $mix_0$ and $mix_1$ and get $sig_0$ and $sig_1$
Finding the flag
Because we can calculate $e$ from $public_key$, so by encrypt $sig_0$ and $sig_1$, we will have the equation
$$\begin{aligned}k = sig_0^e = {flag \over sha256(flag)} + {sha256(flag) \over c} + {c \over flag} \mod fd\end{aligned}$$
with known $k$ and $c = sig_1^e \mod fd$, we can change it to
$$\begin{aligned}k * c * flag * sha256(flag) = flag^2 * c + sha256(flag)^2 * flag + c^2 * sha256(flag) \mod fd\end{aligned}$$
Because len(FLAG) < 64, so $flag < 2^512$. We also have $sha256(flag) < 2^{256}$, when $fd = a_1 * b_1 * c_1 \approx 2^{3072}$, so we can use bivariate coppersmith with function
$$\begin{aligned}g(x, y) = x^2c + y^2x + c^2y - kcxy \mod fd\end{aligned}$$
to find roots $(x_0, y_0) = (flag, sha256(flag))$
The code, after all
solve.sage
from sage.all import *
from Crypto.Util.number import *
from fractions import Fraction
from math import prod
from hashlib import sha256
import itertools
#Step 1
pub = ()
x, y, z = pub
#f = magic(x, y, z)
f = QQ(3701525472893754239556659146967419294548810105088021761582278341178984148706714849495354572560649412946184663258088912346600083850901512993954559285104856171191192277217584795914461587554538912171921135802509605569817764285175424876824473380387225760087531693029912774720506196487387886048720092146542181664493995438130886554006434662910173182386189855173126151273965559205502505991343826706689240290992604129443515094557601688161362570936067972161997111669004650102495491760302561536310799959359506310468970488806518882801567577729407854267148259783351024268951798970899778594609519014411999199382407587199450660822086130822218329160084330279562341477826514749124374700145975627180419620707989403280355093770570604229574635834749773398475083608003053221351055125031829169474647676191591060731048302412840041136589207808630461233905329929617648945992105567023376117108474814613664279799015617517748741353656353240603055262833/1233228582347016947966224073972268144554236820892942499519122000771084166375804575410256498849474001839664438201612077539125732335938974180546116101865678145343967028533823514484007970750393340966594511217807050165719060909011954955474682851519212527228087532500877286327027558523551790732475822426937017444940866615592974442092482434411876518875851004346287404070582765235948489547282744947043755585727828924938737667298963460848381817651284299657969882102172228225806548854044352691115222585573695801350283013181198024885246537475115476935052466323229708374943236919527896588729386077465925760832854469559234925755079146251766439063105010673262343403050052003476148441220953810088244785797541039087544841861476346530581157709458126406121980561603659803563500884868073661022084810883103625906984936967388404739473783378705660995543572971451987404675428545121985331638196771442992280022247133820096024932788948323579723802871)
A = 27 * f * (24 - f**3)
B = 54 * (216 - 36 * f**3 + f**6)
mix = [..]
E = EllipticCurve(QQ, [A, B])
u = QQ((3 * f * f * z - 36 * x)/z)
v = QQ(108*(2 * x * y - f * x * z + z^2)/z^2)
P = E(u, v)
def find_abc(G):
u, v = G.xy()
x_z = QQ((3*n*n - u) / 36)
x = x_z.numerator()
z1 = x_z.denominator()
y_z = QQ((v / 108 + n * x_z - 1) / (2 * x_z))
y = y_z.numerator()
z2 = y_z.denominator()
if z1 != z2:
z = lcm(z1, z2)
x *= (z//z1)
y *= (z//z2)
else:
z = z1 = z2
return x, y, z
#Step 2
P = E(P.division_points(2)[0]) #Magic!
x, y, z = find_abc(P)
d = pow(f.numerator(), -1, (x - 1) * (y - 1) * (z - 1))
#Step 3
mix = [pow(c, d, f.denominator()) for c in mix]
sig0_dec = (mix[0] + mix[1])//2
sig1_dec = (mix[0] - mix[1])//2
sig0 = pow(sig0_dec, f.numerator(), f.denominator())
sig1 = pow(sig1_dec, f.numerator(), f.denominator())
#https://github.com/defund/coppersmith/blob/master/coppersmith.sage
#With a little change
def defund_multivariate(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
#f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m+1):
base = N^(m-i) * f^i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1/factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B*monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
#Step 4
c = sig1
F.<m, h> = PolynomialRing(Zmod(f.denominator()), 2)
g = m^2*c + h^2*m + c^2*h - c * sig0 * h * m
flag_hash = defund_multivariate(g, (2^(64*8), 2^256), m = 3, d = 4)[1]
print(long_to_bytes(int(flag_hash[0])).decode())
flag: HTB{4_s3cur3_crypt0syst3m_sh0u1d_n0t_c0nt41n_s3cr3t_c0mp0n3nts!}