2018 ACTF WriteUp

前言

主办方：XCTF

Crypto

你能看出这是什么加密么（RSA）

1
2
3
4
5
6
7
p=0x928fb6aa9d813b6c3270131818a7c54edb18e3806942b88670106c1821e0326364194a8c49392849432b37632f0abe3f3c52e909b939c91c50e41a7b8cd00c67d6743b4f

q=0xec301417ccdffa679a8dcc4027dd0d75baf9d441625ed8930472165717f4732884c33f25d4ee6a6c9ae6c44aedad039b0b72cf42cab7f80d32b74061

e=0x10001

c=0x70c9133e1647e95c3cb99bd998a9028b5bf492929725a9e8e6d2e277fa0f37205580b196e5f121a2e83bc80a8204c99f5036a07c8cf6f96c420369b4161d2654a7eccbdaf583204b645e137b3bd15c5ce865298416fd5831cba0d947113ed5be5426b708b89451934d11f9aed9085b48b729449e461ff0863552149b965e22b6   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2

p = 0x928fb6aa9d813b6c3270131818a7c54edb18e3806942b88670106c1821e0326364194a8c49392849432b37632f0abe3f3c52e909b939c91c50e41a7b8cd00c67d6743b4f
q = 0xec301417ccdffa679a8dcc4027dd0d75baf9d441625ed8930472165717f4732884c33f25d4ee6a6c9ae6c44aedad039b0b72cf42cab7f80d32b74061
e = 0x10001
c = 0x70c9133e1647e95c3cb99bd998a9028b5bf492929725a9e8e6d2e277fa0f37205580b196e5f121a2e83bc80a8204c99f5036a07c8cf6f96c420369b4161d2654a7eccbdaf583204b645e137b3bd15c5ce865298416fd5831cba0d947113ed5be5426b708b89451934d11f9aed9085b48b729449e461ff0863552149b965e22b6

# RSA 解密
n = p * q
phi = (p-1) * (q-1)
d = gmpy2.invert(e, phi)
m = gmpy2.powmod(c, d, n)

# 将解密后的大整数转换为字节串
# 注意：m 的 bit 长度不一定是 8 的倍数，用 (bit_length+7)//8 计算字节数
byte_len = (m.bit_length() + 7) // 8
m_bytes = m.to_bytes(byte_len, 'big')

# 直接打印全部字节（可能包含不可打印字符，但能看到 flag）
print("全部字节串:", m_bytes)

得到 afctf{R54_|5_$0_$imp13}

MyOwnCBC（AES-ECB）

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
#!/usr/bin/python2.7
# -*- coding: utf-8 -*-

from Crypto.Cipher import AES
from Crypto.Random import random
from Crypto.Util.number import long_to_bytes

def MyOwnCBC(key, plain):
	if len(key)!=32:
		return "error!"
	cipher_txt = b""
	cipher_arr = []
	cipher = AES.new(key, AES.MODE_ECB, "")
	plain = [plain[i:i+32] for i in range(0, len(plain), 32)]
	print (plain)
	cipher_arr.append(cipher.encrypt(plain[0]))
	cipher_txt += cipher_arr[0]
	for i in range(1, len(plain)):
		cipher = AES.new(cipher_arr[i-1], AES.MODE_ECB, "")
		cipher_arr.append(cipher.encrypt(plain[i]))
		cipher_txt += cipher_arr[i]
	return cipher_txt

key = random.getrandbits(256)
key = long_to_bytes(key)

s = ""
with open("flag.txt","r") as f:
	s = f.read()
	f.close()

with open("flag_cipher","wb") as f:
	f.write(MyOwnCBC(key, s))
	f.close()

加密流程：

  • C0 = AES_ECB(key, P0)，输出 32 字节（因为 P0 是 32 字节）

  • C1 = AES_ECB(C0, P1)

  • C2 = AES_ECB(C1, P2)

  • ……

密文文件正是 C0 + C1 + C2 + ... 的拼接

1
2
3
4
plain = [plain[i:i+32] for i in range(0, len(plain), 32)]   # 每 32 字节一组
cipher_arr.append(cipher.encrypt(plain[0]))          # 第一块：用主密钥 key 加密
cipher = AES.new(cipher_arr[i-1], AES.MODE_ECB, "")  # 后续块：用前一块密文做密钥
cipher_arr.append(cipher.encrypt(plain[i]))

AES 是对称加密，加密和解密使用同一个密钥

对于 C1 来说，加密时用的密钥是 C0，而这个 C0 就保存在密文文件的最前面 32 字节

因此只要拿到了密文文件，我们就可以用 C0 作为密钥解密 C1，得到 P1；再用 C1 解密 C2 得到 P2…… 依此类推，完全不需要主密钥 key

解密步骤如下：

    1. 读取 flag_cipher 文件，得到完整密文字节串
    1. 按 32 字节一组切分成 blocks = [C0, C1, C2, ..., Cn]
    1. 对 i 从 1 到 n，用 C_{i-1} 作为密钥，解密 C_i 得到 P_i
    1. 将所有解密出的 P_i 拼接，即得到从第二块开始的明文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Cipher import AES

# 读取密文文件
with open('flag_cipher', 'rb') as f:
    data = f.read()

# 每 32 字节切一个块
blocks = [data[i:i+32] for i in range(0, len(data), 32)]

plaintext = b''
for i in range(1, len(blocks)):
    key = blocks[i-1]          # 前一个密文块就是本轮的密钥
    cipher = AES.new(key, AES.MODE_ECB)
    plain_block = cipher.decrypt(blocks[i])
    plaintext += plain_block

# 打印结果（可能尾部有填充，但 flag 通常以 } 结尾，直接看即可）
print(plaintext.decode('latin-1'))

得到 afctf{Don't_be_fooled_by_yourself}

Morse（摩斯密码）

拿到密文

1
-..../.----/-..../-..../-..../...--/--.../....-/-..../-..../--.../-.../...--/.----/--.../...--/..---/--.../--.../....-/...../..-./--.../...--/...--/-----/...../..-./...--/...--/...--/....-/...--/...../--.../----./--.../-..

解密得到 actf{1s't_s0_345y}

Tiny LFSR（流密码密钥重用）

附件：

  • .bash_history.txt：记录了两条加密命令

  • Encrypt.py：加密脚本

  • Plain.txt：已知明文

  • cipher.txt：Plain.txt 的密文

  • flag_encode.txt：flag.txt 的密文

查看 .bash_history.txt

1
2
3
4
python Encrypt.py key.txt Plain.txt cipher.txt
python Encrypt.py key.txt flag.txt flag_encode.txt
rm flag.txt
rm key.txt

这说明同一个密钥 key.txt 被用来加密了 Plain.txt 和 flag.txt

脚本分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
key = ""                    # 读取 key.txt（十六进制字符串）
R = int(key,16)             # 将 key 转成整数，作为 LFSR 的种子
mask = 0b1101100000000...   # 64 位的 mask

a = ''.join([chr(int(b, 16)) for b in [key[i:i+2] for i in range(0, len(key), 2)]])
# a 是 key 的十六进制解码后的字节串（8 字节，因为 1 字节等于 8bit）

# 加密过程：
# 前 len(a) 字节（即 8 字节）：直接用 a 的对应字节与明文异或
for i in range(0, len(a)):
    ff.write((ord(s[i])^ord(a[i])).to_bytes(1, byteorder='big'))

# 之后的字节：反复调用 lfsr(R, mask) 生成伪随机字节，与明文异或
for i in range(len(a), lent):
    tmp=0
    for j in range(8):       # 每 8 次 LFSR 输出合成一个字节
        (R,out)=lfsr(R,mask)
        tmp=(tmp << 1)^out
    ff.write((tmp^ord(s[i])).to_bytes(1, byteorder='big'))

加密实质：这是一个流密码，密文 = 明文 ⊕ 密钥流

密钥流的前 8 字节是固定的 a，后续由 LFSR 以 R 为种子不断生成

1. 流密码密钥重用

同一个种子 R 被用来加密了两个不同的文件，如果获得一对已知的明文和密文，攻击者就可以通过异或提取整个密钥流

1
密钥流 = 明文 ⊕ 密文

然后，用这个密钥流去异或其他被同一密钥流加密的密文，就能得到对应的明文

2. 已知明文

我们正好有 Plain.txt 的明文内容，以及它的密文 cipher.txt

所以我们可以提取出前 len(Plain) 字节的密钥流，并用来解密 flag_encode.txt 的同样多的字节

但是 flag.txt 的长度可能超过 Plain.txt，此时密钥流就不够用了

3. 恢复 LFSR 种子

要得到完整的密钥流，我们需要知道种子 R（也就是 key.txt 的内容）

注意到：密钥流的前 8 字节就是 a，而 a 由 key.txt 直接解码得到

因此，我们可以通过明文 Plain.txt 的前 8 字节与密文 cipher.txt 的前 8 字节异或，恢复出 a

  • a = Plain[:8] XOR cipher[:8]

  • 然后将 a 转回十六进制字符串，即 key = a.hex()

  • 再 R = int(key, 16)，LFSR 种子到手！

4. 重新生成完整密钥流

有了 R 和公开的 mask，我们就可以完全复现加密时 LFSR 的整个生命周期，生成任意长度的密钥流

从第 9 字节开始，运行与加密程序相同的代码，一直生成到长度 ≥ flag_encode.txt 的长度

5. 解密 flag

将生成的完整密钥流与 flag_encode.txt 逐字节异或，得到完整的 flag.txt 明文

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
# ---------- 原题 LFSR 函数 ----------
def lfsr(R, mask):
    output = (R << 1) & 0xffffffffffffffff
    i = (R & mask) & 0xffffffffffffffff
    lastbit = 0
    while i != 0:
        lastbit ^= (i & 1)
        i = i >> 1
    output ^= lastbit
    return (output, lastbit)

# ---------- 1. 读取文件 ----------
with open('Plain.txt', 'rb') as f: plain = f.read()
with open('cipher.txt', 'rb') as f: cipher = f.read()
with open('flag_encode.txt', 'rb') as f: flag_enc = f.read()

# ---------- 2. 恢复前 8 字节密钥 a ----------
a = bytes([p ^ c for p, c in zip(plain[:8], cipher[:8])])

# ---------- 3. 恢复种子 R ----------
key_hex = a.hex()
R = int(key_hex, 16)
mask = 0b1101100000000000000000000000000000000000000000000000000000000000

# ---------- 4. 生成足够长的密钥流 ----------
keystream = bytearray(a)    # 前 8 字节直接使用
while len(keystream) < len(flag_enc):
    tmp = 0
    for j in range(8):
        R, out = lfsr(R, mask)
        tmp = (tmp << 1) ^ out
    keystream.append(tmp)

# ---------- 5. 解密 ----------
flag = bytes([k ^ f for k, f in zip(keystream, flag_enc)])
print(flag.decode(errors='replace'))

得到 actf{read_is_hard_but_worthy}

Base（Base 编码）

编写脚本循环解码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import re
import base64

s = open('文件路径', 'rb').read()
base16_dic = r'^[A-F0-9=]*$'
base32_dic = r'^[A-Z2-7=]*$'
base64_dic = r'^[A-Za-z0-9/+=]*$'
n = 0

while True:
    n += 1
    t = s.decode()
    if '{' in t:
        print(t)
        break
    elif re.match(base16_dic, t):
        s = base64.b16decode(s)
        print(f'{n} base16')
    elif re.match(base32_dic, t):
        s = base64.b32decode(s)
        print(f'{n} base32')
    elif re.match(base64_dic, t):
        s = base64.b64decode(s)
        print(f'{n} base64')

得到 afctf{U_5h0u1d_Us3_T00l5}

Vigenère（Vigenère 密码明文攻击）

题目给出的 C 程序实现的是标准维吉尼亚密码

找到一个自动破解维吉尼亚密码的在线工具：https://www.guballa.de/vigenere-solver

找到 flag

你听过一次一密么？（Many-Time Pad）

1
2
3
4
5
6
7
8
9
10
11
25030206463d3d393131555f7f1d061d4052111a19544e2e5d
0f020606150f203f307f5c0a7f24070747130e16545000035d
1203075429152a7020365c167f390f1013170b1006481e1314
0f4610170e1e2235787f7853372c0f065752111b15454e0e09
081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a18
0909075412132e247436425332281a1c561f04071d520f0b11
4116111b101e2170203011113a69001b475206011552050219
041006064612297020375453342c17545a01451811411a470e
021311114a5b0335207f7c167f22001b44520c15544801125d
06140611460c26243c7f5c167f3d015446010053005907145d
0f05110d160f263f3a7f4210372c03111313090415481d49

如果同一个 keystream 加密了多段明文，那么任意两段密文异或就等于两段明文异或：

1
c1 XOR c2 = (p1 XOR key) XOR (p2 XOR key) = p1 XOR p2

利用英文文本中含有大量空格（0x20）的特点，当字母与空格异或时，会改变字母的大小写（'a' ^ 0x20 = 'A'），这可以帮助我们推断字符位置

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
59
60
61
62
63
64
from itertools import combinations

cipher_hex = [
    "25030206463d3d393131555f7f1d061d4052111a19544e2e5d",
    "0f020606150f203f307f5c0a7f24070747130e16545000035d",
    "1203075429152a7020365c167f390f1013170b1006481e1314",
    "0f4610170e1e2235787f7853372c0f065752111b15454e0e09",
    "081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a18",
    "0909075412132e247436425332281a1c561f04071d520f0b11",
    "4116111b101e2170203011113a69001b475206011552050219",
    "041006064612297020375453342c17545a01451811411a470e",
    "021311114a5b0335207f7c167f22001b44520c15544801125d",
    "06140611460c26243c7f5c167f3d015446010053005907145d",
    "0f05110d160f263f3a7f4210372c03111313090415481d49"
]

ciphers = [bytes.fromhex(x) for x in cipher_hex]

max_len = max(len(c) for c in ciphers)

# 保存推测出的key
key = [None] * max_len

# 判断是否是英文字母
def is_alpha(x):
    return chr(x).isalpha()

# 统计每个密文每个位置可能为空格
space_count = [ [0]*max_len for _ in range(len(ciphers)) ]

for i in range(len(ciphers)):
    for j in range(len(ciphers)):
        if i == j:
            continue

        xor_bytes = bytes([
            ciphers[i][k] ^ ciphers[j][k]
            for k in range(min(len(ciphers[i]), len(ciphers[j])))
        ])

        for k,b in enumerate(xor_bytes):
            if is_alpha(b):
                space_count[i][k] += 1

# 阈值判断
threshold = 7

for i in range(len(ciphers)):
    for k in range(len(ciphers[i])):
        if space_count[i][k] >= threshold:
            # 假设当前位置是空格
            key[k] = ciphers[i][k] ^ ord(' ')

# 解密
for c in ciphers:
    plain = ""

    for i in range(len(c)):
        if key[i] is not None:
            plain += chr(c[i] ^ key[i])
        else:
            plain += "*"

    print(plain)

得到

1
2
3
4
5
6
7
8
9
10
11
Dear Friend, T*is tim* I u
nderstood my m*stake *nd u
sed One time p*d encr*ptio
n scheme, I he*rd th*t it
is the only en*ryptio*n met
hod that is ma*hemati*cally
 proven to be *ot cra*ked
ever if the ke* is ke*t se
cure, Let Me k*ow if *ou a
gree with me t* use t*is e
ncryption sche*e alwa*s...

人工补全

1
Dear Friend, This time I understood my mistake and used One time pad encryption scheme, I heard that it is the only encryption method that is mathematically proven to be not cracked ever if the key is kept secure, Let Me know if you agree with me to use this encryption scheme always...

恢复 Key 然后解密拿到 flag

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
cipher_hex = [
    "25030206463d3d393131555f7f1d061d4052111a19544e2e5d",
    "0f020606150f203f307f5c0a7f24070747130e16545000035d",
    "1203075429152a7020365c167f390f1013170b1006481e1314",
    "0f4610170e1e2235787f7853372c0f065752111b15454e0e09",
    "081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a18",
    "0909075412132e247436425332281a1c561f04071d520f0b11",
    "4116111b101e2170203011113a69001b475206011552050219",
    "041006064612297020375453342c17545a01451811411a470e",
    "021311114a5b0335207f7c167f22001b44520c15544801125d",
    "06140611460c26243c7f5c167f3d015446010053005907145d",
    "0f05110d160f263f3a7f4210372c03111313090415481d49"
]

ciphers = [bytes.fromhex(x) for x in cipher_hex]

plain = b"Dear Friend, This time I "

cipher = ciphers[0]

key = bytes([
    cipher[i] ^ plain[i]
    for i in range(len(plain))
])

print("KEY =", key)

for c in ciphers:
    res = ""

    for i in range(len(c)):
        if i < len(key):
            res += chr(c[i] ^ key[i])

    print(res)

得到 afctf{OPT_10.I.t3rest.ni}

可怜的 RSA（PKCS1_OAEP 解密）

题目给出公钥

1
2
3
4
5
6
7
8
9
-----BEGIN PUBLIC KEY-----
MIIBJDANBgkqhkiG9w0BAQEFAAOCAREAMIIBDAKCAQMlsYv184kJfRcjeGa7Uc/4
3pIkU3SevEA7CZXJfA44bUbBYcrf93xphg2uR5HCFM+Eh6qqnybpIKl3g0kGA4rv
tcMIJ9/PP8npdpVE+U4Hzf4IcgOaOmJiEWZ4smH7LWudMlOekqFTs2dWKbqzlC59
NeMPfu9avxxQ15fQzIjhvcz9GhLqb373XDcn298ueA80KK6Pek+3qJ8YSjZQMrFT
+EJehFdQ6yt6vALcFc4CB1B6qVCGO7hICngCjdYpeZRNbGM/r6ED5Nsozof1oMbt
Si8mZEJ/Vlx3gathkUVtlxx/+jlScjdM7AFV5fkRidt0LkwosDoPoRz/sDFz0qTM
5q5TAgMBAAE=
-----END PUBLIC KEY-----

编写脚本提取 n 和 e

1
2
3
4
5
6
7
from Crypto.PublicKey import RSA

with open('public.key','rb') as f:
    pub = RSA.import_key(f.read())

print(pub.n)
print(pub.e)

得到 e = 65537 和一个超大的 n

使用 factordb 分解 n 得到

1
2
3
p = 3133337

q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939

flag.enc 是 PKCS1_OAEP，需要使用 OAEP 解密器

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
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import base64

# 读取公钥
with open('public.key', 'rb') as f:
    pub = RSA.import_key(f.read())

n = pub.n
e = pub.e

print("[+] n =", n)
print("[+] e =", e)

# factordb 分解结果
p = 3133337

q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939

# 计算私钥
phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)

print("[+] d =", d)

# 构造 RSA 私钥
private_key = RSA.construct((n, e, d, p, q))

# OAEP 解密器
cipher = PKCS1_OAEP.new(private_key)

# 读取密文
with open('flag.enc', 'rb') as f:
    enc = f.read()

# base64 解码
enc = base64.b64decode(enc)

# 解密
flag = cipher.decrypt(enc)

print("[+] FLAG =", flag.decode())

得到 afctf{R54_|5_$0_B0rin9}

MagicNum（浮点数）

题目附件

1
2
3
4
5
6
72065910510177138000000000000000.000000
71863209670811371000000.000000
18489682625412760000000000000000.000000
72723257588050687000000.000000
4674659167469766200000000.000000
19061698837499292000000000000000000000.000000

根据 IEEE 754 单精度浮点数标准，一个 float 在内存中由 32 位组成：

  • 1 位符号位（S）

  • 8 位指数位（E）

  • 23 位尾数位（M）

将 720659…… 转为二进制，算出它的 IEEE 754 十六进制表达为：0x73666361

在 x86/x64 体系架构下，内存存储通常是小端序，即低位字节存放在低地址，高字节存放在高地址

我们将 0x73666361 按字节逆序（每两个 Hex 为一个字节）排列，得到：

1
61 63 66 73

拼起来就是 acfs

在不知道是 float（4字节）还是 double（8字节）时，可以用 Python 编写一个双向测试脚本

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
import struct

nums = [
    72065910510177138000000000000000.000000,
    71863209670811371000000.000000,
    18489682625412760000000000000000.000000,
    72723257588050687000000.000000,
    4674659167469766200000000.000000,
    19061698837499292000000000000000000000.000000
]

# 尝试 1：假设是 float（单精度 4 字节，小端序 '<f'）
print("--- 尝试 Float 小端序 ---")
flag_f = b""
for n in nums:
    flag_f += struct.pack('<f', n)
print(flag_f.decode('utf-8', errors='ignore'))

# 尝试 2：假设是 double（双精度 8 字节，小端序 '<d'）
print("\n--- 尝试 Double 小端序 ---")
flag_d = b""
for n in nums:
    try:
        flag_d += struct.pack('<d', n)
    except:
        pass
print(flag_d.decode('utf-8', errors='ignore'))

得到 afctf{sec_is_everywhere}

花开藏宝地（Asmuth-Bloom）

提示内容大意是：藏宝图被分成 5 份交给五位贤者保管，只需收集任意 3 份即可恢复宝藏地址。这本质上是 (3, 5) 门限秘密共享方案

推测考察的是 Asmuth-Bloom 秘密共享

题目 5 个压缩包中，前三个的密码可通过暴力破解结合线索推断得到

  • 第一位贤者说 “口令就是我的生日”，这是一个历史日期（19260817）

  • 第二位贤者说 “小声念着自己的名字”（alice）

  • 第三位贤者说 “大声喊出那句咒语”（AVADA）

  • 第四位贤者说 “找了个破锁”（伪加密）

  • 第五位贤者说 “裹上了隐身衣”（NTFS 流）

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 inverse, long_to_bytes
from functools import reduce

# ==================== 三组子秘密 ====================
# 注意：第一行的数是余数（x），第二行的数是模数（m）
x1 = 305345133911395218573790903508296238659147802274031796643017539011648802808763162902335644195648525375518941848430114497150082025133000033835083076541927530829557051524161069423494451667848236452337271862085346869364976989047180532167560796470067549915390773271207901537847213882479997325575278672917648417868759077150999044891099206133296336190476413164240995177077671480352739572539631359
m1 = 347051559622463144539669950096658163425646411435797691973701513725701575100810446175849424000000075855070430240507732735393411493866540572679626172742301366146501862670272443070970511943485865887494229487420503750457974262802053722093905126235340380261828593508455621667309946361705530667957484731929151875527489478449361198648310684702574627199321092927111137398333029697068474762820813413

x2 = 152012681270682340051690627924586232702552460810030322267827401771304907469802591861912921281833890613186317787813611372838066924894691892444503039545946728621696590087591246339208248647926966446848123290344911662916758039134817404720512465817867255277476717353439505243247568126193361558042940352204093381260402400739429050280526212446967632582771424597203000629197487733610187359662268583
m2 = 347051559622463144539669950096658163425646411435797691973701513725701575100810446175849424000000075855070430240507732735393411493866540572679626172742301366146501862670272443070970511943485865887494229487420503750457974262802053722093905126235340380261828593508455621667309946361705530667957484731929151875527489478449361198648310684702574627199321092927111137398333029697068474762820818553

x4 = 100459779913520540098065407420629954816677926423356769524759072632219106155849450125185205557491138357760494272691949199099803239098119602186117878931534968435982565071570831032814288620974807498206233914826253433847572703407678712965098320122549759579566316372220959610814573945698083909575005303253205653244238542300266460559790606278310650849881421791081944960157781855164700773081375247
m4 = 347051559622463144539669950096658163425646411435797691973701513725701575100810446175849424000000075855070430240507732735393411493866540572679626172742301366146501862670272443070970511943485865887494229487420503750457974262802053722093905126235340380261828593508455621667309946361705530667957484731929151875527489478449361198648310684702574627199321092927111137398333029697068474762820820091

# ==================== 全局大素数 p ====================
p = 80804238007977405688648566160504278593148666302626415149704905628622876270862865768337953835725801963142685182510812938072115996355782396318303927020705623120652014080032809421180400984242061592520733710243483947230962631945045134540159517488288781666622635328316972979183761952842010806304748313326215619695085380586052550443025074501971925005072999275628549710915357400946408857

# ==================== 中国剩余定理求解 ====================
mods = [m1, m2, m4]   # 模数
vals = [x1, x2, x4]   # 余数

M = reduce(lambda a, b: a * b, mods)   # 所有模数的乘积
ans = 0

for mi, xi in zip(mods, vals):
    Mi = M // mi
    ti = inverse(Mi, mi)    # Mi 关于 mi 的逆元
    ans += xi * Mi * ti

ans %= M

# ==================== 恢复秘密 ====================
secret = ans % p
print("[+] 恢复出的秘密 S =", secret)

# 转为字节串
flag = long_to_bytes(secret)
print(flag.decode())

Single（单表替换）

题目提供的 C++ 程序本质上是一个单表替换密码的加密机

它通过随机洗牌（random_shuffle）为 26 个英文字母建立了一张一对一的随机映射表，同时保留字母的大小写关系，非字母字符不变，因此加密是可逆的

使用 quipqiup 替换密码破解器

一道有趣的题目（位关系传播）

题目源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
解题思路还是不够详细，这是题目代码：

#加密代码
def encrypt(plainText):
    space = 10
    cipherText = ""
    for i in range(len(plainText)):
        if i + space < len(plainText) - 1:
            cipherText += chr(ord(plainText[i]) ^ ord(plainText[i + space]))
        else:
            cipherText += chr(ord(plainText[i]) ^ ord(plainText[space]))
        if ord(plainText[i]) % 2 == 0:
            space += 1
        else:
            space -= 1
    return cipherText
    
# 密码
# 15120d1a0a0810010a031d3e31000d1d170d173b0d173b0c07060206

有一个致命的变量叫做 space（初始值是 10），在遍历明文的每一个字符时，它会做两件事：

    1. 异或加密：拿当前的字符，和后面距离它 space 那么远的字符进行异或
    1. 改变规则：如果当前字符的 ASCII 码是偶数，space 就加 1；如果是奇数，space 就减 1

因为 space 是动态变化的。要想知道第 5 个字符是跟谁异或的，你就必须知道前 4 个字符到底是奇数还是偶数

可我们现在只有密文，根本不知道明文的奇偶性

这就导致我们连 “谁和谁进行了异或” 都无法确定，产生了一条链式依赖

既然正着推推不出，反着逆也不行，那就采用 “剥洋葱” 的策略：先剥离出最简单、最核心的 “奇偶特征”，再顺藤摸瓜

异或运算（^）有一个天然的铁律：

  • 奇数 ^ 奇数 = 偶数

  • 偶数 ^ 偶数 = 偶数

  • 奇数 ^ 偶数 = 奇数

我们爆破的思路就是：

    1. 假定一种 “奇偶路线图”（比如假设 28 个字符分别是：奇偶奇奇偶……）
    1. 模拟加密过程，因为知道了奇偶，就能完美算出每一步的 space 应该加 1 还是减 1，也就知道了谁和谁配对
    1. 把配对的两个 “假设奇偶性” 异或一下，看看结果是否等于密文对应位置的奇偶性
    1. 一旦发现某一步算出来的奇偶性跟密文对不上，说明这个假设是错的，立马 break 放弃，换下一种假设

拿到了正确的 “奇偶路线图” 后，我们已经百分之百确定每一步的 space 是多少

例如：第 0 个字符是跟第 10 个字符异或的……

得到：明文[A] ^ 明文[B] = 密文[某个已知数字]

根据异或的特性：明文[B] = 明文[A] ^ 密文

这道题的开头一定是 afctf{，结尾一定是 }，提前知道了第 0、1、2、3、4、5 位以及最后一位的真实字符

最后反复循环

假设我们要破解的明文只有 3 个字符，分别记为 P0, P1, P2

我们拿到的密文是：[4, 12, 7]

开头固定格式：

1
P0 = 'a'  (ASCII = 97，奇数)

我们拿到的密文是：

1
[4, 12, 7]

换算成奇偶性就是：

1
[偶数, 偶数, 奇数]

令 space 为 1

1
space = 1

假设这三个数是【奇数、偶数、偶数】

按照规则，下一关的 space 就要减 1，变成：

1
space = 1 - 1 = 0

此时 P0 会和距离为 1 的 P1 配对：

1
加密结果 = P0 ^ P1

根据假设，P0 奇、P1 偶，则：

1
奇 ^ 偶 = 奇

可是实际的密文第 0 位是 4（偶数），直接淘汰这个路线

假设这三个数是【奇数、奇数、奇数】，将第二个由偶数变为奇数，则 space 为 0 了

1
2
P0 ^ P1
奇 ^ 奇 = 偶

实际密文第 0 位是 4（偶数），完美对上！！！

既然知道了路线是【奇、奇、奇】，脚本就百分之百确定了每一关的 space 到底是多少

1
2
P0 和 P1 配对
P1 和 P2 配对

现在我们手里有账本和真正的密文：

1
2
3
P0 ^ P1 = 4
P1 ^ P2 = 12
P0 = 'a' = 97

利用异或的特性，可以直接算出：

1
P1 = 97 ^ 4 = 93  (字符 ']')

那么

1
P2 = 93 ^ 12 = 81  (字符 'Q')

完整解题脚本：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
from Crypto.Util.number import long_to_bytes

def crackit():
    '''暴力破解每个明文字符的最后一位 (LSB)'''
    # 原始密文16进制，转为字节
    tag = b'\x15\x12\r\x1a\n\x08\x10\x01\n\x03\x1d>1\x00\r\x1d\x17\r\x17;\r\x17;\x0c\x07\x06\x02\x06'
    
    # 遍历所有可能的28位二进制序列
    for x in range(2**28):
        temp = bin(x)[2:].zfill(28)
        space = 10
        flag = 0
        for i in range(len(temp)):
            # 根据i和space计算异或的配对索引
            if i + space < len(temp) - 1:
                tempx = int(temp[i]) ^ int(temp[i + space])
            else:
                tempx = int(temp[i]) ^ int(temp[space])
            
            # 检查当前位异或结果是否与密文LSB匹配
            if tempx != (tag[i] % 2):
                flag = 1
                break
            elif int(temp[i]) % 2 == 0:
                space += 1
            else:
                space -= 1
        
        # 如果全部匹配，打印结果
        if flag != 1:
            print("找到正确的LSB序列:", temp)
            return temp
    return None

def crackit_2(lsb_str):
    '''根据LSB序列，解出每个密文字节对应的明文字符序号'''
    tag = b'\x15\x12\r\x1a\n\x08\x10\x01\n\x03\x1d>1\x00\r\x1d\x17\r\x17;\r\x17;\x0c\x07\x06\x02\x06'
    space = 10
    g = []  # 存储配对关系
    for i in range(len(lsb_str)):
        if i + space < len(lsb_str) - 1:
            tempx = int(lsb_str[i]) ^ int(lsb_str[i + space])
            g.append((i, i + space))
        else:
            tempx = int(lsb_str[i]) ^ int(lsb_str[space])
            g.append((i, space))
        
        if int(lsb_str[i]) % 2 == 0:
            space += 1
        else:
            space -= 1
    return g

def solve(g, m):
    '''解明文方程组，迭代求解'''
    # 已知flag格式 afctf{，最后一位为 }，其余未知
    plain = [ord('a'), ord('f'), ord('c'), ord('t'), ord('f'), ord('{')] + [-1] * 21 + [ord('}')]
    
    # 迭代求解直到所有未知数被解出
    while -1 in plain:
        for i in range(28):
            if plain[i] != -1:
                for j in range(len(g)):
                    if g[j][0] == i or g[j][1] == i:
                        if g[j][0] == i:
                            plain[g[j][1]] = m[j] ^ plain[i]
                        if g[j][1] == i:
                            plain[g[j][0]] = m[j] ^ plain[i]
    return plain

if __name__ == '__main__':
    # 原始密文 (16进制)
    cipher_hex = '15120d1a0a0810010a031d3e31000d1d170d173b0d173b0c07060206'
    cipher_bytes = long_to_bytes(int(cipher_hex, 16))
    
    print("开始爆破明文LSB序列...")
    lsb_sequence = crackit()
    if not lsb_sequence:
        print("爆破失败，检查代码。")
        exit()
        
    print("生成异或配对关系...")
    pairs = crackit_2(lsb_sequence)
    
    print("开始迭代解算明文...")
    plain_ascii = solve(pairs, cipher_bytes)
    print("ASCII 结果:", plain_ascii)
    
    flag = ''.join(chr(i) for i in plain_ascii)
    print("解密结果:", flag)
    # 根据题目要求，将afctf替换为flag
    final_flag = flag.replace('afctf', 'flag')
    print("最终FLAG:", final_flag)

One Secret, Two encryption（公共因数）

在生成两套不同的 RSA 密钥对时，重复使用了同一个质数 p

  • 从公钥 1 中提取出：n1 和指数 e1

  • 从公钥 2 中提取出：n2 和指数 e2

拿到 n1 和 n2 之后，直接扔进最大公约数函数里算一下

1
p = gcd(n1, n2)

我们顺手就能算出剩下的两个独立素数

1
2
q1 = n1 / p
q2 = n2 / p
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
import gmpy2
import libnum

# ---------- 1. 已知参数 ----------
n = 4850297138162223468826481623082440249579136876798312652735204698689613969008632545220976699170308454082390834742570718247804202060929493571642074679428565168405877110681518105667301785653517697684490982375078989886040451115082120928982588380914609273008153977907950532498605486225883973643141516024058315360572988744607134110254489421516026937249163493982681336628726033489124705657217768229058487155865265080427488028921879608338898933540825564889012166181346177276639828346376362168934208822467295673761876965864573164529336885250577357767314256581019474130651412100897839606491189424373959244023695669653213498329

p = 174410123761631337520799179808598127914184971978811796722414215239874114048347830609255805203105210941441708658356189056418366104015120153227123562166980882513945308613658062284844636341082646995916907680076101741743945938845994542592182491688095893467336553001430454260431413695816790105384153941685561590503
q = 27809722472252756488236572384949349891208643090117349509994417047989746484576130392206781875743390815588696964830219136848285391966773129269973231061599768809907518881304479207799187410626121509031210549317480187679455501340422680238395009932081263455435640341892702399022829951248686529928945588545968218943
e = 1666626632960368239001159408047765991270250042206244157447171188195657302933019501932101777999510001235736338843107709871785906749393004257614129802061081155861433722380145001537181142613515290138835765236002811689986472280762408157176437503021753061588746520433720734608953639111558556930490721517579994493088551013050835690019772600744317398218183883402192060480979979456469937863257781362521184578142129444122428832106721725409309113975986436241662107879085361014650716439042856013203440242834878648506244428367706708431121109714505981728529818874621868624754285069693368779495316600601299037277003994790396589299

# ---------- 2. 读取密文 ----------
with open('flag_encry1', 'rb') as f:
    cipher_hex = f.read().hex()   # Python 3 直接用 .hex()
c = int(cipher_hex, 16)

# ---------- 3. 计算私钥 d ----------
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)   # 求 e 关于 phi 的模逆元

# ---------- 4. 解密 ----------
m = int(pow(c, d, n))

# ---------- 5. 输出明文 ----------
print(m)
print(libnum.n2s(m))       # 数字转字符串

得到 afctf{You_Know_0p3u55I}