LA CTF 2026 - the clock

Updated Feb 6, 2026 · Created Feb 6, 2026

Challenge

Category: Crypto

chall.py

from random import randrange
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5

p = 

def clockadd(P1,P2):
    x1,y1 = P1
    x2,y2 = P2
    x3 = x1*y2+y1*x2
    y3 = y1*y2-x1*x2
    return x3,y3

def F(p): # caveat: caller must ensure that p is prime
    class F:
        def __init__(self,x):
            self.int = x % p
        def __str__(self):
            return str(self.int)
        __repr__ = __str__
        def __eq__(a,b):
            return a.int == b.int
        def __ne__(a,b):
            return a.int != b.int
        def __add__(a,b):
            return F(a.int + b.int)
        def __sub__(a,b):
            return F(a.int - b.int)
        def __mul__(a,b):
            return F(a.int * b.int)
        def __div__(a,b): # caveat: caller must ensure that b is nonzero
            return a*F(pow(b.int,p-2,p))
    return F

def scalarmult(P, n):
    # caveat: caller must ensure that n is nonnegative
    # caveat: n is limited by python's recursion limit
    if n == 0: return (Fp(0),Fp(1))
    if n == 1: return P
    Q = scalarmult(P, n//2)
    Q = clockadd(Q,Q)
    if n % 2:
        Q = clockadd(P,Q)
    return Q

Fp = F(p)
base_point = (Fp(13187661168110324954294058945757101408527953727379258599969622948218380874617),Fp(5650730937120921351586377003219139165467571376033493483369229779706160055207))

alice_secret = randrange(2**256)
alice_public = scalarmult(base_point, alice_secret)
print("Alice's public key: ", alice_public)

bob_secret = randrange(2**256)
bob_public = scalarmult(base_point, bob_secret)
print("Bob's public key: ", bob_public)

assert scalarmult(bob_public, alice_secret) == scalarmult(alice_public, bob_secret)
shared_secret = scalarmult(bob_public, alice_secret)

key = md5(f"{shared_secret[0].int},{shared_secret[1].int}".encode()).digest()
FLAG = b""
print("Encrypted flag: ", AES.new(key, AES.MODE_ECB).encrypt(pad(FLAG, 16)).hex())

output.txt

Alice's public key: (13109366899209289301676180036151662757744653412475893615415990437597518621948, 5214723011482927364940019305510447986283757364508376959496938374504175747801)
Bob's public key: (1970812974353385315040605739189121087177682987805959975185933521200533840941, 12973039444480670818762166333866292061530850590498312261363790018126209960024)
Encrypted flag: d345a465538e3babd495cd89b43a224ac93614e987dfb4a6d3196e2d0b3b57d9

Solution Summary

Find p → Factor the group order → Discover it's smooth → Pohlig-Hellman to solve discrete log → Decrypt flag

Process

01 First Look: Confused

Got the challenge, looked at chall.py, and found it's not like typical RSA or symmetric encryption. There's a weird function:

def clockadd(P1,P2):
    x1,y1 = P1
    x2,y2 = P2
    x3 = x1*y2+y1*x2
    y3 = y1*y2-x1*x2
    return x3,y3

What is this? No idea.

02 Closer Look: It's a DH Variant

Looking at the code structure:

There's alice_secret, alice_public
There's bob_secret, bob_public
There's shared_secret
Uses shared key for AES encryption

This is Diffie-Hellman key exchange, just using a weird "clock" group instead of normal integer group or elliptic curve.

03 Asked AI for Help

I threw the challenge to AI. AI explained:

clockadd is the group operation on the unit circle x² + y² = 1 (mod p). This addition corresponds to "adding angles", like clock hands rotating, hence the name clock addition.

Makes sense. But line 5 of the code p = is truncated. What's p?

04 Finding p

AI said: Since all points are on the circle, satisfying x² + y² ≡ 1 (mod p), p must divide (x² + y² - 1).

Take GCD of (x² + y² - 1) from multiple points (base_point, Alice's public key, Bob's public key):

import math

# base_point
x1, y1 = (13187661168110324954294058945757101408527953727379258599969622948218380874617,
          5650730937120921351586377003219139165467571376033493483369229779706160055207)
# Alice's public key
x2, y2 = (13109366899209289301676180036151662757744653412475893615415990437597518621948,
          5214723011482927364940019305510447986283757364508376959496938374504175747801)
# Bob's public key
x3, y3 = (1970812974353385315040605739189121087177682987805959975185933521200533840941,
          12973039444480670818762166333866292061530850590498312261363790018126209960024)

val1 = x1*x1 + y1*y1 - 1
val2 = x2*x2 + y2*y2 - 1
val3 = x3*x3 + y3*y3 - 1

p = math.gcd(math.gcd(val1, val2), val3)
# p = 13767529254441196841515381394007440393432406281042568706344277693298736356611

But GCD isn't necessarily p - could be a multiple or contain other factors. Need to verify:

from sympy import isprime

# 1. Check if it's prime
isprime(p)  # Returns True ✓

# 2. Verify points are on the circle
(x1*x1 + y1*y1) % p  # Returns 1 ✓

If GCD wasn't prime, we'd need to factor it to find the real p. Luckily, GCD is directly prime here.

05 Key Problem: Group Order

To break DH, we need to solve the discrete logarithm problem: given G and A = a×G, find a.

I asked AI: Isn't discrete log hard? How to solve it?

AI explained:

Group order is how many elements are in the group. For the unit circle group, order = p + 1 or p - 1 (this is a number theory result, just use it).

Discrete log is usually hard, but the key is the structure of the group order:

If order is a large prime → no way, must brute force, impossible

If order factors into small primes → can use Pohlig-Hellman algorithm

Pohlig-Hellman uses "divide and conquer". For example, if order = 12 = 4 × 3, instead of trying 12 possibilities:

Find a mod 4 in subgroup of 4 elements (only try 0,1,2,3)

Find a mod 3 in subgroup of 3 elements (only try 0,1,2)

Use Chinese Remainder Theorem to combine into a mod 12

More and smaller factors = bigger advantage.

I didn't fully understand the algorithm details, but the idea is clear: if the order factors into small primes, we can solve it quickly.

For this challenge, p mod 4 = 3, so order = p + 1.

06 Factoring the Group Order

I took the group order to https://www.alpertron.com.ar/ECM.HTM to factor:

13767529254441196841515381394007440393432406281042568706344277693298736356612
= 2² × 39623 × 41849 × 42773 × 46511 × 47951 × 50587 × 50741 × 51971 × 54983 × 55511 × 56377 × 58733 × 61843 × 63391 × 63839 × 64489

All small factors! Largest is only 64489. This is a smooth number, Pohlig-Hellman can solve it instantly!

07 Solution

Ran the Pohlig-Hellman script, computed Alice's private key in seconds, then calculated shared secret, decrypted AES to get flag:

lactf{t1m3_c0m3s_f4r_u_4all}

Lessons Learned

Unfamiliar crypto structure? First observe the overall framework (DH, RSA, symmetric?)
Missing parameters might be derivable from known data (using GCD to find p)
Discrete log isn't always hard - depends on whether group order can be factored
Alpertron factors large integers really fast