CTF 密码学与逆向入门笔记

密码学概述

古典密码

栅栏密码

传统

传统栅栏加密是把明文分成 N 个字符一组，然后取出每组的第一个字符进行拼接，再取出每组的第二个字符进行拼接，直到取出每组的最后一个字符进行拼接，从而得到密文。一般而言，N 的值是明文长度的因数，这样可以保证每个分组都是 N 个字符，但也有 N 不是长度因数的情况。每组有 N 个字符就被称为 N 栏栅栏密码。例如，每组有 2 个字符就叫作 2 栏栅栏密码。N 也被称为栏数。

【例题】Teucbonojmsvrhlzdghqikrwfxupoeteayo

带密钥

eg：

密钥：howareu 明文：Thequickbrownfoxjumpsoverthelazydog 将明文每 7 个字符分为一组，即栏数为 7，密钥的长度和栏数相同。根据密钥中字符在 26 字母表（abcd……）中的出现顺序，确定每一列的提取顺序。例如，在表 3.1.3 中，根据字母表顺序，密钥 howareu 中第 1 个出现的字母是 a，就提取“a”对应的那列明文；howareu 中第 2 个出现的字母是 e，就提取“e”对应的那列明文；以此类推，最后得到的密文是：qouryinphoT koolhbxvauwmtdcfsegerjez。解密时，不仅需要知道栏数，还需要知道密钥。将密文 qouryinphoTkoolhbxvauwmtdcfs egerjez 根据密钥长度均分为 7 组，并写出每组对应的密钥字母，如表所示。

以正确的密钥顺序按行恢复字母，如表 3.1.5 所示，再从第 1 列开始拼接字符，就可以得到正确的明文。

W 型

W 型栅栏加密也称为“Rail-Fence Cipher”，其栏数被称为“Zig-Zag”（栏数：有几个 W）。其原理是，根据 Zig-Zag 确定分组后，将明文由上至下以“W”方式将字母填入分组中，当到达最底层分组时，再向上继续填写字符，如此重复，直至明文结束为止。

eg：

明文 WEAREDISCOVEREDFLEEATONCE 及其 3 栏分组结果，如图

按行读取后，得到密文：WECRLTEERDSOEEFEAOCAIVDEN。解密时，需要根据栏数确定每个字符的位置，再根据密文顺序填入密文，最后按照“W”的方式读取即可得到明文。

破解 W 型栅栏密码的关键在于确定其 Zig-Zag 值（即栏数）。根据加密时的步骤，Zig-Zag 值最少是 2，最多不超过明文长度。因此，可以采用枚举 Zig-Zag 的方式对密文进行破解。

凯撒密码

凯撒将信件中的每一个字母用字母表中该字母后的第三个字母替换，即每一个字母都会向后移 3 个位置（把 A 看作第 0 个位置，把 D 看作第 3 个位置），结果如下：

密文字母表：

eg：

明文：ATTACK 密钥：key=3（沿字母表向后循环位移 3 个字母）密文：DWWDFN

ROT 位移密码

ROT 是英文 Rotation（旋转）的缩写。前面说过，凯撒密码是按照字母表向后循环移动 3 个字母的方式对明文进行替换。英文字母表中一共有 26 个字母，显然，循环移动 1～25 个字母都是可以的。这种根据某个表循环移动，从而建立密文，再对明文进行替换的加密方法统称为 ROT 位移密码凯撒密码只是 ROT 位移密码的一种特例。 1）ROT-5 只针对数字加密，其原理是根据数字表循环移动 5 个字符，从而形成密文。其明文和密文的对应关系下：明文：0123456789 密文：5678901234 2）ROT-13：只针对英文字母加密，其原理是根据英文字母表循环移动 13 个字符，从而形成密文。其明文和密文的对应关系如下：明文字母表：

密文字母表：

3）ROT-47：针对 ASCII 字符加密，其原理是根据 ASCII 码的可打印字符范围（32～126），将打印字符表循环移动 47 个字符，从而形成密文。

【例题】rot1.txt

【例题】rot2.txt

【例题】rot3.txt

Atbash 密码（埃特巴什密码）

是代换密码的一种，其加密算法非常简单：使用字母表中的最后一个字母替换第 1 个字母，用倒数第二个字母替换第 2 个字母，直到最后用字母 A 替换字母 Z 为止。明文和密文的对应关系如下：

uozt{}

flag{}

下面给出一个例子：明文：the quick brown fox jumps over the lazy dog

密文：gsv jfrxp yildm ulc qfnkh levi gsv ozab wlt

猪圈密码

猪圈密码是一种以格子为基础的简单替换密码，它利用不同的格子符号表示所有英文字符，如图所示。

针对猪圈密码，CTF 赛题中有 2 种考法

考法 1：根据符号解密。题目会提供由猪圈符号组成的密文，我们只需要找到每个符号对应的明文，就能解密。

Enigmator-Pigpen

考法 2：猪圈字母替换密码。在图中，不考虑图中的点，我们发现图像左右两侧完全一样，也就意味着相同位置的字母可以一一对应

根据上述明文和密文的对应关系进行替换，即可完成加密或者解密。

【例题】猪圈1.png

【例题】helloCRY.txt

培根密码

为了对秘密消息进行编码，需要将消息中的每个字母转换成由 5 个 a/b 字母组成的字符串，其本质是用 5 比特的二进制数表示对应的字母，转换方法如表 3.1.6 所示。不难发现，培根密码的特点是：密文长度应该是 5 的倍数。注意，培根密码提供两种转换方式，在破解培根密码时需要尝试这两种情况。

培根密码的转换方式非常简单，其本质是替换密码。它的特别之处在于，可以通过不明显的特征来表示两种符号 a 和 b（0–1），从而实现消息的隐藏。例如，可以通过大小写、正斜体、元辅音等两种不同的属性来表示两种信息。破解培根密码的关键是能够快速从载体消息中发现两种不同的属性。

如：把字母表的前 13 个字母转为 a，后 13 个字母转为 b

【例题】bacon.txt

简单替换密码

简单替换密码（Simple Substitution Cipher）的原理是将每个明文字母替换为与之唯一对应且不同的密文字母，其对应规则可以是完全随机的。在下面的例子中，密文字母表就是密钥。

下面是一个例子。明文：the quick brown fox jumps over the lazy dog 密文：gir dhjmp luwev swa ohzxf wnru gir ykcb qwt

密文字母频率统计表

对于简单替换密码，密文中出现最多的字母很可能对应明文的字母 E，且密文越长，这种猜测的准确率就越高。我们完全可以根据密文字母频率的统计结果，与表 3.1.8 进行对照，再结合人工修改，就能很快破解出明文。

仿射密码

仿射密码（Affine Cipher）是单表代换密码的一种，利用乘法、加法和模运算将明文字母替换为密文。

加密函数通常为 E（x）=（ax+b）mod m，其中：

1）x 表示明文按某种方式转换得到的数字； 2）a 和 m 互质（即最大公约数为 1）； 3）m 是字母表大小。

上述条件确保明文与密文一一对应，从而可以正确解密。

解密函数为 D（x）= a⁻¹（x-b）mod m，其中 a⁻¹ 是 a 在 Zm 群中的乘法逆元。Zm 群可简单理解为 {0,1,2,…,m-1} 的集合，即小于 m 的非负整数组成的集合。

下面通过例子介绍逆元的概念。如果 a*x≡1（mod m），则称 a 和 x 在模 m 下互为逆元。

假设 m=26，分别计算不同 a 对应的逆元 x：

1）a=2 时，x 无解。因为 ax 必为偶数，而 1 为奇数，同余等式不可能成立。 2）a=3 时，x=9，因为 39=27≡1（mod 26）。 3）a=13 时，x 无解。因为 ax 必为 13 的倍数，模 26 只可能余 13 或 0，同余等式不可能成立。 4）a=17 时，x=23，因为 1723=391≡1（mod 26）。

结论：只有当 a 和 m 互质时，a*x≡1（mod m）才有解 x，这个解 x 就是 a 的逆元，记作 a⁻¹。求出加密函数中 a 的逆元即可解密。一般将加密函数中的 a 和 b 作为仿射密码的密钥。

破解仿射密码

假设我们已经知道仿射密码中的 2 字节密文及其对应的明文，那么就能求解出密钥。用公式表示如下：

其中 x，x 是已知的明文，它们加密后的密文分别是 c，c，把 c，c 相减，可得：

x，x,c，c 均已知，可利用扩展的欧几里得算法求出 a，然后利用式可求出 b。

（仿射密码破解示意图）

之后，运用求逆元的方法求出 a 的逆元 a，就可以得到解密函数，从而对密文解密。求逆元的具体方法是使用 Python 的 Gmpy2 库。

【例题】aff ine-cipher.txt

单表代换密码总结

以上介绍的凯撒密码到仿射密码均属于单表代换密码的范畴。所谓单表代换密码，是指对所有明文字母都用一个固定的代换进行加密，其加密过程是从明文字母表到密文字母表进行一一映射。

通过词频统计分析，破译者可以统计密文中单字母、双字母以及 3 个字母出现的频率，结合已知的大量明文的规律（例如，单字母 e 的出现频率最高，双字母 th 的出现频率最高），可以快速破解密文。我们可以利用 Enigmator 工具包完成字频统计。

多表代换密码

为了改进单表代换密码，解决其不能抵抗词频统计攻击的问题，人们提出了多表代换密码的概念。

多表代换是指在明文消息中采用不同的单表进行代换。通过这种方式，可以把同样的明文代换成不同的密文，从而破坏密文的统计特性，实现抵抗词频统计攻击。

多表代换密码包括棋盘密码（Polybius 密码）、Playfair 密码、维吉尼亚密码（Vigenere Cipher）、弗纳姆密码（Vernam Cipher）、关键字密码和希尔密码（Hill Cipher）等。接下来，我们将重点介绍维吉尼亚密码和希尔密码。

维吉尼亚密码

加解密过程

维吉尼亚密码是由一系列偏移量不同的凯撒密码组成的，属于多表代换密码的一种简单形式。其密码表如图 3.1.20 所示，横坐标代表明文，对应的纵坐标代表密钥。

下面是一个例子。明文：come greatwall 密钥：cipher

首先，去除明文中的空格，然后扩展密钥长度，使其与修改后的明文一样长。由于图 3.1.20 中的横坐标为明文，纵坐标为密钥，因此横纵坐标交叉的位置就是密文（不考虑大小写），如表 3.1.11 所示。因为每个密钥所在行的偏移不一致，导致相同的明文加密后的密文不一致，所以可以抵抗词频分析攻击。

当我们知道维吉尼亚密码的密文和密钥时，解密过程如下：首先根据密钥确定所在行，然后在对应行中找到密文，再查看密文所处于的列，就能在横坐标中找到对应的明文。

破解维吉尼亚密码（key 未知）

破解维吉尼亚密码主要有两个步骤： 1）确定密钥长度。 2）确定密钥。

有两种判断维吉尼亚密码密钥长度的方法：

Kasiski 测试法
Friedman 测试法

【例题】维吉尼亚遇上困难.txt

希尔密码

希尔密码的原理是，将每个字母在字母表中的顺序作为其对应的数字，即 A=0，B=1，C=2 等，将明文转化为 n 维向量，与一个 n×n 的矩阵（可逆）相乘，再将得出的结果模 26。所以希尔密码的形式是矩阵。假设明文是 AXE，转化为向量是[0,23,4]。

密钥为 6 24 1 13 16 19 20 17 15 最终的结果为

则密文为 ksj。由于希尔密码的典型特征为是矩阵，因此如果一个题目中出现了矩阵的提示，就一定要想到希尔密码。

【例题】Hill.txt

逆向

在程序逆向分析中，要静态为主，动态为辅。

❑静态为主：是指优先使用 IDA 等工具查看程序伪码，通过静态分析快速定位关键函数，并仔细阅读关键函数中的算法逻辑。静态分析时，要求选手有一定 C 语言基础，因为 IDA 伪码与 C 语言类似。有相当数量的简单题目在这一步就能解决，这就意味着选手只要会看 C 语言、会使用 IDA 反编译，即使完全不懂动态分析，也能解题拿分。 ❑动态为辅：是指在通过静态分析确定关键函数后，由于 IDA 反编译效果或者程序有混淆，不能读懂其中逻辑时，应针对关键函数采用动态分析方法，通过动态调试跟踪函数操作来确定其内部逻辑。动态分析是静态分析的补充。

静态分析和动态分析没有孰优孰劣，需要具体问题具体分析，因此两种分析方法都要尽量掌握。

静态分析方法

工具

DetectItEasy（DIE）

项目地址

它可以用来检测程序架构和文件类型。“模式”说明程序是 32 位还是 64 位，还能看到程序的编译时间以及编译器和链接器信息。如果程序被加壳，还可以显示壳的详细信息。DIE 不仅能检测 Windows 系统下的 PE 文件，还可以检测 Linux 下的 ELF 文件，是目前最好用的查壳、文件类型识别工具。对程序静态分析时，建议优先使用该工具查看基本信息。

EXEInfoPE 和 PEID

这两个工具和 DIE 功能相似，主要是针对 Windows 系统下的 PE 进行查壳和其他常规信息的检测。但是由于它们已经不再更新，因此可以将它们作为 DIE 工具的辅助检测工具。

IDA Pro

反编译器，同时具备调试器的功能。

官网地址

插件

插件	功能
LazyIDA	convert 快速提取数据等
Keypatch	patch 指令方便
Patching	patch16 进制数据方便
findcrypt-yara	常见加密算法识别
auto-enum	自动恢复常见 api 的枚举变量
Hrtng	高亮括号，重定义关键函数声明，栈字符串识别，反 ollvm 等功能
D810	去 ollvm 混淆脚本，安装 Hrtng 后可不安装该插件
classinformer	反编译 C++时, 可以根据 RTTI 等信息综合恢复类 Class 的相关信息，例如继承信息，类名等。
deREferencing	调试时使用，追踪栈和寄存器指向的内容
HexRaysCodeXplorer	自动识别结构体，显示 C++虚函数，生成函数结构树等
DataExportPlus	提取数据增强版

Windows PE 加载器（pe.ldw）和 MS-DOS EXE 加载器（dos.ldw）均声称它们能够识别选定的文件，因为 PE 文件格式是 MS-DOS EXE 文件格式的扩展形式。Binary File（二进制文件）是这个列表中的最后一个选项，它会一直显示，因为它是 IDA 加载无法识别的文件的默认选项，它提供了最低级的文件加载方法。

使用

IDA 为当前打开的每一个显示窗口都提供了标签，通常在 IDA View-A 中显示反汇编结果。可能有读者发现，加载完程序后，IDA View-A 标签中内容和图 5.2.6 中的不一致，这并不影响后续分析工作。用鼠标左键先单击 IDA View-A 标签，再单击主窗口的任意空白处，然后按空格键，就可以在反汇编结果的代码视图（Text view）或图形视图（Graph view）之间进行切换，也可以在空白处单击鼠标右键进行切换。依次单击“View→Toolbars→Graph view”，工具栏中会增加图形视图工具，如图 5.2.7 所示，单击方框中的 3 个按钮也能够实现切换。

Hex 标签以十六进制方式显示程序数据，它和 010 Editor 的区别在于：Hex 标签中的地址是程序运行加载到内存中的内存地址，而 010 Editor 显示的地址是针对文件的偏移地址。Imports 标签中给出了程序的导入表，即调用了哪些外部函数。

IDA 的常用功能和快捷键

原理和技巧

程序静态分析（Program Static Analysis）是指在不运行代码的前提下，通过词法分析、语法分析、控制流与数据流分析等技术对程序代码进行扫描的一种代码分析技术。目前，静态分析技术的一个发展趋势是研究模拟执行技术，例如符号执行、抽象解释、值依赖分析等技术，以发现更多传统意义上动态测试才能发现的缺陷，并采用约束求解的数学工具进行路径约减或者可达性分析以减少误报，提升分析效率。静态分析的目标对象可以分为三类：源代码、字节码和二进制代码。

1.源代码分析源代码分析的优点是程序的全局信息比较完整，分析的难度较低，分析精度较好；缺点是源代码难以获得。 2.字节码分析字节码分析可以对 C#、Java 等语言编译后生成的字节码进行分析，对于 C/C++语言则无能为力。 3.二进制代码分析二进制代码分析的优点是采用反汇编技术，有广泛的实用性；缺点是缺乏高级语言的结构信息和类型信息，难度大，精确度低。

静态分析实战

[例题]1.exe

【例题】88eb31060c4abd0931878bf7d2dd8c1a

逆向技巧：在 IDA 伪码中看到数字后，无论是正数、负数，还是特别大的数，要都先转换为十六进制数。

单击鼠标右键选择 Hexadecimal，或者在键盘上按 H 键，都可以将数字转换为十六进制。

结合 ASCII 码的可打印范围，以逐个选中后单击鼠标右键选择 Char 或者在键盘上按 R 键将其转换为字符。

字节序

字节序是指多字节数据在计算机内存中存储或在网络中传输时各字节的顺序

对于 2 个字节 12、ab，有两种存储方式：12ab 或者 ab12

字节序只改变字节之间的顺序，不改变单个字节的内容，字节 0xab 无论是哪种顺序，它作为字节永远是 0xab，不会变成 0xba。

字节序分为两种：大端序和小端序。大端序（大端模式）是指数据的高字节保存在内存的低地址中，而数据的低字节保存在内存的高地址中；小端序（小端模式）是指数据的高字节保存在内存的高地址中，而数据的低字节保存在内存的低地址中。要理解大端序和小端序的定义，就需要知道什么是数据的高字节，什么是内存的高地址（悄悄地说，作者背诵定义后 5 分钟也会忘记）。如果记不住上一段的内容，也没有关系，我们推荐一种更简单的记忆法：与我们阅读习惯一致的顺序是大端序，另一种就是小端序。下面有两段内存数据：

0000430：e684 6c4e 0100 1800 53ef 0100 0100 0000 0000440：b484 6c4e 004e ed00 0000 0000 0100 0000 在大端模式下，第一行前 32 比特应该这样读：e6 84 6c 4e（假设 int 占 4 字节）。在小端模式下，第二行前 32 比特应该这样读：4e 6c 84 b4（假设 int 占 4 字节）。

在 IDA 中，大于等于两字节的数据的存储方式和我们的阅读习惯相反。

【例题】base.exe

【例题】change.exe

【例题】bbox.exe

(ctf_py27)PS C:\Users\用户名> python E:\CTFtools\脚本\Crypto\test.py >1.txt

tar=[0x64,0x00,0x47,0x47, 0x43,0x04, 0x46,0x50, 0x6B, 0x05, 0x47, 0x6B, 0x40, 0x04,
0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04, 0x04,0x04,0x04,0x04,0x04,0x04,0x04, 0x04,0x04,0x04,0x04,0x04, 0x04,0x04, 0x04, 0x04, 0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04, 0x04,0x04,0x04, 0x04,0x6B,0x58,0x04, 0x04, 0x53, 0x15]

for i in range(256):
    res=[]
    for t in tar:
        res.append(t^i)
    print '---------------------'
    print ''.join([chr(z) for z in res])

扩展

虚拟机、实验室资源、例题笔记