L3akCTF2025

Last weekend, I participated in L3akCTF2025 and solved some Crypto challenges ,and those are my writeups for most of the challenges I solved(and upsolved).

Crypto/Dumber

Challenge Overview

• Category: Crypto
• Name : Dumber
• Points: 50 (147 solves)
• Description: Don’t try to outsmart me buddy.

TL;DR

In this challenge, we’re given two elliptic curve points derived by multiplying parts of the flag (converted to integers) with random points on a hidden elliptic curve. Our job is to recover the modulus and curve coefficients, then perform discrete logarithms to extract the flag.

Initial Analysis

• We’re provided a Python file chall.py that generates two elliptic curve points

from Crypto.Util.number import  bytes_to_long, long_to_bytes
from sage.all import *
a,b,p = REDACTED,REDACTED,REDACTED
pt1="L3AK{REDACTED"
pt2="REDACTED}"
E = EllipticCurve(Zmod(p), [a, b])
p,q=E.random_element(),E.random_element()
u=bytes_to_long(pt1.encode())*p
v=bytes_to_long(pt2.encode())*q
# I will help u <3
print(p,u,q,v)

• So we have u = pt1 * p and v = pt2 * q where pt1 and pt2 are halfs of the flag, and p,q are random elliptic curve points on a hidden curve E over a finite field of an uknown prime.

• We’re also provided the output.txt that contains the printed values.

(103905521866731574234430443362297034336 : 116589269353056499566212456950780999584 : 1) 

(171660318017081135625337806416866746485 : 122407097490400018041253306369079974706 : 1) 

(161940138185633513360673631821653803879 : 167867902631659599239485617419980253311 : 1) 

(95406403280474692216804281695624776780 : 109560844064302254814641159241201048462 : 1)

Task Analysis

Given

• Coordinates of 4 points supposedly lying on an unknown elliptic curve over a finite field.
• Two of them are the result of scalar multiplication: u = pt1 × p, v = pt2 × q.

Goal

• Recover a,b and the prime.
• Solve the dlp to get the two parts of the flag and decode them into bytes to get the flag.

The Attack

1. Recover the modulus

• we all know that elliptic curves over finite fields satisfy the equation: y^2 ≡ x^3 + ax + b [p].
• given that p and q lies on the curve then y^2 - x^3 ≡ ax + b [p]for any point on the curve.
• so now lets take three points and compute ri = yi^2 - xi ^3, so we’ll have :
  • r1 ≡ ax1 + b [p]
  • r2 ≡ ax2 + b [p]
  • r3 ≡ ax3 + b [p]
• lets substract equations r1-r2 and r2-r3:
  • r1 - r2 ≡ a(x1 - x2) [p]
  • r2 - r3 ≡ a(x2 - x3) [p]
• then we’ll have (r₁ - r₂)/(x₁ - x₂) ≡ a [p], so in theory, this gives us a, but we don’t yet know p, so we can’t do this directly. However, if we build certain expressions from these ri they must vanish modulo p.
• To get rid of both a and b, we construct the following expression : xi * (rj - rk) + xj * (rk - ri) + xk * (ri - rj) ≡ 0 [p]
• if we do this for two or more points we can calculate their pgcd and get p.

2. Recover Curve Coefficients a and b

• with p known, plug in the coordinates of two points into the elliptic curve equation to form two equations:
  • r1 = y1^2 - x1^3 ≡ a*x1 + b [p]
  • r2 = y2^2 - x2^3 ≡ a*x2 + b [p]
• Solving this simple linear system gives a and b, such as :
  • a = ((r1 - r2) * ((x1 - x2)^(-1) % p)) % p
  • b = (r1 - a * x1) % p

3. Rebuild the Curve and Points

• With p, a, b known, reconstruct the elliptic curve over GF(p) and re-create the points p,u,v,q E = EllipticCurve(GF(p), [a, b])

4. Solve the Discrete Logarithm Problem

Using sagemath’s .log() is enough to solve the ecdlp cuz the group order is small enough. So :

• pt1 = u.log(p)
• pt2 = v.log(q)

Conclusion

Here is the full solve script :

from Crypto.Util.number import long_to_bytes
from sage.all import *


coords = [
    (103905521866731574234430443362297034336, 116589269353056499566212456950780999584),
    (171660318017081135625337806416866746485, 122407097490400018041253306369079974706),
    (161940138185633513360673631821653803879, 167867902631659599239485617419980253311),
    (95406403280474692216804281695624776780, 109560844064302254814641159241201048462)
]
def expr(i, j, k):
    xi, yi = coords[i]
    xj, yj = coords[j]
    xk, yk = coords[k]
    ri = yi**2 - xi**3
    rj = yj**2 - xj**3
    rk = yk**2 - xk**3
    return xi*(rj - rk) + xj*(rk - ri) + xk*(ri - rj)




exprs = [abs(expr(i, j, k))
        for i in range(len(coords))
        for j in range(i+1, len(coords))
        for k in range(j+1, len(coords))]


p_mod = exprs[0]
for d in exprs[1:]:
    p_mod = gcd(p_mod, d)


x1, y1 = coords[0]
x2, y2 = coords[1]

r1 = (y1**2 - x1**3) % p_mod
r2 = (y2**2 - x2**3) % p_mod

a = ((r1 - r2) * inverse_mod(x1 - x2, p_mod)) % p_mod

b = (r1 - a * x1) % p_mod

E = EllipticCurve(GF(p_mod), [a, b])

p = E(coords[0])
u = E(coords[1])
q = E(coords[2])
v = E(coords[3])


pt1 = u.log(p)
pt2 = v.log(q)
flag = long_to_bytes(pt1) + long_to_bytes(pt2)
print(flag)

Finally “Dumber” is anything but dumb.

Crypto/Secret²

Challenge Overview

• Category: Crypto
• Name : Secret²
• Points: 465 (28 solves)
• Description: Two secrets lie intertwined inside a strange equation. Can you unravel this mathematical mystery and find the truth hidden within?

TL;DR

The challenge hides two secret integers within a modular arithmetic expression. Given only the square of their relationship, we model the problem algebraically and use Coppersmith’s method on a cleverly constructed bivariate polynomial to recover both secrets. Flag obtained by decoding the two integers.

Initial Analysis

We’re provided this code :

from Crypto.Util.number import bytes_to_long as b2l
from sage.all import *

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,pow(2,1337) + 1337)/secret_2 + pow(1337,1337)
not_secret_anymore = hex(pow(real_secret,2))
print(not_secret_anymore)

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

Let’s denote :

• s1 = secret_1
• s2 = secret_2
• p = 2^1337 + 1337
• c = 1337^1337
• k = (s1/s2 + c)^2 mod p (this is what its given)

We know s1 and s2 are reasonably small assert secret_1.nbits() == 271 so s1 < 2^271 and assert secret_2.nbits() == 247so s2 < 2^247 hich hints at the feasibility of Coppersmith’s attack.

So essentially we’re told :

• (s1/s2 + c)^2 ≡ k mod p Our goal is to recover s1 and s2 from k and p

Task Analysis

We are working in modular arithmetic, and the expression involves a fraction: (s1 / s2 + c)^2 ≡ k [p] Multiply both sides by s2^2 to eliminate the denominator: (s1 + c * s2)^2 ≡ k * s2^2 [p] Bring everything to one side: (s1 + c*s2)^2 - k*s2^2 ≡ 0 [p] This becomes our polynomial equation: f(s1, s2) = (s1 + c*s2)^2 - k*s2^2 ≡ 0 [p] This is a bivariate modular equation over a large modulus, and we are looking for small integer roots (s1, s2). That’s a textbook case for Coppersmith’s method for bivariate modular equations.

The Attack

1. Express as a polynomial

PR.<x, y> = PolynomialRing(Zmod(p), 2)
f = (x + c * y)^2 - k * y^2

This is our target f(x, y) = 0 [p]

2. Apply Coppersmith’s Bivariate Attack

The modulus is too big to be factored so we can’t just take a modular square root. Basically the trick is like bivariate coppersmith, but using polynomial gcd instead of something like jacobian-newton or groebner for the root solving! Coppersmith’s method can find small solutions (x₀, y₀) to f(x, y) ≡ 0 [p], given:

• f(x, y) is a bivariate polynomial
• x₀ < X, y₀ < Y (bounds)
• modulus p is known

So we run : H = multivariate_shift_polynomials(f, bounds=(2^271, 2^247), m=2, d=1)

This constructs a lattice of shifted polynomials based on f, m, and d, performs LLL reduction, and attempts to extract a polynomial with small integer roots.

3. Root Extraction

Once the lattice is reduced, we try to extract g(x, y) that vanishes at the true (s1, s2): g = gcd(H[1][1], H[1][0]) The GCD of reduced polynomials in the basis often reveals a factorized form: g(x, y) = (x - s1)(y - s2) or similar So if we print g it will look like : 172173800672395117345249995446056910949109406728104215721153693572084689971*x - 2473487831244918725787012641969681114920403880867347529915152738869122001520439638*y So (x,y)=2473487831244918725787012641969681114920403880867347529915152738869122001520439638 ,172173800672395117345249995446056910949109406728104215721153693572084689971 Is a root for g.

Conclusion

Here is the full solve script written in sage :

from Crypto.Util.number import long_to_bytes
load('https://raw.githubusercontent.com/Connor-McCartney/coppersmith/main/coppersmith.sage')
p = 2**1337 + 1337
c = 1337**1337
secretoustnin = "0xaf67951fc756caf05e1cb834854880fa6b3919aa390a42a3f2cdcc1943b959192cebea290e4bbe41b517056b95903e9f6ec10d490fdde72cf17a7ab3e65d61fc9c0a750dc20d52626f78c7200744fb9bcc0e7b9f33dd5a83df5d05de7258404b5c56ced4b57e63ab0c7c4761ce76d789734d705e8e137a2000c678c5b90b1df6169499ef39184622d4f83a03985ba8038fdb05aae52d5f2c04f8b8f7a4ac2a54b3d0be67c71752"
k = int(secretoustnin, 16)

PR.<x, y> = PolynomialRing(Zmod(p), 2)

f = (x + c * y)^2 - k * y^2

H = multivariate_shift_polynomials(f, bounds=(2**271, 2**247), m=2, d=1)


g = gcd(H[1][1], H[1][0])
print(g)
parts = g.coefficients()
flag = "L3AK{"
for part in parts[::-1]:
    flag+=long_to_bytes(abs(part)).decode()

flag +="}"
print(flag)

It’s a realistic case of cryptanalysis that applies serious mathematical tools like lattices and polynomial rings — and shows how clever modeling can defeat strong-looking obfuscation,it was so fun and I learned a lot from it.

Crypto/Basic LLL

Challenge Overview

• Category: Crypto
• Name: Basic LLL
• Points: 50 (508 solves)
• Description: Simple crypto is the best crypto.

TL;DR

The challenge hides a prime number p inside an equation of the form k = x*y + a*p, where x and y are small, but a and p are enormous (1024-bit). Because the x*y term is small compared to a*p, we can approximate p ≈ k / a. With this recovered, we break RSA and retrieve the flag.

Initial Analysis

The description “Simple crypto is the best crypto.” hint directly that the structure is mathematically straightforward.

We’re provided a sage script :

def generate():
    p = random_prime(2^1024, lbound=2^1023)
    x=randint(1,2^16)
    y=randint(1,2^256)
    a=randint(2^1023,2^1024)
    q=random_prime(2^1024)
    n=p*q
    return x,a,y,n,p

x,a,y,n,p = generate()
k = x * y + a * p
e=65537
print(f"x = {x}")
print(f"a = {a}")
print(f"n = {n}")
print(f"k = {k}")

m = b'L3AK{<Redacted>}'
flag = int.from_bytes(m, byteorder='big')
c= pow(flag, e, n)
print(f"c = {c}")

With all the values printed in the output.

So we’re given :

• A standard RSA modulus n = p * q
• A ciphertext c ≡ flag^e [n]
• The public exponent e = 0x10001
• And a side equation which will help us solve the challenge : k = x * y + a * p

So we must focus on k to break rsa and solve our challenge.

Task Analysis

Let’s isolate the vulnerability. We are told: k = x * y + a * p We know:

• k (given)
• a (given)
• x*y (is small compared to k*a)
• p is unknown (our goal)

If we rearrange : k = a * p + x * y Then divide both sides by a: k / a = p + (x * y) / a

Note: x*y ≈ 2^272, while a ≈ 2^1024 ⇒ (x*y)/a ≈ 2^-752 ≈ 0

So the fraction (x*y)/a is negligible: k / a ≈ p

This is the core vulnerability: we can recover p by computing ⌊k / a⌋.

The Attack

If we do : p = k // a

we get the true p, because the leftover part (x*y)/a is strictly less than 1.

This leaks one of the two RSA primes. With p, we can compute:

• q = n // p
• phi(n) = (p - 1) * (q - 1)
• d = pow(e,-1,phi)
• Then decrypt: flag = pow(c,d,n)

Conclusion

Here is the full solve script:

from Crypto.Util.number import long_to_bytes
n = 12909957208634846878337953184362917609451224905637563117148705894888627434882610771803126452504238664471840340722310690445704139825753660053450331966698205860077330083433391290469454571152366284661640391190008258576947840075212180965738595761925516686689797153224716140447515370184846067654512660266993573880775530634588475842083212670090415716860925772115834314563453955681012820960922892736520042799257599331942717963921797157341454739255402633419216921702659541513141028779948257696746810146033667942181244847983610429227387863821351416689099862418820999250005071861968501333899759899513283613946626413863922604073
k = 24474689179117620559916890529357882261493825442019850679598519081287156822984032786458479363048845076078220151760752906879055457682971398809768604333650029141164831566127754715775782823279839766009120238777348170982471623193652714921064243946655726118484337862412275391615166714375745390409664610412156281691721978732319253694004232933156865189917761521085635692596755802274763409871937618659197646864593743015558828475450200247766980008744319676783526158213931581034209356092026748307730083927225249093712227456855972520574747646873074625455900058136458828591335711677741591552501530047335481073272381631524755666119
c = 11185314040721202177044508537272244264288033276739579716599246665772965854249656943282002695659011960313245796587834222078633141747802754149848079632693280265262199729548775879612614113828267471629389698999657686858047585254549801752634049341009476489652456620836030696102393122618822021082792763848220677651608135328630551380537642144416978955966827336280510774254681264136102268730343853559751471313539810499170669215479225898738527316798768622089152851154959800113070358637984124299357803777453137311143202502153552192970732744885328421213081964363890280109214401691255867427694709196120824176729643585687319321473
a = 139534605978199350449870348663594126359773246906906418074945064315708552206952695156472923968554408862426942537522569163756593332601739006413404986641247624386522169136633429464195370373009454673819688653512479919153332504769835621608305089536245284458011218876474599059184828911301976396971466368457267831713
e = 0x10001


p = k // a
q = n // p

phi = (p-1)*(q-1)
d = pow(e,-1,phi)

m = pow(c,d,n)
print(long_to_bytes(m))

I think this was an unintended solution