2020 0xGame WriteUp

前言

主办方：南京邮电大学

Misc

flip（波形图 + 摩斯密码 + BinWalk + 倒序）

打开压缩包后得到一个 ZIP 和 MP3

ZIP 需要密码，使用 Audacity 打开 MP3

根据波形长短猜测是摩斯密码

1
....- ----- ----- ---.. ..... -.... -.... ----. ----. ...-- ----- ----- ... .. -.. .-. --- .-- ... ... .- .--.

解密得到

1
400856699300sidrowssap

翻译了一下题目题目名称有翻转的意思，把摩斯密码倒序发现:

1
passwordis003996658004

003996658004 即为压缩包密码

解压后还是压缩包

使用 Kali 的 BinWalk 分离

查看 password.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
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
?gnorw eb ot smees gnihtemos tub ,yranib ni elif etirw ot tnaw I

10100110

11010110

00101100

11000010

11111010

01100110

00001100

11111010

10100110

11000110

11001100

10010110

00001110

11111010

10000010

00000100

11001110

10010110

00000100

00100110

01001110

11110110

11101110

11001110

11001110

10000110

00001110

00000100

10100110

00010110

00101110

00000100

00110100

10101110

11110110

10011110

00000100

01001110

11110110

01100110

00000100

10100110

11010110

10000110

11000110

00000100

01100110

11110110

00000100

10100110

11000110

10100110

10010110

00001110

00000100

10000110

00000100

00101110

11001110

10101110

01010110

00000100

11001110

10010110

00000100

10110110

10100110

00110110

01000110

11110110

01001110

00001110

00000100

11001110

10010110

00010110

00101110

00000100

00101110

10000110

00010110

00101110

00000100

01001110

10100110

01101110

10100110

00110110

11000110

00000100

11110110

11001110

00000100

10100110

01001110

10000110

00000100

10101110

11110110

10011010

明显的倒序排列

将所有内容倒序后得到

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
01011001

01101111

01110101

00100000

01100001

01110010

01100101

00100000

01110011

01101111

00100000

01100011

01101100

01100101

01110110

01100101

01110010

00100000

01110100

01101000

01100001

01110100

00100000

01110100

01101000

01101001

01110011

00100000

01110000

01110010

01101111

01100010

01101100

01100101

01101101

00100000

01101001

01110011

00100000

01101010

01110101

01110011

01110100

00100000

01100001

00100000

01110000

01101001

01100101

01100011

01100101

00100000

01101111

01100110

00100000

01100011

01100001

01101011

01100101

00100000

01100110

01101111

01110010

00100000

01111001

01101111

01110101

00101100

00100000

01110100

01101000

01100101

00100000

01110000

01100001

01110011

01110011

01110111

01101111

01110010

01100100

00100000

01101001

01110011

00100000

01000001

01011111

01110000

01101001

00110011

01100011

01100101

01011111

00110000

01100110

01011111

01000011

00110100

01101011

01100101

I want to write file in binary, but something seems to be wrong?

二进制转十六进制再转 ASCII 码得到

1
You are so clever that this problem is just a piece of cake for you, the password is A_pi3ce_0f_C4ke

使用 A_pi3ce_0f_C4ke 密码提取出压缩包中的 galf_si_siht.png

提示我们打不开文件

使用 010editor 打开该文件

发现文件头不是 PNG 格式

拉到最底下发现还是倒序 黄豆流汗脸.jpg

将整个文件的十六进制倒序后保存为 PNG 图片打开发现二维码，使用二维码扫描工具得到

1
http://am473ur.com/0xgame/flip/bd055250d3906d1f791d8e83b4396893.php

访问拿到 flag（估计不在了）

pacp（SQL 盲注流量 + PNG 宽高）

打开流量包发现是盲注流量

过滤 POST 请求发现有上传一个文件

1
http.request.method == POST

追踪 HTTP 流复制原始数据

用 WinHex 复制成新文件解压缩文件是一张图片，打开没内容，检查 CRC 发现宽高被更改过

使用随波逐流梭哈出原图

differentPic（图像合成）

解压缩文件是两个一模一样的图片

使用 StegSolve 打开选择 Image Combiner 模式（图像合成）

发现可疑内容

保存后再打开切换通道发现是二维码

扫码拿到 flag

extract（BinWalk + Stegpy）

打开压缩包后发现图片

使用 BinWalk 检查发现有隐藏文件

提取出二维码扫描给出提示工具 Stegpy

使用 Stegpy 成功拿到 flag

easyMisc（拨号+ Stegpy）

解压缩出三个文件

打开音频文件听着像是拨号声音，疑似拨号隐写

把频率设置为低频 697、高频 1633

得到下图

对照拨号隐写表格解密出：2821876761

使用 2821876761 解压得到 flag 图片

再次使用 Stegpy 得到 flag

lowerBase64（Base64 解码）

Base64字符串中的字母被随机转换了大小写

正常的Base64解码器要求严格的大小写，所以我们需要找到正确的大小写组合

Base64 编码原理

1
2
3
# Base64 编码过程：
原文: 3 字节 = 24 bits → 分成 4 组，每组 6 bits → 每组映射为 1 个 Base64 字符
# 所以解码时需要以 4 个 Base64 字符为一组进行处理

由于我们不知道哪些字母应该是大写、哪些应该是小写，所以需要暴力枚举所有可能的大小写组合

1
2
3
4
5
6
7
8
9
10
11
12
13
for i in range(0, len(c), 4):  # 以 4 个字符为一组处理
    pos = []
    chunk = c[i:i+4]  # 取出 4 个字符的块
    
    # 为每个字符创建可能的大小写组合
    for char in chunk:
        if char.isalpha():
            pos.append([char.lower(), char.upper()])  # 字母有两种可能
        else:
            pos.append([char])  # 非字母只有一种可能
    
    # 生成所有大小写组合
    cases = ["".join(k) for k in product(*pos)]

举例说明：

如果当前 chunk 是 "AbC1"，那么：

  • 'A' → ['a', 'A']
  • 'b' → ['b', 'B']
  • 'C' → ['c', 'C']
  • '1' → ['1']

通过 product(*pos) 会生成："abc1", "abC1", "aBc1", "aBC1", "Abc1", "AbC1", "ABc1", "ABC1" 共 8 种组合

最后验证结果

1
2
3
4
5
6
7
8
9
10
for case in cases:
    try:
        decoded = b64decode(case)  # 尝试解码
        # 检查解码后的字符是否都在有效字符表中
        if all(chr(byte) in table for byte in decoded):
            real_data += case
            flag += decoded
            break  # 找到有效组合就跳出
    except:
        continue  # 解码失败就尝试下一个组合

threeThousand（ZIP 爆破）

第一次爆出密码是 33

打开发现还有压缩包，且都是加密

写脚本爆破

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
import zipfile
import os
from itertools import product


def try_password(zip_file, password, target_dir):
    try:
        with zipfile.ZipFile(zip_file, 'r') as zip_ref:
            zip_ref.extractall(target_dir, pwd=password.encode('utf-8'))
        print(f"成功解压 {zip_file}，密码: {password}")
        return True
    except Exception as e:
        return False


def main():
    # 获取脚本所在目录
    script_dir = os.path.dirname(os.path.abspath(__file__))

    starting_zip = '2999.zip'
    # 目标解压目录也在同一目录下
    target_directory = os.path.join(script_dir, 'extracted_files')

    # 构建完整的文件路径
    current_zip = os.path.join(script_dir, starting_zip)

    # 确保目标目录存在
    if not os.path.exists(target_directory):
        os.makedirs(target_directory)
        print(f"创建解压目录: {target_directory}")

    # 生成所有可能的两位数密码组合
    passwords = [''.join(p) for p in product('0123456789', repeat=2)]
    print(f"生成的密码列表: {passwords}")
    print(f"脚本目录: {script_dir}")
    print(f"当前处理的文件: {current_zip}")
    print(f"目标解压目录: {target_directory}")

    while True:
        # 检查当前zip文件是否存在
        if not os.path.exists(current_zip):
            print(f'文件 {current_zip} 不存在，停止解压缩。')
            break

        print(f"正在尝试解压: {os.path.basename(current_zip)}")
        password_found = False

        for password in passwords:
            if try_password(current_zip, password, target_directory):
                print(f'成功使用密码 {password} 解压文件 {os.path.basename(current_zip)}！')
                password_found = True
                break

        if not password_found:
            print(f'无法为 {os.path.basename(current_zip)} 找到密码，停止解压缩。')
            break

        # 获取当前文件名（不含路径）
        current_filename = os.path.basename(current_zip)
        # 提取数字并减1
        next_zip_number = int(current_filename.split('.')[0]) - 1
        # 下一个文件应该在目标目录中
        current_zip = os.path.join(target_directory, f'{next_zip_number}.zip')

        print(f"下一个要解压的文件: {os.path.basename(current_zip)}")


if __name__ == "__main__":
    main()

Crypto

Calendar（日期网格坐标密码）

题目给出了一张图片

以及一段字符

1
SAT1,THU1,MON3,MON2,WED3,SUN2,THU1,SUN4,FRI3,THU1,MON4,MON4,FRI4,THU3,SUN4,SUN2,TUE4,THU1,FRI1,MON3,MON2

观察最后的数字只有 1~4，推测这就是行号，而字符就是对应的列

将得到的数字按照字母表的顺序转换最后得到

1
0xGame{calendarpasswordtable}

easyXor（异或加密）

连续两次异或同一个数结果不变

1
2
3
4
5
6
7
8
cipher = [72, 63, 38, 12, 8, 30, 30, 6, 82, 4, 84, 88, 92, 7, 79, 29, 8, 90, 85, 26, 25, 87, 80, 10, 20, 20, 9, 4, 80, 73, 31, 5, 82, 0, 1, 92, 0, 0, 94, 81, 4, 85, 27, 35]
flag = ""
cipher += [ord("^")]
for i in range(len(cipher)-1):
    flag = chr(cipher[len(cipher) - i - 2] ^ cipher[len(cipher) - i - 1]) + flag
    cipher[len(cipher) - i - 2] = ord(flag[0])
print(flag)
# 0xGame{ec15a9eb-08b7-4c39-904d-27eed888f73f}

supperAffine（仿射加密变种）

解题技巧先放前面：

  1. 识别密码体制： 代码中出现了 affine(x, a, b) 和 GCD(MOD, ...)，立即锁定这是仿射密码及其变种
  2. 识别模数： 立即进行模数分解，MOD = 62 = 2 * 31
  3. **代数化简：**看到 f3(f2(f1(x))) 这种结构，立即意识到这是可以合并的

给出源代码

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
from Crypto.Util.number import *
from string import ascii_letters, digits
from random import randint
from secret import flag

assert flag.startswith("0xGame{") and flag.endswith("}")
table = ascii_letters+digits
MOD = len(table)

def affine(x, a, b): return a*x+b

def genKey():
    a = [randint(1, 64) for _ in range(3)]
    b = [randint(1, 64) for _ in range(3)]
    while GCD(MOD, a[0]*a[1]*a[2]) != 1:
        a = [randint(1, 64) for _ in range(3)]
    return a, b


cipher = ""
A, B = genKey()
for i in flag:
    if i not in table:
        cipher += i
    else:
        cipher += table[affine(affine(affine(table.find(i),A[0], B[0]), A[1], B[1]), A[2], B[2]) % MOD]

print("cipher =", cipher)
# cipher = t6b7Tn{2GByBZBB-aan2-JRWn-GnZB-Jyf7a722ffnZ}

equationSet（提公因数 p）

解题技巧先放前面：

  1. 符号化：所有给出的数值用数学符号表示出来，并建立它们之间的关系
  2. 寻找公因数：如果给出的两个大数 A 和 B 都是由相同的素数因子构成的，那么 GCD(A, B) 往往是解密的关键
  3. **确定解题路径：**一旦 p 被分解出来，接下来就要想方设法得到 q 和 r 的信息

题目给出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from secret import flag

e = 65537
m = bytes_to_long(flag.encode())
p, q, r = getPrime(512), getPrime(512), getPrime(512)

n = p*q*r
c = pow(m, e, n)
print(c)
print(n)
print(p+q+r)
print(p*q+p*r)

转换成数学公式
$$
\begin{aligned}
&n\ =\ p\ *\ q\ *\ r\
&t\ =\ p\ *\ q\ +\ p\ *\ r\ =\ p(q\ +\ r)\
&ϕ(n)\ =\ (p\ -\ 1)(q\ -\ 1)(r\ -\ 1)
\end{aligned}
$$
我们可以清楚地看到，p 是 n 和 t 的公共因子

那 GCD(n, t) 会正好是 p 吗？会不会包含其他因子？
$$
\begin{aligned}
&GCD(pqr,p(q\ +\ r))\ =\ p\ *\ GCD(qr,q\ +\ r)
\end{aligned}
$$
由于 q 和 r 都是生成的 512 位随机大素数，它们互质，且它们的和 q+r 极大概率与它们的积 qr 互质

因此 GCD(qr, q+r) = 1

结论： 直接计算 GCD(n, t) 就能无痛提取出素数 p

对于 n=pqr，欧拉函数定义为：
$$
\begin{aligned}
&\phi(n)\ =\ (p-1)(q-1)(r-1)\\
&\phi(n)\ =\ (p-1)\ *\ [(q-1)(r-1)]\\
&n\ -\ t\ =\ pqr\ -\ pq\ - \ pr\
&n\ -\ t\ =\ p(qr\ -\ q\ - \ r)\
&(n\ -\ t)\ //\ p\ =\ (qr\ -\ q\ - \ r)\
&(n\ -\ t)\ //\ p\ +\ 1\ =\ (qr\ -\ q\ - \ r)\ +\ 1\\
&qr\ -\ q\ - \ r\ +\ 1\ =\ q(r\ -\ 1)\ -\ 1(r\ -\ 1)\
&q(r\ -\ 1)\ -\ 1(r\ -\ 1)\ =\ (q\ -\ 1)(r\ -\ 1)\\
&(n\ -\ t)\ //\ p\ +\ 1\ =\ (q\ -\ 1)(r\ -\ 1)\
&\phi(n)\ =\ (p-1)\ *\ [(q-1)(r-1)]\
&\phi(n)\ =\ (p-1)\ *\ [(n\ -\ t)\ //\ p\ +\ 1]\
\end{aligned}
$$
观察公因数 是 Crypto 选手的直觉。看到 n 和 t 有明显的公共结构（都含有 p），第一时间想到的就是 GCD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from Crypto.Util.number import *

# ==========================================
# 题目信息与数学关系回顾
# ------------------------------------------
# 已知：
# n = p * q * r  (三素数 RSA)
# s = p + q + r  (此变量在本脚本中未被使用)
# t = p * q + p * r = p * (q + r)
# ==========================================

# 题目给出的长整数数据（省略部分以保持整洁）
c = 216719040256186298397028655750064798850... 
n = 894056034566447301955142597300391580123...
t = 157435908314881832180551915807491465031...

# [第一步]：提取公共素因子 p
# 数学原理：n = p*q*r，t = p*(q+r)
# 显然 p 是 n 和 t 的最大公约数
p = GCD(n, t)

# [第二步]：巧妙构造欧拉函数 phi(n)
# 目标：phi = (p-1) * (q-1) * (r-1)
# 
# 1. 括号右边推导：((n - t) // p + 1)
#    分子：n - t = pqr - (pq + pr) = pqr - pq - pr = p(qr - q - r)
#    除法：(n - t) // p = qr - q - r
#    加一：qr - q - r + 1
#    因式分解：q(r-1) - 1(r-1) = (q-1)(r-1)
#
# 2. 最终合并：
#    (p-1) * [(q-1)(r-1)] = phi(n)
phi = (p - 1) * ((n - t) // p + 1)

# [第三步]：常规 RSA 私钥计算
# 计算 e 在模 phi 下的乘法逆元 d
d = inverse(65537, phi)

# [第四步]：解密
# m = c^d mod n
m = pow(c, d, n)

# 将解密出的长整数转换为字节串（即明文 Flag）
print(long_to_bytes(m))

Fibonacci（爆破斐波那契数列周期）

解题技巧先放前面：

  1. 识别计算陷阱与核心矛盾：看到一个天文数字立即判定这是计算陷阱
  2. **建立 Pisano 周期的知识框架：**了解周期的基本性质
  3. **掌握求和公式的转化：**一旦找到周期和周期和，必须将求和公式转换为可计算的代数形式
  4. **大数运算：**CTF 中处理超大数论运算，首选 gmpy2 库

题目代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from gmpy2 import next_prime
from functools import reduce
from secret import flag


def F(x):
    if x == 1 or x == 2:
        return 1
    return F(x-1)+F(x-2)


n = reduce(lambda a, b: a*b, [getPrime(4) for _ in range(4)])
r = getRandomNBitInteger(67)
S = sum([F(i) % n for i in range(r)])
p = next_prime(S**16)
q = getPrime(p.bit_length())
m = bytes_to_long(flag)
c = pow(m, 65537, p*q)

print("r =", r)
print("n =", n)
print("c =", c)
print("N =", p*q)

现在分析代码

定义了一个斐波那契数列

1
2
3
4
5
def F(x):
    if x == 1 or x == 2:
        return 1
    # 递归定义，计算量巨大，但由于模运算，实际计算只需在一个周期内完成
    return F(x-1) + F(x-2)

斐波那契数列是一个递推数列，它的核心规则是：从第三项起，数列中的每一项都等于前两项之和
$$
\begin{aligned}
&F_n\ =\ F_{n-1}\ +\ F_{n-2}\ (n \geq 3)
\end{aligned}
$$
在 CTF 和数论领域，斐波那契数列的模运算性质至关重要：

Pisano 周期

  • 定义： 斐波那契数列对任何正整数 n 取模后，都会变成一个循环数列。这个循环的长度就被称为 Pisano 周期，记作
    $$
    \begin{aligned}
    &\pi(n)
    \end{aligned}
    $$

小模数 n 的生成

1
2
3
4
5
# 2. 小模数 n 的生成
# 生成 4 个 4-bit 的小素数（p_i <= 15）
# n 是这四个小素数的乘积
# n 的大小约为 16 bits (n <= 15^4 = 50625)
n = reduce(lambda a, b: a*b, [getPrime(4) for _ in range(4)])

巨大的求和上限 r

1
2
3
4
# 3. 巨大的求和上限 r
# r 是一个 67-bit 的大整数 (r 约等于 2^67)
# 注意：r 是计算 S 的唯一输入，且 r 已经泄露给我们
r = getRandomNBitInteger(67)

S 的计算

1
2
3
# 4. 关键泄露信息 S 的计算 (S是 p 的基础)
# S 是前 r 个斐波那契数在模 n 下的和：S = Sum_{i=0}^{r-1} (F(i) mod n)
S = sum([F(i) % n for i in range(r)])

生成巨大的素数 p

1
2
3
4
5
# 5. 生成巨大的素数 p
# p 是 S^16 之后的第一个素数
# S 的大小约为 r * n (约 2^67 * 2^16 = 2^83)
# p 的大小约为 (2^83)^16 = 2^1328 bits
p = next_prime(S**16)

生成素数 q

1
2
3
# 6. 生成素数 q
# q 是一个与 p 相同长度的素数 (q 约 1328 bits)
q = getPrime(p.bit_length())

首先要求出 p -> S -> r 这个顺序

先看 S 的计算方式
$$
\begin{aligned}
&S\ =\ \sum_{i-0}^{r-1}{F((i)\ \ (mod\ n))}
\end{aligned}
$$
求和次数 r 太大，但是，求和时使用的模数 n 却非常小（不到 65536）

这是整个解题的关键步骤。我们不能循环 r 次，但 n 很小，所以我们要找规律

Pisano 周期（重复的舞蹈）

当斐波那契数列对一个小数字 n 取模时，它的结果会不断重复，形成一个循环。这个循环的长度就是 Pisano 周期 T

  • 斐波那契数列 mod n 就像一个舞者在一个很小的圆形舞台（模数 n）上跳舞。它跳了一段时间后，姿势和位置一定会回到起点 (1, 1)
  • 周期 T 就是这支舞完整跳完一次所需要的步数

通过脚本实现

1
2
3
4
5
6
a, b = 1, 1
while True:
    a, b = b, (a + b) % n # 找到下一步的舞步
    if a == 1 and b == 1: # 检查是否回到起点
        T = period = len(fibs) # 记录步数 T
        break

因为 n 很小，这个循环很快就能结束，我们得到了周期 T 和跳一圈舞的总得分 Sum_{cycle}

现在我们有了舞蹈的规律，就可以计算 r 步的总得分 S：

  • 完整周期数 k： k = r // T （看看 r 步能跳多少次完整的舞）
  • 剩余步数 rem： rem = r % T （最后多出来没跳完的几步）

$$
\begin{aligned}
&S\ =\ (完整次数\ k\ *\ 一圈的总得分\ Sum_{cycle})\ +\ (剩余几步的得分\ Sum_{cycle})
\end{aligned}
$$

这一步就将天文数字 r 转换成了一个可计算的公式，得到了我们想要的秘密蓝图 S

脚本代码 作用 简单理解
p = next_prime(S ** 16) 计算第一个秘密零件 p。 严格按照题目的公式，找到 S^{16} 之后的第一个素数
q = N // p 计算第二个秘密零件 q。 N 是 p 和 q 的乘积，所以 q = N / p
phi = (p - 1) * (q - 1) 计算制造蓝图 \phi(N)
d = inverse(65537, phi) 计算万能钥匙 d。 inverse 是求一个数在 \pmod{phi} 世界里的“倒数”
m = pow(c, d, N) 解密！ 使用万能钥匙 d 打开保险箱 N 中的密文 c
long_to_bytes(m) 将解密得到的数字 m 转换回 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
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
from Crypto.Util.number import *
import gmpy2

# ==========================================
# 1. 在此填入题目给出的参数 (从你的题目输出中复制)
# ==========================================
r = 6799657976717333  # 题目给出的 r (67-bit integer)
n = 34969  # 题目给出的 n (小整数，约 16-bit)
c = 182306974283951620352146026941583994848813143690343545292100780435573376889099600153592983212384957591086328477660614034391593564733860826251499298995355977799109267846836211477797049861348446512705981010295182077777939692478140339301301250656211795668782349225298841295102744088295274299888068087536135862146848855194234931032258224223054120694400807261402442809227521150204434199401928373883267697928229945582110688115412960868921538084717338343966490113059627708880297277412143561561837953806960309840302665509500602335832680764801782789278492075478763944213005349707521471401389317139473794212210077629296628421658105048387207038261321205  # 题目给出的密文 c
N = 1885611999537620305525377668936000019248252379006235038175895811710218489750248037027959751027236326639084060685909621893589756343903429224938045802850975926055076789137326688384533999739909152386986919824268841500802585809839133132715892685629871188263336038221503698167753853207939360629026179572549702198037779413041272313618794196167670066872427987596564652249864272782397242041014605617282098654595635031878004275878165728021995744626212185694275937448739806439006047047376363093018124169182873374456718929377731991273039952515054850718253257895996999907977029169396644305213162133388169761391593110121229266422245167572929912914529689341  # 题目给出的公钥 N


# ==========================================
# 2. 核心函数：寻找 Pisano 周期并计算周期和
#    对应思路 2 的优化版：直接在 Python 中实现
# ==========================================
def get_pisano_info(n):
    # 斐波那契数列缓存，用于计算余数部分的和
    fibs = [1, 1]

    # 寻找周期：暴力迭代直到再次出现 "1, 1"
    # 因为 n 很小，这个循环会很快结束
    a, b = 1, 1
    period = 0

    while True:
        # 下一项 F(i) = F(i-1) + F(i-2)
        a, b = b, (a + b) % n
        fibs.append(b)

        # 检查是否回到了起点 (1, 1)
        # 注意：现在的 b 是新的一项，a 是上一项
        if a == 1 and b == 1:
            # 找到了循环节！
            # 此时 fibs 最后两个是 1, 1，属于下一个周期的开始，要去掉
            fibs.pop()
            fibs.pop()
            period = len(fibs)
            break

    period_sum = sum(fibs)
    return period, period_sum, fibs


print(f"[*] Analyzing Pisano period for n = {n}...")
period, period_sum, fibs = get_pisano_info(n)
print(f"[+] Period found: T = {period}")
print(f"[+] Sum of one period: {period_sum}")

# ==========================================
# 3. 计算 S
#    利用公式：S = (完整周期的次数 * 周期和) + (剩余部分的和)
# ==========================================
k = r // period  # 完整的周期数
rem = r % period  # 剩余的项数

# 剩余部分的和 = 前 rem 项之和
rem_sum = sum(fibs[:rem])

# 计算最终的 S (注意题目中 S 是模 n 后求和，不需要再对 S 取模)
S = k * period_sum + rem_sum
print(f"[+] Calculated S = {S}")

# ==========================================
# 4. 恢复 RSA 密钥 p, q
#    题目逻辑：p = next_prime(S**16)
# ==========================================
# 注意 S**16 很大，需要用 gmpy2 处理大数运算
base_p = gmpy2.mpz(S) ** 16
p = int(gmpy2.next_prime(base_p))

# 验证 p 是否正确
if N % p == 0:
    print("[+] Successfully recovered p!")
    q = N // p
else:
    print("[-] Failed to recover p. Check parameters.")
    exit()

# ==========================================
# 5. 标准 RSA 解密
# ==========================================
e = 65537
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

m = pow(c, d, N)
flag = long_to_bytes(m)

print("\n--------------------------------------------------")
print("Flag:", flag.decode())
print("--------------------------------------------------")

easyRSA（线性组合泄露 d 与 φ(n)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag.encode())
e = 65537
p, q = getPrime(1024), getPrime(1024)
d = inverse(e, (p-1)*(q-1))
x = 11*d+7*(p-1)*(q-1)
c = pow(m, e, p*q)

print("n =", p*q)
print("c =", c)
print("x =", x)

# n = 15321211041844905603734344178124947500324300419514650914959277216026081094496518094622195813971694335738777589926626969243883848477814650916143749322154944235584863085124154540941941026813506509060939499627059712020664731558566028207969260861863294704292014958955493668692256998253634012942569080200336487172402729072437050952572508561453302097971258470685521456512378089846772560530301852104802168974905937732653119166440832834381675710869396094149006807933529429939569477709674581421481769103309376717894952118650888932952440197471338958967318775671821835706884032860123711415773758546392549257375305940969423099611
# c = 14896093236493033914781929755936872928003725648997746598164823180134348743474984136539422027221313199599273430548738399424773586673404519182726589878322104929749149555906399158136445184378100079558203687049497943904275695897824656260657349522646553949766831267321006314984113971129230701131171378457086851261467999754137290017989201512492586108768533159551545321805463224339252886492732021354821330371600069958523522302729848548167244423902572054475396534469987383265867036041513161170273368613864180696427386890714264902686976581317435011139081192227958859641684254938165261747405568369502852705979424383731908971282
# x = 265060901898485540806769085700708185460124724747068797929982044073895401490880169847709049380530156090772787935089173201664711759633269693627724735457902114209008145932150728406880988293457762401679305297063608204632708505031098047582175011825482347052645324085149631658741807382378778694666759557421043250548432429798543553950625554307402164142007388940921309688918410535907564996075660231557340541491155676279511654970843992008027830570227549010293790074386638365293013298327534604995316180405779571245069623638693068707267840181413082202552862853411080755107836252852929279422343700808788459217261282790226013328915

RSA 里，我们有：

  • p, q 两个大素数

  • n = p * q

  • φ(n) = (p-1)*(q-1)

  • 公钥指数 e = 65537（题目固定）

  • 私钥指数 d 满足 e * d ≡ 1 (mod φ(n))

这等价于存在一个整数 k，使得：

1
e * d = k * φ(n) + 1

即

1
d = (k * φ(n) + 1) / e

题目除了给 n 和密文 c，还给了

1
x = 11 * d + 7 * φ(n)

也就是说，x 是 d 和 φ(n) 的一个线性组合，系数分别是 11 和 7

将上面 d 的表达式代入 x

1
x = 11 * [ (kφ + 1)/e ] + 7φ

两边同时乘以 e，去掉分母

1
e * x = 11 * (kφ + 1) + 7eφ

展开

1
e * x = 11kφ + 11 + 7eφ

把常数项移到左边，含 φ 的项合并

1
e * x - 11 = (11k + 7e) φ

记 T = e x - 11，则

1
T = (11k + 7e) * φ

这是一个关键等式，T 是 φ 的整数倍，倍数 A = 11k + 7e 依赖于未知的 k

从 e * d = k φ + 1 得

1
k = (e * d - 1) / φ

因为 d < φ（实际上 d 是模 φ 下的逆元，通常比 φ 略小），所以

1
e * d - 1 < e * φ - 1  →  k < e

所以思路：

  • 计算 T = e * x - 11（已知 x 和 e）

  • 对每个可能的 k 从 0 到 e-1，计算 A = 11k + 7e

  • 如果 A 能整除 T，那么 φ = T // A 就是一个候选的欧拉函数值

  • 用这个 φ 去分解 n，因为 p + q = n - φ + 1，p * q = n，所以 p 和 q 是二次方程 X^2 - (p + q)X + n = 0 的两个根

  • 判断 p 和 q 是否为整数且满足 p * q == n，若是，则分解成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import *
from math import isqrt

n = ...   # 从题目获取
c = ...   # 密文
x = ...   # 泄露的数值

e = 65537

T = e * x - 11

for k in range(1, e):               # 枚举 k = 1 .. e-1
    A = 11 * k + 7 * e
    if T % A != 0:
        continue
    phi = T // A

    # 用 phi 恢复 p+q
    s = n - phi + 1
    delta = s * s - 4 * n
    r = isqrt(delta)
    if r * r != delta:
        continue

    p = (s + r) // 2
    q = (s - r) // 2
    if p * q != n:
        continue

    # 成功分解，计算 d 并解密
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    print(flag)
    break

Web

？？？？（Shell 通配符绕过）

打开页面提示输入 yulige 获得 flag

但是前端限制了只能输入 4 字符，右键改源代码删掉

提交按钮被禁用了，删掉 disable 属性

提交后给出提示

访问过去给出了黑名单源码

1
if(preg_match("/[A-Za-ko-z0-9]+/", $cmd))

它唯独漏掉了三个小写字母：l、m、n

1
$blacklist = "~!@#%^$&\/*()（）<>《》-_{}[]'/\":,";

同样漏掉了空格、?、.

所以我们可以利用 nl 这个命令读取文件，其文件名采用正则的形式代替

1
2
#   nl fl4g_is_here.php
cmd=nl ?l??????????.???

Pwn

欢迎来到 0xGame 平台（签到）

直接 nc 即可

帮我取一个题目名称（ret2text）