HNCTF-2026

2026-06-08/更新于 2026-07-18

RSA

源码

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

file = open("outext.txt", "w")

m = bytes_to_long(flag.encode())
e = 0x10001

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
s = getRandomRange(2**0, 2**5)
n = p * q * r
hint_1 = powmod(p, r, n)
hint_2 = powmod(r, s - 2, n)

c = powmod(m, e * (s - 1), n)
file.write(f"n={n}\n")
file.write(f"hint_1={hint_1}\n")
file.write(f"hint_2={hint_2}\n")
file.write(f"c={c}\n")

# n = 979979396280795025447159604653924698007421096864863532640467914347154790478966309310242938046375382963295576018108365493749631126829441159428446514913045553768462359812141188437867022522642883215617924930162362975118753135307868195989529952635950471650238440782216155187808858076406173123376307233605251322063056796573051571421373804400742814841380628966244338908899920978345766251241466839953205051967073060065807266111902771444846685228931419177071776202794447
# hint_1 = 63829737789015303255616010995430271442615363334005654136790603132124697763248934614727407142426063514798780422988294297457892974476968909011594056992955895743933371737158975962646294428475380486162081880712675820233377927503162194872237855275106302109770193104087596464371630697812485876577638759333868021626793193900551035852971032420289295901322943785198833653840660632317598841581456445704445974646032512822137015643024549120429185146320086905286336984565780
# hint_2 = 811225663987535096929418484923252315039418484176390289011682551835727122657404871203738500127970361216735459526184706907379779604453737161603694233134616612209864675829711293451990923072581678837181277865189990566773712777076953922847187456309194004847987239678695437936130991596979472315709241564675102503547056625609492959906116295807701067076200192520193721233660324426348223046220024274205328004516104292752500294107591971181194232357501832617229377939678909
# c = 554491127748739273581999967419384543160020010465406113035040735016528899552140169583353294062576591579973382955030891201758740151326341677432402990540380379170704264251101185973670282744523850032981933697291881931773848908998356042585230566838554495089166039238470892330078315451993029959200347825405258393357495512040019534150921164118639093729837315213487083882435472600420840995787008748593481029626822135460873446903992348211665228818922931223995184301813181

分析

由 hint_1 = powmod(p, r, n)，即 $h i n t_{1} \equiv p^{r} (\mod n)$ 。又因为 n = p * q * r，上式可以写成 $h i n t_{1} \equiv p^{r} \equiv 0 (\mod p)$

得到 $gcd (h i n t_{1}, n) = p$ ，此时已经得到一个素数。继续对 hint1 下手。由费马小定理，原式还可以写成 $h i n t_{1} \equiv p^{r} \equiv p (\mod r)$ ，即 $(h i n t_{1} - p) \equiv 0 (\mod r)$ 。但注意，这里的 $h i n t_{1}$ 已经是 $p$ 的倍数，如果直接写 $gcd (h i n t_{1} - p, n)$ ，得到的是 $p \cdot r$ 。

得到 $gcd (h i n t_{1} - p, n) / / p = r$ ，那么 q = n // p // r。

对于 hint_2，它是用来爆破 s 的。如果 powmod(r, s - 2, n) = hint_2，则得到 s。

加密过程中 c = powmod(m, e * (s - 1), n)，意味着在本题中，作用于明文 $m$ 的总加密指数并不是单纯的 $e$ ，而是 $E = e \cdot (s - 1)$ 。在标准的 RSA 中，加密指数必须和 $ϕ (n)$ 互质才能求出唯一的私钥指数 $d$ 。已知 $ϕ (n)$ 是偶数，如果 $(s - 1)$ 恰好也是偶数，那么就会导致 $gcd (E, ϕ (n)) \neq 1$ 。于是有以下两种情况：

二者互质。直接求 $d \equiv E^{- 1} (\mod ϕ (n))$ ， $m \equiv c^{d} (\mod n)$
二者不互质。记 $g = gcd (E, ϕ (n))$ ，令 $E^{'} = E / g$ ，此时 $E^{'}, ϕ (n)$ 一定互质。求局部私钥 $d^{'} = (E^{'})^{- 1} (\mod ϕ (n))$ ，得到中间值 $m^{g} = c^{d^{'}} mod n$ 。由于 $g$ 通常为 $2$ ，且模数 $n = p \cdot q \cdot r$ 很大（1536bits，开方后相当于 96 字节），直接开方即可。

由此写 exp。

EXP

import gmpy2
from Crypto.Util.number import *

n = 979979396280795025447159604653924698007421096864863532640467914347154790478966309310242938046375382963295576018108365493749631126829441159428446514913045553768462359812141188437867022522642883215617924930162362975118753135307868195989529952635950471650238440782216155187808858076406173123376307233605251322063056796573051571421373804400742814841380628966244338908899920978345766251241466839953205051967073060065807266111902771444846685228931419177071776202794447
hint_1 = 63829737789015303255616010995430271442615363334005654136790603132124697763248934614727407142426063514798780422988294297457892974476968909011594056992955895743933371737158975962646294428475380486162081880712675820233377927503162194872237855275106302109770193104087596464371630697812485876577638759333868021626793193900551035852971032420289295901322943785198833653840660632317598841581456445704445974646032512822137015643024549120429185146320086905286336984565780
hint_2 = 811225663987535096929418484923252315039418484176390289011682551835727122657404871203738500127970361216735459526184706907379779604453737161603694233134616612209864675829711293451990923072581678837181277865189990566773712777076953922847187456309194004847987239678695437936130991596979472315709241564675102503547056625609492959906116295807701067076200192520193721233660324426348223046220024274205328004516104292752500294107591971181194232357501832617229377939678909
c = 554491127748739273581999967419384543160020010465406113035040735016528899552140169583353294062576591579973382955030891201758740151326341677432402990540380379170704264251101185973670282744523850032981933697291881931773848908998356042585230566838554495089166039238470892330078315451993029959200347825405258393357495512040019534150921164118639093729837315213487083882435472600420840995787008748593481029626822135460873446903992348211665228818922931223995184301813181
e = 65537

p = gmpy2.gcd(hint_1, n)
r = gmpy2.gcd(hint_1 - p, n) // p
q = n // p // r
s = 0

for i in range(2, 2**5 + 1):
    if pow(r, i - 2, n) == hint_2:
        s = i
        break

phi = (p - 1) * (q - 1) * (r - 1)
E = e * (s - 1)
if gmpy2.gcd(E, phi) == 1:
    d = gmpy2.invert(E, phi)
    m = pow(c, d, n)
    print(long_to_bytes(m))
else:
    g = gmpy2.gcd(E, phi)
    E_prime = E // g
    d = gmpy2.invert(E_prime, phi)
    m_pow = pow(c, d, n)
    # 注意 iroot()函数返回的是元组
    m, exact = gmpy2.iroot(m_pow, g)
    print(long_to_bytes(m))

RSA_pro

源码

from Crypto.Util.number import bytes_to_long, getPrime, inverse
from secret import flag

assert len(flag) == 65
assert flag.startswith(b"H&NCTF{") and flag.endswith(b"}")

P_BITS = 512
LEAK_BITS = 256
BRUTE_BITS = 8
LOW_BITS = P_BITS - LEAK_BITS - BRUTE_BITS
HINT_BYTES = LEAK_BITS // 8
HINT_BITS = LEAK_BITS


class RSAByteOracle:
    def __init__(self):
        self.p = getPrime(P_BITS)
        self.q = getPrime(P_BITS)
        self.n = self.p * self.q
        self.e = 65537
        self.d = inverse(self.e, (self.p - 1) * (self.q - 1))
        self.p_high = self.p >> (BRUTE_BITS + LOW_BITS)
        self.cnt = HINT_BITS
        if bytes_to_long(flag) >= self.n:
            raise ValueError("flag is too large for this RSA modulus")
        self.c_hint = self.encrypt(self.p_high)
        self.c = self.encrypt(flag)

    def encrypt(self, m):
        if isinstance(m, bytes):
            m = bytes_to_long(m)
        return pow(m, self.e, self.n)

    def decrypt(self, c):
        if self.cnt <= 0:
            print("No attempts left.")
            return
        c %= self.n
        m = pow(c, self.d, self.n)
        self.cnt -= 1
        print("bit =", m & 1)
        print(f"Attempts remaining: {self.cnt}")


def show_challenge(rsa):
    print("n =", rsa.n)
    print("e =", rsa.e)
    print("c_hint =", rsa.c_hint)
    print("c =", rsa.c)


MENU = """
[RSA Hint Byte Oracle Console]
[1] Decrypt a ciphertext
[2] Show challenge data
[3] Close

Select action > """


if __name__ == "__main__":
    rsa = None
    while True:
        try:
            opt = int(input(MENU))
        except Exception:
            break

        if opt == 1:
            if rsa is None:
                print("Load the challenge data first.")
                continue
            c = int(input("ciphertext >>> "))
            rsa.decrypt(c)
        elif opt == 2:
            if rsa is None:
                print("Challenge ready.")
                rsa = RSAByteOracle()
            show_challenge(rsa)
        elif opt == 3:
            print("Session closed.")
            break
        else:
            print("Unknown selection.")

分析

一道 Orcale 交互题目。先看 RSAByteOracle 这个类的 decrypt 方法：

def decrypt(self, c):
    if self.cnt <= 0:
        print("No attempts left.")
        return
    c %= self.n
    m = pow(c, self.d, self.n)
    self.cnt -= 1
    print("bit =", m & 1)
    print(f"Attempts remaining: {self.cnt}")

传入一个密文参数 c，使用 类中的 私钥 d 解密后输出明文末位（m & 1），之后 cnt--。而 cnt = HINT_BITS = BRUTE_BITS + LOW_BITS，且 c_hint = pow(p_high, e, n)，联想到这个预言系统和恢复 p_high 有关。提示我们爆破 8 位，那么在 beta = 0.499, epsilon = 0.005 的情况下，小根（未知量）的比特上界就是 249 比特。 $256 - 8 = 248 < 249$ ，理论是可以恢复 p 的。

那么怎么构造密文，从而把 p_high 套出来呢？下面先证明一下 RSA 的乘法同态性质。

已知 $c = m^{e} (\mod n)$ ， $c, m$ 是双射关系。由模运算的性质，两边同时乘以 $k^{e}$ ，就有 $k^{e} \cdot c \equiv (k \cdot m)^{e} (\mod n)$ 。也就是说当我们把密文乘以 $k^{e}$ 之后，解密得到的新明文相当于原明文乘以 $k$ 。来验证一下：

from Crypto.Util.number import *

p = 17
q = 19
n = p * q
e = 7
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

m = 123
c = pow(m, e, n)
print(c)
# c = 251

# 对 c 乘以 2^e，相当于对应的 m 乘以 2
c_new = c * pow(2, e)
m_new = pow(c_new, d, n)
print(m_new)
# m_new = 246

因此，想要只通过返回的明文末位来得到 p_high，我们可以将原密文乘以 $(2^{- i})^{e}$ ，使得明文在右移 $i$ 位后再被截取末位，从而得到 p_high 的第 $i$ 位。乘以 $(2^{- i})^{e}$ ，相当于乘以 $2^{i e}$ 关于 $n$ 的模逆元，即 pow(2, -i*e, n)。但是在操作时要注意模运算的性质：

第一次截取，直接是 $p_{h i g h} & 1$ ，没问题。

但是当第二次及以后乘以 $2^{i}$ 的模逆元（相当于除以 $2^{i}$ ）时，一定会遇到 $p_{h i g h}$ 为奇数的情况。由于 $n$ 是奇数，且模运算没有小数存在，得到的不是 $p_{h i g h} >> 1$ ，而是 $(p_{h i g h} + n) >> 1$ ，这就会导致最终的数据错乱。

举个例子。假设模数 $n = 13, m = 5$ ，2 的模逆元 $i n v_{2} = \frac{n + 1}{2} mod n = 7$ 。

第一轮直接得到 5 在二进制下的末位。
第二轮我们让 $m \times i n v_{2} mod n$ ，即 $5 \times 7 \equiv 35 \equiv 9 (\mod 13)$ 。注意这里得到的是奇数，取末位是 1，但是 5 的倒数第二位二进制是 0，这就产生了矛盾。

该怎么解决这个问题？首先注意到任何正整数都能写成 $2 k + b_{0}$ 的形式，其中 $k = 0, 1, \dots, b = 0 或 1$ 。当 $b_{0} = 0$ 时，这个数乘以模逆元就相当于直接除以 2，没有任何问题。但当 $b_{0} = 1$ 时，直接除以 2 会得到小数，而小数在模环上是不被允许的。此时在 $n$ 为奇数的情况下，乘以 2 的模逆元就相当于这个数加上 $n$ ，再除以 2，这就是所谓污染的来源。但需要注意的是，被污染并不一定保证该位的比特反转，所以不能简单通过判断前一位是否为奇来反转当前位。

记 $m = p_{h i g h}$ 。假设我们正在探测第 $i$ 位，且前面的比特位都是 确认无误的，记它们为 $m_{k n o w n}$ 。于是有

m = m_{h i g h} \times 2^{i} + m_{k n o w n}

靶机接收到我们发送的 payload 之后，实际上就是把 $m$ 乘以 $2^{- i}$ 。对上式两边乘以 $2^{- i}$ ：

m \times 2^{- i} \equiv m_{h i g h} + (m_{k n o w n} \times 2^{- i}) (\mod n)

虽然 $m \times 2^{- i}$ 是可能被污染的（因为模运算的性质），但是它的末位就是靶机返回的 orcale_bit，是已知的。 $m_{k n o w n} \times 2^{- i}$ 的末位也是已知的。所以我们对上式变形：

m_{h i g h} \equiv m \times 2^{- i} - (m_{k n o w n} \times 2^{- i}) (\mod n)

写成取末位（模 2）的形式：

m_{h i g h} (\mod 2) \equiv (m \times 2^{- i} (\mod n)) - (m_{k n o w n} \times 2^{- i} (\mod n)) (\mod 2)

在二进制的不进位运算中，加减法是完全等价的。上式可以简单地用异或写成：

b_{r e a l} = b_{o r a c l e} \oplus b_{p o l l u t i o n}

得到真正的 $m_{h i g h}$ 末位后，把它拼接到 $m_{k n o w n}$ 后面。重复这个方法，直到还原出所有比特。

得到 p_high 之后，本题就变为 $p$ 高位已知的问题，直接 copper 即可。

EXP

# sage
from Crypto.Util.number import *
from pwn import *

HOST, PORT = 
io = remote(HOST, PORT)

# 获取基本数据
io.recvuntil(b"Select action >")
io.sendline(b"2")

io.recvline()
io.recvuntil(b"n = ")
n = int(io.recvline().strip())
io.recvuntil(b"e = ")
e = int(io.recvline().strip())
io.recvuntil(b"c_hint = ")
c_hint = int(io.recvline().strip())
io.recvuntil(b"c = ")
c = int(io.recvline().strip())

# 初始化 p_high
p_high = 0

# 构造 payload
for i in range(256):
    io.recvuntil(b"Select action >")
    io.sendline(b"1")
    io.recvuntil(b"ciphertext >>> ")
    
    # 专门作用于外层密文的模逆元
    inv2_outer = pow(2, -i*e, n)
    payload = (c_hint * inv2_outer) % n
    io.sendline(str(payload).encode())
    io.recvuntil(b"bit = ")
    # 得到未经过校正的 orcale_bit
    orcale_bit = int(io.recvline().strip())
    
    # 对该 bit 修正
    inv2_inner = pow(2, -i, n)
    pollution_bit = (p_high * inv2_inner) % n & 1
    # 在 sage 里，异或是^^
    real_bit = orcale_bit ^^ pollution_bit
    
    # 拼接修正过的 bit
    p_high |= (real_bit << i)
    
# 循环后我们就得到了完整的 256 位 p_high，爆破打 copper
R.<x> = PolynomialRing(Zmod(n))
# 爆破的是 8 个比特，总组合是 2^8 种
for i in range(2^8):
    f = (p_high << 256) + (i << 248) + x
    f = f.monic()
    roots = f.small_roots(X = 2^248, beta = 0.499, epsilon = 0.005)
    if roots:
        p = (p_high << 256) + (i << 248) + int(roots[0])
        if n % p == 0:
            q = n // p
            d = inverse(e, (p - 1) * (q - 1))
            m = pow(c, d, n)
            try:
                print(long_to_bytes(m).decode())
            except:
                pass

校验比特那部分真的卡了我好久…

RSA_pro_max

豪华版 RSA（

源码

from sage.all import *
import random
import string


E = 65537
BASE = 256
OFFSET_R = 64
OFFSET_I = 64
K = 16
PRIME_BITS = 128
PREFIX = b"H&NCTF{"
SUFFIX = b"}"


def gi(a, b=0):
    return (ZZ(a), ZZ(b))


def gadd(x, y):
    return (x[0] + y[0], x[1] + y[1])


def gsub(x, y):
    return (x[0] - y[0], x[1] - y[1])


def gmul(x, y):
    return (x[0] * y[0] - x[1] * y[1], x[0] * y[1] + x[1] * y[0])


def gnorm(x):
    return x[0] * x[0] + x[1] * x[1]


def nearest_div(num, den):
    return ZZ(floor(QQ(num) / QQ(den) + QQ(1) / QQ(2)))


def gaussian_divmod(x, y):
    den = gnorm(y)
    qr = nearest_div(x[0] * y[0] + x[1] * y[1], den)
    qi = nearest_div(x[1] * y[0] - x[0] * y[1], den)
    q = (qr, qi)
    r = gsub(x, gmul(q, y))
    return q, r


def gaussian_mod(x, n):
    return gaussian_divmod(x, n)[1]


def gaussian_mulmod(x, y, n):
    return gaussian_mod(gmul(x, y), n)


def gaussian_powmod(x, e, n):
    x = gaussian_mod(x, n)
    res = gi(1, 0)
    while e:
        if e & 1:
            res = gaussian_mulmod(res, x, n)
        x = gaussian_mulmod(x, x, n)
        e >>= 1
    return res


def random_prime_1mod4(bits):
    while True:
        p = ZZ(random_prime(ZZ(2) ** bits - 1, lbound=ZZ(2) ** (bits - 1)))
        if p % 4 == 1 and gcd(p - 1, E) == 1:
            return p


def random_gaussian_prime(bits):
    # A Gaussian prime whose norm is a rational prime of the requested bit size.
    ell = random_prime_1mod4(bits)
    a, b = two_squares(ell)
    if random.randrange(2):
        b = -b
    return gi(a, b), ell


def build_flag():
    with open("flag.txt", "rb") as f:
        return f.read().strip()


def flag_to_gaussian_poly(flag):
    half = len(flag) // 2
    real = flag[:half]
    imag = flag[half:]
    m = gi(0, 0)
    for i, (a, b) in enumerate(zip(real, imag)):
        m = gadd(m, gmul(gi(a, b), gi(BASE ** i, 0)))
    return m


flag = build_flag()
assert flag.startswith(b"H&NCTF{") and flag.endswith(b"}")
assert len(flag) == 2 * (K + 2)
half = len(flag) // 2

p, np = random_gaussian_prime(PRIME_BITS)
q, nq = random_gaussian_prime(PRIME_BITS)
while np == nq:
    q, nq = random_gaussian_prime(PRIME_BITS)

N = gmul(p, q)
M = flag_to_gaussian_poly(flag)
C = gaussian_powmod(M, E, N)

assert gnorm(M) > gnorm(N)

print(f"e = {E}")
print(f"base = {BASE}")
print(f"offset = ({OFFSET_R}, {OFFSET_I})")
print(f"k = {K}")
print(f"S = ({flag[0]}, {flag[half]})")
print(f"P = ({flag[half - 1]}, {flag[-1]})")
print(f"N = ({N[0]}, {N[1]})")
print(f"C = ({C[0]}, {C[1]})")



# e = 65537
# base = 256
# offset = (64, 64)
# k = 16
# S = (72, 117)
# P = (97, 125)
# N = (-285076339391714133886998989405561241005, -158629281313461832934731017808709616276)
# C = (43768499594212098138374344295509835882, 25834506882323987292031095052053291634)