2025 能源 CTF

没有报名参赛，赛后讨了份题目看看，都是比较基础的知识点，随便记录下。

NumberTheory

from Crypto.Util.number import *import hintflag=b'xxx'e=65537p=getPrime(512)q=getPrime(512)n=p*qm=bytes_to_long(flag)c=pow(m,e,n)k=getPrime(1024)assert hint + 233 * k == 233 * k * pprint(n)print(c)print(hint)# n = # c =# hint =

题目数据就不贴了，没有什么特殊的点，自己本地生成也是一样的。

基于 RSA 公钥加密，额外给出 hint 满足 hint + 233 * k == 233 * k * p，其中 k 是一个 1024 比特未知素数。

应该是 经典的利用费马小定理凑出 kp 然后和 n 做 GCD 从而做到分解 的题目。

根据费马小定理，对于任意与 p 互素的数 a，有 

因此

所以随便取一个 a，做一个 GCD(pow(a,hint,n)-1,n) 就好

后面就不用多说了。

easy_lwe

from Crypto.Util.number import *from secrets import flagassert len(flag) == 38p = getPrime(512)m = getPrime(512)while m > p:    m = getPrime(512)aa = []cc = []bb = []for i in range(30):    a = getPrime(512)    b = getPrime(400)    c = (a * m + b) % p    aa.append(a)    cc.append(c)    bb.append(b)enc = pow(m,flag,p)print(f'p = {p}')print(f'aa = {aa}')print(f'cc = {cc}')print(f'enc = {enc}')# p = 0x83b05d231fd40ff8ca26b4fb8136dc920754c14412960ce2ec700457861d48fe74f3958fc3a153f77a23fb850ecf0ac1e9722c71b6cc8a104b372cc17bf1528f# aa = []# cc = []# enc = 

题目给出 30 组 ，其中  已知， 未知但是  只有 400 比特

那么就是一个 经典的 HNP (Hidden number problem)

p = aa = []cc = []# Lattice of HNP # 
# [0 p ....       ]# [    ....       ]# [a a .... K/p   ]# [c c ....     K ]length = len(aa)target_verctor_length = 400K = 2**target_verctor_lengtha = []for i in range(length):    b = []for j in range(length):if i == j:            b.append(p)else:            b.append(0)    b.append(0)    b.append(0)    a.append(b)b = []for i in range(length):    b.append(aa[i])b.append(K/p)b.append(0)a.append(b)b = []for i in range(length):    b.append(cc[i])b.append(0)b.append(K)a.append(b)M = Matrix(QQ,a)L = M.LLL()for i in range(L.ncols()):if L[i][-1] == 2** target_verctor_length:        m0 = (cc[0] - abs(L[i][0]))/aa[0] % p        m1 = (cc[1] - abs(L[i][1]))/aa[1] % passert m0 == m1        print(f"m = {m}")break

然后 enc = pow(m,flag,p)，需要解一个 DLP (Discrete Logarithm Problem) 。这里贴出了 p，显然这并不是一个随便选取的 p

我们可以在 factordb.com 上直接查到 p-1 的分解。又是 经典的 Pohlig-Hellman 算法解离散对数问题

6897108443...78<154> = 2 · 3 · 193 · 877 · 2663 · 662056037 · 812430763 · 814584769 · 830092927 · 849943517 · 969016409 · 1000954193<10> · 1022090869<10> · 1048277339<10> · 7938574420...73<64>

虽然 p-1 有一个很大的因子，不过由于题目已经给出 flag 的长度是 38 字节，因此我们可以抛去这个很大的因子，只在这个光滑的子群里去解 DLP 就好了。

先看一下光滑子群的长度

big_div = 7938574420107972329924249635772221961795521132311900945710547973psub = (p-1)// big_divprint(psub.bit_length())

只有 299 比特，flag 是 304 比特，因此还需要枚举几比特。

m = m0big_div = 7938574420107972329924249635772221961795521132311900945710547973psub = (p-1)// big_divprint(psub.bit_length())enc_sub = pow(enc,big_div,p)m_sub = pow(m,big_div,p)flag_sub = discrete_log(Mod(enc_sub,p),Mod(m_sub,p),ord = psub)for i in range(2**5):    flag_sub += psubifb'flag'in long_to_bytes(flag_sub):        print(long_to_bytes(flag_sub))# flag{70b1b709ce431682addb581596320007}

simpleSignin

from Crypto.Util.number import *from gmpy2 import *import osflag = b'xxx'p = next_prime(bytes_to_long(os.urandom(128)))q = next_prime(bytes_to_long(os.urandom(128)))r = next_prime(q)n = p * q * re = 0x10001print(f"n = {n}")print(f"c = {pow(bytes_to_long(flag), e, n)}")print(f"gift1 = {p % (2**10)}")print(f"gift2 = {(p >> 20) % 2 ** 800}")# n = # c = # gift1 = # gift2 = 

基于 RSA 公钥加密，额外给出 p 的低 10 比特，去掉低 20 比特后的低 800 比特（也就是中间800比特）。

乍一看以为要用二元 copper 去求 p 的高位和低位。再看一下，低 20 比特已经给出了10比特，那剩下的 10 比特直接爆破一下，那么就是 经典的就是已知 p 低位攻击 了。（呃，这样子出题的么，，，，）

稍微注意一下 n 有三个 1024 比特的素因子，所以 beta 设一个 0.33

R.<x> = Zmod(n)[]for i in range(2^10): f = x * 2^820 + gift2 * 2^20 + i * 2^10 + gift1 ans = f.monic().small_roots(X=2^(1024-820),beta=0.33)if len(ans) != 0:  p = int(f(ans[0]))        print("[+]",p)break

然后也别这那了，盲猜出题人没有对 flag 做填充，经典的 TexbookRSA ，模 p 下解了。

print(long_to_bytes(pow(c,inverse(0x10001,p-1),p)))

cy

from secret import flagfrom Crypto.Util.number import getPrimeflag = bin(int.from_bytes(flag, 'big'))[2:]private_key = []g = getPrime(10)private_key.append(g)for i in range(len(flag) - 1):    g = g * 2    private_key.append(g)a = getPrime(20)b = getPrime(len(flag) + 20)public_key = []for i in private_key:    public_key.append((a * i) % b)print(public_key)c = 0for i in range(len(flag)):    c += int(str(flag)[i])*public_key[i]print(c)

这题基于 knapsack cryptosystem，给出一个公钥列表 public_key，根据 flag 的二进制选取公钥列表里的元素进行相加得到 c

可以看到 private_key 是一个超递增的序列，因此如果我们我们能获得 private_key ，直接拿着其中的元素对 c 逐一进行大小判断即可，具体加密方案可以看我博客的古老文章 https://jayxv.github.io/2020/06/08/密码学学习笔记之knapsack/

注意到这里的公钥 a = getPrime(20) 选的实在太小了，我们直接分解 private_key 里的第一个元素就能获得 a 和 g 了。

有了 g 也就有了 private_key。此时想要解密还需要对 c  乘以 a 在 b 下的逆。把 c 从 public_key 的子集和转为 private_key  的子集和。

至于求b，可以注意到 public_key 最后部分的元素已经是相同比特的，显然已经是模上 b 了，而根据 private_key 生成规则我们知道后一个元素是前一个元素的 2 倍，所以直接前一个元素的两倍减去后一个元素就是 b 了。

a = 797627g = 967b = public_key[-2] * 2 - public_key[-1]c = c * inverse(a,b) % bprivate_key = []private_key.append(g)for i in range(len(public_key) - 1):    g = g * 2    private_key.append(g)flag = ""for each in private_key[::-1]:if c >= each:        flag = '1' + flag        c -= eachelse:        flag = '0' + flagassert c == 0print(long_to_bytes(int(flag,2)))

（PS：其实也不用管他这那的，直接用 经典的 01 背包板子一把梭 就可以了）