secret^2

This page covers a writeup as detailed as I can go into the process of solving "secret^2"

secret^2 was part of l3ak CTF 2025s great set of crypto challenges, so before we get going, kudos to the writing team, you guys did great work.

Handouts

You're given this sage script:

from Crypto.Util.number import bytes_to_long as b2l

secret_1 = Integer(b2l(b'<Redacted 1>'))
secret_2 = Integer(b2l(b'<Redacted 2>'))

assert secret_1.nbits() == 271
assert secret_2.nbits() == 247

real_secret = Mod(secret_1,  2^1337 + 1337)/secret_2 + 1337^1337
not_secret_anymore = hex(real_secret^2)
print(not_secret_anymore)

# assert flag  == b"L3AK{" + secret_1 + secret_2 + b"}"
# 0xaf67951fc756caf05e1cb834854880fa6b3919aa390a42a3f2cdcc1943b959192cebea290e4bbe41b517056b95903e9f6ec10d490fdde72cf17a7ab3e65d61fc9c0a750dc20d52626f78c7200744fb9bcc0e7b9f33dd5a83df5d05de7258404b5c56ced4b57e63ab0c7c4761ce76d789734d705e8e137a2000c678c5b90b1df6169499ef39184622d4f83a03985ba8038fdb05aae52d5f2c04f8b8f7a4ac2a54b3d0be67c71752

Analysis & Solver

What happens is the following:

1. The flag is sliced into 2 main parts, lets call them s1 and s2 , where s1 is 271 bits in size and s2 is 247.

2. real_secret or we can call it r is computed as follows: $r \equiv \frac {s1} {s2} + 1337^{1337} \pmod {2^{1337} + 1337}$

3. Then not_secret_anymore or nsr is computed by squaring r (under the same ring of course).

So, the intuitive way of solving it is by taking the root of nsr under our ring and do some rational reconstruction to retrieve s1 and s2 thus retrieving the flag.

But of course not, because we're dealing with a 1337 bit composite modulus, so taking the root under this ring is just as hard as factorizing it :)

Next, I thought of a coppersmith approach, what if I build a polynomial:

$$f(x) = (x + 1337^{1337} )^2 - nsr \mod {2^{1337} + 1337}$$

and solve for small root x and do rational reconstruction, valid method right? Not really.

Because "x" in this case is s1/s2 mod a huge modulus we're actually dealing with a 1333 (approximately) bit long number, which is NOT a "small root" whatsoever :))

So I evolved my approach from univariate to bivariate coppersmith method, with this polynomial:

$$f(x,y) = (x + y1337^{1337}y)^2 - nsr\times y^2 \mod {2^{1337} + 1337}$$

Now, we have a valid "coppersmith-able" polynomial.

We got rid of the fraction by multiplying the whole thing with y^2, in order to make it a polynomial :)

This is it for the math!

All you need now is use cuso 's implementation: https://github.com/keeganryan/cuso as it's the best bivariate implementation out there as of now.

from sage.all import *
import cuso
from Crypto.Util.number import long_to_bytes as l2b


p = Integer(2**1337 + 1337)
s = int("0xaf67951fc756caf05e1cb834854880fa6b3919aa390a42a3f2cdcc1943b959192cebea290e4bbe41b517056b95903e9f6ec10d490fdde72cf17a7ab3e65d61fc9c0a750dc20d52626f78c7200744fb9bcc0e7b9f33dd5a83df5d05de7258404b5c56ced4b57e63ab0c7c4761ce76d789734d705e8e137a2000c678c5b90b1df6169499ef39184622d4f83a03985ba8038fdb05aae52d5f2c04f8b8f7a4ac2a54b3d0be67c71752", 16)          

PR = PolynomialRing(ZZ	, ['s1', 's2'])
s1, s2 = PR.gens()

c  = pow(1337, 1337, p)                  

f  = (s1 + c*s2)**2 - s * s2**2          

roots = cuso.find_small_roots(f, {s1: (0, 2**271), s2: (0, 2**247)})
print(roots)
roots = roots[0]
s2, s1 = roots[s2], roots[s1]
flag = "l3ak{" + (l2b(s1) + l2b(s2)).decode() + "}"
print(flag)

# l3ak{Squ4R1ng_mY_s3cr3t_w4Snt_5m4rT_b1Vari4Te_p0lyN0MiaLs_4r3_s0Lvabl3}

It's a simple challenge, a nice way to showcase bivariate coppersmith, kudos to the writer!