QCTF 2025 WriteUp - Q1uJu's House

复现平台：A1CTF

打星号(*)的是赛时未解出赛后复现的，打感叹号(!)是看了官方 WriteUp 有所修改的，打连接符(-)的是没复现出来咕咕咕的。

Crypto#

Week 1#

Basic Number theory#

题目:

1
from Crypto.Util.number import *
2
from secret import flag
3

4
def gift(m, prime):
5
    return pow(m, (prime + 1) // 2, prime)
6

7
m = bytes_to_long(flag)
8
p = getPrime(256)
9
q = getPrime(256)
10

11
print(f'p = {p}')
12
print(f'q = {q}')
13
print(f'gift1 = {gift(m, p)}')
14
print(f'gift2 = {gift(m, q)}')
15

16
# p = ...
17
# q = ...
18
# gift1 = ...
19
# gift2 = ...

\begin{aligned} gift_1\equiv m^{\frac{p+1}{2}}\pmod{p}\equiv m^{\frac{p-1}{2}}*m\pmod{p}\equiv m*(\frac{m}{p})\pmod{p}\\ gift_2\equiv m^{\frac{q+1}{2}}\pmod{q}\equiv m*(\frac{m}{q})\pmod{q}\\ gift_1\equiv \pm{m}\pmod{p},gift_2\equiv \pm{m}\pmod{q} \end{aligned}

再CRT一下穷举四种可能就好了。

exp.py：

1
from sympy.ntheory.residue_ntheory import crt
2
from Crypto.Util.number import long_to_bytes
3

4
p = ...
5
q = ...
6
gift1 = ...
7
gift2 = ...
8

9
gift1_ = [gift1, -gift1]
10
gift2_ = [gift2, -gift2]
11
for i in gift1_:
12
    for k in gift2_:
13
        s, _ = crt([p, q], [i, k])
14
        flag = long_to_bytes(s)
15
        if b'flag' in flag:
16
            print(flag.decode())
17
            break
18
# flag{Th3_c0rner5t0ne_0f_C2ypt0gr@phy}

Strange Machine#

题目：

1
from secret import msg_len, offset, plaintext
2
from Crypto.Util.number import long_to_bytes
3
from random import randbytes
4
from base64 import b64encode
5
from pwn import xor
6
import os
7

8
flag = os.getenv('FLAG')
9

10

11
def banner():
12
    print("你发现了一个奇怪的机器，它对你的消息进行了加密。")
13
    print("你截获了这个机器第一次的密文，同时可以继续使用该机器进行加密。")
14
    print("注意:所有密文输出都经过 base64 编码，方便你复制分析。\n")
15

16

17
def menu():
18
    print(f"1. 加密消息")
19
    print(f"2. 校验明文是否正确")
20
    print(f"3. 退出")
21

22

23
class Key:
24
    def __init__(self):
25
        self.seed = randbytes(msg_len)
26

27
    def generate(self):
28
        self.seed = self.seed[offset:] + self.seed[:offset]
29
        return self.seed
30

31

32
def pad(msg):
33
    pad_len = msg_len - len(msg)
34
    return msg + pad_len * long_to_bytes(pad_len)
35

36

37
def encrypt(msg, key):
38
    cipher = xor(pad(msg), key)
39
    return b64encode(cipher)
40

41

42
def main():
43
    banner()
44
    key = Key()
45
    cur_key = key.generate()
46
    cipher1 = encrypt(plaintext, cur_key)
47
    print(f'[*] 首次密文(base64):{cipher1}\n')
48
    while True:
49
        try:
50
            menu()
51
            choice = int(input(f"[?] 请输入你的选择:"))
52
            if choice == 1:
53
                msg = input(f"[?] 请输入要加密的消息(长度小于等于{msg_len}): ").encode()
54
                if len(msg) > msg_len:
55
                    print(f"[!] 输入消息过长，最长为 {msg_len} 字节\n")
56
                    continue
57

58
                cur_key = key.generate()
59
                cipher = encrypt(msg, cur_key)
60

61
                print(f"[*] 你的消息已加密(密文): {cipher}\n")
62
                continue
63

64
            if choice == 2:
65
                msg = input(f"[?] 请输入待校验的明文: ").encode()
66
                if msg == plaintext:
67
                    print(f"[*] 这是你的flag: {flag}\n")
68
                    break
69
                print("[!] 校验错误!\n")
70
                continue
71

72
            if choice == 3:
73
                print("再见~\n")
74
                break
75

76
            print("[!] 无效输入\n")
77
        except Exception:
78
            print("[!] 出现错误!\n")
79
            break
80

81

82
if __name__ == "__main__":
83
    main()

1 没有限制次数，可以多加密几次一样的明文，已知明文攻击，推出offset再推出key然后和首次密文异或求解，然后选 2 校验明文即可，带中文了交互脚本写的有点麻烦，手拿数据手输了。

exp.py：

1
from base64 import b64decode
2
from pwn import xor
3

4
C1_b64 = "sHACJ0klMagdhYDm53eTNw=="
5
known_b64_list = [
6
    "29T2vjOCBs8oHm4WYCH+RA==",
7
    "Hm4WYCH+RNvU9r4zggbPKA==",
8
    "9r4zggbPKB5uFmAh/kTb1A==",
9
    "FmAh/kTb1Pa+M4IGzygebg==",
10
]
11
msg_len = 16
12
C1 = b64decode(C1_b64)
13
known_list = [b64decode(x) for x in known_b64_list]
14
K_list = [xor(c, b'0' * msg_len) for c in known_list]
15
offset = 0
16
for i in range(len(K_list) - 1):
17
    idx = (K_list[i] + K_list[i]).find(K_list[i + 1])
18
    offset = idx if idx != -1 else 0
19
print(f"{offset = }")
20
K1 = K_list[0][-offset:] + K_list[0][:-offset]
21
P_padded = xor(C1, K1)
22
pad_len = P_padded[-1]
23
plaintext = P_padded[:-pad_len].decode()
24
print(plaintext)
25
# offset = 9
26
# Oh,you find it!
27
# flag{094dc384-ba84-4fdf-871d-8e4a3ed761c0}

beyondHex#

题目：

这是什么东西？ 807G6F429C7FA2200F46525G1350AB20G339D2GB7D8

多了个G，加上题目名字超过 16 进制，猜测是 17 进制。

exp.py：

1
from Crypto.Util.number import long_to_bytes
2

3
s = "807G6F429C7FA2200F46525G1350AB20G339D2GB7D8"
4
print(long_to_bytes(int(s, 17)).decode())
5
# flag{welc0me_t0_?CTF!}

certificate#

题目：

private.pem：

-----BEGIN RSA PRIVATE KEY----- MIICewIBAAKBgQCdA0+pqynKvc3/BH5ojnUXBMdWy9Lzi9TwSaOgiJ6ky//QBrWG CNan98CYNcoKux2yOtHKIjxUrPh+LdgjmW+/paWPJyrnoQw5SqD+FvqNTjG7Akvx +TUXyMflL9qodrWBEbl/xmN01Qbivo36+U1mFDB+6LENk/3BwWXHVj0DvQIhAL7t Vc3/3jEFe+paWKNoTV++2B8D1T+ii7ZYsy3kU1yNAoGA???????????????????? ???????????????????????????????????????????????????????????????? ???????????????????????????????????????????????????????????????? ??????????????????????kCQQ?????????????????????????????????????? ????????????????????????????????????????????????AkE????????????? ???????????????????????????????????????????????????????????????? ?????????wJAJrKFhI5pl/oBN2BZqLTf+NacGqTFrzmbi7RVFaN43kXYXu11urXy LTncfJXBpRhtGFdsL31jiswhiYRp9yjT+wJB???????????????????????????? ??????????????????????????????????????????????????????????MCQQ?? ???????????????????????????????????????????????????????????????? ???????????????????? -----END RSA PRIVATE KEY-----

又又又又要经典的手撕私钥了，这边给个La佬和tover佬的链接。

3082 027b # Begin Sequence: len=0x027b

0201 # Version: (len=0x01) 00

0281 81 # n: (len=0x81) 009d034fa9ab29cabdcdff047e688e751704c756cbd2f38bd4f049a3a0889ea4cbffd006b58608d6a7f7c09835ca0abb1db23ad1ca223c54acf87e2dd823996fbfa5a58f272ae7a10c394aa0fe16fa8d4e31bb024bf1f93517c8c7e52fdaa876b58111b97fc66374d506e2be8dfaf94d6614307ee8b10d93fdc1c165c7563d03bd

02 21 # e: (len=0x21) 00beed55cdffde31057bea5a58a3684d5fbed81f03d53fa28bb658b32de4535c8d

0281 80 # d: (len=0x80) …9

02 41 # p: (len=0x41) 0…

02 41 # q: (len=0x41) …

# 加上w解base64会乱

wJAJrKFhI5pl/oBN2BZqLTf+NacGqTFrzmbi7RVFaN43kXYXu11urXyLTncfJXBpRhtGFdsL31jiswhiYRp9yjT+wJB c09009aca161239a65fe804dd8166a2d37fe35a706a9316bce66e2ed154568de37917617bb5d6ead7c8b4e771f257069461b4615db0bdf58e2b30862611a7dca34fec090

# 所以去了w解base64

JAJrKFhI5pl/oBN2BZqLTf+NacGqTFrzmbi7RVFaN43kXYXu11urXyLTncfJXBpRhtGFdsL31jiswhiYRp9yjT+wJB 24026b285848e6997fa01376059a8b4dff8d69c1aa4c5af399b8bb45515a378de45d85eed75bab5f22d39dc7c95c1a5186d18576c2f7d638acc21898469f728d3fb024

2 40 # dp: (len=0x40) 26b285848e6997fa01376059a8b4dff8d69c1aa4c5af399b8bb45515a378de45d85eed75bab5f22d39dc7c95c1a5186d18576c2f7d638acc21898469f728d3fb

02 4 # dq …3

0241 0…

变成了dp泄露，e很大，上轮子梭。

exp.py：

1
from Crypto.Util.number import *
2
from gmpy2 import *
3

4
n = ...
5
e = ...
6
c = ...
7
dp = ...
8
m = 2
9
p = gcd(pow(m, dp * e, n) - m, n)
10
q = n // p
11
assert p * q == n
12
phi = (p - 1) * (q - 1)
13
d = invert(e, phi)
14
m = pow(c, d, n)
15
print(long_to_bytes(m).decode())
16
# This is your flag:flag{4n_3xc3551v3ly_l4r93_publ1c_k3y_c4n_b3_pr0bl3m4t1c}

two Es#

题目：

1
from Crypto.Util.number import *
2
import random
3
from secret import flag
4

5
p, q = getPrime(512), getPrime(512)
6
n = p * q
7

8
e1 = random.getrandbits(32)
9
e2 = random.getrandbits(32)
10

11
m = bytes_to_long(flag)
12
c1 = pow(m, e1, n)
13
c2 = pow(m, e2, n)
14

15
print(f'{n = }')
16
print(f'{e1 = }')
17
print(f'{e2 = }')
18
print(f'{c1 = }')
19
print(f'{c2 = }')
20

21
'''
22
n = ...
23
e1 = ...
24
e2 = ...
25
c1 = ...
26
c2 = ...
27
'''

如题，两个e，共模攻击。

exp.py：

1
from gmpy2 import gcdext, iroot
2
from Crypto.Util.number import long_to_bytes
3

4
n = ...
5
e1 = ...
6
e2 = ...
7
c1 = ...
8
c2 = ...
9
s, s1, s2 = gcdext(e1, e2)  # 扩展欧几里得算法，求最大公约数
10
m = iroot((pow(c1, s1, n) * pow(c2, s2, n) % n), s)[0]
11
print(long_to_bytes(m).decode())
12
# flag{s01v3_rO0T_bY_7he_S4mE_m0dU1u5}

xorRSA#

题目：

1
from Crypto.Util.number import *
2
from secret import flag
3

4
p, q = getPrime(1024), getPrime(1024)
5
n = p * q
6
e = 65537
7
m = bytes_to_long(flag)
8
c = pow(m, e, n)
9
p_q = p ^ q
10

11
print(f'{n = }')
12
print(f'{e = }')
13
print(f'{c = }')
14
print(f'{p_q = }')
15

16
'''
17
n = ...
18
e = 65537
19
c = ...
20
p_q = ...
21
'''

泄露了p^q，给个DexterJie师傅的链接。

exp.py：

1
from Crypto.Util.number import *
2
import sys
3
sys.setrecursionlimit(3000)
4

5
N = ...
6
e = 65537
7
c = ...
8
gift = ...
9

10
# 低位往高位爆
11
def findp(p, q):
12
    if len(p) == 1024:
13
        pp = int(p,2)
14
        if N % pp == 0:
15
            print("p = ",pp)
16
            print("q = ",N // pp)
17
            qq = N // pp
18
            d = inverse(65537,(pp-1)*(qq-1))
19
            m = pow(c,d,N)
20
            print(long_to_bytes(m))
21
            return
22
    else:
23
        l = len(p)
24
        pp = int(p,2)
25
        qq = int(q,2)
26
        if (pp ^ qq) % (2 ** l) == gift % (2 ** l) and pp * qq % (2 ** l) == N % (2**l):
27
            findp('1' + p,'1' + q)
28
            findp('1' + p,'0' + q)
29
            findp('0' + p,'1' + q)
30
            findp('0' + p,'0' + q)
31

32
findp('1','1')
33
# flag{U5e_PruN1ng_41g0rI7hm_tO_sEarch}

Week 2#

AES_mode#

题目：

1
from Crypto.Cipher import AES
2
from Crypto.Util.Padding import pad
3
import binascii
4
from Crypto.Util.number import bytes_to_long
5
from secret import flag
6
import os
7

8
iv = flag.strip(b'flag{').strip(b'}')
9

10
key = os.urandom(16)
11

12
hint = os.urandom(4) * 8
13
print(bytes_to_long(hint)^bytes_to_long(key))
14

15
msg = b'Welcome to ?CTF! , I hope you can have fun!!!!!!'
16
def encrypto(message):
17
    aes = AES.new(key,AES.MODE_CBC,iv)
18
    return aes.encrypt(message)
19

20
print(binascii.hexlify(encrypto(msg))[-32:])
21
'''
22
...
23
b'...'
24
'''

hint部分老熟了，一道经典老题的泄露方式。key只有 16 位，而hint有8 * 4 = 32位，异或后，生成的随机四字节会泄露，所以直接将第一个已知值转为字节，取前面 16 字节会发现是某四字节的四次重复，便可恢复hint并恢复key。然后题目给了CBC模式下加密的明文和最后一块的密文，有了key就可以一路倒推回去了。

exp.py：

1
from Crypto.Util.number import long_to_bytes, bytes_to_long
2
from Crypto.Util.strxor import strxor
3
from Crypto.Cipher import AES
4

5
hint_xor_key = ...
6
# print(long_to_bytes(hint_xor_key))
7
# b'\xca\xd8N\x97\xca\xd8N\x97\xca\xd8N\x97\xca\xd8N\x97Q\xe1\x80\x0b\x8c>y\x1f\x9a\xa0\xd8A\x0b\xb7c\xa4'
8
c3 = bytes.fromhex('...')
9
hint = b'\xca\xd8N\x97' * 8
10
key = long_to_bytes(hint_xor_key ^ bytes_to_long(hint))
11
msg = b'Welcome to ?CTF! , I hope you can have fun!!!!!!'
12
cipher = AES.new(key, AES.MODE_ECB)
13
c2 = strxor(msg[32:], cipher.decrypt(c3))
14
c1 = strxor(msg[16:32], cipher.decrypt(c2))
15
iv = strxor(msg[:16], cipher.decrypt(c1))
16
print("flag{" + iv.decode() + "}")
17
# flag{CBc_Us3s_Iv!=ECb}

Common RSA#

题目：

1
from Crypto.Util.number import *
2
from secret import flag
3

4
assert flag.startswith(b'flag{') and flag.endswith(b'}')
5

6
p, q = getPrime(512), getPrime(512)
7
n = p * q
8
e = 65537
9
m = bytes_to_long(flag)
10
c = pow(m, e, n)
11

12
hint = pow(p + q, 2, n)
13

14
print(f'{n = }')
15
print(f'{e = }')
16
print(f'{c = }')
17
print(f'{hint = }')
18

19
'''
20
n = ...
21
e = 65537
22
c = ...
23
hint = ...
24
'''

由题目给的hint可以很简单的通过平方和和n分解p和q，然后分解出p和q后发现gcd(e, p - 1)和gcd(e, q - 1)都为 65537，e太大了，考虑 AMM 算法打出m，p和q都挺大，打一个就行了。

exp.py：

1
# SageMath 10.7
2
import time
3
import random
4
from tqdm import trange, tqdm
5
from gmpy2 import iroot, invert
6
from Crypto.Util.number import *
7

8
def AMM(o, r, q):
9
    start = time.time()
10

11
    g = GF(q)
12
    o = g(o)
13
    p = g(random.randint(1, q))
14
    while p ^ ((q-1) // r) == 1:
15
        p = g(random.randint(1, q))
16
    print('[+] Find p:{}'.format(p))
17
    t = 0
18
    s = q - 1
19
    while s % r == 0:
20
        t += 1
21
        s = s // r
22
    print('[+] Find s:{}, t:{}'.format(s, t))
23
    k = 1
24
    while (k * s + 1) % r != 0:
25
        k += 1
26
    alp = (k * s + 1) // r
27
    print('[+] Find alp:{}'.format(alp))
28
    a = p ^ (r**(t-1) * s)
29
    b = o ^ (r*alp - 1)
30
    c = p ^ s
31
    h = 1
32
    for i in range(1, t):
33
        d = b ^ (r^(t-1-i))
34
        if d == 1:
35
            j = 0
36
        else:
37
            print('[+] Calculating DLP...')
38
            j = - discrete_log(d, a)
39
            print('[+] Finish DLP...')
40
        b = b * (c^r)^j
41
        h = h * c^j
42
        c = c^r
43
    result = o^alp * h
44
    end = time.time()
45
    print("Finished in {} seconds.".format(end - start))
46
    print('Find one solution: {}'.format(result))
47
    return result
48

49
def onemod(p,r):
50
    t=p-2
51
    while pow(t,(p-1) // r,p)==1:
52
        t -= 1
53
    return pow(t,(p-1) // r,p)
54

55
def solution(p,root,e):
56
    g = onemod(p,e)
57
    may = set()
58
    for i in range(e):
59
        may.add(root * pow(g,i,p)%p)
60
    return may
61

62
def union(x1, x2):
63
    a1, m1 = x1
64
    a2, m2 = x2
65
    d = gmpy2.gcd(m1, m2)
66
    assert (a2 - a1) % d == 0
67
    p1,p2 = m1 // d,m2 // d
68
    _,l1,l2 = gmpy2.gcdext(p1,p2)
69
    k = -((a1 - a2) // d) * l1
70
    lcm = gmpy2.lcm(m1,m2)
71
    ans = (a1 + k * m1) % lcm
72
    return ans,lcm
73

74
def excrt(ai,mi):
75
    tmp = zip(ai,mi)
76
    return reduce(union, tmp)
77

78
n = ...
79
e = 65537
80
c = ...
81
hint = ...
82
p, q = None, None
83
for k in trange(1000000):
84
    try:
85
        sq = hint + k * n
86
        res = iroot(sq, 2)
87
        if res[0] ** 2 == sq:
88
            sum = res[0]
89
            D = sum ** 2 - 4 * n
90
            diff = iroot(D, 2)[0]
91
            p = (sum + diff) // 2
92
            q = (sum - diff) // 2
93
            if p * q == n:
94
                break
95
    except:
96
        continue
97
cp = c % p
98
mp = AMM(cp, e, p)
99
mps = solution(p, mp, e)
100
for mpp in tqdm(mps):
101
     ai = [int(mpp)]
102
     mi = [p]
103
     m = CRT_list(ai,mi)
104
     flag = long_to_bytes(m)
105
     if b'flag' in flag:
106
         print(flag.decode())
107
         exit(0)
108
# flag{1t_i5_N0T_4_c0mmOn_R5A!}

Furious BlackCopper#

题目：

1
from Crypto.Util.number import *
2
from secret import flag
3

4
p,q,r = [getPrime(1024) for _ in range(3)]
5
n = p*q*r
6
e = 65537
7

8
c = pow(bytes_to_long(flag),e,n)
9

10
print(f"n = {n}")
11
print(f"c = {c}")
12
print(f"hint1 = {p % (1<<20)}")
13
print(f"hint2 = {(p>>30) % (2**800)}")
14

15
'''
16
n = ...
17
c = ...
18
hint1 = ...
19
hint2 = ...
20
'''

就常规打，爆破 10 位就行。

exp.py：

1
# SageMath 10.7
2
from tqdm import trange
3
from Crypto.Util.number import *
4

5
e = 65537
6
n = ...
7
c = ...
8
hint1 = ...
9
hint2 = ...
10
PR.<x> = PolynomialRing(Zmod(n))
11
for i in trange(2 ** 10):
12
    pl = hint1 + i * 2 ** 20 + hint2 * 2 ** 30
13
    f = x * 2 ** 830 + pl
14
    res = f.monic().small_roots(X=2**194, beta=0.19, epsilon=0.02)
15
    if len(res) != 0:
16
        p = res[0] * 2 ** 830 + pl
17
        dp = inverse(e, p - 1)
18
        m = pow(c, dp, p)
19
        print(long_to_bytes(int(m)).decode())
20
        break
21
#  27%|█████████████████████▍                                                          | 275/1024 [00:05<00:14, 51.46it/s]
22
# flag{C0pp3R_W0u1d_B3_T4sty_W1tH_F0rc3}

baby Elgamal#

题目：

1
from Crypto.Util.number import *
2
import random
3
from secret import flag
4

5
p = getPrime(512)
6
g = random.randint(2, p - 2)
7
x = random.getrandbits(32)
8
y = pow(g, x, p)
9

10
print(f'{p = }')
11
print(f'{g = }')
12
print(f'{y = }')
13

14
k = random.randint(2, p - 2)
15
m = bytes_to_long(flag)
16
c1 = pow(g, k, p)
17
c2 = m ^ pow(y, k, p)
18

19
print(f'{c1 = }')
20
print(f'{c2 = }')
21

22
'''
23
p = ...
24
g = ...
25
y = ...
26
c1 = ...
27
c2 = ...
28
'''

都给了g了，bsgs 直接打就行。

exp.py：

1
from Crypto.Util.number import long_to_bytes
2

3
p = ...
4
g = ...
5
y = ...
6
c1 = ...
7
c2 = ...
8

9
N = 1 << 32
10
m = 1 << 16
11

12
baby = {}
13
cur = 1
14
for j in range(m):
15
    baby[cur] = j
16
    cur = (cur * g) % p
17

18
gm = pow(g, m, p)
19
gm_inv = pow(gm, -1, p)
20

21
cur = y
22
x = None
23
for i in range((N + m - 1) // m + 1):
24
    if cur in baby:
25
        x = i * m + baby[cur]
26
        if x < N:
27
            break
28
    cur = (cur * gm_inv) % p
29

30
assert x is not None
31

32
s = pow(c1, x, p)
33
m_int = c2 ^ s
34
flag = long_to_bytes(m_int)
35
print(x, flag.decode())
36
# 1616680587 flag{31g4m41_D15cr373_10g}

findKey in middle#

题目：

1
from Crypto.Util.Padding import pad
2
from Crypto.Util.number import *
3
from random import getrandbits
4
from Crypto.Cipher import AES
5
from hashlib import sha256
6
from secret import flag
7

8
def f(x, y):
9
    return (pow(3, x, p) * pow(5, y, p)) % p
10

11
def split_key(key):
12
    x, y = getPrime(16), getPrime(16)
13
    assert x * y > key
14
    k1, k2 = key % x, key % y
15
    return k1, k2, x, y
16

17
def aes_encrypt(key, flag):
18
    aes = AES.new(key, AES.MODE_ECB)
19
    return aes.encrypt(pad(flag, 16))
20

21
p = 1000000007
22

23
key = getrandbits(32)
24
k1, k2, mod1, mod2 = split_key(key)
25
x = f(k1, k2)
26

27
cipher = aes_encrypt(sha256(long_to_bytes(key)).digest()[:16], flag)
28

29
print(f'x = {x}')
30
print(f'mod = {(mod1, mod2)}')
31
print(f'cipher = {cipher}')
32
# x = ...
33
# mod = (..., ...)
34
# cipher = ...

简而言之密钥被两个模数拆分了，然后给了提示，要从提示推出两个拆分的密钥然后 crt 打出原密钥再派生出 AES 的密钥解密就行。

exp.py：

1
from Crypto.Cipher import AES
2
from Crypto.Util.Padding import unpad
3
from Crypto.Util.number import long_to_bytes
4
from hashlib import sha256
5

6
p = ...
7
x = ...
8
mod1, mod2 = ..., ...
9
cipher = ...
10
pow3 = {}
11
v = 1
12
for i in range(mod1):
13
    pow3[v] = i
14
    v = (v * 3) % p
15
k1 = k2 = None
16
pow5 = 1
17
inv5 = pow(5, p - 2, p)
18
inv5_k = 1
19
for j in range(mod2):
20
    t = (x * inv5_k) % p
21
    if t in pow3:
22
        k1 = pow3[t]
23
        k2 = j
24
        break
25
    inv5_k = (inv5_k * inv5) % p
26
if k1 is None:
27
    raise RuntimeError("未找到(k1,k2)")
28
def crt(a1, m1, a2, m2):
29
    n1 = m2
30
    n2 = m1
31
    inv_n1 = pow(n1, -1, m1)
32
    inv_n2 = pow(n2, -1, m2)
33
    x = (a1 * n1 * inv_n1 + a2 * n2 * inv_n2) % (m1 * m2)
34
    return x
35
key = crt(k1, mod1, k2, mod2)
36
assert key < mod1 * mod2
37
aes_key = sha256(long_to_bytes(key)).digest()[:16]
38
pt = unpad(AES.new(aes_key, AES.MODE_ECB).decrypt(cipher), 16)
39
print("k1 =", k1, "k2 =", k2)
40
print("key =", key)
41
print(pt.decode("utf-8"))
42
# k1 = 12050 k2 = 27449
43
# key = 1313232941
44
# flag{e31343dd-4795-4236-bbec-11b8410b5ce6}

strange random#

题目：

1
from Crypto.Util.number import *
2
import random
3
from sympy import prime
4
def sssstranger(p,q):
5
    n = p*q
6
    list=[]
7
    for i in range(312):
8
        x=random.getrandbits(32)
9
        list.append(x)
10
    print(list)
11
    return n
12

13

14

15
p=getStrongPrime(512)
16
q=getStrongPrime(512)
17
r=getStrongPrime(512)
18
n1=sssstranger(p,q)
19
print(n1)
20
n2=sssstranger(q,r)
21
print(n2)
22
e=random.getrandbits(32)
23
m=bytes_to_long(b"xxx")
24
c=pow(m,e,n1*n2//q)
25
print(c)
26
'''
27
[...]
28
...
29
[...]
30
...
31
...
32
'''

前半是个 MT19937，randcrack 创出e，然后会发现后面e和p，q，r都不互素，可以取r来打flag。

\begin{aligned} n=p*q*r,\varphi{(n)}=(p-1)*(q-1)*(r-1)\\ c\equiv m^e\pmod{n}\\ g:=gcd(e,r)=4\\ e:=g*h,c^{h^{-1}}\equiv m^g\pmod{r} \end{aligned}

在模r下缩小范围从m ** 4求解m。

exp.py：

1
# SageMath 10.7
2
from math import gcd
3
from Crypto.Util.number import inverse, long_to_bytes
4
from randcrack import RandCrack
5

6
outputs = [...]
7
n1 = ...
8
n2 = ...
9
c = ...
10
rc = RandCrack()
11
for v in outputs:
12
    rc.submit(v)
13
e = rc.predict_getrandbits(32)
14
# print("predicted e =", e)
15
# predicted e = 1297450108
16
q = gcd(n1, n2)
17
p = n1 // q
18
r = n2 // q
19
N = (n1 * n2) // q
20
phi = (p - 1) * (q - 1) * (r - 1)
21
# print(gcd(e, p - 1), gcd(e, q - 1), gcd(e, r - 1), gcd(e, phi))
22
# 436 2 4 436
23
g = gcd(e, r - 1)
24
er = e // g
25
phir = r - 1
26
dr = inverse(er, phir)
27
cr = pow(c, dr, r)
28
PR.<x> = PolynomialRing(Zmod(r))
29
f = x ** g - cr
30
res = f.roots(multiplicities=False)
31
for i in res:
32
    m = long_to_bytes(int(i))
33
    if all(1 <= c <= 127 for c in m):
34
        print(m.decode(errors="ignore"))
35
# flag{wwooooow_u_no_the_randdoooooo0m!!!}

Week 3#

Backpack#

题目：

1
import random
2
from secret import flag
3

4
assert flag.startswith(b'flag{') and flag.endswith(b'}')
5
assert len(flag) == 18
6

7
nbits = 100
8
a = [random.randint(1<<(nbits-1),1<<nbits) for i in range(len(flag))]
9
b = sum([i*j for i,j in zip(a,flag)])
10

11
print(f'{a = }')
12
print(f'{b = }')
13

14
'''
15
a = [...]
16
b = ...
17
'''

很简洁的题目，但是一开始思索了下是z3还是格攻击求解，但是约束应该都还是不太够，所以先通过flag{和}的固定首尾搭配来降维。然后常规背包格打就行。

M=\begin{pmatrix} 1 & & & & a[5]\\ & 1 & & & a[6]\\ & & \ddots & & \vdots\\ & & & 1 & a[-2]\\ & & & & -b\\ \end{pmatrix}

exp.py：

1
# SageMath 10.7
2

3
a = [...]
4
b = ...
5
b = b - ord('f') * a[0] - ord('l') * a[1] - ord('a') * a[2] - ord('g') * a[3] - ord('{') * a[4] - ord('}') * a[-1]
6
a = a[5:-1]
7
n = len(a)  # 18
8
B = 1 << 0
9
M = Matrix(ZZ, n + 1)
10
for i in range(n):
11
    M[i, i] = B
12
    M[i, n] = a[i]
13
M[n, n] = -b
14
res = M.LLL()
15
flag = "flag{"
16
for i in res[0]:
17
    flag += chr(i)
18
flag += "}"
19
print(flag)
20
# flag{342y_14771C3}

Great Block Cipher#

题目：

1
def encrypt(msg, key, iv):
2
    assert len(msg) % 16 == 0
3
    assert len(key) == 16 and len(iv) == 16
4
    xor = lambda a, b:[i^j for i,j in zip(a,b)]
5
    sbox = [...]
6
    cipher = []
7
    ks = [key[:4],key[4:8],key[8:12],key[12:]]
8
    for i in range(16*4):
9
        nk = 0
10
        for j in range(4):
11
            nk = int.from_bytes(ks[i+j],'big') ^ (3377808869 * nk % (1<<32))
12
        ks.append(nk.to_bytes(4,'little'))
13
    block_count = len(msg)//16
14
    for block in range(block_count):
15
        m = list(msg[16*block:16*(block+1)])
16
        m = xor(m, iv)
17
        m = xor(m, b''.join(ks[:4]))
18
        for loop in range(16):
19
            m = [sbox[i] for i in m]
20
            for i in range(4):
21
                a = bin(sum([m[4*i+j]*256**j for j in range(4)]))[2:].zfill(32)
22
                b = []
23
                d = i+3
24
                c1, c2 = 32//d, 32%d
25
                k = 0
26
                for j in range(d):
27
                    if j < c2:
28
                        b.append(a[k:k+c1+1])
29
                        k += c1+1
30
                    else:
31
                        b.append(a[k:k+c1])
32
                        k += c1
33
                c = ''
34
                for j in range(c1+1):
35
                    for k in range(d):
36
                        if len(b[k]) > j:
37
                            c += b[k][j]
38
                m[4*i],m[4*i+1],m[4*i+2],m[4*i+3] = int(c,2).to_bytes(4,'big')
39
            if loop < 15:
40
                a = []
41
                b = [10, 13, 3, 11, 7, 9, 0, 15, 5, 12, 8, 4, 6, 14, 2, 1]
42
                for i in range(4):
43
                    for j in range(4):
44
                        a.append(sum([b[4*i+k]*m[j+4*k] for k in range(4)])%256)
45
                m = a
46
            m = xor(m, b''.join(ks[4*(loop+1):4*(loop+2)]))
47
        cipher.append(bytes(m))
48
        iv = m
49
    return b''.join(cipher)
50

51
def pad(msg):
52
    l = (len(msg)//16+1)*16
53
    return msg.ljust(l,chr(l-len(msg)).encode())
54

55
flag = b'flag{*********}'
56

57
what = b'www.bilibili.com/video/BV1ox4y1e71S'
58
key, iv = what[:16], what[-16:]
59
cipher = encrypt(pad(flag), key, iv)
60
print(cipher.hex())
61
# ...

题目给出的encrypt()函数自定义了一个分组对称加密算法，但是整体特征还是类似AES-CBC加密方式，只是用了自定义的S-box，按位重排函数，模 256 下的 4x4 矩阵混合以及自定义的密钥扩展方式。

大致流程是先将Block与iv异或，然后和key异或，接着进入 16 轮迭代：1. S-box 替换，2. bit 混合，3. 线性混合，4. 异或子密钥。

解密的话就是反向执行，ai 调了调，自己修了下出了（又像逆向题了emmm），唉我的 AES 是真菜。

exp.py：

1
def invert_matrix_mod256(M):
2
    """
3
    计算 4x4 矩阵在模 256 下的逆矩阵。
4
    线性混合步骤的逆运算。
5
    """
6
    n = 4
7
    # 构造增广矩阵 [M | I]
8
    A = [[M[i][j] % 256 for j in range(n)] + [1 if i == j else 0 for j in range(n)] for i in range(n)]
9
    # 模 256 下的逆元（利用扩展欧几里得）
10
    def inv(a):
11
        a %= 256
12
        t, nt = 0, 1
13
        r, nr = 256, a
14
        while nr:
15
            q = r // nr
16
            t, nt = nt, t - q * nt
17
            r, nr = nr, r - q * nr
18
        return None if r != 1 else t % 256
19
    # 高斯消元法
20
    row = 0
21
    for col in range(n):
22
        pivot = None
23
        for r in range(row, n):
24
            if inv(A[r][col]) is not None:
25
                pivot = r
26
                break
27
        if pivot is None:
28
            return None  # 不可逆
29
        # 交换主元行
30
        A[row], A[pivot] = A[pivot], A[row]
31
        ip = inv(A[row][col])
32
        # 主元行归一化
33
        for c in range(2 * n):
34
            A[row][c] = (A[row][c] * ip) % 256
35
        # 其他行消元
36
        for r in range(n):
37
            if r == row:
38
                continue
39
            f = A[r][col] % 256
40
            if f:
41
                for c in range(2 * n):
42
                    A[r][c] = (A[r][c] - f * A[row][c]) % 256
43
        row += 1
44
    # 取右半部分为逆矩阵
45
    return [r[n:] for r in A]
46

47
def inv_bitmix_word(w, i):
48
    """
49
    逆位混合函数，对单个 4 字节（32bit）word 逆变换。
50
    参数:
51
        w : list[int]，长度为 4
52
        i : 第 i 个 word 的索引 (0~3)
53
    """
54
    d = i + 3
55
    c1, c2 = 32 // d, 32 % d
56
    lens = [c1 + 1 if j < c2 else c1 for j in range(d)]
57
    # 根据加密阶段的分块顺序重建索引
58
    idx = 0
59
    bidx = []
60
    for ln in lens:
61
        bidx.append(list(range(idx, idx + ln)))
62
        idx += ln
63
    # 加密时按列交织，现在要按列逆序恢复
64
    order = [bidx[r][c] for c in range(max(lens)) for r in range(d) if c < len(bidx[r])]
65
    bits = bin(int.from_bytes(bytes(w), 'big'))[2:].zfill(32)
66
    restored = ['0'] * 32
67
    for pc, pa in enumerate(order):
68
        restored[pa] = bits[pc]
69
    return list(int(''.join(restored), 2).to_bytes(4, 'little'))
70

71
ciphertext = bytes.fromhex("...")
72
what = b'www.bilibili.com/video/BV1ox4y1e71S'
73
key, iv = what[:16], what[-16:]
74
xor = lambda a, b: [i ^ j for i, j in zip(a, b)]
75
# 逆 S-box
76
sbox = [...]
77
inv_sbox = [0] * 256
78
for i, v in enumerate(sbox):
79
    inv_sbox[v] = i
80
# 密钥扩展，与 encrypt() 相同
81
ks = [key[:4], key[4:8], key[8:12], key[12:]]
82
for i in range(64):
83
    nk = 0
84
    for j in range(4):
85
        nk = int.from_bytes(ks[i + j], 'big') ^ (3377808869 * nk % (1 << 32))
86
    ks.append(nk.to_bytes(4, 'little'))
87
# 加密中使用的混合矩阵
88
b = [[10, 13, 3, 11], [7, 9, 0, 15], [5, 12, 8, 4], [6, 14, 2, 1]]
89
binv = invert_matrix_mod256(b)
90
# 分块解密
91
blocks = [ciphertext[i:i + 16] for i in range(0, len(ciphertext), 16)]
92
result = []
93
prev_iv = iv
94
for blk in blocks:
95
    m = list(blk)
96
    # 共 16 轮逆序进行
97
    for round_idx in range(15, -1, -1):
98
        # 1. XOR 当前轮的子密钥
99
        m = xor(m, b''.join(ks[4 * (round_idx + 1):4 * (round_idx + 2)]))
100
        # 2. 若不是最后一轮，则执行线性混合的逆运算
101
        if round_idx < 15:
102
            temp = [0] * 16
103
            for j in range(4):
104
                col = [m[j + 4 * k] for k in range(4)]
105
                col = [sum(binv[i][k] * col[k] for k in range(4)) % 256 for i in range(4)]
106
                for i in range(4):
107
                    temp[i * 4 + j] = col[i]
108
            m = temp
109
        # 3. 位重排逆变换
110
        for i in range(4):
111
            m[4 * i:4 * i + 4] = inv_bitmix_word(m[4 * i:4 * i + 4], i)
112
        # 4. S-box 逆变换
113
        m = [inv_sbox[x] for x in m]
114
    # 5. 轮外 XOR 初始 key 部分 与 CBC iv
115
    m = xor(m, b''.join(ks[:4]))
116
    m = xor(m, prev_iv)
117
    result.append(bytes(m))
118
    prev_iv = blk  # CBC 链接
119
plaintext = b''.join(result)
120
padlen = plaintext[-1]
121
print(plaintext[:-padlen].decode())
122
# flag{7h3_Ch4rm_0f_SyMm3tr1c_EnCrYpT1On!!!}

abc equation(!)#

题目：

1
import os
2

3
flag = os.getenv('FLAG')
4

5
if __name__ == "__main__":
6
    a, b, c = int(input('a = ')), int(input('b = ')), int(input('c = '))
7
    if a > 0 and b > 0 and c > 0:
8
        f1 = 2744*a**3 + 10648*b**3 + 17984728*c**3 + 3161480*a**2 + 12256398*a*b + 9908932*b**2 + 115107342*a*c + 185540278*b*c + 52709471256*c
9
        f2 = 10241*a**2*b + 16093*a*b**2 + 121961*a**2*c + 464002*a*b*c + 301169*b**2*c + 2282413*a*c**2 + 3586649*b*c**2 + 1698355526*c**2 + 1440958176*a + 2321077176*b + 538357358480
10
        if f1 == f2:
11
            print(flag)

题目主要就是解一个三元三次方程大于 0 的特解，由于不知道数多大，大概范围在哪，爆破成本很高，问题主要就来到了怎么降低计算量去求解了。

首先设：

F(a,b,c)=f_1(a,b,c)-f_2(a,b,c)=0

题目要求就是要找这个方程的一组正整数解。我们可以考虑降维来看：

F(a,b,c)=A_3(b,c)a^3+A_2(b,c)a^2+A_1(b,c)a+A_0(b,c)=0

这样对每个固定的(b, c)，我们只需找一个a使得这个方程成立即可。

接下来可以用一下模数筛的思想：

如果 $F(a,b,c)\equiv 0\pmod{p}$ ，则a必是此方程的解。那么可以对若干的小素数求出可能的余数解，然后CRT合并就可以得到对一个大模数下的方程的解，这样每个(b, c)只需验证少量a的同余类即可。

exp.py：

1
# SageMath 10.7
2
from tqdm import tqdm
3
from itertools import product
4

5
def F(a,b,c):
6
    f1 = 2744*a**3 + 10648*b**3 + 17984728*c**3 + 3161480*a**2 + 12256398*a*b + 9908932*b**2 + 115107342*a*c + 185540278*b*c + 52709471256*c
7
    f2 = 10241*a**2*b + 16093*a*b**2 + 121961*a**2*c + 464002*a*b*c + 301169*b**2*c + 2282413*a*c**2 + 3586649*b*c**2 + 1698355526*c**2 + 1440958176*a + 2321077176*b + 538357358480
8
    return f1 - f2
9

10
def Fa_mod_p(b,c,p):
11
    R.<x> = GF(p)[]
12
    return R( F(x, ZZ(b), ZZ(c)) )
13

14
def crt_combine(res_lists, mods):
15
    M = 1
16
    for m in mods:
17
        M *= m
18
    if any(len(S) == 0 for S in res_lists):
19
        return [], M
20
    cand = set()
21
    for tpl in product(*res_lists):
22
        r = 0
23
        mod = 1
24
        ok = True
25
        for ri, mi in zip(tpl, mods):
26
            try:
27
                r = crt([r, ri], [mod, mi])
28
            except Exception:
29
                ok = False
30
                break
31
            mod *= mi
32
        if ok:
33
            cand.add(int(r % M))
34
    return sorted(cand), M
35

36
# 太小再加
37
BMAX, CMAX = 400, 400
38
AMAX = 200000
39
# 不够可以加模数
40
PRIMES = [7, 11, 13, 17, 19, 23]
41
for b in tqdm(range(1, BMAX + 1)):
42
    for c in range(1, CMAX + 1):
43
        root_sets = []
44
        for p in PRIMES:
45
            P = Fa_mod_p(b,c,p)
46
            rs = [int(r) for r in P.roots(multiplicities=False)]  # a ≡ r (mod p)
47
            if not rs:
48
                root_sets = []
49
                break
50
            root_sets.append(rs)
51
        if not root_sets:
52
            continue
53
        residues, M = crt_combine(root_sets, PRIMES)
54
        if not residues:
55
            continue
56
        # 只在 a ≡ residue (mod M) 的序列上检查，步长 = M
57
        for r in residues:
58
            start = r if r > 0 else r + M
59
            for a in range(start, AMAX + 1, M):
60
                if a <= 0:
61
                    continue
62
                if F(a,b,c) == 0:
63
                    print(f"FOUND  a={a}  b={b}  c={c}")
64
                    raise SystemExit
65
#  30%|█████████████████████▉                                                    | 355/1200 [00:17<00:41, 20.42it/s]
66
# FOUND  a=1347  b=356  c=365

1
> ncat challenge.ilovectf.cn 30786
2
a = 1347
3
b = 356
4
c = 365
5
flag{16fe3697-ca92-4635-91ce-76d08c93f189}

观察了一下官方 WriteUp，居然是转到椭圆曲线上求解吗hhh，有点意外了，复现一下。（但是这个观察立方项系数发现是立方数然后还要想到放缩求平移常数实在有点emmmm想不到）

当f1 == f2时，可以令：

\begin{cases} a=\frac{x-3}{7}\\ b=\frac{y}{11}-37\\ c=\frac{z}{131}+29 \end{cases}

则有原式等价于：

8x^3-19x^2y-19xy^2+8y^3-19x^2z-46xyz-19y^2z-19xz^2-19yz^2+8z^3=0

然后可以使用EllipiticCurve_from_cubic将上述三次齐次式映射到一条有理数域的椭圆曲线，利用gens找到椭圆曲线的生成元，再通过椭圆曲线上的加法和数乘计算出该生成元的n倍点并在这些点中找到一个满足a，b，c都为正整数的(x, y, z)。

exp.py：

1
# SageMath 10.7
2
F.<a, b, c> = ZZ[]
3
f1 = 2744*a**3 + 10648*b**3 + 17984728*c**3 + 3161480*a**2 + 12256398*a*b + 9908932*b**2 + 115107342*a*c + 185540278*b*c + 52709471256*c
4
f2 = 10241*a**2*b + 16093*a*b**2 + 121961*a**2*c + 464002*a*b*c + 301169*b**2*c + 2282413*a*c**2 + 3586649*b*c**2 + 1698355526*c**2 + 1440958176*a + 2321077176*b + 538357358480
5
f = f1 - f2
6
F2.<x, y, z> = QQ[]
7
g = f((x - 3) / 7, y / 11 - 37, z / 131 + 29)
8
F = EllipticCurve_from_cubic(g, morphism=True)
9
E = F.codomain()
10
G = E.gens()[0]
11
Finv = F.inverse()
12
for k in range(100):
13
    ABC = Finv(k * G)
14
    AA, BB, CC = ABC
15
    d = max(AA.denominator(), BB.denominator(), CC.denominator())
16
    AA, BB, CC = AA * d, BB * d, CC * d
17
    AA, BB, CC = ((AA - 3) / 7, BB / 11 - 37, CC / 131 + 29)
18
    if all([i.denominator() == 1 and i > 0 for i in [AA, BB, CC]]):
19
        print(k)
20
        print('a =', AA)
21
        print('b =', BB)
22
        print('c =', CC)
23
        print(f(AA, BB, CC))
24
        break

my crypto#

题目：

1
from Crypto.Util.number import *
2
from Crypto.Cipher import AES
3
from secret import keys, flag
4

5
assert all([isPrime(i) for i in keys])
6

7
a, b, c, d = keys
8
flag1 = flag[:16]
9
flag2 = flag[16:]
10

11
def getrandbits(nbits):
12
    global a
13
    a = (a * b + c) % d
14
    res = a % (1 << (nbits % 32))
15
    for i in range(nbits>>5):
16
        a = (a * b + c) % d
17
        res = (res << 32) + a
18
    return res
19

20
def my_getPrime(nbits):
21
    while 1:
22
        p = getrandbits(nbits)
23
        if isPrime(p):
24
            return p
25

26
k = b''.join([long_to_bytes(i) for i in keys])
27
cipher = AES.new(k,AES.MODE_ECB)
28
c1 = cipher.encrypt(flag1)
29
print(c1.hex())
30
# b7a6aa2e92065c6ca0f641774daa6be7
31

32
p = my_getPrime(512)
33
q = my_getPrime(512)
34
n = p * q
35
d = my_getPrime(32)
36
e = pow(d, -1, (p-1)*(q-1))
37
m = bytes_to_long(flag2)
38
c2 = pow(m, e, n)
39
print(f'{n = }')
40
print(f'{e = }')
41
print(f'{c2 = }')
42

43
'''
44
n = ...
45
e = ...
46
c2 = ...
47
'''

分两个部分，前半是个 AES-ECB，关键是求key，key由a，b，c，d四个参数组成；后半部分是 RSA，用了自己写的 LCG 函数生成p，q，d。AES的key中的四个参数同时以 LCG 的参数参与了后半部分的 RSA，后半部分的 RSA 可以直接 Wiener 板子打出d，就能求解后半部分 flag。然后有了d和k可以分解n，求出p和q，再把p和q从高位往低位每 32 比特提取，可以得到 LCG 的状态组（但是p和q的状态组之间不连续），然后通过 LCG 可以求得a，b，c，d四个参数就可以解前半部分 flag 了。

exp.py：

1
from Crypto.Util.number import *
2
from Crypto.Cipher import AES
3
from sympy import *
4

5
class ContinuedFraction():
6
    def __init__(self, numerator, denominator):
7
        self.numberlist = []
8
        self.fractionlist = []
9
        self.GenerateNumberList(numerator, denominator)
10
        self.GenerateFractionList()
11

12
    def GenerateNumberList(self, numerator, denominator):
13
        # 生成简单连分数
14
        while numerator != 1:
15
            quotient = numerator // denominator
16
            remainder = numerator % denominator
17
            self.numberlist.append(quotient)
18
            numerator = denominator
19
            denominator = remainder
20

21
    def GenerateFractionList(self):
22
        self.fractionlist.append([self.numberlist[0], 1])
23
        for i in range(1, len(self.numberlist)):
24
            numerator = self.numberlist[i]
25
            denominator = 1
26
            for j in range(i):
27
                temp = numerator
28
                numerator = denominator + numerator * self.numberlist[i - j - 1]
29
                denominator = temp
30
            self.fractionlist.append([numerator, denominator])
31

32
n = ...
33
e = ...
34
c2 = ...
35
res = ContinuedFraction(e, n)
36
for k, d in res.fractionlist:
37
    # 判断哪一个是我们所需的d
38
    if k == 0 or k == 1:
39
        continue
40
    elif (e * d - 1) % k == 0:
41
        break
42
m = pow(c2, d, n)
43
flag2 = long_to_bytes(m).decode()
44
phi = (e * d - 1) // k
45
p, q = var("p q")
46
eq1 = Eq(p * q, n)
47
eq2 = Eq((p - 1) * (q - 1), phi)
48
p, q = solve([eq1, eq2], [p, q])[0]
49
assert p * q == n
50
state = [(p >> (32 * (15 - i))) & 0xffffffff for i in range(16)]
51
diff = []
52
for i in range(len(state) - 1):
53
    diff.append(state[i + 1] - state[i])
54
d = diff[-1] * diff[-3] - diff[-2] ** 2
55
for i in range(2, len(diff) - 1):
56
    d = gcd(d, diff[i] * diff[i - 2] - diff[i - 1] ** 2)
57
assert isPrime(int(d))
58
for i in range(2, len(diff) - 1):
59
    b = (diff[i] * invert(diff[i - 1], d)) % d
60
b += d
61
binv = invert(b, d)
62
c = (state[1] - state[0] * b) % d
63
for i in range(len(state) - 1):
64
    assert state[i + 1] == (b * state[i] + c) % d
65
a = (state[0] - c) * binv % d
66
c1 = bytes.fromhex("b7a6aa2e92065c6ca0f641774daa6be7")
67
while 1:
68
    a = (a - c) * binv % d
69
    cnt += 1
70
    if cnt % 100000 == 0:
71
        print(cnt)
72
    if isPrime(int(a)):
73
        k = b''.join([long_to_bytes(i, 4) for i in [a, b, c, d]])
74
        cipher = AES.new(k, AES.MODE_ECB)
75
        flag1 = cipher.decrypt(c1)
76
        if b'flag{' in flag1:
77
            print(flag1.decode() + flag2)
78
            break
79
# a = 3597317387
80
# b = 4126288123
81
# c = 3523486777
82
# d = 3952641229
83
# flag{LCG_is_n0t_a_cryp7o_5ecure_PRNG}

期末考试(!)#

题目：

1
from secret import B, C
2
import numpy as np
3

4
p = 251
5
A = np.diag([np.random.randint(0,p) for i in range(6)])
6

7
B = np.matrix(B)
8
C = np.matrix(C)
9
print(B * C %p)
10

11
'''
12
[...]
13
'''
14

15
D = B * A * C %p
16
print('D =',D.tolist())
17

18
'''
19
D = [...]
20
'''
21

22
flag = bytes(B.reshape((1,36)).tolist()[0])
23
assert flag[:4] == b'flag'
24
print(flag)
25

26
# b'flag{you_need_to_solve_by_yourself!}' ## fakeflag

加密流程是在模 251 的域上取随机对角阵 A，选择可逆矩阵 B 以及 B 的逆矩阵 C。输出：

D\equiv BAC\mod{251}

flag就是 B 矩阵按行展平。可以验证一下 D 在域上是可对角化且特征值互异：

1
# SageMath 10.7
2
print(D.is_diagonalizable())
3
print(D.eigenvalues())
4
# True
5
# [182, 150, 132, 109, 68, 16]

首先这题要说一下自由度的问题：

设 $A=diag(\lambda_1,\dots,\lambda_6),B=[v_1v_2\dots v_6]$ 的列是 $D$ 的右特征向量，满足

Dv_i=\lambda_iv_i,D=BAB^{-1}

其中有两类等价变换不会改变 $D$ ：

**列缩放：**任取可逆对角矩阵 $S=diag(s_1,\dots,s_6)$
$B'=BS,A'=S^{-1}AS=A,B'A'(B')^{-1}=D$
含义：每列特征向量可乘任意非零标量，自由度 $(\mathbb{F}^{\times}_{251})^6$ ，规模为 250^6。
**列置换：**任取置换矩阵 $P$ ，
$B'=BP,A'=P^{-1}AP=diag(\lambda_{\pi(1)},\dots,\lambda_{\pi(6)}),B'A'(B')^{-1}=D$
含义：列顺序可任意换，同时对 $A$ 以相同置换重排对角元，自由度 6!。

也就是说 $D$ 唯一确定的是“每个特征空间的方向”，而不是具体的列向量的顺序。然后再看回这道题就会发现，是个有点巧妙的题了，flag{}刚好限制了 6 个列缩放自由度，只需要再爆破一下列置换自由度就行了。

exp.py：

1
# SageMath 10.7
2
from itertools import permutations
3

4
# 取一条向量并规范化
5
def canon(v):
6
    v = vector(F, v)
7
    for x in v:
8
        if x != 0:
9
            return (1 / x) * v
10
    return v
11

12
p = 251
13
D = Matrix(GF(p), [...])
14
spec = D.eigenvectors_right()
15
pairs = [(lam, canon(vs[0])) for lam, vs, mult in spec]
16
# 全排列列顺序
17
target_head = list(b"flag{")
18
for perm in permutations(range(6)):
19
    # 组 B, A
20
    cols = [pairs[i][1] for i in perm]
21
    lams = [pairs[i][0] for i in perm]
22
    B = Matrix(F, cols).transpose()
23
    # 必须可逆
24
    if B.rank() < 6:
25
        continue
26
    try:
27
        C = B.inverse()
28
    except ZeroDivisionError:
29
        continue
30
    A = diagonal_matrix(F, lams)
31
    if B * A * C != D:
32
        continue
33
    # 固定右下角为 '}'
34
    if B[5, 5] == 0:
35
        continue
36
    s5 = F(125) * (B[5, 5]) ** -1
37
    B[:, 5] *= s5
38
    # 固定首行为 b"flag{"
39
    ok = True
40
    for j in range(5):
41
        if B[0, j] == 0:
42
            ok = False
43
            break
44
        sj = F(target_head[j]) * (B[0, j]) ** -1
45
        B[:, j] *= sj
46
    if not ok:
47
        continue
48
    # 重新验证可逆与相似关系
49
    try:
50
        C = B.inverse()
51
    except ZeroDivisionError:
52
        continue
53
    if B * A * C != D:
54
        continue
55
    if all(32 <= int(x) <= 126 for x in B.list()):
56
        flag = bytes(int(x) for x in B.list())
57
        print(flag.decode())
58
        break
59
# flag{3Njoy_My_eZ_m4tr1x_5imi1aRi7y!}

参照官方exp码一个，主要是学习记录一下 SageMath 的diagonalization函数的使用。

exp.py：

1
# SageMath 10.7
2
from itertools import permutations
3

4
D = Matrix(GF(251), [...])
5
A, E = D.diagonalization()
6
eye = [[1 if i == j else 0 for j in range(6)] for i in range(6)]
7
for m in permutations(range(6)):
8
    P = []
9
    for i in m:
10
        P.append(eye[i])
11
    P = Matrix(Zmod(251), P)
12
    for n in range(32, 127):
13
        B = E / P * diagonal_matrix([ord("f"), ord("l"), ord("a"), ord("g"), ord("{"), n])
14
        flag = B.list()
15
        if all([32 <= i <= 127 for i in flag]) and flag[-1] == 125:
16
            print(bytes(flag).decode())
17
# flag{3Njoy_My_eZ_m4tr1x_5imi1aRi7y!}

粗心的刀客塔#

题目：

作战中，粗心的刀客塔在给干员们下达机密指令时漏发了部分内容，为了省事，他直接用原来的密钥重发了完整指令。可他万万没想到，这个看似简单的操作，却导致战术被普瑞赛斯全盘破解。

1
from Crypto.Util.number import *
2
from secret import flag
3
import string
4

5
assert all([32 <= i < 127 for i in flag])
6

7
p = getPrime(256)
8
q = getPrime(256)
9
n = p * q
10
e = 101
11
m = bytes_to_long(flag)
12
leak = pow(m >> 24, e, n)
13
c = pow(m, e, n)
14

15
print(f"{n = }")
16
print(f"{c = }")
17
print(f"{leak = }")
18

19
'''
20
n = ...
21
c = ...
22
leak = ...
23
'''

好简洁的题目，好舒服啊哈哈哈哈哈。根据描述以及这个代码内容，相关信息攻击，上板子！但是会有个问题，这个右移 24 位怎么解决呢，肯定不能爆破，有点大了。这个时候观察一下题目给的一个提示：assert all([32 <= i < 127 for i in flag])，那么我们爆破直接爆破两位字符就可以了（最后一位一定是}）。

exp.py：

1
# SageMath 10.7
2
from Crypto.Util.number import *
3
from tqdm import trange
4
from sys import exit
5

6
def franklinReiter(n, e, c1, c2, r):
7
    PR.<x> = PolynomialRing(Zmod(n))
8
    g1 = x ** e - c1
9
    g2 = (x * 2 ** 24 + r) ** e - c2
10

11
    def gcd(g1, g2):
12
        while g2:
13
            g1, g2 = g2, g1 % g2
14
        return g1.monic()
15
    return -gcd(g1, g2)[0]
16

17
e = ...
18
n = ...
19
c = ...
20
leak = ...
21
for i in trange(32, 127):
22
    for j in range(32, 127):
23
        r = i * 65536 + j * 256 + ord("}")
24
        x = franklinReiter(n, e, leak, c, r)
25
        m = int(x * 2 ** 24 + r)
26
        try:
27
            flag = long_to_bytes(m)
28
            if b'flag{' in flag:
29
                print(flag.decode())
30
                raise SystemExit
31
        except SystemExit:
32
            print("Over!")
33
            raise SystemExit
34
        except:
35
            continue
36
#   1%|▉                                                                                   | 1/95 [00:00<00:14,  6.38it/s]
37
# flag{Franklin-Reiter_Re1at3d_Mes5age_4t7ack!!}
38
# Over!

Week 4#

Crazy List(-)#

题目：

1
import hashlib
2
from random import randint
3
from secret import flag
4

5
def crash(b):
6
    assert type(b) == list
7
    def T(b):
8
        a = [abs(i) for i in b]
9
        n, l, r = max(a) + 1, len(b), []
10
        p = list(range(n))
11
        p1 = p.copy()
12
        for i in a:
13
            p[i-1], p[i] = p[i], p[i-1]
14
        F = set(i+1 for i in range(n-1) if p[i]>p[i+1])
15
        p = [p.index(i) for i in range(n)]
16
        S = set(i+1 for i in range(n-1) if p[i]>p[i+1])
17
        while p != p1:
18
            for i in range(n-1):
19
                if p[i]>p[i+1]:
20
                    p[i], p[i+1] = p[i+1], p[i]
21
                    r.append(i+1)
22
        return r, S, F
23
    n, l = max(b) + 1, len(b)
24
    p, r, B, S, F = list(range(n)), [], [[]], [set()], []
25
    for i in b:
26
        if {p[i-1],p[i]} in r:
27
            F.append(set(j+1 for j in range(n-1) if p[j]>p[j+1]))
28
            p, r = list(range(n)), []
29
            B.append([])
30
            S.append(set())
31
        B[-1].append(i)
32
        r.append({p[i-1],p[i]})
33
        if abs(p[i-1]-p[i]) == 1:
34
            S[-1].add(min(p[i-1],p[i])+1)
35
        p[i-1], p[i] = p[i], p[i-1]
36
    F.append(set(j+1 for j in range(n-1) if p[j]>p[j+1]))
37
    check = True
38
    while check:
39
        check = False
40
        for i in range(len(B)-1):
41
            d = S[i+1].difference(F[i])
42
            if len(d) != 0:
43
                d1 = d.pop()
44
                B[i], S[i], F[i] = T(B[i]+[d1])
45
                B[i+1], S[i+1], F[i+1] = T([-d1]+B[i+1])
46
                check = True
47
    nB = []
48
    for i in B:
49
        nB.extend(i)
50
    return nB
51

52
def hash_list(b):
53
    b = crash(b)
54
    h = hashlib.sha512(bytes(b)).digest()
55
    return h
56

57
n = 10
58
nLen = 70
59

60
x1, x2 = [randint(1,n-1) for i in range(nLen)], [randint(1,n-1) for i in range(nLen)]
61

62
a = [randint(1,2*n-1) for i in range(1000)]
63
b = x1 + a + x2
64

65
y1, y2 = [randint(n+1,2*n-1) for i in range(nLen)], [randint(n+1,2*n-1) for i in range(nLen)]
66

67
xor = lambda a,b:bytes([i^j for i,j in zip(a,b)])
68
c1 = crash(y1 + a + y2)
69
c2 = xor(flag, hash_list(y1 + b + y2))
70

71
a = crash(a)
72
b = crash(b)
73

74
with open('output.txt','w') as f:
75
    f.write(f'{a = }\n')
76
    f.write(f'{b = }\n')
77
    f.write(f'{c1 = }\n')
78
    f.write(f'{c2 = }\n')

群论没学好笑的，这个有点太难了，先鸽一鸽害。

Myneighbors#

题目：

1
from secret import magical_num, flag
2
from Crypto.Util.Padding import pad
3
from Crypto.Util.number import *
4
from Crypto.Cipher import AES
5
import hashlib
6

7
p = 431
8
F.<i> = GF(p^2, modulus = x^2 + 1)
9
E = EllipticCurve(j=F(magical_num))
10
assert E.is_supersingular()
11

12
P = E(0).division_points(2)[1:]
13
neighbors = []
14
for idx in range(len((P))):
15
    phi = E.isogeny(P[idx])
16
    EE = phi.codomain()
17
    neighbors.append(EE.j_invariant())
18

19
assert E.j_invariant() in neighbors
20

21
P = E(0).division_points(3)[1:]
22
shuffle(P)
23

24
phi = E.isogeny(P[0])
25
E = phi.codomain()
26
H = hashlib.md5(str(E.j_invariant()).encode()).hexdigest().encode()
27
key, iv = H[:16], H[16:]
28

29
aes = AES.new(key, AES.MODE_CBC, iv)
30
cipher = aes.encrypt(pad(flag, 16))
31
print(f'cipher: {cipher.hex()}')
32
#cipher: 49e90a91357fef12c54234b3cb553bb2fdd61f2af8c7e78b3d5ffdeac7022af0

本周签到题，真就只做出来这一道，哭了qaq。同源真难啊，先简单学习一下，后面系统学习总结一下。

加密代码首先选定了一条特定的超奇异曲线，从这条超奇异椭圆曲线出发，通过一个3-isogeny得到新曲线，并用新曲线的j-invariant的md5值切割为 AES 的key和iv来加密flag。解密枚举出满足约束条件的候选起点曲线E，并对每个候选枚举所有非平凡3-torsion子群生成的3-isogeny，找到能解出flag的那条就行。

exp.py：

1
# SageMath 10.7
2
from sage.all import *
3
from hashlib import md5
4
from tqdm import trange
5
from Crypto.Cipher import AES
6
from Crypto.Util.Padding import unpad
7

8
p = 431
9
F.<i> = GF(p^2, modulus=x^2 + 1)
10
cipher = bytes.fromhex("49e90a91357fef12c54234b3cb553bb2fdd61f2af8c7e78b3d5ffdeac7022af0")
11
found = False
12
for magical_num in trange(p):
13
    E = EllipticCurve(j=F(magical_num))
14
    if E.is_supersingular() and found == False:
15
        P = E(0).division_points(3)[1:]
16
        for p in P:
17
            try:
18
                phi = E.isogeny(p)
19
                E1 = phi.codomain()
20
                H = md5(str(E1.j_invariant()).encode()).hexdigest().encode()
21
                key, iv = H[:16], H[16:]
22
                aes = AES.new(key, AES.MODE_CBC, iv)
23
                flag = aes.decrypt(cipher)
24
                if b'flag{' in flag:
25
                    print(unpad(flag, 16).decode())
26
                    found = True
27
                    break
28
            except:
29
                continue
30
    elif found:
31
        break
32
    else:
33
        continue
34
#  14%|███████████▌                                                                    | 62/431 [00:00<00:00, 1200.25it/s]
35
# flag{I_@m_4_n31gh80r_0f_my53lf}

RSA紧缩术(*)#

题目：

1
from Crypto.Util.number import *
2
from secret import flag
3

4
p = getPrime(1024)
5
q = getPrime(1024)
6

7
n = p * q
8
phi = (p - 1) * (q - 1)
9

10
e = getPrime(128)
11
d = pow(e, -1, phi)
12
leak = (1145 * d + 1419 * p + 19810 * q) >> 200
13

14
m = bytes_to_long(flag)
15
c = pow(m, e, n)
16

17
print(f'{n = }')
18
print(f'{e = }')
19
print(f'{c = }')
20
print(f'{leak = }')
21

22
'''
23
n = ...
24
e = ...
25
c = ...
26
leak = ...
27
'''

变式 RSA 的私钥d高位泄露的 CopperSmith 攻击。

主要还是考虑将已知d的高位泄露想办法转化为已知p的高位泄露。leak = (1145 * d + 1419 * p + 19810 * q) >> 200，我们可以记：

L_{high}=leak*2^{200},L=L_{high}+L_{low}

由已知

L_{high}=1145d+1419p+19810q-L_{low}

左右同乘e，移项可得

\begin{aligned} &e\cdot L_{high}-1419ep-19810eq+e\cdot L_{low}-1145=1145(ed-1)\\ =&1145(k\cdot \varphi(n))=1145kn-1145k(p+q-1)\\ \Rightarrow&k=\frac{e\cdot L_{high}}{1145n}+\frac{-1419ep-19810eq+e\cdot L_{low}-1145+1145k(p+q-1)}{1145n} \end{aligned}

而第二项根据位数分析一下可知应该很小，在0 - 1之间，我们可以考虑k = (e * L_high) // (1145 * n)。从上述式子还能找出一个等式：

ep\cdot L_{high}-1419ep^2-19810en+ep\cdot L_{low}-1145p-1145k(np-p^p-n+p)=0

由于e * p * L_low很小，我们省略这一项然后在实数域对p求解可以得到p的高位（但是不是我们常见意义的高位，并非说是p >> 200 << 200这种高位，只是p减去了一个小值p_low而已），然后 CopperSmith 打出p的低位就能分解n了。

exp.py：

1
# SageMath 10.7
2
from tqdm import trange
3
from Crypto.Util.number import long_to_bytes
4

5
n = ...
6
e = ...
7
c = ...
8
leak = ...
9
L_high = leak << 200
10
k = (e * L_high) // (1145 * n)
11
RF.<ph> = RealField(2000)[]
12
f1 = e * ph * L_high - 1419 * e * ph ** 2 - 19810 * e * n - 1145 * ph - 1145 * k * (n * ph - ph ** 2 - n + ph)
13
for res, _ in f1.roots():
14
    p_high = int(res)
15
    PR.<pl> = PolynomialRing(Zmod(n))
16
    f2 = pl + p_high
17
    p_low = f2.small_roots(X=2**200, beta=0.4, epsilon=0.02)
18
    if p_low:
19
        p = int(p_low[0] + p_high)
20
        q = n // p
21
        assert p * q == n
22
        phi = (p - 1) * (q - 1)
23
        d = inverse_mod(e, phi)
24
        m = pow(c, d, n)
25
        print(long_to_bytes(int(m)).decode())
26
        break
27
# flag{c0pp3r5mith_Shrinkage_Technique}

Xaleid◆scopiX(*)#

题目：

1
from Crypto.Util.number import *
2
import random
3
import os
4

5
flag = open('/home/ctf/flag').read()
6

7
basis = random.randint(2,(1<<128)-2)
8
prime = getPrime(128)
9

10
def kaleidoscope(msg):
11
    r = basis
12
    for i in msg:
13
        r = r * prime % (1 << 128)
14
        r = r ^ i
15
    return r
16

17
def main(i):
18
    key = os.urandom(random.randint(64,128))
19
    print('Hello! Your gift:', kaleidoscope(key))
20
    s1 = input('Tell me your name: ').encode()
21
    print('Hello,', kaleidoscope(s1), '! Let\'s sign in!')
22
    s2 = input('Your account: ').encode()
23
    print('Your account:', kaleidoscope(s2))
24
    s3 = int(input('Your password: '))
25
    if s3:
26
        if s3 == kaleidoscope(s1 + key + s2):
27
            print('Sign in successfully!')
28
            s4 = input('Your operation: ')
29
            if s4 == 'flag':
30
                if s2 == b'admin':
31
                    print(flag)
32
                else:
33
                    print('Permission deny')
34
            elif s4 == 'logout' and i:
35
                main(i-1)
36
            else:
37
                print('Unknown operation')
38
        else:
39
            print('Password incorrect!')
40

41
if __name__ == '__main__':
42
    main(1)

也算是第一次了解 FNV 了，上一次看到 FNV 还是在 R3 上，根本看不懂那个hhh。

本题服务器会在我们每一次发送字符串后返回哈希值。而basis和prime是固定的，因此我们可以想办法把basis和prime求出来。题目有一个较大的泄漏点就是没有检查s1是否为空字符串，所以我们可以发送空字符串s1直接得到basis值，然后发送任意字节比如"1"，就可以得到((basis * prime) % (2 ** 128)) ^ ord("1")，这样就可以求出prime的值，考虑到basis可能为偶数，题解使用了gcdext去逆basis求解prime，当basis为偶数时穷举可能的prime。

然后求出这两个已知信息后，易知s1 + key的哈希值就是key的哈希值，而且key + s2的哈希值是在key的基础上以key的哈希值作为basis算出的s2的哈希值。因此只要我们有key的哈希值和prime就可以在不知道key的实际值的情况下伪造key + s2的哈希值。题目给了两轮的机会，可以在第一轮验证时求出basis和prime的值然后logout，在第二轮伪造出key + "admin"的哈希值获取flag。

exp.py：

1
from pwn import *
2
from gmpy2 import gcdext, is_prime
3

4
def kaleidoscope(basis, prime, msg):
5
    r = basis
6
    for i in msg:
7
        r = r * prime % (1 << 128)
8
        r = r ^ i
9
    return r
10

11
r = remote("ctf.a1natas.com", 24524)
12
r.recvuntil(b'Hello! Your gift: ')
13
key = int(r.recvline().strip().decode())
14
r.sendafter(b'Tell me your name: ', b'\n')
15
basis = int(r.recvline()[7:-18].decode())
16
r.sendafter(b'Your account: ', b'1\n')
17
r.recvuntil(b'Your account: ')
18
s2 = int(r.recvline().strip().decode())
19
g = gcdext(basis, 1 << 128)
20
p_r= ((s2 ^ ord("1")) * g[1] % (1 << 128)) // g[0]
21
for i in range(g[0]):
22
    prime = p_r + i * (1 << 128) // g[0]
23
    if is_prime(prime) and prime.bit_length() == 128:
24
        pswd = (key * prime % (1 << 128)) ^ ord("1")
25
        r.sendline(str(pswd).encode())
26
        r.sendline(b'logout')
27
        r.recvuntil(b'Hello! Your gift: ')
28
        key = int(r.recvline().strip().decode())
29
        r.sendafter(b'Tell me your name: ', b'\n')
30
        r.sendafter(b'Your account: ', b'admin\n')
31
        r.recvuntil(b'Your password: ')
32
        r.sendline(str(kaleidoscope(key, prime, b'admin')).encode())
33
        r.sendafter(b'Your operation: ', b'flag\n')
34
        print(r.recvline().decode())
35
# flag{ea93b1b3-8a01-4145-9b4d-2fde98400fae}

ezECC(-)#

题目：

1
from Crypto.Util.Padding import pad
2
from Crypto.Cipher import AES
3
from secrets import flag
4
import random
5
import hashlib
6

7
class Niederreiter_Cryptosystem:
8
    def __init__(self, n, k):
9
        self.F = GF(2^8,repr='int')
10
        alpha = self.F.list()[1:]
11
        self.C = codes.GeneralizedReedSolomonCode(alpha, k)
12
        self.t = (n - k) // 2
13
        self.pub, self.priv = self.gen(n, k)
14

15
    def get_recover_ability(self):
16
        return self.t
17

18
    def get_key(self):
19
        return self.priv
20

21
    def gen(self, n, k):
22
        H = self.C.parity_check_matrix()
23
        P = Permutations(n).random_element().to_matrix()
24
        S = random_matrix(self.F, n-k, n-k)
25
        while S.det() == 0:
26
            S = random_matrix(self.F, n-k, n-k)
27
        Pub = S * H * P
28
        return Pub, (S, H, P)
29

30
    def encrypt(self, msg):
31
        e = vector(self.F, [self.F._cache.fetch_int(x) for x in msg])
32
        return self.pub * e
33

34

35
n, k = 255, 223
36
encryptor = Niederreiter_Cryptosystem(n, k)
37
key = [random.getrandbits(8) for _ in range(encryptor.get_recover_ability())] + [0] * (n - encryptor.get_recover_ability())
38
random.shuffle(key)
39

40
cipher = encryptor.encrypt(key)
41
S, H, P = encryptor.get_key()
42

43
key = hashlib.sha256(str(key).encode()).digest()
44
aes = AES.new(key, AES.MODE_ECB)
45
c = aes.encrypt(pad(flag, 16))
46

47

48
with open('output.txt', 'w') as file:
49
    file.write('encrypted key: ' + str(cipher) + '\n')
50
    file.write('S: ' + str(S.list()) + '\n')
51
    file.write('P: ' + str(P.list()) + '\n')
52
    file.write('encrypted flag: ' + str(c))

初看这题应该就要单纯的根据这个私钥解出原来的密文，题目也没有藏着掖着很直接的就给出了Niederreiter密码系统。

复现好像有点问题一直不对hhh，先鸽了。

linear function?(*)#

题目：

1
import random
2
from Crypto.Util.number import *
3
P = ...
4

5
def pairing(a, b):
6
    return (a * b) % P
7

8
def modexp(base, exp):
9
    return pow(base, exp, P)
10

11
def fake_hash(msg: bytes) -> int:
12
    return (bytes_to_long(msg)+q*114514114514)% P
13

14
q = 1# ?? #small number
15

16
g1 = pow(random.randint(2, P-1), (P-1)//q, P)
17
g2 = pow(random.randint(2, P-1), (P-1)//q, P)
18
x = random.randint(2, q-1)
19
y = random.randint(2, q-1)
20

21

22
pk1 = modexp(g1, x)
23
pk2 = modexp(g2, y)
24

25

26
flag = b""
27

28
m = fake_hash(flag)
29
c1 = modexp(m, y)
30
c2 = pow(pairing(m, g2), x, P)
31

32
print("g1 =", g1)
33
print("g2 =", g2)
34
print("pk1 =", pk1)
35
print("pk2 =", pk2)
36
print("c1 =", c1)
37
print("c2 =", c2)
38
'''
39
g1 = ...
40
g2 = ...
41
pk1 = ...
42
pk2 = ...
43
c1 = ...
44
c2 = ...
45
'''

考点是双线性配对，这是一类满足 $e(g^a,h^b)=e(g,h)^{ab}$ 的映射，它允许将两个群元素中的指数线性地组合。本题中的pairing(a, b) = ab mod p是一个不安全的伪双线性配对，满足双线性性质： $(a\cdot b)^x=a^x\cdot b^x$ ，但是暴露了指数结构，使得密文中的指数可以被代数拆解从而恢复明文。

题目给出了密文：

c_1\equiv m^y\pmod{P},c_2\equiv (m\cdot g_2)^x\pmod{P}

其中m = fake_hash(flag) = (bytes_to_long(flag) + q * 114514114514) % P。

由于pairing是线性的：

c_2\equiv (mg_2)^x\equiv m^x\cdot g_2^x\pmod{P}

如果我们能得到x，就可以直接消去g2项：

m^x\equiv c_2/g_2^x\pmod{P}

而且计算阶发现g1和g2的阶足够小且较为平滑（且很巧ord(g1) = 2 * ord(g2)），可以直接DLP打出x和y，这样就能恢复出：

m^y\equiv c_1 \pmod{P},m^x\equiv c_2/g_2^x\pmod{P}

然后通过计算发现d = gcd(x, y) = 3，我们可以通过扩展欧几里得找到u，v使

ux+vy=d

这样我们便可以找到m ** 3，然后在模P下开三次方找到三个根，分别逆fake_hash筛出flag。

exp.py：

1
# SageMath 10.7
2
from Crypto.Util.number import long_to_bytes
3

4
P = ...
5
g1  = ...
6
g2  = ...
7
pk1 = ...
8
pk2 = ...
9
c1  = ...
10
c2  = ...
11
ZP = Zmod(P)
12
g1, g2, pk1, pk2, c1, c2 = ZP(g1), ZP(g2), ZP(pk1), ZP(pk2), ZP(c1), ZP(c2)
13
ord_g1 = g1.multiplicative_order()
14
ord_g2 = g2.multiplicative_order()
15
# ord(g1) == 2 * ord(g2)
16
q_sub = Integer(ord_g2)
17
x = discrete_log(pk1 % P, g1 % P, ord=q_sub*2)
18
y = discrete_log(pk2 % P, g2 % P, ord=q_sub)
19
QMAX = max(x, y) * 4
20
mx = c2 / (g2 ** x)
21
my = c1
22
d, u, v = xgcd(x, y)
23
md = (mx ** u) * (my ** v)   # md = m^d
24
F = GF(P)
25
mdF = F(int(md))
26
roots = list(mdF.nth_root(3, all=True))
27
candidates_m = [ZP(int(r)) for r in roots]
28
for ridx, m in enumerate(candidates_m):
29
    m_int = Integer(m)
30
    for q_try in range(2, Q_MAX + 1):
31
        val = (m_int - q_try * C) % P
32
        msg = int_to_bytes(val)
33
        if msg.startswith(b"flag{") and msg.endswith(b"}"):
34
            print(msg.decode())
35
            raise SystemExit
36
# flag{pair1n9_13_s000_fun}

官方的 WriteUp 就更暴力一些了，直接通过爆破去找x，y，然后在模P下恢复到m的gcd(y, P - 1) = 3次方，再进行开方计算flag = long_to_bytes((r - q * 114514114514) % P)筛出真正的flag。

exp.py：

1
from sys import exit
2
from gmpy2 import gcd, invert
3
from Crypto.Util.number import long_to_bytes
4
from sympy.ntheory.residue_ntheory import nthroot_mod
5

6
def modexp(base, exp):
7
    return pow(base, exp, P)
8

9
def force(base, value, p, q):
10
    cur = 1
11
    for e in range(q):
12
        if cur == value:
13
            return e
14
        cur = (cur * base) % p
15
    return None
16

17
P = ...
18
g2 = ...
19
pk2 = ...
20
c1 = ...
21
y = None
22
for q in range(100, 150):
23
    rec_y = force(g2, pk2, P, q)
24
    y = rec_y
25
    if y != None:
26
        M = (P - 1) // gcd(y, P - 1)
27
        e = invert(y // gcd(y, P - 1), M)
28
        m3 = pow(c1, e, P)
29
        roots = nthroot_mod(m3, 3, P, all_roots=True)
30
        for r in roots:
31
            flag = long_to_bytes((r - q * 114514114514) % P)
32
            if flag.startswith(b"flag{") and flag.endswith(b"}"):
33
                print(flag.decode())
34
                exit(1)
35
# flag{pair1n9_13_s000_fun}

异域症(*)#

题目：

1
from Crypto.Util.number import *
2
import os
3
from secret import flag
4
import hashlib
5

6
def mul(a, b, n):
7
    return ((a[0]*b[0]+2*a[1]*b[2]+2*a[2]*b[1]) % n, (a[0]*b[1]+a[1]*b[0]+2*a[2]*b[2]) % n, (a[0]*b[2]+a[2]*b[0]+a[1]*b[1]) % n)
8
def powmod(a, b, n):
9
    res = (1, 0, 0)
10
    while b > 0:
11
        if b & 1 == 1:
12
            res = mul(res, a, n)
13
        a = mul(a, a, n)
14
        b >>= 1
15
    return res
16

17
p = getPrime(512)
18
q = getPrime(512)
19
N = p * q
20

21
e = 13
22

23
mask = [os.urandom(64) for i in range(3)]
24
m = tuple(bytes_to_long(i) for i in mask)
25
hint = mask[2]
26

27
c = powmod(m, e, N)
28

29
xor = lambda a,b:[i^j for i,j in zip(a,b)]
30
cipher = bytes(xor(hashlib.sha512(b''.join(mask)).digest(),flag))
31

32
print(f'{N = }')
33
print(f'{e = }')
34
print(f'{c = }')
35
print(f'{hint = }')
36
print(f'{cipher = }')
37

38
'''
39
N = ...
40
e = 13
41
c = (..., ..., ...)
42
hint = b'...'
43
cipher = b'...'
44
'''

前两天 ISCTF 上碰到的下架的题目也是结式题，在这再仔细学习学习（不过这题好难，是环上的结式并非是域上的）。

首先本题得了解一下商环，在此暂时不展开说明。了解完仔细看看这个mul函数就会发现这是一个商环 $R=\mathbb{F}_N[x]/(x^3-2)$ 上的乘法。而m是R中的一个随机元素并且泄露了其a2分量，根据m和c的各分量相等我们可以给出三个方程，未知数为a0和a1。

为了进一步简化问题，可以利用结式（Resultant）来消去一个未知数。结式是通过消去多项式中的一个变量，得到另一个关于剩余变量的方程。在本题中，环上无法使用resultant函数，可以利用 Sylvester 矩阵 来计算结式，并通过计算行列式来判断多项式是否有公共根。具体来说，通过计算多项式的 Sylvester 矩阵的行列式来得到结式，从而消去未知数，并通过得到的方程求解出 (a_0) 和 (a_1)。再结合hint就可以计算出m了。

exp.py：

1
# SageMath 10.7
2
from Crypto.Util.number import *
3
from hashlib import sha512
4

5
def poly_gcd(f, g):
6
    if f.degree() < g.degree():
7
        f, g = g, f
8
    while not g.is_zero():
9
        f, g = g, f % g
10
    return f
11

12
xor = lambda a, b: [i ^^ j for i, j in zip(a, b)]
13

14
N = ...
15
e = 13
16
c = (..., ..., ...)
17
hint = b'...'
18
cipher = b'...'
19
h = bytes_to_long(hint)
20
R.<s, t, x> = Zmod(N)[]
21
C = c[0] + c[1] * x + c[2] * x ** 2
22
m = s + t * x + h * x ** 2
23
c1 = m ** e - C
24
# 这里 c2 = c1 % (x ** 3 - 2) 有点小问题，还没弄明白，手搓了一个
25
c2 = c1
26
while c2.degree(x) >= 3:
27
    for i in range(3, c2.degree(x) + 1):
28
        c2 += 2 * c2.coefficient({x:i}) * (x ** (i - 3))
29
        c2 -= c2.coefficient({x:i}) * (x ** i)
30
cc1 = c2.coefficient({x:0})
31
cc2 = c2.coefficient({x:1})
32
cc3 = c2.coefficient({x:2})
33
ccc1 = cc1.sylvester_matrix(cc2, R.gen(1)).det()
34
ccc2 = cc1.sylvester_matrix(cc3, R.gen(1)).det()
35
F2.<q> = Zmod(N)[]
36
ccc1 = ccc1(q, 0, 0)
37
ccc2 = ccc2(q, 0, 0)
38
mask1 = N - poly_gcd(ccc1, ccc2).monic()[0]
39
ccc3 = cc1(mask1, q, 0)
40
ccc4 = cc2(mask1, q, 0)
41
mask2 = N - poly_gcd(ccc3, ccc4).monic()[0]
42
flag = bytes(xor(sha512(long_to_bytes(int(mask1)) + long_to_bytes(int(mask2)) + hint).digest(), cipher))
43
print(flag.decode())
44
# flag{D0N'T_B3_Depr3s5i0n_bE_HOpefu1_4nd_HappY}

持续更新中~

Crypto#

Week 1#

Basic Number theory#

Strange Machine#

beyondHex#

certificate#

two Es#

xorRSA#

Week 2#

AES_mode#

Common RSA#

Furious BlackCopper#

baby Elgamal#

findKey in middle#

strange random#

Week 3#

Backpack#

Great Block Cipher#

abc equation(!)#

my crypto#

期末考试(!)#

粗心的刀客塔#

Week 4#

Crazy List(-)#

Myneighbors#

RSA紧缩术(*)#

Xaleid◆scopiX(*)#

ezECC(-)#

linear function?(*)#

异域症(*)#