# HTB University CTF 2023: Brains and Bytes

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](/pTtY4gtrQYuiex-cov2hJg) 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)} \\ 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 \\ ed_q &= l(p-1) + 1\end{aligned}$$

Rewrite it:

$$\begin{aligned}kp = k - 1 + ed_p \\ 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](https://en.wikipedia.org/wiki/Kerckhoffs%27s_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} \\ 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 $private\_key$ 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 calculate $G_{pub}.division\_point(2)$, 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) \\ 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 \\ 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

$$k = sig_0^e = {flag \over sha256(flag)} + {sha256(flag) \over c} + {c \over flag} \mod fd$$

with known $k$ and $c = sig_1^e \mod fd$, we can change it to the equation

$$k*c*flag*sha256(flag)= flag^2*c + sha256(flag)^2*flag + c^2*sha256(flag) \mod fd$$

Because `len(FLAG) < 64`, so $flag < 2^{64*8} = 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

$$g(x, y) = x^2c + y^2x + c^2y - kcxy \mod fd$$

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!}

| Column 1 | Column 2 | Column 3 |
| -------- | -------- | -------- |
| Text | Text | Text |