Cybersec Crypto

[Crypto] Bivariate Copper Writeup

2025 HKCERT Crypto Writeup

HKCert 2025 crypto/Bivariate copper Writeup

0x00 Attachment

chall.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# chall.py
from Crypto.Util.number import *
from secret import *

with open("message", "r") as f:
    message = f.read().strip().encode()

m = bytes_to_long(flag)
message = bytes_to_long(message)

p = getPrime(1024)
q = getPrime(25)
N = p * q
e = 65537

c = pow(message, e, N)
r1, r2 = getPrime(512), getPrime(512)
k = getPrime(64)

t1 = (k * inverse(m + r1, p)) % p
t2 = (k * inverse(m + r2, p)) % p

leak1 = t1 >> 244
leak2 = t2 >> 244

print(f'{e = }')
print(f'{N = }')
print(f'{c = }')

print(f'{k = }')
print(f'{r1 = }')
print(f'{r2 = }')
print(f'{leak1 = }')
print(f'{leak2 = }')

'''
e = 65537
N = 3333577291839009732612693330613476891341287017491683764014849337158389717338712200133085615150269196268856288361865352673921704626130772582853528604556994221890454520933132803888321775335519781063447756692130742361931522856942232406992357982482263472763363458621836220024977864980600979194500121897419553619426163227
c = 1277272201928931051067525742142583320131498687502905469530557519241347169899260720694873154669476372724906606385788056536109971768256973988460766527896895880291037980646963981472637862512247195798266373251524526460097881602691641026093728861572872156172787168597410496150253340538386296663073088345799201197096884740
k = 9352039867057736323
r1 = 10421792656200324147964684790160875926436411483496860422433732508593789212449544620816674407170998779863336939494663076247759140488927744939619406024905901
r2 = 8806088830734144089522276896226392806947836111998696180055727048752624989402057411311728398322297424598954586424896296000606209022432442660527640463521679
leak1 = 4266222222502644630611545246271868348722888987303187402827005454059765428769160822475080050046035916876078546634293907218937483241284454918367519709206766322037148585465519188582916280829212776096606923824120883699251868362915920299645
leak2 = 1176921186497191878459783787148403806360469809421921990427675048480656171919274113895695842508460760829511824635106692634456334400022597605585661597793889066395539405395254174368285751236344600489419240628821864912762242188289636510706
'''

0x01 Basic Information

From chall.py (as implied by your parameters), the server generates:

  • A large RSA modulus: N = p*q

  • q is small (25 bits) (this is crucial)

  • A prime p is large (≈ 1024 bits)

  • Some secret “flag integer” m

  • Random offsets r1, r2 (known)

  • A secret multiplier k (known)

  • Two “leaks” leak1, leak2 derived from values t1, t2:

    • t1 = k * inverse(m + r1, p) mod p
    • t2 = k * inverse(m + r2, p) mod p
    • leak1 = t1 >> 244
    • leak2 = t2 >> 244

So you do not see full t1, t2; you only see their high bits. That missing part becomes our “small unknown”.

0x02 Factor RSA and decrypt the built-in hint

Because q is only 25 bits, factoring N is trivial by trial division / small prime search.

Once you factor:

  • p = N // q
  • compute φ(N) = (p-1)(q-1)
  • d = e^{-1} mod φ(N)
  • decrypt: msg = c^d mod N

You already confirmed the plaintext is:

Hurry up and go smelt copper!

That’s a direct hint: use Coppersmith (lattice small root).

0x03 Convert leaks into “known high bits + small unknown”

You know:

  • leak1 = t1 >> 244
  • leak2 = t2 >> 244

Let shift = 244 and define:

  • a1 = leak1 * 2^shift
  • a2 = leak2 * 2^shift

Then write the unknown low bits as:

  • t1 = a1 + x
  • t2 = a2 + y

where the bounds are:

  • 0 ≤ x < 2^shift
  • 0 ≤ y < 2^shift

So x and y are small compared to p (since p ~ 2^1024 and 2^244 is much smaller).

This is exactly the “small root” situation.

0x04 Eliminate the flag m and obtain a bivariate modular equation

We start from the definitions:

$$ [ t_1 \equiv k(m+r_1)^{-1} \pmod p ] [ t_2 \equiv k(m+r_2)^{-1} \pmod p ] $$

Rearrange both:

$$ [ (m+r_1)t_1 \equiv k \pmod p ] [ (m+r_2)t_2 \equiv k \pmod p ] $$

Now eliminate m. From the first:

$$ [ m \equiv kt_1^{-1} - r_1 \pmod p ] $$

Plug into the second:

$$ [ (kt_1^{-1} - r_1 + r_2)t_2 \equiv k \pmod p ] $$

Multiply by t1:

$$ [ k t_2 + (r_2 - r_1)t_1 t_2 \equiv k t_1 \pmod p ] $$

Bring all to one side:

$$ [ (r_2-r_1)t_1t_2 + k(t_2 - t_1) \equiv 0 \pmod p ] $$

Now substitute t1 = a1 + x, t2 = a2 + y:

$$ [ F(x,y)=(r_2-r_1)(a_1+x)(a_2+y) + k((a_2+y)-(a_1+x)) \equiv 0 \pmod p ] $$

This is a bivariate polynomial congruence with a small root (x,y).

0x05 Simplify the polynomial structure (bilinear form)

Expand F(x,y) and collect terms in (x,y):

It becomes:

$$ [ f(x,y) = Axy + B_x x + B_y y + C \equiv 0 \pmod p ] $$

Where:

  • $$ (A = (r_2-r_1)) $$
  • $$ (B_x = A a_2 - k) $$
  • $$ (B_y = A a_1 + k) $$
  • $$ (C = A a_1 a_2 + k(a_2-a_1)) $$

(all taken mod p)

So it’s bilinear (degree 2 but only via x*y), which is friendly for lattice methods.

0x06 Bivariate Coppersmith idea (high-level)

We want to find small integers (x,y) such that:

  • f(x,y) ≡ 0 (mod p)
  • |x| < X = 2^244
  • |y| < Y = 2^244

Coppersmith-style approach:

  1. Build many polynomials that vanish at the root modulo a high power of p, e.g. terms like:

    • $$ (x^i y^j f(x,y)^k p^{m-k}) $$

  2. Scale monomials by X^a Y^b so evaluation at the root stays small.

  3. Put coefficient vectors into a lattice.

  4. Apply LLL to get short vectors → polynomials that are actually zero over integers at the root (not just mod p).

  5. Use elimination (e.g. resultant) to solve for x and y.

This is often attributed to variants of Howgrave-Graham criteria and Jochemsz–May constructions for multivariate cases.

0x07 Solve for the flag once (x,y) is found

After recovering x:

  • t1 = a1 + x
  • from $$((m+r_1)t_1 \equiv k \pmod p)$$: $$ [ m \equiv k t_1^{-1} - r_1 \pmod p ] $$

Since the flag integer is small (a typical CTF string), the residue corresponds directly to the plaintext bytes.

0x08 Reference implementation (Sage)

This is a complete “drop-in” solver pattern:

  • Factors N
  • Builds bilinear f(x,y)
  • Constructs a lattice (Jochemsz–May style)
  • Uses LLL
  • Extracts candidate polynomials and eliminates via resultants
  • Verifies (x,y) by checking f(x,y) ≡ 0 (mod p)
  • Recovers m and prints bytes

Run with: sage -python coppersolve.py

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

from sage.all import *

e = 65537
N = Integer(3333577291839009732612693330613476891341287017491683764014849337158389717338712200133085615150269196268856288361865352673921704626130772582853528604556994221890454520933132803888321775335519781063447756692130742361931522856942232406992357982482263472763363458621836220024977864980600979194500121897419553619426163227)
c = Integer(1277272201928931051067525742142583320131498687502905469530557519241347169899260720694873154669476372724906606385788056536109971768256973988460766527896895880291037980646963981472637862512247195798266373251524526460097881602691641026093728861572872156172787168597410496150253340538386296663073088345799201197096884740)

k  = Integer(9352039867057736323)
r1 = Integer(10421792656200324147964684790160875926436411483496860422433732508593789212449544620816674407170998779863336939494663076247759140488927744939619406024905901)
r2 = Integer(8806088830734144089522276896226392806947836111998696180055727048752624989402057411311728398322297424598954586424896296000606209022432442660527640463521679)
leak1 = Integer(4266222222502644630611545246271868348722888987303187402827005454059765428769160822475080050046035916876078546634293907218937483241284454918367519709206766322037148585465519188582916280829212776096606923824120883699251868362915920299645)
leak2 = Integer(1176921186497191878459783787148403806360469809421921990427675048480656171919274113895695842508460760829511824635106692634456334400022597605585661597793889066395539405395254174368285751236344600489419240628821864912762242188289636510706)

q = Integer(23520857)
p = N // q

phi = (p-1)*(q-1)
d = inverse_mod(e, phi)
msg = Integer(pow(c, d, N))
print("message =", msg.to_bytes((msg.nbits()+7)//8, 'big'))

shift = 244
X = Integer(1) << shift
Y = Integer(1) << shift
a1 = leak1 << shift
a2 = leak2 << shift

def centerlift(z, mod):
    z = Integer(z % mod)
    if z > mod//2:
        z -= mod
    return z

# Bilinear coefficients modulo p:
A  = (r2 - r1) % p
Bx = (A * a2 - k) % p
By = (A * a1 + k) % p
C  = (A * a1 * a2 + k*(a2 - a1)) % p

# Use centered integers for nicer LLL behavior
A  = centerlift(A,  p)
Bx = centerlift(Bx, p)
By = centerlift(By, p)
C  = centerlift(C,  p)

PR = PolynomialRing(ZZ, names=('x','y'), order='lex')
x, y = PR.gens()
f = A*x*y + Bx*x + By*y + C

def try_bivariate(f, p, X, Y, m, t, take=6):
    polys = []
    # Jochemsz–May style shifts
    for kpow in range(m+1):
        fk = f**kpow
        pk = Integer(p)**(m - kpow)
        for i in range(t+1):
            for j in range(t+1 - i):   # i+j <= t
                polys.append((x**i) * (y**j) * fk * pk)

    mons = set()
    for g in polys:
        mons |= set(g.monomials())
    mons = sorted(mons, key=lambda mm: (mm.degree(), mm.degree(y), mm.degree(x)))
    exps = [mon.exponents()[0] for mon in mons]  # list of (ax, ay)

    rows = []
    for g in polys:
        row = []
        for (ax, ay), mon in zip(exps, mons):
            coeff = g.monomial_coefficient(mon)
            row.append(Integer(coeff) * (X**ax) * (Y**ay))
        rows.append(row)

    M = Matrix(ZZ, rows)
    Mred = M.LLL()

    def vec_to_poly(v):
        gQ = 0
        den = Integer(1)
        terms = []
        for (ax, ay), mon, vv in zip(exps, mons, v):
            if vv == 0:
                continue
            cQ = QQ(vv) / QQ((X**ax) * (Y**ay))
            den = lcm(den, cQ.denominator())
            terms.append((cQ, mon))
        for cQ, mon in terms:
            gQ += (cQ * den) * mon
        return PR(gQ)

    gs = []
    for idx in range(min(take, Mred.nrows())):
        g = vec_to_poly(Mred.row(idx))
        if g != 0:
            gs.append(g)

    if len(gs) < 2:
        return None

    # Eliminate via resultant and search small roots
    for i in range(min(4, len(gs))):
        for j in range(i+1, min(6, len(gs))):
            g1, g2 = gs[i], gs[j]
            try:
                R = g1.resultant(g2, y)
            except Exception:
                continue
            if R == 0:
                continue
            Ru = R.univariate_polynomial()

            for x0, _ in Ru.roots():
                x0 = Integer(x0)
                if not (0 <= x0 < X):
                    continue

                gy = g1(x=x0)
                if gy == 0:
                    continue
                gyu = gy.univariate_polynomial()

                for y0, _ in gyu.roots():
                    y0 = Integer(y0)
                    if not (0 <= y0 < Y):
                        continue

                    # Verify original modular equation
                    if (A*x0*y0 + Bx*x0 + By*y0 + C) % p == 0:
                        return (x0, y0)
    return None

sol = None
for m in [2,3,4,5,6]:
    for t in [1,2,3,4,5]:
        print(f"[+] trying m={m}, t={t}")
        sol = try_bivariate(f, p, X, Y, m=m, t=t)
        if sol:
            break
    if sol:
        break

if not sol:
    raise RuntimeError("No root found; increase m/t or adjust lattice construction.")

x0, y0 = sol
print("[+] found (x,y) =", sol)

# Recover m (flag integer) using t1 = a1 + x
t1 = a1 + x0
m_int = (k * inverse_mod(t1, p) - r1) % p
flag = Integer(m_int).to_bytes((Integer(m_int).nbits()+7)//8, 'big')
print("flag =", flag)

1
2
3
4
5
6

$   sage -python solver.py
message = b'Hurry up and go smelt copper!'
[+] trying m=2, t=1
[+] trying m=2, t=2
[+] found (x,y) = (26935065816404425348087810146545330304118198184338416823761954915055210704, 3508779780900061165273789436142261523358634325843505345455544824287405353)
flag = b'flag{H4hAHhhHh4_c0pP3r_N07_v1OI3n7_3n0uGh}'
© 2020 - 2026 SISUBENY
Built with Hugo
Theme Stack designed by Jimmy