BBH3MT 无风
← 返回文章列表

从加密推解密-通用原理

默认分类#西电CTF_2026

从加密推解密-通用原理

发布于 2026-10-19 02:27:09

根据此wp摘抄

拿到加密代码，怎么写出解密代码

一套可迁移的方法，TEA / XTEA / XXTEA / ChaCha 这类 ARX 密码通吃。 配套可运行实验：同目录 lab.c（gcc -O0 -o lab lab.c && ./lab）。

0. 先记住一句话

解密 = 把加密的每一步「倒着放」，每一步用它的逆运算。

就这一句。剩下全是怎么用。数学上就是 (f∘g)⁻¹ = g⁻¹ ∘ f⁻¹。

1. 为什么必须“倒着放”

加密做的事：

代码块

明文 --步骤1--> --步骤2--> ... --步骤n--> 密文

状态一路被改写，每一步都依赖上一步的结果。要回到明文，只能从最后一步开始撤销：先撤步骤 n，再撤步骤 n-1……

就像穿衣服：先穿袜子再穿鞋，脱的时候必须先脱鞋再脱袜子。 顺序反过来是本质，不是技巧。

2. 逆运算速查表（背下这张表，大部分题就能做）

加密里的写法

解密里的写法

备注

x += e;

x -= e;

模 2³² 加法，减 = 加补数

x -= e;

x += e;

x ^= e;

x ^= e;

XOR 自逆，原样写

x = e;

不能直接逆

覆盖赋值丢信息，必须事先备份旧值

swap(a, b);

swap(a, b);

自逆

x = rotl(x, k);

x = rotr(x, k);

循环移位可逆

x <<= k;

x >>= k;（仅当高位没丢）

普通移位丢位，一般不可逆

x = T[x];

x = Tinv[x];

查表

三个要点：

  • 表里的 e 在解密时必须和加密时算出同一个值 —— 这条引出第 3 节的核心判据。

  • XOR 自逆，所以它永远不用“翻”。

  • 普通移位丢位，所以别指望靠反向移位去求逆。

3. 最重要的一节：什么时候“取逆”，什么时候“照抄”

这就是”+ 变 - 了，为什么 >> 不变“的根源。

判据只有一个：看等号左边是不是你正在还原的那个未知量。

  • 左边是待还原的状态 → 取逆。

  • 整个表达式其实是由已知量组成的一个数 → 照抄，一个字符都别改。

拿 TEA 那一行举例：

c

v1 = v1 + G(v0, sum);   /* 加密 */

  • 左边 v1 是待还原的 → 那个 + 要变 -。

  • 右边 G(v0, sum)：v0 在密文里就有，sum 自己能算 → 它是个已知数。你只是要把「加密时加上的那个数」算出来，再减掉。

所以：

c

v1 = v1 - G(v0, sum);   /* 解密：G 一字不改 */

用代数看更清楚：解方程 y = x + f(z)（z 已知）得 x = y - f(z)。 变的只有那个 +；f 从来不是“被求逆”，它只是被重新算了一遍。

由此推出所有细节：

位置

处理

原因

外层 v0 += …

取逆 → -=

它在造值，要撤销

内层 (x>>5) + k1 里的 +

照抄

它在参与重算那个已知数

内层 <<4 / >>5

照抄

同上。写成 <<5 就等于算了个错的 G

k[sum & 3] 的下标

照抄

下标也是“重算已知量”

语句顺序、轮序

倒过来

依赖链要反向剥

一句话：要撤销的才取逆，要重算的必须照抄。

4. 为什么语句顺序和 sum 方向也要反过来

因为加密中的依赖是有方向的：

代码块

v0 先改  →  v1 的更新读的是【新】v0

依赖链 v0 → v1。解密只能沿链倒着剥：

c

v1 -= G(v0, sum);   /* v0 已知（密文里就有），先把 v1 还原出来 */
v0 -= F(v1, sum);   /* 这里的 v1 必须是【刚还原出的新值】 */

两个必须注意的点：

  • 两条语句换序：加密 v0 在前，解密 v1 在前。

  • 第二行必须用第一行刚算出的新值，缓存旧值是经典错误（lab.c 第 4 节有反例）。

轮与轮之间同理：加密 1→32 轮，解密 32→1 轮，所以 sum 要从终值往回走，而不是从 0 开始。

5. ARX 密码的统一套路

TEA / XTEA / XXTEA / ChaCha / Salsa 这类只用三种运算：Add（模加）、Rotate/Shift（移位）、Xor（异或），再加“把密钥混进来”。

套第 3 节的判据，结构永远是这四句话：

代码块

外层 v0/v1 的更新   → 取逆（+= 变 -=）      ← 翻转
内层混洗函数 F/G    → 照抄                 ← 不变
密钥下标表达式      → 照抄                 ← 不变
轮序、sum 走向      → 倒过来               ← 反向

XTEA 的混洗函数比 TEA 更紧凑，同样原样照抄：

代码块

F(x) = ((x << 4) ^ (x >> 5)) + x

6. 为什么这些密码敢这么设计

TEA 更新 v1 时，混洗函数作用在 v0 上，而 v0 是已知的另一个字。 因为“已知”，所以永远不用求 F 的逆 —— 直接算出来减掉就行。

反面对比：如果某一轮写成 v0 = F(v0)（只依赖自己），解密就必须真的把 F 求逆， 要解开 <<4、>>5、^ 的纠缠，而移位还丢位，根本做不到。

ARX 的设计原则：把难逆的混洗函数作用在“已知量”上，再用可逆运算（+** / ^）把它混进状态。**

所以你以后看到任何

c

x += f(其他字);      x ^= f(其他字);

都能立刻写出解密：

c

x -= f(其他字);      x ^= f(其他字);     /* f 原样 */

这是 Feistel 结构的思想；TEA 是它的“模加版本”。

7. TEA / XTEA 逐行推导

TEA

加密（对应 chall6 tea_encrypt @ 0x401205）：

c

sum = 0;
for (i = 0; i < 32; i++) {
    sum += D;                                        /* D = 0x9E3779B9 */
    v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
    v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
}

解密（机械照做）：轮序倒、v1 在前、外层取逆、内层照抄、sum 反向：

c

sum = D * 32;                                        /* = 0xC6EF3720 */
for (i = 0; i < 32; i++) {
    v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);   /* 先 v1 */
    v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);   /* 用新的 v1 */
    sum -= D;
}

XTEA

加密（对应 xtea_encrypt @ 0x4012d8）：

c

sum = 0;
for (i = 0; i < 32; i++) {
    v0 += (((v1<<4) ^ (v1>>5)) + v1) ^ (sum + k[sum & 3]);
    sum += D;                                        /* 注意：v0 算完才更新 sum */
    v1 += (((v0<<4) ^ (v0>>5)) + v0) ^ (sum + k[(sum>>11) & 3]);
}

和 TEA 的关键差别：TEA 每轮“先加 sum 再两个都用”；XTEA 是“v0 用旧 sum，加完才更新，v1 用新 sum”。 解密必须尊重这个不对称：

c

sum = D * 32;
for (i = 0; i < 32; i++) {
    v1 -= (((v0<<4) ^ (v0>>5)) + v0) ^ (sum + k[(sum>>11) & 3]);  /* 对应"v1 用新 sum" */
    sum -= D;
    v0 -= (((v1<<4) ^ (v1>>5)) + v1) ^ (sum + k[sum & 3]);        /* 对应"v0 用旧 sum" */
}

回到 tea6solve.c 的填空

c

uint delta = 0xC6EF3720;                 /* 原来写 0x0 */

for (int i = 1; i <= 32; i++) {
    cipher[1] -= (((cipher[0] << 4) ^ (cipher[0] >> 5)) + cipher[0])
               ^ (key[(delta >> 11) & 3] + delta);            /* 第一个 0x0 */
    delta += 1640531527;                                      /* 原来写 0x0；≡ delta -= 0x9E3779B9 */
    cipher[0] -= (((cipher[1] << 4) ^ (cipher[1] >> 5)) + cipher[1])
               ^ (key[delta & 3] + delta);                    /* 两个 0x0 都在这 */
}

密文和密钥（chall6 .rodata，已按小端还原）：

c

uint cipher2[4] = {0x60EC68AB, 0x940251CE, 0xB427534C, 0xDF435416};
uint key2[4]    = {0xDEADBEEF, 0xCAFEBABE, 0x11223344, 0x55667788};

最终 flag：moectf{Wh4t_a_n1ce_cup_0f_TEA!!}

8. 三个经典坑（本次全踩过一遍）

坑 1 · sum 起始值 必须从加密结束时的 sum 开始。TEA/XTEA 都是 32 轮、每轮加一次 D，终值 = D*32 = 0xC6EF3720。写成 0 直接全乱。

不确定就跑一遍加密，把 sum 打印出来 —— 这比推理可靠。

坑 2 · 第二行用了旧值

c

uint old = v1;
v1 -= G(v0, sum);
v0 -= F(old, sum);   /* 错！必须用刚算出的新 v1 */

坑 3 · C 的有符号溢出与字面量类型

c

uint sum = -1640531527 * 32;        /* int 溢出，UB：GCC 常给对，但不保证 */
uint sum = (uint)0x9E3779B9 * 32;   /* 规范写法；或直接 0xC6EF3720u */

另外 (sum >> 11) & 3 里的 sum 必须是无符号，否则右移是算术移位，下标会算错。模板用 uint 正好避开了。

9. 实战流程（拿到新题照这五步走）

  • 抄 —— 把反编译的加密函数逐行抄成能编译的 C，一行都别省，标出状态变量。

  • 定 —— 确认轮数、块大小、sum/delta 演化方式、密钥、字节序（x86 小端）。

  • 推 —— 机械套用：轮倒序、语句倒序、外层取逆、内层照抄、sum 反向。

  • 验 —— 写 round-trip 测试：用抄来的 encrypt 加密任意数据，再用自己的 decrypt 解，必须完全一致。 这一步比肉眼推理可靠得多，第 8 节的三个坑它全能抓出来。

  • 对 —— 把解出的明文喂回原始程序验证：echo -n 'flag' | ./chall6。

10. 练习

  • 补完 tea6solve.c 的填空，跑出 flag。

  • 把 lab.c 第 4 节的“反例”改成正确版，确认全部 PASS。

  • 思考：XTEA 两半分别用 sum & 3 和 (sum >> 11) & 3 两个不同的位段取密钥，这样做对扩散有什么好处？如果都用 sum & 3 会怎样？

  • 进阶：自己写一个 XXTEA 解密。它的结构是 x += f(邻居)，套第 3 节判据试。