Trendy Windy Trigonity (CSCTF 2024)

LLL

Challenge overview

In this CTF challenge, we are given the following encryption script:

from Crypto.Util.number import bytes_to_long
flag = REDACTED 
print(len(flag)) 
R = RealField(1000)
a = bytes_to_long(flag[:len(flag)//2])
b = bytes_to_long(flag[len(flag)//2:])
x = R(0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557302303874143106908193100)

enc = a*cos(x)+b*sin(x) 

#38
#2.78332652222000091147933689155414792020338527644698903976732528036823470890155538913578083110732846416012108159157421703264608723649277363079905992717518852564589901390988865009495918051490722972227485851595410047572144567706501150041757189923387228097603575500648300998275877439215112961273516978501e45

The flag is split into two parts and converted to two integer values, $a$ and $b$. The script also defines a value $x = 0.7587\dots$ The flag is then encrypted as:

\[\large a \cdot \cos(x) + b \cdot \sin(x) = 2.7833 \dots\]

Recovering the flag

We must solve for the two unknowns $a$ and $b$. We can first get the actual values for $\cos(x)$ and $\sin(x)$, and then scale them by $10^{300}$ to eliminate the decimals. That way, we can work with whole numbers instead:

sin_x = int(R(sin(x))*10^300)
cos_x = int(R(cos(x))*10^300)
enc =  int(enc*10^300)

From here, we can rearrange:

\[\large a \cdot \cos(x) + b \cdot \sin(x) - enc \approx 0\]

We can encode our values in a matrix:

\[\large M = \begin{bmatrix} \cos(x) & 1 & 0 & 0 \\ sin(x) & 0 & 1 & 0 \\ -enc & 0 & 0 & 1\\ \end{bmatrix}\]

Since we have scaled up our known values, we can recover $a$ and $b$ using lattice reduction. After LLL, this will leave us with a short vector in the form of:

\[\large (a \cdot cos(x) + b \cdot sin(y) - enc, a, b, 1)\]

We can construct the matrix basis in SageMath like so:

M = Matrix(ZZ, [
    [cos_x, 1, 0, 0],
    [sin_x, 0, 1, 0],
    [-enc,  0, 0, 1],
]).LLL()

From here, we can look at the reduced basis and quickly see that the first row is the shortest vector:

sage: M[0]
(-15072279561902375628763173372008305345187322476795529354825338687, 1501403158973585406817603354497647816859742771, 2461834501240441634675537458806974655348946301, 1)
sage: M[1]
(-7391861668707603282709231218455828032078905961290926586835454990586821475776990031713155846459308562947919441185021868660, 314542509734288297909903500277415340854483533948710727152673295447868841674323466027269529700099155554576091659555786257701301206449266229145, -237086336634781754726112897494132806473786182003092834756129311769494361699763840138472843167059944437722442955730943096407833119784484329152, 23407755087802489987290113835273172227532540875462199393589430593743547685435037491405562141068)
sage: M[2]
(-86008852239251166992557883620519450679508029675304176608461890794439175296151101648277914048866131761611633684294863025010, -420585066010882796869527410081839280633711977689303381295676996668959509593195217532891886055288288371553908082547486869056528984111179693625, -270075717391839377414210661342525817119151716931995218589666935717661694079295386742694420894381612443933488654685346824874968393331572139174, -176420250365570679868485640927550795943793938088366342014101624636616969734670056934980489248661)

From the source code, we know the flag is 38 bytes long, meaning $a$ and $b$ are around 19 bytes each. This equates to 152 bits. In fact, since the flag consists of ascii characters, the first bit will be 0, meaning we actually have 151 bits for each. This fits well with the results of the LLL:

sage: M[0,1].nbits()
151
sage: M[0,2].nbits()
151

We can then reconstruct the flag by converting each half from long to bytes:

a = int(M[0, 1])
b = int(M[0, 2])
print(bytes.fromhex(f"{a:x}{b:x}"))

This gives us our flag: CSCTF{Trigo_453_Tr3ndy_FuN_Th35e_D4Y5}

Solve.sage

R = RealField(1000)
enc = R("2.78332652222000091147933689155414792020338527644698903976732528036823470890155538913578083110732846416012108159157421703264608723649277363079905992717518852564589901390988865009495918051490722972227485851595410047572144567706501150041757189923387228097603575500648300998275877439215112961273516978501e45")
x   = R("0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557300303874143106908193100")

sin_x = int(R(sin(x))*10^300)
cos_x = int(R(cos(x))*10^300)
enc =  int(enc*10^300)

M = Matrix(ZZ, [
    [cos_x, 1, 0, 0],
    [sin_x, 0, 1, 0],
    [-enc,  0, 0, 1],
]).LLL()

a = int(M[0, 1])
b = int(M[0, 2])
print(bytes.fromhex(f"{a:x}{b:x}"))