CornCTF2025 | ECRSA - ByteTheCookies

Introduction#

ECRSA was a crypto CTF from cornCTF 2025.

Source#

1
#!/usr/bin/env python3
2
from secret_params import curve_p, a, b, order, secret_point_x, secret_point_y
3
import os
4

5
FLAG = os.getenv("FLAG", "corn{__redacted_redacted_redacted__redacted_redacted_redacted__}").encode()
6

7
assert FLAG.startswith(b"corn{") and FLAG.endswith(b"}")
8
assert len(FLAG) == 64
9

10
def sign(m, x):
11
    if m == 0 or m == 1 or m == n-1:
12
        print("No weak messages allowed here")
13
        return None
14
    try:
15
        user_point = E.lift_x(x)
16
    except ValueError:
17
        print(f"Invalid point: {x} does not describe any point on the curve")
18
        return None
19
    sig = pow(m, d, n)
20
    sig = sig * user_point + secret_point
21
    return sig.xy()[0], sig.xy()[1]
22

23
def verify(sig, m, x):
24
    try:
25
        user_point = E.lift_x(x)
26
    except ValueError:
27
        print(f"Invalid point: {x} does not describe any point on the curve")
28
        return False
29
    sig_point = sig - secret_point
30
    # don't want to make you wait too long
31
    # c = sig_point.log(user_point)
32
    c = 0x69
33
    c = pow(c, e, n)
34
    return c == m
35

36
assert curve_p.bit_length() == 513
37
assert order.bit_length() == 513
38

39
K = GF(curve_p)
40
a = K(a)
41
b = K(b)
42
K = GF(curve_p)
43
E = EllipticCurve(K, (a, b))
44
E.set_order(order)
45
secret_point = E(secret_point_x, secret_point_y)
46

47
flag = int.from_bytes(FLAG, byteorder='big')
48

49
p = random_prime(2<<255, lbound=2<<254)
50
q = random_prime(2<<255, lbound=2<<254)
51
n = p*q
52

53
while flag >= n or n>curve_p or n>order:
54
    p = random_prime(2<<255, lbound=2<<254)
55
    q = random_prime(2<<255, lbound=2<<254)
56
    n = p*q
57

58
e = 0x10001
59
d = pow(e, -1, (p-1)*(q-1))
60

61
print("Welcome to my custom signing and verification system!")
62
print("Here are my public parameters:")
63
print(f"e: {e}")
64
print(f"n: {n}")
65

66
print(f"Leak: {pow(flag, e, n)}")
67

68
while True:
69
    print("1. Sign\n2. Verify\n3. Exit")
70
    choice = int(input())
71
    if choice == 1:
72
        m = int(input("Enter message: "))
73
        x = Integer(input("Enter x-coordinate of your point: "))
74
        sig = sign(m, x)
75
        print(f"Signature: {sig}")
76
    elif choice == 2:
77
        try:
78
            sig_x = Integer(input("Enter x-coordinate of signature: "))
79
            sig_y = Integer(input("Enter y-coordinate of signature: "))
80
            sig = E(sig_x, sig_y)
81
        except TypeError:
82
            print("Invalid signature")
83
            continue
84
        m = int(input("Enter message: "))
85
        x = K(Integer(input("Enter x-coordinate of your point: ")))
86
        if verify(sig, m, x):
87
            print("Valid signature")
88
        else:
89
            print("Invalid signature")
90
    elif choice == 3:
91
        break
92
    else:
93
        print("Invalid choice")

The flag is simply encrypted with RSA, while the service provides a modified ECDSA signing oracle.

Solution#

There are 3 steps to the solution:

Recover the secret_point
Figure out the curve parameters
Obtain the flag

Recovering `secret_point`#

This step is really easy as the check in sign for the value of m is done before the modular reduction, therefore sending a multiple of the modulus will pass the check but pow(m, d, n) will result in a 0, meaning sign will give back secret_point

Figuring out the curve parameters#

With secret_point now ours and being able to provide sign with any user_point we can query the oracle to obtain a few points on the curve, with said points we can recover the parameters:

1
def solve_curve_parameters(r):
2
    points = set()
3

4
    for x_in in trange(1, 100):
5
        try:
6
            point = sign(r, n+1, x_in)
7
            points.add(point)
8
            if len(points) >= 10: # arbitrary
9
                break
10
        except:
11
            continue
12

13
    points = list(points)
14
    dets = []
15
    for i in range(len(points) - 3):
16
        (x1, y1), (x2, y2), (x3, y3) = points[i], points[i+1], points[i+2]
17

18
        # Y = y^2 - x^3 -> Y = ax + b (mod p).
19
        Y1 = y1**2 - x1**3
20
        Y2 = y2**2 - x2**3
21
        Y3 = y3**2 - x3**3
22

23
        # w := Y1 - Y2 = a(x1 - x2) (mod p)
24
        # z := Y2 - Y3 = a(x2 - x3) (mod p)
25
        # So w(x2 - x3) and z(x1 - x2) differ by a multiple of p
26
        I = (Y1 - Y2) * (x2 - x3) - (Y2 - Y3) * (x1 - x2)
27

28
        if I != 0:
29
            dets.append(I)
30

31
    p = gcd(dets)
32
    dx = x1 - x2
33
    a = (Y1 - Y2) * pow(dx, -1, p) % p
34

35
    # From Y1 = a*x1 + b (mod p), we solve for b.
36
    b = (Y1 - a * x1) % p
37

38
    # Check if (y3^2) % p == (x3^3 + a*x3 + b) % p
39
    lhs = y3**2 % p
40
    rhs = (x3**3 + a * x3 + b) % p
41

42
    if lhs == rhs:
43
        return p, a, b
44

45
    return None, None, None

Getting the flag#

The idea is to use an LSB-Oracle:

$c \equiv m^e \pmod n$
$(2^ec)^d \equiv 2m \pmod n$
the previous value is even if $m \leq n/2$ , odd otherwise (because $n$ is odd)
so we can construct bit by bit the value of $m$ by multiplying $c$ by $2^e$ each time

In the context of the challenge we need a way to distinguish odd and even values of pow(m, d, n). This can be achieved with a point of order $2$ on the curve, since when pow(m, d, n) is even, multiplying it with our given point $P$ will give the identity, which added to secret_point will give this one back, otherwise we’ll get $P$ plus secret_point.

1
def lsb_oracle(r, P):
2
    l, u = 0, n
3

4
    c = enc_flag
5
    e2 = pow(2, e, n)
6
    for _ in trange(n.bit_length()):
7
        c *= e2
8
        Q = E(sign(r, c % n, P.xy()[0])) - sp # sp = secret_point
9
        if Q == E.zero():
10
            u = (l + u) >> 1
11
        else:
12
            l = (l + u) >> 1
13
    return (l + u) >> 1

Full solve script#

1
import os
2
os.environ['TERM'] = 'linux'
3

4
from pwn import *
5
from tqdm import trange
6

7
# Signing utility
8
def sign(r, m, x):
9
    r.recvuntil(b't\n')
10
    r.sendline(b'1')
11
    r.recvuntil(b': ')
12
    r.sendline(str(m).encode())
13
    r.recvuntil(b': ')
14
    r.sendline(str(x).encode())
15

16
    r.recvuntil(b': ')
17
    data = r.recvline(False).decode()[1:-1].split(', ')
18
    return int(data[0]), int(data[1])
19

20

21
def solve_curve_parameters(r):
22
    points = set()
23

24
    for x_in in trange(1, 100):
25
        try:
26
            point = sign(r, n+1, x_in)
27
            points.add(point)
28
            if len(points) >= 10: # arbitrary
29
                break
30
        except:
31
            continue
32

33
    points = list(points)
34
    dets = []
35
    for i in range(len(points) - 3):
36
        (x1, y1), (x2, y2), (x3, y3) = points[i], points[i+1], points[i+2]
37

38
    # Y = y^2 - x^3 -> Y = ax + b (mod p).
39
        Y1 = y1**2 - x1**3
40
        Y2 = y2**2 - x2**3
41
        Y3 = y3**2 - x3**3
42

43
    # w := Y1 - Y2 = a(x1 - x2) (mod p)
44
    # z := Y2 - Y3 = a(x2 - x3) (mod p)
45
    # So w(x2 - x3) and z(x1 - x2) differ by a multiple of p
46
        I = (Y1 - Y2) * (x2 - x3) - (Y2 - Y3) * (x1 - x2)
47

48
        if I != 0:
49
            dets.append(I)
50

51
    p = gcd(dets)
52
    dx = x1 - x2
53
    a = (Y1 - Y2) * pow(dx, -1, p) % p
54

55
    # From Y1 = a*x1 + b (mod p), we solve for b.
56
    b = (Y1 - a * x1) % p
57

58
    # Check if (y3^2) % p == (x3^3 + a*x3 + b) % p
59
    lhs = y3**2 % p
60
    rhs = (x3**3 + a * x3 + b) % p
61

62
    if lhs == rhs:
63
        return p, a, b
64

65
    return None, None, None
66

67
def lsb_oracle(r, P):
68
    l, u = 0, n
69

70
    c = enc_flag
71
    e2 = pow(2, e, n)
72
    for _ in trange(n.bit_length()):
73
        c *= e2
74
        Q = E(sign(r, c % n, P.xy()[0])) - sp
75
        if Q == E.zero():
76
            u = (l + u) >> 1
77
        else:
78
            l = (l + u) >> 1
79
    return (l + u) >> 1
80

81
r = remote('ecrsa.challs.cornc.tf', 1337, ssl=True) if args.REMOTE else process('./ecrsa.sage')
82

83
e = 65537
84
r.recvuntil(b'n: ')
85
n = int(r.recvline(False).decode())
86
r.recvuntil(b'k: ')
87
enc_flag = int(r.recvline(False).decode())
88

89
p, a, b = solve_curve_parameters(r)
90
E = EllipticCurve(GF(p), [a, b])
91
# order = E.order()
92
# Cached for speed
93
order = 16069075899419272706313306230384148392684766596987923274252840802156807638348274231565457533546984784193487763139164096443059279726687808489053779972143886
94
E.set_order(order)
95
q = order // 2
96

97
# Get point of order 2
98
while (P := E.random_point()).order() != order: continue
99
P *= q
100

101
assert P.order() == 2
102

103
# Get secret point
104
sp = E(sign(r, 2*n, 1))
105

106
m = lsb_oracle(r, P)
107
# Last byte isn't always right, just ignore and force the }
108
print('flag:', int(m).to_bytes(64)[:-1].decode() + '}')
109

110

111
r.close()

flag: corn{br34k1ng_dl0g_15_h4rd_bu7_m0d_2_m4k35_3v3ry7h1ng_funn13r!!}