Mobile wallpaper 1Mobile wallpaper 2Mobile wallpaper 3Mobile wallpaper 4Mobile wallpaper 5Mobile wallpaper 6
Profile Image of the Author
Q1uJu
Announcement
Hope my blog can help you.
Site Statistics
Posts
5
Categories
2
Tags
2
Total Words
13,640
Running Time
0 days
Last Activity
0 days ago
3470 words
17 minutes
HSCCTF 2025 WriteUp
2025-12-13
WriteUp
2025

题目后面带(!)的是指AI出了但还没复现的~

CRYPTO#

Ancient#

base64 -> base32 -> base85 -> base45 -> base62 -> base58

flag{cl@ss1cal_c1pher_@re_really_1nterest1ng}

Sign_in#

题目：

from Crypto.Util.number import *
from gmpy2 import *
import random


get_context().precision = 2048


L = 5
S = getPrime(144)
a = getPrime(32)
b = random.randint(0, S - 1)


def split_and_pad_single_char_rule(msg, L):
    segments = []
    assert L >= 1
    pad_len = L - 1
    for char_idx, char_byte in enumerate(msg):
        char_ascii = char_byte
        pad_bytes = bytes([(char_ascii + i + 1) % 256 for i in range(pad_len)])
        seg_bytes = bytes([char_byte]) + pad_bytes
        segments.append(bytes_to_long(seg_bytes))
    return segments


def encrypt_segment(m_i, a, b, M):
    return (a * m_i + b) % M


flag = "flag{___________________}"
msg_bytes = flag.encode()
m_segments = split_and_pad_single_char_rule(msg_bytes, L)
c_segments = [encrypt_segment(mi, a, b, S) for mi in m_segments]


print(f"a = {a}")
print(f"S = {S}")
print(f"L = {L}")
print(f"C = {c_segments}")
print(f'M = {m_segments}')


'''
a = 3517115977
S = 13338196046628817705384101887069807236659077
L = 5
C = [...]
'''

整体加密流程就是先用split_and_pad_single_char_rule这个特殊的填充算法填充字符，例如f（ASCII 102, 0x66）填充后就是\x66\x67\x68\x69\x6a然后转换为一个大整数m。

然后剩下encrypt_segment就是一个简单的仿射加密，我们这里可以取确定的最后一位flag也就是}来进行填充后，通过一对已知明文密文对和a还有S求解出b，然后就可以求解整个密文组了。

exp.py：

from Crypto.Util.number import inverse


a = 3517115977
S = 13338196046628817705384101887069807236659077
L = 5
C = [...]
m_last = int("".join(hex(ord("}") + i)[2:] for i in range(L)), 16)
b = (C[-1] - a * m_last) % S
a_inv = inverse(a, S)
flag = ""
for c in C:
    m = (c - b) * a_inv % S
    flag += chr(int(hex(m)[2:4], 16))
print(flag)
# flag{s1gn_1n_t0geth5r_xixi}

Math#

题目：

from Crypto.Util.number import *




def gen_rev_sum(m,p):
    sum = 0
    round = 0
    while m > 0:
        digit = m % p
        if round % 2 == 0:
            sum -= digit
        else:
            sum += digit
        m = m // p
        round += 1
    return sum // 2025




e = 65537
p = getPrime(256)
q = getPrime(256)
n = p*q


m1 = getRandomNBitInteger(2048)
m2 = getRandomNBitInteger(2048)
sum1 = gen_rev_sum(m1, p)
sum2 = gen_rev_sum(m2, p)


flag = "flag{--------------------------}"
m = bytes_to_long(flag.encode())


print("m1 =",m1)
print("m2 =",m2)
print("sum1 =",sum1)
print("sum2 =",sum2)
print("n =",n)
print("c =",pow(m,e,n))


'''
m1 = ...
m2 = ...
sum1 = ...
sum2 = ...
n = ...
c = ...
e = 65537
'''

直接看加密使用的gen_rev_sum函数：

  1. 将m进行p进制分解：

    m=d0+d1∗p+d2∗p2+…m=d_0+d_1*p+d_2*p^2+\dots

  2. 计算一个交替和S：

    S=−d0+d1−d2+d3−⋯=∑(−1)i+1diS=-d_0+d_1-d_2+d_3-\cdots=\sum(-1)^{i+1}d_i

  3. 最终返回sum := S // 2025。

由于最后给出的是整除了的值，所以得爆破一下余数r：S = sum * 2025 + r， 0 <= r < 2025。

然后p进制分解可以在模(p + 1)运算上推导：

p≡−1(modp+1)pi≡(−1)i(modp+1)m≡∑di(−1)i(modp+1)S=∑di(−1)i+1≡−∑di(−1)i(modp+1)m+S=∑di(−1)i−∑di(−1)i≡0(modp+1)\begin{aligned} p\equiv -1\pmod{p+1}\\ p^i\equiv (-1)^i\pmod{p+1}\\ m\equiv \sum d_i(-1)^i\pmod{p+1}\\ S=\sum d_i(-1)^{i+1}\equiv -\sum d_i(-1)^i\pmod{p+1}\\ m+S=\sum d_i(-1)^i-\sum d_i(-1)^i\equiv 0\pmod{p+1} \end{aligned}

那么可以用gcd(m1 + S1, m2 + S2)来打出p + 1。

exp.py：

from Crypto.Util.number import long_to_bytes
from gmpy2 import gcd, invert
from tqdm import trange
from sys import exit


m1 = ...
m2 = ...
sum1 = ...
sum2 = ...
n = ...
c = ...
e = 65537
base1 = m1 + sum1 * 2025
base2 = m2 + sum2 * 2025
for r1 in trange(2025):
    v1 = base1 + r1
    for r2 in range(2025):
        v2 = base2 + r2
        g = gcd(v1, v2)
        if g.bit_length() >= 254:
            p = g - 1
            q = n // p
            assert p * q == n
            phi = (p - 1) * (q - 1)
            d = invert(e, phi)
            m = pow(c, d, n)
            print(long_to_bytes(m).decode())
            exit(0)
#  62%|██████▏   | 1254/2025 [00:18<00:11, 68.31it/s]
# flag{Reverse_Sum_Mod_p+i_GCD_2025!}

EZRSA#

题目：

from Crypto.Util.number import *


def tran(n):
    s_bin = bin(n)[2:]
    bit_map = {'0': '10', '1': '01'}
    p_bin = '11' + ''.join([bit_map[bit] for bit in s_bin[1:]])
    return int(p_bin, 2)


def keygen(nbit):
    while True:
       s = getPrime(nbit)
       p = tran(s)
       if not isPrime(p):
          continue
       s_bin = bin(s)[2:].zfill(nbit)
       q_bin = (s_bin[:nbit // 2]
              + '1' * (nbit // 2)
              + s_bin[nbit // 2:]
              + '1' * (nbit // 2))
       q = int(q_bin, 2)
       if isPrime(q):
             return p,q


flag = "flag{____________________________}"
nbit = 256
p, q = keygen(nbit)
m = bytes_to_long(flag.encode())
e= 65537
n = p * q
c = pow(m, e, n)


print(f'n = {n}')
print(f'c = {c}')


"""
n = ...
c = ...
"""

p和q的生成依赖于一个初始的 256 bit 的种子s。

p的生成：

  • 将s转为二进制。
  • 忽略最高位，对其余位进行映射：0->10，1->01。
  • 头部固定拼接11。

q的生成：

  • 将s转为二进制s_bin，s_high = s_bin[:128], s_low = s_bin[128:]。
  • q就是拼接s_high + 1 * 128 + s_low + 1 * 128。

最后得到两个 512 bit 的n的质因数。

解密的话直接从低位开始往上逐比特爆破 + 剪枝就行。

exp.py：

from Crypto.Util.number import inverse, long_to_bytes
from tqdm import trange
from sys import exit


def gen_p_q(s_bits):
    s_bin = "".join(str(b) for b in s_bits)
    # p
    bit_map = {'0': '10', '1': '01'}
    p_bin = '11' + ''.join([bit_map[bit] for bit in s_bin[1:]])
    p = int(p_bin, 2)
    # q
    q_bin = (s_bin[:nbit // 2]
             + '1' * (nbit // 2)
             + s_bin[nbit // 2:]
             + '1' * (nbit // 2))
    q = int(q_bin, 2)
    return p, q


n = ...
c = ...
e = 65537
nbit = 256
s_bits = [0] * nbit
stack = [(255, 0)]
for k in trange(nbit):
    idx = 255 - k
    found = False
    for bit in [0, 1]:
        s_bits[idx] = bit
        p, q = gen_p_q(s_bits)
        check_bits = 2 * (k + 1)
        mask = (1 << check_bits) - 1
        if (p * q) & mask == n & mask:
            found = True
            break
    if not found:
        print(f"Error finding bit at index {idx} (k={k})")
        exit(1)
p, q = gen_p_q(s_bits)
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())
# 100%|██████████| 256/256 [00:00<00:00, 27760.33it/s]
# flag{n1ce_th1s_RSA_I_can_do_it}

Where#

题目：

from Crypto.Util.number import *
import random


flag = "flag{_______________________________}"
m = bin(bytes_to_long(flag.encode()))[2:]
p = getPrime(300)
q = getPrime(300)
n = p * q


R.<x> = PolynomialRing(Zmod(n))


def gen(m):
    C = []
    for bit in m:
        if bit == '0':
            C.append(random.randint(1, n-1))
        else:
            x = random.randint(1, 2^80)
            y = random.randint(1, p-1)
            val = 65537 + x*(1-x) +(q - x)*y + (y + x)*(q + x)
            C.append(R(val))
    return C


c = gen(m)
print(f"n = {n}")
print(f"c = {c}")

主要看gen函数，当m的bit == '1'时，密文：

Ci=65537+x∗(1−x)+(q−x)∗y+(y+x)∗(q+x)C_i=65537+x*(1-x)+(q-x)*y+(y+x)*(q+x)

在模n域下展开：

Ci=65537+x−x2+qy−xy+yq+xy+xq+x2=65537+x+2yq+xq=65537+x+q(2y+x)\begin{aligned} C_i=65537+x-x^2+qy-xy+yq+xy+xq+x^2\\ =65537+x+2yq+xq=65537+x+q(2y+x) \end{aligned}

而本题最后加到C列表里的也是R(val)，所以如果我们模q看：

Ci≡65537+x(modq)C_i\equiv 65537+x\pmod{q}

这说明对于bit = 1的密文，(C_i - 65537)(mod q)一定小于2 ** 80，而对于bit = 0，(C_i - 65537)(mod q)会随机且大概率接近2 ** 300。而第一个密文C[0]一定对应bit = 1，那么我们可以有方程：

f=C0−65537−x0≡0(modq)f=C_0-65537-x_0\equiv 0\pmod{q}

此时x只有2 ** 80，可以直接 Copper 打出q，然后根据x的值反推flag的比特流就行。

exp.py：

# SageMath 10.7
from Crypto.Util.number import long_to_bytes


n = ...
c = [...]
PR.<x> = PolynomialRing(Zmod(n))
target_val = c[0] - 65537
f = target_val - x
roots = f.monic().small_roots(X=2**80, beta=0.27)
x_0 = roots[0]
q = gcd(int(c[0] - 65537 - x_0), n)
m_bits = ""
threshold = 2 ** 81
for i in c:
    x = (i - 65537) % q
    if x < threshold:
        m_bits += "1"
    else:
        m_bits += "0"
print(long_to_bytes(int(m_bits, 2)).decode())
# flag{where_1s_th5_flag_where}

StillRSA#

题目：

from Crypto.Util.number import *
from gmpy2 import *




def gen():
    while(1):
        p1 = getPrime(128)
        p2 = getPrime(512)
        q2 = getPrime(512)
        s = q2 & ((1 << 56) - 1)
        q1 = 2 * p1 + s
        r1 = 2 * q1 + s
        if is_prime(q1) and is_prime(r1):
            n1 = p1 * q1 * r1
            n2 = p2 * q2
            break
    return n1,n2,p1,p2




n1,n2, p1, p2 = gen()
e = 65537


flag = "flag{---------------------------------------}".encode()
m1 = bytes_to_long(flag[: (len(flag)+1) // 2])
m2 = bytes_to_long(flag[(len(flag)+1) // 2 :])


c1 = powmod(m1, e, n1)
c2 = powmod(m2, e, n2)


gift = p2 >> 262


print(f"e = {e}")
print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"p1 = {p1}")
print(f"gift = {gift}")


'''
e = 65537
n1 = ...
n2 = ...
c1 = ...
c2 = ...
p1 = ...
gift = ...
'''

flag分为了两部分。

第一部分

n1=p1q1r1,q1=2p1+s,r1=2q1+sn1/p1=q1r1=(2p1+s)(4p1+3s)=8p12+10p1s+3s2\begin{aligned} n_1=p_1q_1r_1,q_1=2p_1+s,r_1=2q_1+s\\ n_1/p_1=q_1r_1=(2p_1+s)(4p_1+3s)=8p_1^2+10p_1s+3s^2\\ \end{aligned}

已知n1和p1，直接解一元二次方程得到s即可分解出q1和r1。

第二部分

第一部分求出的s是q2的低 56 位，还给出了p2的高 250 位，可以从q2的低 56 位求出p2的低 56 位：

n2=p2q2,n2≡p2⋅s(mod256)p2(mod256)=n2⋅s−1(mod256)\begin{aligned} n_2=p_2q_2,n_2\equiv p_2\cdot s\pmod{2^{56}}\\ p_2\pmod{2^{56}}=n_2\cdot s^{-1}\pmod{2^{56}} \end{aligned}

然后 copper 打出p的中间部分就行。

exp.py：

# SageMath 10.7
from Crypto.Util.number import inverse, long_to_bytes


e = 65537
n1 = ...
n2 = ...
c1 = ...
c2 = ...
p1 = ...
gift = ...
# Part 1
s = var('s')
f = (2 * p1 + s) * (4 * p1 + 3 * s) - n1 // p1
s = int(f.roots(multiplicities=False)[1])
q1 = 2 * p1 + s
r1 = 2 * q1 + s
assert p1 * q1 * r1 == n1
phi1 = (p1 - 1) * (q1 - 1) * (r1 - 1)
d1 = inverse(e, phi1)
m1 = pow(c1, d1, n1)
flag1 = long_to_bytes(m1).decode()
# Part 2
p2h = gift << 262
p2l = inverse(s, 2 ** 56) * n2 % (2 ** 56)
PR.<x> = PolynomialRing(Zmod(n2))
f = p2h + x * 2 ** 56 + p2l
res = f.monic().small_roots(X=2**206, beta=0.4)[0]
p2 = int(p2h + res * 2 ** 56 + p2l)
q2 = n2 // p2
assert p2 * q2 == n2
phi2 = (p2 - 1) * (q2 - 1)
d2 = inverse(e, phi2)
m2 = pow(c2, d2, n2)
flag2 = long_to_bytes(m2).decode()
print(flag1 + flag2)
# flag{Im_a_fw_that_only_crafts_RSA_challenges}

Abg#

题目：

from Crypto.Util.number import *


def ECC(bit):
    g = getPrime(bit)
    a = getPrime(bit)
    b = getPrime(bit)


    E = EllipticCurve(GF(g),[a,b])
    J = E.random_point()
    K = E.random_point()
    L = E.random_point()


    r = getPrime(bit // 2)
    k = getPrime(16)


    s  = r * J
    s1 = r * J + k * L
    s2 = r * k * J


    return L.xy(), s.xy(), s1.xy(), s2.xy(), K.xy()


def RSA(m, s, bit):
    p = getPrime(bit)
    q = getPrime(bit)
    rr = getPrime(bit)
    n = p * q


    gift = pow(rr, rr * (p-1), n)
    enc = pow(m, int(s), n)


    return gift, n, enc


flag = "flag{--------------------------------}"
m = bytes_to_long(flag.encode())


L, s, s1, s2, K = ECC(256)
gift, n, enc = RSA(m, abs(int(s[0] - s[1])), 512)


print("L =", L)
print("s1 =", s1)
print("s2 =", s2)
print("K =", K)
print("enc =", enc)
print("gift =", gift)
print("n =", n)


'''
L = (..., ...)
s1 = (..., ...)
s2 = (..., ...)
K = (..., ...)
enc = ...
gift = ...
n = ...
'''

题目分为一个 ECC 层和一个 RSA 层。

ECC层

随机生成一个椭圆曲线以及三个随机点。接着生成了一个随机秘密点s = r * J和一个很小的随机数k = getPrime(16)，同时给了我们s1和s2：

s1=s+k⋅L,s2=k⋅ss_1=s+k\cdot L,s_2=k\cdot s

首先要通过已知的四个点L，s1，s2，K联立方程来求出g，a，b三个参数。

x1−x2≡(y12−y22)−(x13−x23)(modg)x_1-x_2\equiv (y_1^2 - y_2^2)-(x_1^3 - x_2^3)\pmod{g}

有点类似 LCG 的消元法就可以求出。

接下来看k，k只有 16 位，可以直接爆破找到一个满足以下等式的k：

s2=k⋅(s1−k⋅L)=k⋅s1−k2⋅Ls_2=k\cdot (s_1-k\cdot L)=k\cdot s_1-k^2\cdot L

有k后就可以直接算得s = s1 - k * L。

RSA层

主要点在e = |x - y|，以及给我们的后门gift：

gift≡rrrr(p−1)(modn)⇒gift=(rrrr)p−1≡1(modp)gift\equiv rr^{rr(p-1)}\pmod{n} \Rightarrow gift=(rr^{rr})^{p-1}\equiv 1\pmod{p}

所以有p = gcd(gift - 1, n)。

exp.py：

# SageMath 10.7
from Crypto.Util.number import inverse, long_to_bytes


L = (..., ...)
s1 = (..., ...)
s2 = (..., ...)
K = (..., ...)
enc = ...
gift = ...
n = ...
points = [L, s1, s2, K]
val_list = []
for i in range(len(points) - 1):
    x1, y1 = points[i]
    x2, y2 = points[i + 1]
    lhs = x1 - x2
    rhs = (y1 ** 2 - y2 ** 2) - (x1 ** 3 - x2 ** 3)
    val_list.append((lhs, rhs))
candidates = []
for i in range(len(val_list) - 1):
    v1 = val_list[i]
    v2 = val_list[i + 1]
    res = v1[1] * v2[0] - v2[1] * v1[0]
    candidates.append(abs(res))
g = candidates[0]
for c in candidates[1:]:
    g = gcd(g, c)
lhs, rhs = val_list[0]
a = (rhs * inverse_mod(lhs, g)) % g
x, y = L
b = (y ** 2 - x ** 3 - a * x) % g
E = EllipticCurve(GF(g), [a, b])
P_L = E(L)
P_s1 = E(s1)
P_s2 = E(s2)
k = None
for k_guess in primes(2, 65536):
    term1 = k_guess * P_s1
    term2 = (k_guess * k_guess) * P_L
    check = term1 - term2
    if check == P_s2:
        k = k_guess
        break
P_s = P_s1 - k * P_L
s_coords = P_s.xy()
e = abs(int(s_coords[0]) - int(s_coords[1]))
p = gcd(gift - 1, n)
q = n // p
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(enc, d, n)
print(long_to_bytes(m).decode())
# flag{this_1s_a_so_EZ_Ecc_and_RSA_}

1ZRSA(!)#

题目：

from Crypto.Util.number import *
from gmpy2 import *
import random


def RSA(m,nbit):
    while True:
        p, q, e = getPrime(nbit), getPrime(nbit), getPrime(nbit)
        n = p * q
        phi_n = (p - 1) * (q - 1)
        d = int(inverse(e, phi_n))
        if len(bin(d)[2:]) == 1024:
            break


    keep_bits = nbit * 2 - 100
    mask = int((1 << keep_bits) - 1)
    d_ = d & mask
    c = powmod(m, e, n)
    return c,n,e,d_


def gen(nbit):


    c, n, e, d_ = RSA(m, nbit)
    N = getPrime(nbit * 2)
    t = random.randint(1, nbit * 2 - 1)
    C = [random.randint(0, N - 1) for _ in range(t - 1)] + [powmod(d_,1,N)]
    R.<x> = GF(N)[]
    f = R(0)
    for i in range(t):
        f += x ** (t - i - 1) * C[i]
    enc = [(a, f(a)) for a in [random.randint(1, N - 1) for _ in range(t)]]


    with open("output.txt", "w", encoding="utf-8") as f_out:
        f_out.write(f"c = {c}\n")
        f_out.write(f"n = {n}\n")
        f_out.write(f"e = {e}\n")
        f_out.write(f"N = {N}\n")
        f_out.write(f"enc = {enc}\n")


flag = "flag{-------------------------------}"
m = bytes_to_long(flag.encode())


if __name__ == "__main__":
    gen(512)

主要考察了d的低位泄露以及Shamir的秘密共享方案。

秘密共享可以直接利用 SageMath 的lagrange_polynomial函数恢复P(x)，然后计算P(0)得到d_low。

后面d的低位泄露具体其实有点不是很清楚了，之前的二元脚本打不通，翻到了鸡块师傅的博客然后找到论文，让Gemini根据论文写的脚本了，之后还得再好好学习学习，附个论文链接。

exp.py：

# SageMath 10.7
from sage.all import *
import time
from math import isqrt
from Crypto.Util.number import inverse, long_to_bytes


def solve_bloemer_may_heavy(n, e, d_low, leak_bits):
    print(f"[*] Initializing HEAVY Attack (Leak: {leak_bits} bits)...")


    # 1. 构造模数 M
    M_shift = 2**leak_bits
    Modulus = e * M_shift
    C = (e * d_low - 1) % Modulus


    # 2. 定义环和变量
    PR = PolynomialRing(ZZ, names=['y', 'z'])
    y, z = PR.gens()


    # f(y, z) = y(N - z) - C
    f = y * (n - z) - C


    # 3. 设定界限
    Y_bound = e                  # k < e
    Z_bound = isqrt(n) * 3       # z approx 2*sqrt(N)


    print(f"[*] Modulus bits: {Modulus.nbits()}")
    print(f"[*] Unknowns product: {(Y_bound * Z_bound).nbits()}")
    print(f"[*] Ratio: {(Y_bound * Z_bound).nbits() / Modulus.nbits():.4f}")


    # 4. 构造 Lattice (高强度参数)
    # 提升 m 到 6，t 到 3
    m = 6
    t = 3


    poly_list = []


    # y-shifts: y^j * M^i * f^(m-i)
    for i in range(m + 1):
        for j in range(i + 1):
            g = (y**j) * (Modulus**i) * (f**(m - i))
            poly_list.append(g)


    # z-shifts: z^j * M^i * f^(m-i)
    for i in range(m + 1):
        for j in range(1, t + 1):
            h = (z**j) * (Modulus**i) * (f**(m - i))
            poly_list.append(h)


    # 去重
    poly_list = sorted(list(set(poly_list)), key=lambda p: p.degree())


    # 构建矩阵 (修复 Deprecation Warning)
    seq = Sequence(poly_list, PR)
    try:
        B, monomials = seq.coefficients_monomials()
    except AttributeError:
        B, monomials = seq.coefficient_matrix()
    monomials = vector(monomials)


    # 权重平衡
    factors = [monomial(Y_bound, Z_bound) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)


    print(f"[*] Lattice dimension: {B.nrows()}x{B.ncols()}")
    print(f"[*] Running LLL (hold tight, this may take 1-2 mins)...")


    start = time.time()
    B = B.dense_matrix().LLL()
    print(f"[*] LLL finished in {time.time() - start:.2f}s")


    # 还原
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)


    # 5. 提取根
    print("[*] Extracting roots...")


    vecs = []
    for i in range(B.nrows()):
        h_vec = B.row(i)
        h_poly = h_vec * monomials


        if h_poly != 0 and not h_poly.is_constant():
            # 强制类型转换为 ZZ 上多项式
            h_poly = h_poly.change_ring(ZZ)
            # 归一化 (去除公因子)
            h_poly = h_poly // h_poly.content()
            vecs.append(h_poly)


    # 尝试策略 1: 简单的单变量因子
    for h in vecs:
        try:
            for fac, _ in h.factor():
                if fac.degree(z) == 1 and fac.degree(y) == 0:
                    val = -fac.constant_coefficient() / fac.leading_coefficient()
                    if val in ZZ: return int(val)
        except: pass


    # 尝试策略 2: Sylvester Resultant
    if len(vecs) >= 2:
        print("[*] Trying Sylvester Resultant...")
        # 尝试前几对向量
        for i in range(min(3, len(vecs))):
            for j in range(i + 1, min(4, len(vecs))):
                h1 = vecs[i]
                h2 = vecs[j]
                try:
                    res_matrix = h1.sylvester_matrix(h2, y)
                    res_poly = res_matrix.det()
                    if res_poly != 0 and res_poly.degree(z) > 0:
                        roots = res_poly.univariate_polynomial().roots()
                        for root, _ in roots:
                            if root in ZZ: return int(root)
                except: pass


    # 尝试策略 3: Groebner Basis (作为最后的兜底)
    if len(vecs) >= 2:
        print("[*] Trying Groebner Basis (Fallback)...")
        try:
            # 在 QQ 上计算 GB
            PR_QQ = PolynomialRing(QQ, names=['y', 'z'])
            ideal_polys = [PR_QQ(p) for p in vecs[:3]] # 取前3个
            I = Ideal(ideal_polys)
            gb = I.groebner_basis()


            for p in gb:
                # 寻找 z - z0
                if p.degree(PR_QQ.gen(1)) == 1 and p.degree(PR_QQ.gen(0)) == 0:
                    val = -p.constant_coefficient() / p.leading_coefficient()
                    if val in ZZ: return int(val)
        except Exception as e:
            print(f"[-] GB failed: {e}")


    return None


c = ...
n = ...
e = ...
N = ...
enc = [...]
R_field = GF(N)
points = [(R_field(x), R_field(y)) for x, y in enc]
poly_shamir = PolynomialRing(R_field, 'w').lagrange_polynomial(points)
d_low = int(poly_shamir(0))
leak_bits = 924
z_val = solve_bloemer_may_heavy(n, e, d_low, leak_bits)
s = z_val + 1
diff = isqrt(s ** 2 - 4 * n)
p = (s + diff) // 2
q = (s - diff) // 2
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())
# flag{Coppersmith_Lagrange_RSA_7f9d2b4e0a3c5e8g1h6j0k9l3m5n2p4q}
HSCCTF 2025 WriteUp
https://q1uju.cc/posts/hscctf-2025-writeup/writeup/
Author
Q1uJu
Published at
2025-12-13
License
CC BY-NC-SA 4.0

Some information may be outdated

ISCTF 2025 WriteUp
Hello World!
© 2025 Q1uJu. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 7.6