LA CTF 2026 - The Clock | kudaliar's blog

Flag: lactf{t1m3_c0m3s_f4r_u_4all}

Challenge Overview

This challenge implements a Diffie-Hellman key exchange over a “clock” group, where points satisfy the equation $x^2 + y^2 = 1$ (the unit circle). The goal is to recover the shared secret and decrypt the flag.

Given Information

Challenge source code with a missing prime p
Alice’s public key: $(13109366899209289301676180036151662757744653412475893615415990437597518621948, 5214723011482927364940019305510447986283757364508376959496938374504175747801)$
Bob’s public key: $(1970812974353385315040605739189121087177682987805959975185933521200533840941, 12973039444480670818762166333866292061530850590498312261363790018126209960024)$
Encrypted flag: d345a465538e3babd495cd89b43a224ac93614e987dfb4a6d3196e2d0b3b57d9

Step 1: Recover the Prime p

The clock group consists of points $(x, y)$ satisfying $x^2 + y^2 \equiv 1 \pmod{p}$ . For valid points, $x^2 + y^2 - 1$ must be divisible by $p$ .

1
base_x = 13187661168110324954294058945757101408527953727379258599969622948218380874617
2
base_y = 5650730937120921351586377003219139165467571376033493483369229779706160055207
3
alice_x = 13109366899209289301676180036151662757744653412475893615415990437597518621948
4
alice_y = 5214723011482927364940019305510447986283757364508376959496938374504175747801
5
bob_x = 1970812974353385315040605739189121087177682987805959975185933521200533840941
6
bob_y = 12973039444480670818762166333866292061530850590498312261363790018126209960024
7

8
base_sum = base_x**2 + base_y**2 - 1
9
alice_sum = alice_x**2 + alice_y**2 - 1
10
bob_sum = bob_x**2 + bob_y**2 - 1
11

12
p = gcd(gcd(base_sum, alice_sum), bob_sum)

Result:

1
p = 13767529254441196841515381394007440393432406281042568706344277693298736356611

Verification: $p$ is prime and all given points satisfy the curve equation.

Step 2: Analyze the Group Structure

For the clock group over $\mathbb{F}_p$ where $p \equiv 3 \pmod{4}$ :

The group order is $p + 1$
The group is isomorphic to the multiplicative subgroup of $\mathbb{F}_{p^2}$ of order $p+1$

Mapping: A point $(x, y)$ maps to the element $y + x \cdot i \in \mathbb{F}_{p^2}$ , where $i^2 = -1$ .

Step 3: Factor the Group Order

1
group_order = p + 1
2
# Factorization: 2^2 × 39623 × 41849 × 42773 × 46511 × 47951 × 50587 × 50741 × 51971 × 54983 × 55511 × 56377 × 58733 × 61843 × 63391 × 63839 × 64489

Since the group order factors into small primes, the Pohlig-Hellman algorithm is applicable.

Step 4: Solve Discrete Logarithm

Using Pohlig-Hellman combined with Baby-Step Giant-Step (BSGS) for each prime power:

1
def discrete_log_ph(base, target, order, factors, p):
2
    # Pohlig-Hellman algorithm
3
    results = []
4
    moduli = []
5

6
    for q, e in factors.items():
7
        qe = q ** e
8
        cofactor = order // qe
9

10
        # Reduce to subgroup of order q^e
11
        base_q = fp2_pow(base, cofactor, p)
12
        target_q = fp2_pow(target, cofactor, p)
13

14
        # Solve in subgroup using BSGS
15
        x = solve_prime_power(base_q, target_q, q, e, p)
16

17
        results.append(x)
18
        moduli.append(qe)
19

20
    # Combine using CRT
21
    return crt(results, moduli)
22

23
# Find Alice's secret key
24
alice_secret = discrete_log_ph(base_fp2, alice_fp2, group_order, factors, p)
25
# Result: 13194345531092541282960468403774854038006010561489947009251825743361373440013

Step 5: Compute Shared Secret and Decrypt

1
def clockadd(P1, P2, p):
2
    x1, y1 = P1
3
    x2, y2 = P2
4
    x3 = (x1 * y2 + y1 * x2) % p
5
    y3 = (y1 * y2 - x1 * x2) % p
6
    return (x3, y3)
7

8
def scalarmult(P, n, p):
9
    if n == 0: return (0, 1)
10
    if n == 1: return P
11
    Q = scalarmult(P, n // 2, p)
12
    Q = clockadd(Q, Q, p)
13
    if n % 2: Q = clockadd(P, Q, p)
14
    return Q
15

16
# Compute shared secret
17
shared_secret = scalarmult(bob_public, alice_secret, p)
18
# (12908236301563930913711454458378166788650310064605426549082577875696820848112,
19
#  6746606992515589635357750300060959445352892536721721582298343132524571854099)
20

21
# Derive AES key
22
key = md5(f"{shared_secret[0]},{shared_secret[1]}".encode()).digest()
23

24
# Decrypt flag
25
cipher = AES.new(key, AES.MODE_ECB)
26
plaintext = cipher.decrypt(encrypted_flag)

Key Takeaways

Recovering hidden parameters: When the prime is missing but points are given, use the curve equation to derive it via GCD.
Clock group structure: The clock curve $x^2 + y^2 = 1$ over $\mathbb{F}_p$ (with $p \equiv 3 \pmod{4}$ ) has order $p+1$ and can be mapped to a subgroup of $\mathbb{F}_{p^2}^*$ .
Pohlig-Hellman attack: When the group order has only small prime factors, discrete logarithms become computationally feasible.

Full Solver Script

1
from hashlib import md5
2
from Crypto.Cipher import AES
3
import math
4

5
# Given data
6
base_point = (
7
    13187661168110324954294058945757101408527953727379258599969622948218380874617,
8
    5650730937120921351586377003219139165467571376033493483369229779706160055207
9
)
10
alice_public = (
11
    13109366899209289301676180036151662757744653412475893615415990437597518621948,
12
    5214723011482927364940019305510447986283757364508376959496938374504175747801
13
)
14
bob_public = (
15
    1970812974353385315040605739189121087177682987805959975185933521200533840941,
16
    12973039444480670818762166333866292061530850590498312261363790018126209960024
17
)
18
encrypted_flag = bytes.fromhex("d345a465538e3babd495cd89b43a224ac93614e987dfb4a6d3196e2d0b3b57d9")
19

20
# Recover p
21
base_x, base_y = base_point
22
alice_x, alice_y = alice_public
23
bob_x, bob_y = bob_public
24

25
base_sum = base_x**2 + base_y**2 - 1
26
alice_sum = alice_x**2 + alice_y**2 - 1
27
bob_sum = bob_x**2 + bob_y**2 - 1
28

29
def gcd(a, b):
30
    while b:
31
        a, b = b, a % b
32
    return a
33

34
p = gcd(gcd(base_sum, alice_sum), bob_sum)
35
print(f"p = {p}")
36

37
# Group order
38
group_order = p + 1
39

40
# Factorization
41
factors = {2: 2, 39623: 1, 41849: 1, 42773: 1, 46511: 1, 47951: 1,
42
           50587: 1, 50741: 1, 51971: 1, 54983: 1, 55511: 1, 56377: 1,
43
           58733: 1, 61843: 1, 63391: 1, 63839: 1, 64489: 1}
44

45
# F_p2 operations
46
def fp2_mul(a, b, p):
47
    a_real, a_imag = a
48
    b_real, b_imag = b
49
    real = (a_real * b_real - a_imag * b_imag) % p
50
    imag = (a_real * b_imag + a_imag * b_real) % p
51
    return (real, imag)
52

53
def fp2_pow(a, n, p):
54
    result = (1, 0)
55
    base = a
56
    while n > 0:
57
        if n & 1:
58
            result = fp2_mul(result, base, p)
59
        base = fp2_mul(base, base, p)
60
        n >>= 1
61
    return result
62

63
def point_to_fp2(point):
64
    x, y = point
65
    return (y, x)
66

67
base_fp2 = point_to_fp2(base_point)
68
alice_fp2 = point_to_fp2(alice_public)
69

70
# BSGS
71
def bsgs(base, target, order, p):
72
    m = int(math.isqrt(order)) + 1
73
    baby_steps = {}
74
    current = (1, 0)
75
    for j in range(m):
76
        if current not in baby_steps:
77
            baby_steps[current] = j
78
        current = fp2_mul(current, base, p)
79

80
    base_m_inv = fp2_pow(base, order - m, p)
81
    gamma = target
82
    for i in range(m):
83
        if gamma in baby_steps:
84
            return (i * m + baby_steps[gamma]) % order
85
        gamma = fp2_mul(gamma, base_m_inv, p)
86
    return None
87

88
# Pohlig-Hellman
89
def discrete_log_ph(base, target, order, factors, p):
90
    results = []
91
    moduli = []
92

93
    for q, e in factors.items():
94
        qe = q ** e
95
        cofactor = order // qe
96
        base_q = fp2_pow(base, cofactor, p)
97
        target_q = fp2_pow(target, cofactor, p)
98

99
        x = 0
100
        cur_base = base_q
101
        cur_target = target_q
102

103
        for i in range(e):
104
            base_reduced = fp2_pow(cur_base, q ** (e - i - 1), p)
105
            target_reduced = fp2_pow(cur_target, q ** (e - i - 1), p)
106
            xi = bsgs(base_reduced, target_reduced, q, p)
107
            x += xi * (q ** i)
108

109
            if i < e - 1:
110
                inv = fp2_pow(cur_base, xi, p)
111
                inv = (inv[0], (-inv[1]) % p)
112
                cur_target = fp2_mul(cur_target, inv, p)
113
                cur_base = fp2_pow(cur_base, q, p)
114

115
        results.append(x)
116
        moduli.append(qe)
117

118
    # CRT
119
    def extended_gcd(a, b):
120
        if b == 0:
121
            return a, 1, 0
122
        g, x1, y1 = extended_gcd(b, a % b)
123
        return g, y1, x1 - (a // b) * y1
124

125
    def crt(rems, mods):
126
        x = 0
127
        M = 1
128
        for m in mods:
129
            M *= m
130
        for ri, mi in zip(rems, mods):
131
            Mi = M // mi
132
            _, si, _ = extended_gcd(Mi, mi)
133
            x = (x + ri * Mi * si) % M
134
        return x
135

136
    return crt(results, moduli)
137

138
# Get Alice's secret
139
alice_secret = discrete_log_ph(base_fp2, alice_fp2, group_order, factors, p)
140
print(f"Alice secret: {alice_secret}")
141

142
# Compute shared secret
143
def clockadd(P1, P2):
144
    x1, y1 = P1
145
    x2, y2 = P2
146
    x3 = (x1 * y2 + y1 * x2) % p
147
    y3 = (y1 * y2 - x1 * x2) % p
148
    return (x3, y3)
149

150
def scalarmult(P, n):
151
    if n == 0: return (0, 1)
152
    if n == 1: return P
153
    Q = scalarmult(P, n // 2)
154
    Q = clockadd(Q, Q)
155
    if n % 2: Q = clockadd(P, Q)
156
    return Q
157

158
shared_secret = scalarmult(bob_public, alice_secret)
159
print(f"Shared secret: {shared_secret}")
160

161
# Decrypt
162
key = md5(f"{shared_secret[0]},{shared_secret[1]}".encode()).digest()
163
cipher = AES.new(key, AES.MODE_ECB)
164
plaintext = cipher.decrypt(encrypted_flag)
165
print(f"Flag: {plaintext}")