Misay's blog

L3HCTF2025

发表于 更新于 分类于
L3HCTF2025-复现

写在前面

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

math_problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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 = 
'''

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

由三个因子构成

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

OK，我们求出来了，这里当时尝试直接转化到模下的RSA，因为 所以 我们已知对于素数，有 那么可以去计算 可以计算出 恰好这里就小于,直接就解出来了，我们来试试如何按照出题人的预期用上这个，为了叙述方便 我们用代替,我们有 这里显然,我们考虑二项式定理展开，对超过3的项都会被模出0，整理不难得到 注意到这个方程我们只有不知道 而且最多400位，大概是的，我们可以考虑尝试解这个方程，直接来求

稍微整理一下就是 但貌似这个的时间复杂度不好把握哈，但是呢我们发现还能往下来化 我们转化到模下进行 得到这个之后，我们不妨设,在上述方程中对取除数，很容易就得到 这样我们就解出来了，现在我们已知 也就是的低400位，来发Copper,注意要换到模的环下进行

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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?}

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

EzECDSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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")

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

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

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

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

我们能消去,即有

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

我们来尝试消去

即整理出关于若干组的方程

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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

主要划分为两个部分

  • 参数准备

    我们生成512位的素数 随后构建 ,接着是生成私钥的过程，满足 而我们已知的位数为1021位

  • 加密

    • 构建取模环

    • 构建多项式环

      1
      2
      P = PolynomialRing(R, 't')
      t = P.gen()

      构建了一个系数定义在模环下，以为不定元的多项式环，即

    • 对多项式环取商

      1
      Q = P.quotient(t**n - r)

      相当于在多项式环的域上，再有 把多项式环压缩到次幂之下

    • 把作为系数嵌入

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

      即

    • 指数运算

      1
      2
      c_poly = m_poly ** e

      在商环中把多项式提升到次幂

    • 运算结果

      最终lift出来的多项式就是

谔这里给了的位数就直接连分数手法来解就ok，值得注意的是这里的乘法群的阶你可以考虑从提升到来卡好这个边界关系即 直接考虑连分数攻击来找即可，随后直接用私钥解密，exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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