L3HCTF2025 • Misay's blog

写在前面#

在从bw回汉的高铁上尝试了一下，题目知识点都比较熟悉，难度也很适中，成功AK了，不过还有很多值得细细琢磨的点，本文来尝试复现分析一下

math_problem#

import gmpy2
from gmpy2 import *
from Crypto.Util.number import *
from random import randint
from gmpy2 import invert
from scret import flag

def myfunction(num):
    output = 0
    output=num**3
    return output

if __name__ == '__main__':
    flag_len = len(flag)
    p, q = getPrime(512), getPrime(512)

    while True:
        r = getPrime(512)
        R = bytes_to_long(str(r).encode())
        if isPrime(R):
            break

    n = p * q * r
    hint1 = R * r
    mod = myfunction(n)
    hint2 = pow(3*n+1, p % (2 ** 400), mod)
    m = bytes_to_long(flag)
    c = pow(m, 65537, n)

    print('All data:')
    print(f'n = {n}')
    print(f'c = {c}')
    print(f'hint1 = {hint1}')
    print(f'hint2 = {hint2}')


'''
All data:
n = 
c = 
hint1 = 
hint2 = 
'''

python

自己的解法感觉应该是非预期了，有点难绷,先讲一下

$n$ 由三个因子构成 $n=p\;\cdot\;q\;\cdot\;r$

它给了你

h_1=r\;\cdot\;R

当然这里的 $R$ 是把 $r$ 转字符串之后进行一个long_to_bytes的一个乘算，注意到这个函数是 $r$ 转大端序之后拼接每一位的十六进制得到的，也就是说 $h_1$ 是随着 $r$ 递增的，那么本意可能是让我们去做一个二分来求出 $r$ ?的确可行但是这里也给了 $n$ ，直接做一个gcd就可以了…总之都贴一下吧

from Crypto.Util.number import bytes_to_long, long_to_bytes

hint1 = ...
def find_r(hint1):
    low = 1 << 511  # 2^511
    high = (1 << 512) - 1  # 2^512 - 1

    while low <= high:
        mid = (low + high) // 2
        s = str(mid)
        R = bytes_to_long(s.encode())
        product = mid * R

        if product == hint1:
            return mid
        elif product < hint1:
            low = mid + 1
        else:
            high = mid - 1

    return None

r = find_r(hint1)
print("Found r:", r)
print(hint1 % r)
# Found r: ...
# 0

python

OK，我们求出来了 $r$ ，这里当时尝试直接转化到模 $r$ 下的RSA，因为

r\;|\;n

所以

c\equiv\;m^e\;mod\;r

我们已知对于素数 $r$ ，有

\phi_r=r-1

那么可以去计算

d_r\equiv\;e^{-1}\;mod\;\phi_r

可以计算出

m\equiv\;c^{d_r}\;mod\;r

恰好这里 $m$ 就小于 $r$ ,直接就解出来了，我们来试试如何按照出题人的预期用上这个 $h_2$ ，为了叙述方便我们用 $s$ 代替 $p\;mod\;2^{400}$ ,我们有

h_2\equiv\;(3n+1)^s\;mod\;n^3

这里显然 $s>>3$ ,我们考虑二项式定理展开，对 $3n$ 超过3的项都会被模出0，整理不难得到

h_2\equiv\;1\;+\;s\;\cdot\;3n\;+\;\frac{s(s-1)}{2}\;\cdot\;9n^2\;mod\;n^3

注意到这个方程我们只有 $s$ 不知道而且 $s$ 最多400位，大概是 $n^3$ 的 $\frac{1}{12}$ ，我们可以考虑尝试解这个方程，直接来求 $s$

稍微整理一下就是

\frac{9n^2}{2}s^2+(3n-\frac{9n^2}{2})s+1-h_2\equiv0\;mod\;n^3

但貌似这个的时间复杂度不好把握哈，但是呢我们发现还能往下来化

h_2-1\equiv\;s\;\cdot\;3n\;+\;\frac{s(s-1)}{2}\;\cdot\;9n^2\;\;mod\;n^3

我们转化到模 $n$ 下进行

h_2-1\equiv\;0\;mod\;n

得到这个之后，我们不妨设 $h_2-1=kn$ ,在上述方程中对 $n$ 取除数，很容易就得到

\frac{h_2-1}{n}\equiv3s\;mod\;n

这样我们就解出来了 $s$ ，现在我们已知

s\equiv\;p\;mod\;2^{400}

也就是 $p$ 的低400位，来发Copper,注意要换到模 $p*q$ 的环下进行

exp

n = ...
c = ...
hint1 = ...
hint2 = ...

r = gcd(n,hint1)
nn = n // r
R = Zmod(nn)
P.<x> = PolynomialRing(R)
ss = ((hint2-1)//n) % n
s = ss // 3
p_low = s
print(s)

f = x * 2^400 + p_low
f = f.monic()
res = f.small_roots(X = 2^112, beta = 0.5)
p_high = int(res[0])
# print(p_high.bit_length())
p = int(p_high) * 2^400 + p_low
# print(nn % p) 0
q = nn // p
phi = (p - 1) * (q - 1) * (r - 1)
d = inverse_mod(65537, phi)
print(long_to_bytes(pow(c, d, n)))
# L3HCTF{1s_4h1s_r3a11y_m4th?}

python

想法是好的大火也更容易做出来双赢（）

EzECDSA#

import hashlib
import random
from ecdsa import NIST256p, SigningKey

class FlawedNonceGenerator:
    def __init__(self, n):
        self.n = n
        self.a = random.randrange(1, n)
        self.b = random.randrange(1, n)
        self.c = random.randrange(1, n)
        self.last_k = random.randrange(1, n)

    def generate_nonce(self):
        current_k = self.last_k
        next_k = (self.a * current_k**2 + self.b * current_k + self.c) % self.n
        self.last_k = next_k
        
        return current_k


curve = NIST256p
n = curve.order
private_key = SigningKey.from_secret_exponent(random.randrange(1, n), curve=curve)
d = private_key.privkey.secret_multiplier
public_key = private_key.get_verifying_key()

messages = [
    b"Hello player, welcome to L3HCTF 2025!",
    b"This is a crypto challenge, as you can probably tell.",
    b"It's about ECDSA, a very... robust algorithm.",
    b"I'm sure there are no implementation flaws whatsoever.",
    b"Anyway, here are your signatures. Good luck!",
    f"Oh, and the flag is L3HCTF{{{d}}}. Don't tell anyone!".encode(),
]
nonce_generator = FlawedNonceGenerator(n)
f = open('signatures.txt', 'w')

for i in range(6):
    k = nonce_generator.generate_nonce()
    message = messages[i]
    h = int.from_bytes(hashlib.sha256(message).digest(), 'big')
    R = k * curve.generator
    r = R.x() % n
    s_inv = pow(k, -1, n)
    s = (s_inv * (h + d * r)) % n
    f.write(f"h: {h}, r: {r}, s: {s}\n")

python

$k$ 相关的ECDSA签名问题，搜索神秘关键词related nonce可以找到一篇paper，贴一下

https://eprint.iacr.org/2023/305.pdf ↗

这里 $k$ 之间是一个二次非线性相关，定位到paper的关键部分，即

这里我们能把每个 $k_i$ 写成含未知数 $d$ 的一个线性方程，即

k_i=\frac{h_i}{s_i}+\frac{r_i}{s_i}\;d

k_j=\frac{h_j}{s_j}+\frac{r_j}{s_j}\;d

我们能消去 $d$ ,即有

k_j=\frac{r_js_i}{r_is_j}k_i+\frac{h_jr_i-h_ir_j}{r_is_j}

paper利用了这里系数 $a_i$ 相对不变好消去的关键

我们来尝试消去 $a_i$

即整理出关于若干组 $k_{ij}$ 的方程

而 $k_{ij}$ 又和 $d$ 直接相关，也就是整理出了关于 $d$ 的四次方程直接解就OK，exp如下

# from Crypto.Util.number import *
# from ecdsa import NIST256p
# with open("signatures.txt", "r") as f:
#     data = f.read()
#     h = []
#     r = []
#     s = []
#     lines = data.strip().split('\n')
#     for line in lines:
#         parts = line.split(', ')
#         hh = parts[0].split(': ')[1]
#         h.append(int(hh))
#         rr = parts[1].split(': ')[1]
#         r.append(int(rr))
#         ss = parts[2].split(': ')[1]
#         s.append(int(ss))


h = [5832921593739954772384341732387581797486339670895875430934592373351528180781, 85517239535736342992982496475440962888226294744294285419613128065975843025446, 90905761421138489726836357279787648991884324454425734512085180879013704399530, 103266614372002123398101167242562044737358751274736728792365384600377408313142, 9903460667647154866199928325987868915846235162578615698288214703794150057571, 54539896686295066164943194401294833445622227965487949234393615233511802974126]
r = [78576287416983546819312440403592484606132915965726128924031253623117138586396, 60425040031360920373082268221766168683222476464343035165195057634060216692194, 75779605492148881737630918749717271960050893072832415117470852442721700807111, 89519601474973769723244654516140957004170211982048028366151899055366457476708, 17829304522948160053211214227664982869100868125268116260967204562276608388692, 66428683990399093855578572760918582937085121375887639383221629490465838706027]
s = [108582979377193966287732302562639670357586761346333866965382465209612237330851, 27924509924269609509672965613674355269361001011362007412205784446375567959036, 72740499400319841565890543635298470075267336863033867770902108413176557795256, 23639647021855356876198750083669161995553646511611903128486429649329358343588, 74400189461172040580877095515356365992183768921088660926738652857846750009205, 25418035697368269779911580792368595733749376383350120613502399678197333473802]


# curve = NIST256p
# n = curve.order
# print(n)
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
PR.<x> = PolynomialRing(GF(n))
def k(i, j):
    f = ((r[i] * s[j] - r[j] * s[i]) * x + h[i] * s[j] - h[j] * s[i]) * inverse_mod(s[i], n) * inverse_mod(s[j], n)
    return f


equation = (k(1, 2) * k(1, 2) - k(2, 3) * k(0, 1)) * k(1, 3) * k(2, 3) - (k(2, 3) * k(2, 3) - k(3, 4) * k(1, 2)) * k(0, 1) * k(0, 2)
res = equation.roots()
d = res[0][0]
flag = "L3HCTF{" + f"{d}" + "}"
print(flag)

RRRSSSAAA#

from sage.all import *

from secret import flag

def generate_vulnerable_key(bits=1024):
    p_bits = bits // 2
    q_bits = bits - p_bits

    while True:
        p = random_prime(2**(p_bits), lbound=2**(p_bits-1))
        q = random_prime(2**(q_bits), lbound=2**(q_bits-1))
        if p != q and p > q and p < 2*q:
            break
            
    N = p * q
    phi = (p**4 - 1) * (q**4 - 1)

    d_bits = 1024
    d_bound = 2**d_bits

    while True:
        d_small = randint(2, d_bound)
        d = phi - d_small
        if gcd(d, phi) == 1:
            if d_small.bit_length() == 1021:
                break

    e = inverse_mod(d, phi)
    
    return N, e

def encrypt(m, N, e):
    n = 4
    r = 2
    R = Integers(N)
    P = PolynomialRing(R, 't')
    t = P.gen()
    Q = P.quotient(t**n - r)

    m_poly = Q([m, 0, 0, 0])

    c_poly = m_poly ** e

    return c_poly.lift()

if __name__ == "__main__":
    N, e = generate_vulnerable_key()
    m = int.from_bytes(flag, 'big')
    c = encrypt(m, N, e)

    print(f"N = {N}")
    print(f"e = {e}")
    print(f"c = {c}")

# N = 99697845285265879829811232968100099666254250525000506525475952592468738395250956460890611762459685140661035795964867321445992110528627232335703962897072608767840783176553829502743629914407970206513639916759403399986924602596286330464348286080258986075962271511105387188070309852907253486162504945490429185609
# e = 74900336437853271512557457581304251523854378376434438153117909482138661618901386551154807447783262736408028580620771857416463085746907317126876189023636958838207330193074215769008709076254356539808209005917645822989554532710565445155350102802675594603406077862472881027575871589046600011223990947361848608637247276816477996863812313225929441545045479384803449990623969591150979899801722841101938868710054151839628803383603849632857020369527380816687165487370957857737696187061619496102857237814447790678611448197153594917852504509869007597997670022501500067854210261136878917620198551551460145853528269270832725348151160651020188255399136483482428499340574623409209151124687319668989144444549871527949104436734300277004316939985015286758651969045396343970037328043635061226100170529991733947365830164811844853806681198818875837903563263114249814483901121700854712406832325690101810786429930813776784979083590353027191492894890551838308899148551566437532914838098811643805243593419063566975400775134981190248113477610235165151367913498299241375039256652674679958159505112725441797566678743542054295794919839551675786573113798857814005058856054462008797386322048089657472710775620574463924678367455233801970310210504653908307254926827
# c = 98460941530646528059934657633016619266170844887697553075379408285596784682803952762901219607460711533547279478564732097775812539176991062440097573591978613933775149262760936643842229597070673855940231912579258721734434631479496590694499265794576610924303262676255858387586947276246725949970866534023718638879

plaintext

主要划分为两个部分

参数准备

我们生成512位的素数 $p\;\;\;q$ 随后构建 $\phi\;=\;(p^4-1)(q^4-1)$ ,接着是生成私钥 $d$ 的过程，满足
$d=\phi-d_s$
而我们已知 $d_s$ 的位数为1021位
加密
- 构建取模环 $R$
- 构建多项式环 $P$
```
P = PolynomialRing(R, 't')
t = P.gen()
```
  python
  构建了一个系数定义在模 $N$ 环下，以 $t$ 为不定元的多项式环，即
  $P = R[t] = \{a_0 + a_1 t + a_2 t^2 + \dots + a_k t^k \mid a_i \in R\}$
- 对多项式环 $P$ 取商 $Q=\frac{P}{t^n-r}$
```
Q = P.quotient(t**n - r)
```
  python
  相当于在多项式环 $P$ 的域上，再有
  $t^n\equiv\;r\;mod\;t^n-r$
  把多项式环压缩到 $n$ 次幂之下
- 把 $m$ 作为系数嵌入
```
m_poly = Q([m, 0, 0, 0])
```
  python
  即
  $m \mapsto m + 0t + 0t^{2} + 0t^{3}$
- 指数运算
```
c_poly = m_poly ** e
```
  py
  在商环 $Q$ 中把多项式 $m_{poly}$ 提升到 $e$ 次幂
  $(m + 0\,t + 0\,t^2 + 0\,t^3)^e=\sum_{k_0+k_1+k_2+k_3=e}\binom{e}{k_0,k_1,k_2,k_3}\;m^{k_0}(0)^{k_1}(0)^{k_2}(0)^{k_3}\;t^{k_1+2k_2+3k_3}.$
- 运算结果
  
  最终lift出来的多项式就是 $m^e$

谔这里给了 $d_s$ 的位数就直接连分数手法来解就ok，值得注意的是这里的乘法群的阶你可以考虑从 $N$ 提升到 $N^4$ 来卡好这个边界关系即

d\sim\frac{1}{3}N^{\frac{1}{4}}

直接考虑连分数攻击 $\frac{e}{N^4}$ 来找 $d_s$ 即可，随后直接用私钥解密，exp

from Crypto.Util.number import *
N = 
e = 
c = 

def wienerAttack(N, e):
    res = []
    rres = []
    cf = continued_fraction(e / N)
    convers = cf.convergents()
    for pkds in convers:
        pk, pds = pkds.as_integer_ratio()
        if pk == 0:
            continue
        if (e * pd + 1) % pk != 0:
            continue
        if pds.bit_length() == 1021:
            pphi = (e * pds + 1) // pk
            res.append(pphi - pds)
            rres.append(pphi)
        return res, rres
res = wienerAttack(N^4, e)
d = res[0][0]
phi = res[0][0]
n = 4
r = 2
R = Integers(N)
P = PolynomialRing(R, 't')
t = P.gen()
Q = P.quotient(t**n - r)
c_poly = Q([c, 0, 0, 0])
m_poly = c_poly ** d
m = m_poly.lift()
print(long_to_bytes(m))
# b'L3HCTF{d2f790fb12af914d7a34055d73f3c1bdc484cfcd75c4d4a493e31af5791ff309}'

类似的思路可以见DASCTF的EzMatrix