文章总结： 本文详细解析CISCN2025EzFlagCrypto题目，通过逆向分析ELF二进制文件，识别出基于斐波那契数列模16和自定义字符表的Flag生成算法。针对直接计算大数Fibonacci的效率瓶颈，作者应用Pisano周期理论将时间复杂度降至常数级，并编写Python脚本成功复现了求解过程，最终还原了Flag。 综合评分： 93 文章分类： CTF,逆向分析,二进制安全
CISCN 2025 – EzFlag Crypto 深度解析
原创
破镜安全
破镜安全
2025年12月31日 08:00 四川
CISCN 2025 – EzFlag Crypto 深度解析
前言
本文将详细分析CISCN 2025中的一道密码学题目EzFlag，通过完整的逆向分析过程，逐步揭示题目背后的算法原理，并最终求解出flag。文章面向CTF初学者，会详细讲解每一个技术细节和思维过程。
一、题目初探
1.1 文件基本信息
首先拿到题目文件后，第一步是了解文件的基本信息。我们使用Linux的file命令：
file EzFlag
输出结果：
EzFlag: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=85828d956eb2c59aad2251102f9f90196b8eb80c, for GNU/Linux 3.2.0, not stripped
从这个输出中我们可以获得几个重要信息：
- ELF 64-bit: 这是一个Linux平台的64位可执行文件
- dynamically linked: 动态链接，说明程序依赖系统库
- not stripped: 符号表未被剥离，这对逆向分析非常有利
符号表未被剥离意味着程序中保留了函数名、变量名等信息，这将大大降低逆向难度。
1.2 字符串提取
在逆向工程中，字符串提取是最快速有效的信息收集方法之一。使用strings命令可以提取二进制文件中所有可读的ASCII字符串：
strings EzFlag
在输出中，我们可以找到一些非常关键的信息：
Enter password:
V3ryStr0ngp@ssw0rd
Wrong password!
flag{
012ab9c3478d56ef
让我们分析这些字符串的含义：
- Enter password:: 提示用户输入密码
- V3ryStr0ngp@ssw0rd: 这很可能就是程序验证的密码
- Wrong password!: 密码错误时的提示
- flag{: flag的标准开头
- 012ab9c3478d56ef: 一个16字符的字符串，每个字符都是十六进制字符
这个16字符的字符串非常特别，它包含了0-9和a-f中的部分字符，很可能是某种查找表或映射表。
二、程序流程分析
2.1 运行程序观察
在开始深入逆向之前，先运行程序看看它的行为：
chmod +x EzFlag
./EzFlag
程序会提示输入密码。如果随便输入一些内容，会显示”Wrong password!”。现在使用我们从字符串中找到的密码：
echo "V3ryStr0ngp@ssw0rd" | ./EzFlag
程序开始输出：
Enter password: flag{10632674-1d...
程序会一个字符一个字符地慢慢输出flag，每个字符之间有明显的延时。这说明程序在逐字符生成并输出flag。
2.2 反汇编分析
现在使用objdump工具对程序进行反汇编：
objdump -d EzFlag > disasm.txt
查看main函数的关键部分：
129b <main>:
# ... 初始化代码 ...
12b0: lea 0xd50(%rip),%rax # 加载"Enter password: "
12c4: call 10b0 <_ZStlsISt...> # 输出提示
12da: call 1040 <_ZSt7getline...> # 读取用户输入
12f0: call 15d3 <_ZStneI...> # 比较密码
12f7: je 132e <main+0x93> # 密码正确则跳转
12f9: lea 0xd2b(%rip),%rax # 加载"Wrong password!"
# ... 输出错误信息并退出 ...
132e: lea 0xd06(%rip),%rax # 加载"flag{"
1356: movq $0x1,-0x18(%rbp) # seed = 1
135e: movl $0x0,-0x1c(%rbp) # i = 0
136a: mov -0x18(%rbp),%rax # 加载seed
1371: call 1229 <_Z1fy> # 调用函数f(seed)
13dd: shlq $0x3,-0x18(%rbp) # seed << 3
13e2: mov -0x1c(%rbp),%eax # 加载i
13e5: add $0x40,%eax # i + 0x40
13ea: add %rax,-0x18(%rbp) # seed += (i + 0x40)
从汇编代码中，我们可以梳理出程序的主要流程：
- 密码验证阶段：
- 提示用户输入密码
- 读取用户输入
- 与硬编码的密码字符串比较
- 密码错误则输出提示并退出
- Flag生成阶段：
- 输出”flag{“前缀
- 初始化seed = 1，循环变量i = 0
- 进入循环（共32次）
- 每次循环调用函数f(seed)生成一个字符
- 更新seed：seed = (seed << 3) + (0x40 + i)
- 在特定位置插入连字符
2.3 核心函数f的分析
函数f是整个算法的核心，让我们仔细分析它的汇编代码：
1229 <_Z1fy>:
1235: movq $0x0,-0x8(%rbp) # a = 0
123d: movq $0x1,-0x10(%rbp) # b = 1
1245: movq $0x0,-0x18(%rbp) # i = 0
124f: mov -0x10(%rbp),%rax # tmp = b
1253: mov %rax,-0x20(%rbp) # 保存tmp
1257: mov -0x8(%rbp),%rdx # 加载a
125b: mov -0x10(%rbp),%rax # 加载b
125f: add %rdx,%rax # a + b
1262: and $0xf,%eax # (a + b) & 0xF
1265: mov %rax,-0x10(%rbp) # b = (a + b) & 0xF
1269: mov -0x20(%rbp),%rax # 加载tmp
126d: mov %rax,-0x8(%rbp) # a = tmp
1271: addq $0x1,-0x18(%rbp) # i++
1276: mov -0x18(%rbp),%rax # 加载i
127a: cmp -0x28(%rbp),%rax # 比较i和n
127e: jb 124f <_Z1fy+0x26> # i < n则继续循环
1280: mov -0x8(%rbp),%rax # 加载a
1287: lea 0x3072(%rip),%rax # 加载K（字符表）
1291: call 10d0 <_ZNKSt...> # K[a]
将汇编代码还原为C++伪代码：
char f(uint64_t n) {
uint64_t a = 0;
uint64_t b = 1;
for (uint64_t i = 0; i < n; i++) {
uint64_t tmp = b;
b = (a + b) & 0xF; // 模16运算
a = tmp;
}
return K[a]; // K = "012ab9c3478d56ef"
}
这段代码是什么意思呢？让我们仔细分析：
变量初始化：
- a = 0
- b = 1
循环体：
- 保存b的值到临时变量
- 计算a + b，然后对16取模（
& 0xF等价于% 16） - 将结果赋值给b
- 将之前保存的b值赋给a
这个模式是什么呢？让我们手动计算前几项：
- 第0次循环前：a=0, b=1
- 第1次循环后：a=1, b=1
- 第2次循环后：a=1, b=2
- 第3次循环后：a=2, b=3
- 第4次循环后：a=3, b=5
- 第5次循环后：a=5, b=8
是的，这就是著名的Fibonacci数列！
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
只不过这里对每一项都进行了模16运算。最后，函数将Fibonacci数列第n项模16的结果作为索引，从字符表"012ab9c3478d56ef"中查找对应的字符。
三、深入理解算法
3.1 Fibonacci数列模运算
Fibonacci数列的定义：
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) for n ≥ 2
在本题中，程序计算的是F(n) mod 16，即第n个Fibonacci数对16取模的结果。
让我们计算前几个Fibonacci数模16的值：
n F(n) F(n) mod 16
0 0 0
1 1 1
2 1 1
3 2 2
4 3 3
5 5 5
6 8 8
7 13 13
8 21 5
9 34 2
10 55 7
11 89 9
12 144 0
3.2 字符映射表
字符映射表是："012ab9c3478d56ef"
这个表的作用是将0-15的数字映射到特定字符：
索引 0 -> 字符 '0'
索引 1 -> 字符 '1'
索引 2 -> 字符 '2'
索引 3 -> 字符 'a'
索引 4 -> 字符 'b'
索引 5 -> 字符 '9'
索引 6 -> 字符 'c'
索引 7 -> 字符 '3'
索引 8 -> 字符 '4'
索引 9 -> 字符 '7'
索引 10 -> 字符 '8'
索引 11 -> 字符 'd'
索引 12 -> 字符 '5'
索引 13 -> 字符 '6'
索引 14 -> 字符 'e'
索引 15 -> 字符 'f'
3.3 Seed更新机制
从汇编代码中我们看到，每次循环后seed的更新方式为：
seed = (seed << 3) + (0x40 + i)
其中：
seed << 3是左移3位，相当于乘以80x40是十六进制，等于十进制的64i是循环变量，从0到31
让我们计算前几次的seed值：
第0次：seed = 1
第1次：seed = (1 << 3) + 64 = 8 + 64 = 72
第2次：seed = (72 << 3) + 65 = 576 + 65 = 641
第3次：seed = (641 << 3) + 66 = 5128 + 66 = 5194
第4次：seed = (5194 << 3) + 67 = 41552 + 67 = 41619
可以看到seed值增长非常快。到第30次循环时，seed已经是一个天文数字。
四、性能优化的关键：Pisano周期
4.1 问题的挑战
如果我们直接按照函数f的逻辑来实现，当seed非常大时（比如第30次循环），需要循环数万亿次甚至更多。这在实际计算中是不可行的，程序会运行极其缓慢。
但题目程序能够正常运行，说明一定有优化方法。这个优化的关键就是Pisano周期。
4.2 什么是Pisano周期
Pisano周期是数论中的一个重要概念，由意大利数学家Leonardo Pisano（即Fibonacci）的名字命名。
定义：对于任意正整数m，Fibonacci数列模m是一个周期序列，其最小正周期π(m)称为Pisano周期。
核心性质：
F(n) mod m = F(n mod π(m)) mod m
这意味着，Fibonacci数列模m的值会周期性重复。对于模16的情况，周期是多少呢？
4.3 验证Pisano周期
让我们编写代码验证Fibonacci数列模16的周期：
def calculate_fibonacci_mod16():
a, b = 0, 1
sequence = [a]
for i in range(50):
a, b = b, (a + b) % 16
sequence.append(a)
return sequence
seq = calculate_fibonacci_mod16()
print("前25个值：", seq[:25])
输出：
前25个值：[0, 1, 1, 2, 3, 5, 8, 13, 5, 2, 7, 9, 0, 9, 9, 2, 11, 13, 8, 5, 13, 2, 15, 1, 0]
观察输出：
- 第0个值：0
- 第24个值：0
- 第1个值：1
- 第25个值：1
序列从第24个位置开始重复！这说明Fibonacci数列模16的Pisano周期π(16) = 24。
数学验证：
F(0) mod 16 = 0 = F(24) mod 16
F(1) mod 16 = 1 = F(25) mod 16
F(2) mod 16 = 1 = F(26) mod 16
...
4.4 利用周期优化算法
有了周期性这个性质，我们可以将任意大的n简化：
def fib(n):
n = n % 24 # 利用周期性优化
a, b = 0, 1
for _ in range(n):
a, b = b, (a + b) % 16
return a
这样，无论n多大，我们最多只需要循环24次！时间复杂度从O(n)降低到O(1)（因为24是常数）。
例如：
- 计算F(1000000) mod 16时，只需要计算F(1000000 mod 24) = F(16) mod 16
- 而不需要循环1000000次
五、完整求解过程
5.1 算法实现
现在我们可以编写完整的求解脚本：
#!/usr/bin/env python3
# 字符映射表
tbl = "012ab9c3478d56ef"
def fib(n):
"""
计算第n个Fibonacci数模16
利用Pisano周期优化
"""
n %= 24 # Pisano周期为24
a, b = 0, 1
for _ in range(n):
a, b = b, (a + b) % 16
return a
def solve():
"""
模拟程序的flag生成逻辑
"""
seed = 1
result = []
# 生成32个字符
for i in range(32):
# 计算Fibonacci数并查表
fib_index = fib(seed)
char = tbl[fib_index]
result.append(char)
# 更新seed
seed = ((seed << 3) + (0x40 + i)) & 0xFFFFFFFFFFFFFFFF
# 拼接字符串
s = "".join(result)
# 插入连字符：在位置8, 13, 18, 23后插入
# 格式：8-5-5-5-9
flag = f"flag{{{s[:8]}-{s[8:13]}-{s[13:18]}-{s[18:23]}-{s[23:]}}}"
return flag
if __name__ == "__main__":
flag = solve()
print(f"Flag: {flag}")
5.2 详细执行过程
让我们详细追踪前几次迭代的过程：
第0次迭代：
- seed = 1
- fib(1) mod 16 = 1
- tbl[1] = ‘1’
- 新seed = (1 << 3) + 64 = 72
第1次迭代：
- seed = 72
- 72 mod 24 = 0
- fib(0) mod 16 = 0
- tbl[0] = ‘0’
- 新seed = (72 << 3) + 65 = 641
第2次迭代：
- seed = 641
- 641 mod 24 = 17
- fib(17) mod 16 = 13
- tbl[13] = ‘6’
- 新seed = (641 << 3) + 66 = 5194
第3次迭代：
- seed = 5194
- 5194 mod 24 = 10
- fib(10) mod 16 = 7
- tbl[7] = ‘3’
- 新seed = (5194 << 3) + 67 = 41619
继续这个过程32次，我们得到32个字符：
106326741d21909f2914769f60219a24
5.3 格式化输出
根据程序的汇编代码，在特定位置会插入连字符’-‘：
139d: cmpl $0x7,-0x1c(%rbp) # i == 7?
13a1: je 13b5 # 是则输出'-'
13a3: cmpl $0xc,-0x1c(%rbp) # i == 12?
13a7: je 13b5 # 是则输出'-'
13a9: cmpl $0x11,-0x1c(%rbp) # i == 17?
13ad: je 13b5 # 是则输出'-'
13af: cmpl $0x16,-0x1c(%rbp) # i == 22?
13b3: jne 13dd # 不是则继续
这说明在第7、12、17、22个字符后（即第8、13、18、23个位置后）插入连字符。
格式化后：
flag{10632674-1d219-09f29-14769-f60219a24}
5.4 运行验证
执行脚本：
python3 solve.py
输出：
Flag: flag{10632674-1d219-09f29-14769-f60219a24}
我们也可以运行原程序验证（注意程序有延时）：
echo "V3ryStr0ngp@ssw0rd" | ./EzFlag
程序会慢慢输出：
Enter password: flag{10632674-1d2...
前14个字符flag{10632674-1d2与我们的计算结果完全一致，验证了算法的正确性。
六、技术要点总结
6.1 逆向分析技巧
本题中使用的逆向分析技巧包括：
1. 静态分析工具
file: 识别文件类型和架构strings: 快速提取可读字符串objdump: 反汇编查看程序逻辑
2. 汇编代码阅读
- 识别函数调用（call指令）
- 理解循环结构（cmp、jb等跳转指令）
- 分析变量操作（mov、add、shl等指令）
3. 算法识别通过观察变量更新模式识别出Fibonacci数列：
tmp = b
b = a + b
a = tmp
6.2 数学优化原理
Pisano周期的应用
Pisano周期是解决本题的关键。它的重要性在于：
- 周期性：Fibonacci数列模m具有固定周期
- 可预测性：知道周期后可以快速计算任意项
- 实用性：将指数级复杂度降低到常数级
对于模16的情况：
- 周期π(16) = 24
- F(n) mod 16 = F(n mod 24) mod 16
- 最多只需计算24次循环
位运算技巧
& 0xF等价于% 16：更高效的模运算<< 3等价于* 8：更高效的乘法& 0xFFFFFFFFFFFFFFFF：确保64位范围内
6.3 字符映射表
映射表"012ab9c3478d56ef"的设计：
- 长度为16，对应0-15的索引
- 包含数字和字母，看起来像UUID格式
- 实现了自定义的”编码”方案
6.4 程序设计模式
本题程序的设计体现了几个有趣的模式：
- 延时输出：使用sleep逐字符输出，增加程序运行时间
- 种子机制：使用seed生成伪随机但确定的字符序列
- 数学难题：表面上需要巨大计算量，实际有巧妙解法
七、学习建议
对于想要学习密码学CTF题目的同学，本题提供了以下学习要点：
7.1 基础知识
必备工具
- Linux命令行基础（file, strings, objdump）
- Python编程（用于快速实现算法）
- 基础数论知识（模运算、周期性）
汇编语言
- x86-64基本指令集
- 函数调用约定
- 寄存器使用规则
7.2 解题思路
信息收集
- 使用自动化工具快速提取信息
- 运行程序观察行为
- 不放过任何可疑的字符串
静态分析
- 找到main函数，理解主流程
- 分析关键函数的实现
- 还原高级语言伪代码
算法识别
- 观察变量更新模式
- 识别常见算法（Fibonacci、哈希等）
- 寻找数学规律
优化求解
- 识别算法瓶颈
- 应用数学理论优化
- 验证结果正确性
7.3 进阶方向
学完本题后，可以继续学习：
- 更多数论知识
- 欧拉函数
- 中国剩余定理
- 原根与离散对数
- 密码学算法
- RSA加密
- 椭圆曲线密码
- 哈希函数
- 逆向工程
- IDA Pro、Ghidra等工具
- 动态调试技术
- 反混淆技术
八、总结
本题是一道设计精巧的密码学题目，主要考察以下能力：
- 逆向分析能力：通过反汇编理解程序逻辑
- 算法识别能力：识别Fibonacci数列
- 数学优化能力：应用Pisano周期理论
- 编程实现能力：将分析结果转化为代码
解题的核心在于发现并利用Pisano周期性质，将看似需要巨大计算量的问题转化为简单的模运算。这体现了CTF题目的精髓：不是暴力破解，而是找到巧妙的解决方法。
通过本题的学习，我们不仅掌握了具体的解题技巧，更重要的是培养了逆向思维和数学建模能力。这些能力将在今后的CTF竞赛和实际安全工作中发挥重要作用。
最终Flag：
flag{10632674-1d219-09f29-14769-f60219a24}
附录：完整求解代码
#!/usr/bin/env python3
"""
CISCN 2025 - EzFlag Crypto Challenge Solver
完整实现，包含详细注释
"""
# 从程序中提取的字符映射表
CHAR_TABLE = "012ab9c3478d56ef"
# Fibonacci数列模16的Pisano周期
PISANO_PERIOD = 24
def fibonacci_mod16(n):
"""
计算第n个Fibonacci数模16的值
参数:
n: Fibonacci数列的索引
返回:
F(n) mod 16的值（0-15之间的整数）
算法:
利用Pisano周期优化：F(n) mod 16 = F(n mod 24) mod 16
这样可以避免大数计算，最多只需循环24次
"""
# 利用Pisano周期优化
n = n % PISANO_PERIOD
# Fibonacci数列的初始值
a, b = 0, 1
# 迭代计算第n项
for _ in range(n):
a, b = b, (a + b) % 16
return a
def generate_flag():
"""
模拟程序的flag生成逻辑
返回:
生成的完整flag字符串
算法流程:
1. 初始化seed = 1
2. 循环32次，每次：
a. 计算F(seed) mod 16
b. 使用结果作为索引从字符表中获取字符
c. 更新seed = (seed * 8) + (64 + i)
3. 在指定位置插入连字符
"""
seed = 1
characters = []
# 生成32个字符
for i in range(32):
# 计算Fibonacci数模16
fib_value = fibonacci_mod16(seed)
# 从字符表中查找对应字符
char = CHAR_TABLE[fib_value]
characters.append(char)
# 更新seed：左移3位（乘8）加上(64 + i)
# 使用位掩码确保在64位范围内
seed = ((seed << 3) + (0x40 + i)) & 0xFFFFFFFFFFFFFFFF
# 拼接所有字符
flag_body = "".join(characters)
# 在指定位置插入连字符
# 格式：8个字符-5个字符-5个字符-5个字符-9个字符
formatted_flag = (
f"flag{{"
f"{flag_body[0:8]}-"
f"{flag_body[8:13]}-"
f"{flag_body[13:18]}-"
f"{flag_body[18:23]}-"
f"{flag_body[23:32]}"
f"}}"
)
return formatted_flag
def main():
"""主函数"""
print("CISCN 2025 - EzFlag Solver")
print("=" * 50)
# 生成flag
flag = generate_flag()
# 输出结果
print(f"\nFlag: {flag}")
print("=" * 50)
if __name__ == "__main__":
main()
希望本文能帮助读者深入理解这道题目的解题思路和技术细节，在CTF学习之路上更进一步。
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全《CISCN 2025 – EzFlag Crypto 深度解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论