H3CTF2025-Crypto-WP

发表于 2025-10-15 更新于 2025-10-17 阅读次数：

哈工大新生赛，记录3道Cyrpto 0解题

isoDream

题目描述

又是一个漫长的夏夜，你合上书本观察起房间里的吊灯，萦回的光影仿佛在告诉你它的补空间的基本群是<a,b|a^2=b^3>
“是时候去睡觉了”，你想着，期待着在梦里能遇见更加广阔的域，好让你用除法狠狠地切割那些多项式，把它们分解成再不分离的素元。
你闭上眼，耳边似乎听见某种曲线的纽结。你顺着一条椭圆的同源路径走去，远方的地平线闪烁着超奇异的光芒，群和域的边界正缓缓向你靠近。

Author: Swizzer

题目附件

chall.py

from sage.all import GF, EllipticCurve, polygen, PolynomialRing, Zmod
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
import random


def getSafePrime(bits: int) -> int:
  while True:
    p = getPrime(bits - 1)
    q = 2 * p + 1
    if isPrime(q):
      return q


def encrypt(m: int, p: int, exponents: list[int]):
  modulus = p**3
  y = PolynomialRing(Zmod(modulus), "x").quotient("x**3 + x + 1", "y").gen()
  g = 13 * y + 37
  powers = [pow(m, e, modulus) for e in exponents]
  return [g**e for e in powers]


def transform(secret: int):
  while True:
    try:
      p = getSafePrime(384)
      x = polygen(GF(p))
      F = GF(p**2, "i", modulus=x**2 + 1)
      j = F(secret)
      E = EllipticCurve(j=j)
      kerl = E(0).division_points(5)[1:]
      E2 = E.isogeny(random.choice(kerl)).codomain()
      return p, E2.j_invariant()
    except Exception as _:
      continue


if __name__ == "__main__":
  m = bytes_to_long(open("flag.txt", "rb").read().strip())
  p_m, (re, im) = transform(m)
  p = getSafePrime(256)
  pt = int(re + im)

  # fmt:off
  exps = [(getPrime(384) - 1) * p for _ in range(8)] + [getPrime(384) * (p - 1) for _ in range(8)]
  # fmt: on
  ct = encrypt(pt, p, exps)
  print(p_m)
  print(exps)
  print(ct)

还有一个输出文件： output.txt

解题思路

首先用flag作为j不变量生成了一个曲线，然后又生成了这条曲线的一个度为5的同源曲线，然后对同源曲线的j不变量传入encrypt，得到输出。

所以思路就是先逆向encrypto，然后拿到同源曲线，计算相邻的曲线的j不变量就是flag。

encrypto函数流程如下：

对消息m进行8次加密：\(c_i = m^{e_i} \mod p^3\)
在\(\mathbb{Z}_{p^3}[x]/(x^3 + x + 1)\)上求\(g^{c_i}\)，其中\(g = 13x + 37\)

首先是8个DLP，且基环是\(\mathbb{Z}_{p^3}[x]/(x^3 + x + 1)\)，但是由于 \(x^3 + x + 1\) 在 \(\mathbb{Z}_{p^3}\) 上能完全分解，所以其实只用在 \(\mathbb{Z}_{p^3}\) 上求解DLP 。\(\mathbb{Z}_{p^k}\)上的DLP可以参考[3]。

所以可以得到8个 \(c_i \mod p^2\)，之后不能直接套用RSA解密，因为加密指数和 \(\phi(p^2)\) 有较大的公因子。所以要换一个思路：共模攻击。这样加密指数就会降到2，然后再当e=2的RSA解就行。

最后，相邻同源可以用classical_modular_polynomial关联起来。

exp

# padic_DLP.py
def padic_dlp(g:int, y:int, p:int, s:int) -> int:
    """Solve p-adic DLP

    refer to https://math.stackexchange.com/questions/1863037/discrete-logarithm-modulo-powers-of-a-small-prime
    
    return x mod(p^(s - 1)) that satisify g^x = y mod(p^s)
    """
    def theta(k, p, s):
        return (pow(k, (p - 1) * p ** (s - 1), p ** (2 * s - 1)) - 1) // (p ** s)
    g, y, p, s = int(g), int(y), int(p), int(s)
    return pow(theta(g, p, s), -1, p ** (s - 1)) * theta(y, p, s) % (p ** (s - 1))

# exp.py
from sage.all import GF, EllipticCurve, polygen, PolynomialRing, Zmod, factor, vector, Qp, lcm, gcd, xgcd, classical_modular_polynomial
from Crypto.Util.number import getPrime, isPrime, bytes_to_long, GCD, long_to_bytes
import random
from ctf_tools.crypto.padic_DLP import padic_dlp

Phi5 = classical_modular_polynomial(5)

with open("/home/root_xu/CTF/Challenge/2025/H3CTF/isoDream/output.txt", "r") as f:
    pm = int(f.readline())
    exps = eval(f.readline())
    ct = f.readline()

p = gcd(exps[:8]) // 2
assert isPrime(p)
F = PolynomialRing(Zmod(p**3), "x")
x = F.gen()
ct = eval(ct, globals={"y": x})

fp = x**3 + x + 1
fp = fp.change_ring(Qp(p, 3))
roots = [Zmod(p**3)(root) for root in fp.roots(multiplicities=False)]

f = x**3 + x + 1
g = 13 * x + 37
g_eval = g(roots[0])

cl = []
for c in ct:
    c_eval = c(roots[0])
    rsa_c = padic_dlp(int(g_eval), int(c_eval), p, 3)
    cl.append(rsa_c)

e0, e1 = exps[7], exps[8]
c0, c1 = cl[7], cl[8]
_, s, t = xgcd(e0, e1)
c2 = (pow(c0, s, p**2) * pow(c1, t, p**2)) % (p**2)
f = x**2 - c2
f = f.change_ring(Qp(p, 2))
pts = [int(Zmod(p**2)(root)) for root in f.roots(multiplicities=False)]

x = polygen(GF(pm))
F = GF(pm**2, "i", modulus=x**2 + 1)
for pt in pts:
    if pt.bit_length() > 400:
        continue
    j = F(pt)
    ms = Phi5(X = j).univariate_polynomial().change_ring(F).roots(multiplicities=False)
    for m in ms:
        print(long_to_bytes(int(m)))

# H3CTF{0ops_wh4t_a_m4try0shk4_d0LL_mad3_by_m3}

Another Encrypt And Decrypt

题目描述

1 2	Another...? 有问题请联系@ZhouMo hint1 : Forbidden Attack

题目附件

附件太多了，这里就放个压缩包：
handout.zip

接口分析

题目一共有2个重要文件：client.py 和 server.py ，他们共享一个AES-GCM的密钥，提供如下接口：

client.py：
可以发送包含 username 字段的POST数据包，且必须满足 2 <= len(username) <= 10，然后将其封装为
payload_bytes = json.dumps({"route": "/chat", "data": username}).encode("utf-8") 交给AES-GCM加密，然后把 username、nonce、data 发送给server， data 包含密文和消息验证码。

server.py：
可发送POST数据包，且必须包含 username、nonce、data 这3个字段。server会从 data 中提取密文和消息验证码，然后进行解密和验证，如果验证失败会返回错误。成功验证后，

如果解密消息的 routre 字段为 "/chat" 的话，会从 GREETINGS 里随机选一个作为明文。
如果解密消息的 routre 字段为 "/getflag" 的话，则将FLAG作为明文。

然后生成 nonce = username + get_random_bytes(12 - len(username)) ，用它对明文进行加密并返回 data 、 nonce，data 包含密文和消息验证码。

解题思路

题目提示了 forbidden attack，去网上搜搜能发现github上有讲解文章[1]。
就这题顺便学习了一下GCM模式，参考[2]。

首先只能借助client的接口，因为GCM是带验证的模式，我们没有密钥来生成消息验证码。

下面是GCM模式的认证加密过程：

\(C\) 是CRT模式加密的密文，\(A\) 是关联消息，\(H\) 是 \(GHASH\) 的密钥，其中 \(GHASH(H, A, C) = X_{m + n + 1}\)，\(X_i\)定义如下：

由于题目未设置关联信息，所以 \(m=0\)。而且这里使用的 \(\cdot\) 是 \(GF(2^{128})\) 上的乘法，且异或对应 \(GF(2^{128})\) 上的加法，所以 \(GHSH(H, A, C)\)可以在 \(GF(2^{128})\)上表示成如下形式： \[ GHASH(H, A, C) = C_1H^n + C_2H^{n - 1} + \cdots + C_nH \]

消息验证码 \(T\) 可以表示成： \[ T = C_1H^n + C_2H^{n - 1} + \cdots + C_nH + S\\ S = E(K, Y_0) \]

由于初始向量长度是96bits的时候，初始计数器 \(Y_0\) 只与 \(IV\) 有关，这里的 \(IV\) 其实就算服务端使用的 nonce。而服务器使用的 nonce 的前面10bytes字节都是可控的，只有最后2bytes是随机的。那么根据生日攻击的原理，只要我们用恒定的10bytes的 username 多次交互，就很有可能出现 nonce 复用的情况。这样会能到2个消息认证码 \(T,T'\)： \[ \begin{aligned} T = C_1H^n + C_2H^{n - 1} + \cdots + C_nH + S\\ T' = C'_1H^n + C'_2H^{n - 1} + \cdots + C'_nH + S \end{aligned} \]

这是一个二元二次方程组，可以解得 \(H,S\)。之后，为了加密，我们还要获取密钥流，这点非常简单，由于使用CRT模式，将明文与密文异或即可活动密钥流。密钥流是和 \(IV\)相关的，也就是一个 \(IV\) 对应一个密钥流。

一切准备工作都做好后，我们就可以将 route 字段的消息设置为 /getflag，然后选一个前面重复出现过的 nonce，用它对应的密钥流来加密消息，同时用它对应的 \(H,S\) 来计算消息认证码。发送给server后，服务器会将加密的FLAG发送给我们。为了解密，我们要获取到服务器使用的 nonce 对应的密钥流，所以可以接着向client发送消息，来查看是否出现了加密flag使用的 nonce ，由于有2个随机字节，所以每次有 \(\frac{1}{2^{16}}\) 的概率成功。为了提高成功的概率，可以多获得几次加密的flag，比如1000次，这样每次成功的概率会达到 \(\frac{1000}{2^{16}}\)。最后还有一个问题是flag可能比较长，有些通过异或获取的密钥流长度可能不够，解决的方法就是多爆几次。

exp

import requests
import json
import random
from tqdm import trange
from sage.all import GF, PolynomialRing
from os import urandom

MAP_GREETINGS = {
    26: b'{"result": "Hello World!"}', 
    27: b'{"result": "BV1iXXhYpEcw!"}', 
    31: b'{"result": "Capture The Flag!"}', 
    32: b'{"result": "Welcome To H^3CTF!"}',
    39: b'{"result": "Miss Suzuran is our light"}',
    43: b'{"result": "You\'ve found the secret of 42"}'
}

CLIENT = "http://127.0.0.1:5001/"
SERVER = "http://127.0.0.1:5000/"

R = 0xe1000000000000000000000000000000
F = GF(2**128, modulus=[int(i) for i in bin(R)[2:].zfill(128)] + [1], name="x")

def bytes2GF(a: bytes):
    assert len(a) == 16
    return F.from_integer(int(bin(int.from_bytes(a, byteorder='big'))[2:].zfill(128)[::-1], 2))

def GF2bytes(a):
    return int(bin(a.to_integer())[2:].zfill(128)[::-1], 2).to_bytes(16, byteorder='big')

def pad(x: bytes):
    return x + b"\x00" * (-len(x) % 16)

request_data = {"username": "a"*10}

print("search for plain-cipher pairs with the same nonce")
nonces = []
ciphers = []
tags = []
pairs = []
for _ in trange(10000):
    if len(pairs) == 2:
        break
    response = requests.post(CLIENT + "/send", data=request_data)
    data = response.json()
    nonce = bytes.fromhex(data["nonce"])
    cipher = bytes.fromhex(data["data"])[:-16]
    tag = bytes.fromhex(data["data"])[-16:]
    if nonce in nonces:
        idx = nonces.index(nonce)
        if len(cipher) == len(ciphers[idx]):
            continue
        pairs.append((nonce, (cipher, ciphers[idx]), (tag, tags[idx])))
    nonces.append(nonce)
    ciphers.append(cipher)
    tags.append(tag)

print("solve authenticate key H and S")
PR = PolynomialRing(F, ['H', 'S'])
H, S = PR.gens()
roots = []
all_poly = []
for pair in pairs:
    c1, c2 = pair[1]
    nonce = pair[0]
    t1, t2 = pair[2]
    t1, t2 = bytes2GF(t1), bytes2GF(t2)
    polys = []
    for c, t in [[c1, t1], [c2, t2]]:
        X = pad(c) + b"\x00" * 8 + (len(c) * 8).to_bytes(8, byteorder='big')
        assert len(X) % 16 == 0
        f = 0
        for i in range(0, len(X), 16):
            block = bytes2GF(X[i:i+16])
            f = (f + block) * H
        f += S
        f += t
        polys.append(f)
    all_poly.append(polys)
    f1, f2 = polys
    poly = (f1 + f2).univariate_polynomial()
    roots.append([root[0] for root in poly.roots()])

r1, r2 = roots
r1 = set(r1)
r2 = set(r2)
H_ = list(r1.intersection(r2))[0]
S1 = all_poly[0][0](H=H_).univariate_polynomial().roots()[0][0]
S2 = all_poly[1][0](H=H_).univariate_polynomial().roots()[0][0]
S_ = [S1, S2]

print("recv encrypted flag")
def find_maxlen(pairs):
    tmp = [len(pairs[0][1][0]), len(pairs[0][1][1]), len(pairs[1][1][0]), len(pairs[1][1][1])]
    tmp = tmp.index(max(tmp))
    return tmp // 2, tmp % 2

msg = json.dumps({"route": "/getflag"}).encode()
idx0, idx1 = find_maxlen(pairs)
nonce = pairs[idx0][0]
c1 = pairs[idx0][1][idx1]
m1 = MAP_GREETINGS[len(c1)]
xor_key = [i ^ j for i, j in zip(m1, c1)]
assert len(msg) <= len(xor_key)
print(f"{len(xor_key) = }")
print(f"{m1 = }")

cipher =  bytes([i ^ j for i, j in zip(xor_key, msg)])
X = pad(cipher) + b"\x00" * 8 + (len(cipher) * 8).to_bytes(8, byteorder='big')
assert len(X) % 16 == 0

f = 0
for i in range(0, len(X), 16):
    block = bytes2GF(X[i:i+16])
    f = (f + block) * H_
f += S_[idx0]
tag = GF2bytes(f)

data = {
    "username": "a" * 10,
    "nonce": nonce.hex(),
    "data": (cipher + tag).hex()
}

nonces = []
ciphers = []
for _ in trange(1000):
    response_json = requests.post(SERVER + "/encrypted", json=data).json()
    cipher = bytes.fromhex(response_json["data"][:-16])
    nonce = bytes.fromhex(response_json["nonce"])
    
    if nonce not in nonces:
        nonces.append(nonce)
        ciphers.append(cipher)
    else:
        idx = nonces.index(nonce)
        if len(cipher) > len(ciphers[idx]):
            ciphers[idx] = cipher

assert len(ciphers) == len(nonces)

print("finding xor_key for encryptedflag...")
request_data = {"username": "a"*10}
for i in trange(1000):
    response = requests.post(CLIENT + "/send", data=request_data)
    data = response.json()
    nonce = bytes.fromhex(data["nonce"])
    cipher = bytes.fromhex(data["data"])[:-16]
    if nonce in nonces:
        idx = nonces.index(nonce)
        xor_key = [a ^ b for a, b in zip(cipher, MAP_GREETINGS[len(cipher)])]
        flag =  [a ^ b for a, b in zip(ciphers[idx], xor_key)]
        print(bytes(flag))

SSS???

题目描述

你，去学密码了吧，和我不认识的多项式一起。
为什么？那个多项式的模数是多少？为什么要跟她一起去？你怎么没有告诉我？我跟她的确不互素，可是我想了解你啊。我最想了解你，最想待在你身边，我希望我是最亲近你的人，而且我不希望自己不是最亲近你的那个人。明明我就想和你变得更要好，你为什么要这么做？
我！讨厌你在我不知道的有限域里对别的多项式露出笑容！也讨厌你和别的多项式做Shamir Secret Sharing！我希望你只和我分享密钥！只待在我身旁！
密码学也是，我也很想学啊！

Author: Swizzer

题目附件

from random import SystemRandom
from Crypto.Util.number import getPrime, isPrime, bytes_to_long

random = SystemRandom()


class Polynomial:
  def __init__(self, p: int, deg: int):
    self.p = p
    self.deg = deg
    self.coeffs = [random.randint(0, p) for _ in range(self.deg + 1)]

  def evaluate(self, x: int) -> int:
    result = 0
    for coeff in reversed(self.coeffs):
      result = (result * x + coeff) % self.p
    return result

  def get_coeffs(self) -> list[int]:
    return self.coeffs

  def set_coeff(self, idx: int, value: int):
    self.coeffs[idx] = value % self.p


def level1():
  p = 2 * getPrime(512)
  f = Polynomial(p, random.randint(8, 16))
  secret = f.get_coeffs()[0]
  print(f"[*] p: {p}")

  x = int(input("gimme your x > "))
  assert 0 < x < p, "😡No cheating!"

  print(f"[*] share: {f.evaluate(x)}")
  guess = int(input("🔐 > "))
  assert guess == secret, "😎Try harder~"

  flag = open("flag1.txt", "r").read().strip()
  print("🥳🥳🥳")
  print(f"[+] Here's level1's flag: {flag}")


def level2():
  p = int(input("gimme your p > "))
  assert isPrime(p) and p.bit_length() > 128, "😡No cheating!"
  f = Polynomial(p, 16)

  for _ in range(10):
    x = int(input("gimme your x > "))
    assert 0 < x < p, "😡No cheating!"
    print(f"[*] share: {f.evaluate(x)}")

  idx, guess = map(int, input("🔐 > ").split(","))
  secret = f.get_coeffs()[idx]
  assert guess == secret, "😎Try harder~"

  flag = open("flag2.txt", "r").read().strip()
  print("🥳🥳🥳")
  print(f"[+] Here's level2's flag: {flag}")


def level3():
  p = getPrime(512)
  f = Polynomial(p, 9)
  flag = open("flag3.txt", "r").read().strip()
  assert len(flag) == 44
  secret = bytes_to_long(flag.encode())
  f.set_coeff(0, secret)
  xs = [random.randrange(1, p) for _ in range(10)]
  shares = [f.evaluate(x) for x in xs]
  print(f"[*] p: {p}")
  print(f"[*] xs: {xs}")
  for i, share in enumerate(shares, 1):
    print(hex(share)[:-i] + "?" * i)


def challenge():
  print("🥰Welcome to my SSS backroom!")
  while True:
    try:
      choice = int(input("📝Choose a level to escape > "))
      if choice == 1:
        level1()
      elif choice == 2:
        level2()
      elif choice == 3:
        level3()
      else:
        print("🚫Invalid choice.")
        exit(0)
    except Exception as e:
      print(f"😵Error: {e}")


if __name__ == "__main__":
  challenge()

解题思路

一共3个level对应3个flag。level 3为0解题。

level 1

题目流程如下：

生成了一个秘密多项式 \(f\)
\(8<degree(f)<16\)
模数是 \(2p\)
我们可以选一个 \(x\)，求值得到 \(f(x)\)，\(x\) 必须满足 \(0 < x < 2p\)。

要求我们获取 \(f\) 的常数项，这里限制了 \(x\) 不能为 \(0\)，但是可以让 \(x = p\)，这样在模 \(p\)意义下就能得到常数项模 \(p\) 的值，常数项有 \(1/2\) 不超过 \(p\)，所以每次有 \(1/2\)的成功率。

level 2

这次要求模数必须是素数，且秘密多项式的度数为16，而我们只能进行10次求值。题目需要我们得到多项式的任意一个系数就行。

思路是选10个10次单位根 \(\{\omega_i |\omega_i^{10} = 1, i \in \{1, \cdots, 10\}\}\)，而由于是在模 \(p\) 意义下，要想找到10个10次单位根，\(p\) 必须满足 \(10 | p - 1\)，然后我们把10次单位根带入求职可以得到： \[\begin{aligned} f(\omega_i) &= a_0 + a_1\omega_i + a_2\omega_i^2 + \cdots + a_{16}\omega_i^{16}\\ &=(a_0 + a_{10}) + (a_1 + a_{11})\omega_i + \cdots + (a_6 + a_{16})\omega_i^6 + a_7\omega_i^7 + a_8\omega_i^8 + a_9\omega_i^9 \end{aligned} \] 这样刚好10个系数10个方程，可以得到 \(a_7, a_8, a_9\)的精确值。

level 3

这次生成的多项式度是10，而且题目生成了11个 \(x_i, i \in \{0, 1, \cdots, 10\}\)，每个 \(f(x_i)\) 都会抹去 \(4i\) 比特低位。记： \[ y_i = y_i^{(h)} + y_i^{(l)} \]

\[ \mathbf{M} = \begin{pmatrix} 1 & x_0 & \cdots & x_0^{10} \\ 1 & x_1 & \cdots & x_1^{10} \\ \vdots & \vdots & & \vdots \\ 1 & x_{10} & \cdots & x_{10}^{10} \\ \end{pmatrix} \] 则： \[ \mathbf{M} \begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_{10} \end{pmatrix}= \begin{pmatrix} y_0\\ y_1 \\ \vdots \\ y_{10} \end{pmatrix}= \begin{pmatrix} y_0^{(h)}\\ y_1^{(h)} \\ \vdots \\ y_{10}^{(h)} \end{pmatrix}+ \begin{pmatrix} y_0^{(l)}\\ y_1^{(l)} \\ \vdots \\ y_{10}^{(l)} \end{pmatrix} \] 同时左乘\(\mathbf{M}^{-1}\)： \[ \begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_{10} \end{pmatrix}= \mathbf{M}^{-1} \begin{pmatrix} y_0^{(h)}\\ y_1^{(h)} \\ \vdots \\ y_{10}^{(h)} \end{pmatrix}+ \mathbf{M}^{-1} \begin{pmatrix} y_0^{(l)}\\ y_1^{(l)} \\ \vdots \\ y_{10}^{(l)} \end{pmatrix} \] 其中\(a_0\)只有384bits，所以单独考虑这一项： \[ a_0 = b + c_oy_0^{(l)} + c_1y_1^{(l)} + \cdots + c_{10}y_{10}^{(l)} \] 此时可以造格： \[ (y_0^{l}, y_1^{l}, \cdots, y_{10}^{l}, 1, k) \begin{pmatrix} c_0 & 2^{36 + 344} & &\\ c_1 & & 2^{32 + 344} &\\ \vdots & & &\ddots \\ c_{11} &&&&2^{344} \\ b&&&&&2^{384}\\ p \end{pmatrix}= (a_0, 2^{36 + 344}y_0^{(l)}, 2^{32 + 344}y_1^{(l)}, \cdots, 2^{344}y_{10}^{(l)}, 2^{384}) \]

但实际格出来会比 \(a_0\) 小，需要利用flag的已知前缀H3CTF{和后缀}，最后再爆破2字节。

exp

exp没找到就不放了（

isoDream

题目描述

题目附件

解题思路

exp

Another Encrypt And Decrypt

题目描述

题目附件

接口分析

解题思路

exp

SSS???

题目描述

题目附件

解题思路

level 1

level 2

level 3

exp

References