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

让我们分析这些字符串的含义：

1. Enter password:: 提示用户输入密码

2. V3ryStr0ngp@ssw0rd: 这很可能就是程序验证的密码

3. Wrong password!: 密码错误时的提示

4. flag{: flag的标准开头

5. 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)

从汇编代码中，我们可以梳理出程序的主要流程：

1. 密码验证阶段：

   • 提示用户输入密码

   • 读取用户输入

   • 与硬编码的密码字符串比较

   • 密码错误则输出提示并退出

2. 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位，相当于乘以8

• 0x40是十六进制，等于十进制的64

• i是循环变量，从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周期是解决本题的关键。它的重要性在于：

1. 周期性：Fibonacci数列模m具有固定周期

2. 可预测性：知道周期后可以快速计算任意项

3. 实用性：将指数级复杂度降低到常数级

对于模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 程序设计模式

本题程序的设计体现了几个有趣的模式：

1. 延时输出：使用sleep逐字符输出，增加程序运行时间

2. 种子机制：使用seed生成伪随机但确定的字符序列

3. 数学难题：表面上需要巨大计算量，实际有巧妙解法

七、学习建议

对于想要学习密码学CTF题目的同学，本题提供了以下学习要点：

7.1 基础知识

必备工具

• Linux命令行基础（file, strings, objdump）

• Python编程（用于快速实现算法）

• 基础数论知识（模运算、周期性）

汇编语言

• x86-64基本指令集

• 函数调用约定

• 寄存器使用规则

7.2 解题思路

信息收集

1. 使用自动化工具快速提取信息

2. 运行程序观察行为

3. 不放过任何可疑的字符串

静态分析

1. 找到main函数，理解主流程

2. 分析关键函数的实现

3. 还原高级语言伪代码

算法识别

1. 观察变量更新模式

2. 识别常见算法（Fibonacci、哈希等）

3. 寻找数学规律

优化求解

1. 识别算法瓶颈

2. 应用数学理论优化

3. 验证结果正确性

7.3 进阶方向

学完本题后，可以继续学习：

1. 更多数论知识

   • 欧拉函数

   • 中国剩余定理

   • 原根与离散对数

2. 密码学算法

   • RSA加密

   • 椭圆曲线密码

   • 哈希函数

3. 逆向工程

   • IDA Pro、Ghidra等工具

   • 动态调试技术

   • 反混淆技术

八、总结

本题是一道设计精巧的密码学题目，主要考察以下能力：

1. 逆向分析能力：通过反汇编理解程序逻辑

2. 算法识别能力：识别Fibonacci数列

3. 数学优化能力：应用Pisano周期理论

4. 编程实现能力：将分析结果转化为代码

解题的核心在于发现并利用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学习之路上更进一步。