LA CTF 2026 - the clock

题目

分类： Crypto

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())

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

解法总结

找到 p → 分解群的阶 → 发现是光滑数 → Pohlig-Hellman 求离散对数 → 解密 flag

过程

01 初看题目，一脸懵逼

拿到题目，看到 chall.py，发现跟一般的 RSA 或者对称加密都不太一样。有个奇怪的函数：

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

这是什么？完全看不懂。

02 仔细观察，发现是 DH 变种

再看看代码结构：

• 有 alice_secret、alice_public
• 有 bob_secret、bob_public
• 有 shared_secret
• 用共享密钥做 AES 加密

这不就是 Diffie-Hellman 密钥交换，只是用了一个奇怪的 "clock" 群，而不是普通的整数群或椭圆曲线。

03 丢给 AI 分析

我把题目丢给 AI，AI 解释说：

clockadd 是单位圆 x² + y² = 1 (mod p) 上的群运算。这个加法对应"角度相加"，就像时钟指针转动，所以叫 clock addition。

原来如此。但是代码第 5 行的 p = 后面被截断了，p 是多少？

04 找到 p

AI 说：既然所有点都在圆上，满足 x² + y² ≡ 1 (mod p)，那么 p 一定整除 (x² + y² - 1)。

用多个点（base_point、Alice 公钥、Bob 公钥）的 (x² + y² - 1) 取 GCD：

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

但 GCD 不一定就是 p，可能是 p 的倍数或包含其他因子。需要验证：

from sympy import isprime

# 1. 检查是否是质数
isprime(p)  # 返回 True ✓

# 2. 验证点确实在圆上
(x1*x1 + y1*y1) % p  # 返回 1 ✓

如果 GCD 不是质数，就需要分解它找出真正的 p。这道题运气好，GCD 直接就是质数。

05 关键问题：群的阶

现在要破解 DH，就是要解离散对数问题：已知 G 和 A = a×G，求 a。

我问 AI：离散对数问题不是很难吗？怎么解？

AI 解释说：

群的阶就是群里有多少个元素。对于单位圆群，阶 = p + 1 或 p - 1（这是数论结论，直接用就行）。

离散对数通常很难，但关键看群的阶的结构：

• 如果阶是大质数 → 没办法，必须暴力尝试，不可能
• 如果阶能分解成小因子 → 可以用 Pohlig-Hellman 算法

Pohlig-Hellman 的思路是"分而治之"。比如阶 = 12 = 4 × 3，不需要试 12 种可能，而是：

1. 在 4 个元素的子群里找 a mod 4（只试 0,1,2,3）
2. 在 3 个元素的子群里找 a mod 3（只试 0,1,2）
3. 用中国剩余定理合并得到 a mod 12

因子越多越小，优势越大。

我没有完全理解这个算法的细节，但思路是清楚的：如果阶能分解成小因子，就能快速求解。

对于这道题，p mod 4 = 3，所以阶 = p + 1。

06 分解群的阶

我把群的阶拿到 https://www.alpertron.com.ar/ECM.HTM 去分解：

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

全是小因子！最大的才 64489。这就是个光滑数，Pohlig-Hellman 可以秒解！

07 解题

运行 Pohlig-Hellman 脚本，几秒钟就算出了 Alice 的私钥，然后计算共享密钥，解密 AES 得到 flag：

lactf{t1m3_c0m3s_f4r_u_4all}