强网杯 s9 Elliptic Curve Cryptography

强网杯 s9 2025 - theorezhnp

题目源码

强网杯官方附件 theorezhnp_2ca30345b20024baf4aa65470a9279ed.zip 里的 server.py 如下：

from Crypto.Cipher import AES
from ecdsa import NIST521p
from ecdsa.ecdsa import Public_key
from ecdsa.ellipticcurve import Point 
from random import randrange
from sys import stdin
from hashlib import *
from secret import seed_token, flag
import time, signal

signal.alarm(600)

def read(l):
    return stdin.read(l + 1).strip()

def pr(msg, key=None):
    if not key:
        print(msg)
    else:
        key = sha256(str(key).encode()).digest()
        print(AES.new(key, AES.MODE_ECB).encrypt(msg.encode()).hex())

def inp():
    try:
        return Point(E, int(read(131), 16), int(read(131), 16))
    except:
        pass
    return None

def DH(priv, pub):
    shared = priv * pub
    return shared.x()

token = input("Please input your team token: ")

if not token:
    exit()

def generate_token(seed, token):  
    return sha256((seed + '&' + sha1(token[::-1].encode()).hexdigest()[:10]).encode()).hexdigest()

to_encrypted_token = generate_token(seed_token, token)

E = NIST521p.curve
G = NIST521p.generator  
m = 235
n = G.order() 
Alice_sk = randrange(n)
Alice_pk = Public_key(G, Alice_sk * G).point
pr(f'Hi, Bob! Here is my public key: {Alice_pk.x() :x}')

Bob_sk = randrange(n)
Bob_pk = Public_key(G, Bob_sk * G).point
pr(f'Hi, Alice! Here is my public key: {Bob_pk.x() :x}')

shared_AB = DH(Alice_sk, Bob_pk)
shared_BA = DH(Bob_sk, Alice_pk)
assert shared_AB == shared_BA

pr('Now, it is your turn:')
for _ in range(19):
    Mallory_pk = inp()
    if not Mallory_pk:
        pr('Invalid pk!')
        exit()
    shared_AC = DH(Alice_sk, Mallory_pk)
    pr(f'Leak: {shared_AC >> m :x}')

pr(to_encrypted_token, shared_AB) 

pr("Give me your token:")
Guess_Token = input() 
if Guess_Token == to_encrypted_token:
    pr("Win for flag: " + flag)
else:
    pr("You Lose")

这题和 AliyunCTF 2024 的 BabyDH2 是同一条线。题面里直接写了 babyDH2 in AliCTF2024 is easy for u, but now? can you do more?，所以解法主干还是 ECHNP，只是这次换成了 NIST521p，泄露的是高位，而且取样次数和最终目标也都变了。

服务端会给出 Alice 和 Bob 的公钥横坐标，然后允许我们提交 19 个点，拿到

⌊x([a]Q)2235⌋\left\lfloor \frac{x([a]Q)}{2^{235}} \right\rfloor

的高位。这里 19 次刚好可以组织成一组标准取样：

H0=x([a]B)≫235,H_0 = x([a]B) \gg 235,

再配上 9 对

x([a](B+iG))≫235,x([a](B−iG))≫235.x([a](B+iG)) \gg 235,\qquad x([a](B-iG)) \gg 235.

这样就能把问题喂给现成的 ECHNP / Coppersmith 求解器。和 AliyunCTF 2024 那题相比，这里至少有三处要一起改：曲线换成 NIST521p，泄露改成高位，所以求解器要跑 msb=True，并且最后不再是直接验证密钥，而是要解出加密后的派生 token。

拿到共享秘密 shared_AB 之后就没别的花活了。题目把 generate_token(seed_token, token) 得到的那串派生 token 用 shared_AB 派生出的 AES-ECB 密钥加密后发给我们，因此只要用恢复出来的共享秘密把它解开，再把这个派生 token 原样回传即可。

解题脚本

下面这份脚本就是在公开 BabyDH2 代码基础上，把曲线、泄露方式和最终 token 逻辑改成强网杯这一题的版本。optimized_echnp_solver.py 可以直接用 tl2cents/Implementation-of-Cryptographic-Attacks 仓库里的实现。

from pwn import remote
from Crypto.Cipher import AES
from hashlib import sha256
from ecdsa import NIST521p
from sage.all import EllipticCurve, GF, ZZ
from optimized_echnp_solver import echnp_coppersmith_solver_optimized

io = remote("47.105.112.224", 11421)
io.sendlineafter(b"Please input your team token: ", b"test")

def submit_pk(Qx, Qy):
    io.sendline(hex(int(Qx))[2:].zfill(131).encode())
    io.sendline(hex(int(Qy))[2:].zfill(131).encode())
    io.recvuntil(b"Leak: ")
    return ZZ(int(io.recvline().strip().decode(), 16))

def gen_samples(sample_n, A, B, G):
    H0 = submit_pk(B[0], B[1])
    positiveH, negativeH, xQ = [], [], []
    for i in range(1, sample_n + 1):
        Q = i * G + B
        positiveH.append(submit_pk(Q[0], Q[1]))
        Q = -i * G + B
        negativeH.append(submit_pk(Q[0], Q[1]))
        xQ.append(ZZ((i * A)[0]))
    return H0, positiveH, negativeH, xQ

curve = NIST521p.curve
p = curve.p()
a = curve.a()
b = curve.b()
SageCurve = EllipticCurve(GF(p), [a, b])
R = GF(p)

io.recvuntil(b"Hi, Bob! Here is my public key: ")
Ax = R(int(io.recvline().strip().decode(), 16))
io.recvuntil(b"Hi, Alice! Here is my public key: ")
Bx = R(int(io.recvline().strip().decode(), 16))

A = SageCurve.lift_x(Ax)
B = SageCurve.lift_x(Bx)
G = SageCurve.lift_x(R(NIST521p.generator.x()))

io.recvuntil(b"Now, it is your turn:\n")

sample_n = 9
d = 3
t = 2
kbit = 235
H0, positiveH, negativeH, xQ = gen_samples(sample_n, A, B, G)

shared_AB = echnp_coppersmith_solver_optimized(
    SageCurve,
    G,
    A,
    B,
    kbit,
    H0,
    positiveH,
    negativeH,
    xQ,
    d,
    t,
    True,
    "XHS22",
    20,
)

enc_token = bytes.fromhex(io.recvline().strip().decode())
key = sha256(str(shared_AB).encode()).digest()
derived_token = AES.new(key, AES.MODE_ECB).decrypt(enc_token).decode()

io.sendlineafter(b"Give me your token:\n", derived_token.encode())
io.interactive()

参考资料

Back