babyvm 逆向分析（乘法逆元在加密算法中的应用）

码农UP2U

发布于 2026-03-16 17:21:57

650

前面三篇文章链接：

关于 babyvm 其实到第三篇文章已经算是结束了，这里的补充完全是继续介绍一下关于算法的还原。有些时候并不一定可以暴力破解，也不一定可以用 z3 模拟，那么最终还是要落到算法的逆运算上，这样就可能不得不使用到数学了。包括商业化的 VMP 里面就有很多关于数字电路、数学等相关的知识，比如与非门、或非门之类的。

0x01：还原算法的思路

上篇文章，我们使用 z3 库来完成了 flag 的计算，那么整个算法是否可逆呢？其实是可逆的。

我们分析到的算法如下：

pMem[0] = pMem[0] ^ pMem[1];
pMem[1] = pMem[1] ^ pMem[2];
pMem[2] = pMem[2] ^ pMem[3];
pMem[3] = pMem[3] ^ pMem[4];
pMem[4] = pMem[4] ^ pMem[5];
pMem[5] = pMem[5] ^ pMem[6];

pMem[6] = (pMem[8] + 2 * pMem[7] + 3 * pMem[6]) * pMem[12];
pMem[7] = (pMem[9] + 2 * pMem[8] + 3 * pMem[7]) * pMem[12];
pMem[8] = (pMem[10] + 2 * pMem[9] + 3 * pMem[8]) * pMem[12];

swap(pMem[13], pMem[19]);
swap(pMem[14], pMem[18]);
swap(pMem[15], pMem[17]);

在整个算法当中，pMem[0] 到 pMem[5] 是通过异或完成的。

整个异或的解密过程是逆序异或的。

当前的 pMem[5] 是确定的，只要用它与 pMem[6] 进行异或操作，那么就可以得到原始 pMem[5] 的值，依次再逐个的异或，就可以得到 pMem[4] 到 pMem[0] 的原始值了。

但问题是 pMem[6] 的值是未知的。因为 pMem[6] 的值需要 pMem[7]、pMem[8] 和 pMem[12] 来参与运算。没有 pMem[6] 的值就无法计算原始的 pMem[5] 的值了。这就是问题所在！

对于想要求得 pMem[6] 的值来说，目前只有 pMem[12] 是已知的，pMem[7] 和 pMem[8] 的值不是已知的、因为它也是经过运算后的值，不是原始的值，因此不能用来计算 pMem[6] 的值。

好在，虽然我们无法直接计算 pMem[6] 的原始值，但是我们可以通过计算得到 pMem[8] 的原始值。因为 pMem[9]、pMem[10] 和 pMem[12] 是已知的。

计算出 pMem[8] 以后，就可以继续计算 pMem[7]，有了 pMem[7] 就可以计算得到 pMem[6] 了。有了 pMem[6] 就可以完成之前的 pMem[5] 的异或运算了。

当然了，还有一步是交换操作，这个就比较简单了。

0x02：还原第二步的算法

按照上面的分析，我们首先要来还原下面这几个式子，先来看看式子的计算。

pMem[6] = (pMem[8] + 2 * pMem[7] + 3 * pMem[6]) * pMem[12];
pMem[7] = (pMem[9] + 2 * pMem[8] + 3 * pMem[7]) * pMem[12];
pMem[8] = (pMem[10] + 2 * pMem[9] + 3 * pMem[8]) * pMem[12];

我们目前先来还原 pMem[8] 的值，也只能先还原它，这个在前面也提到过，它的计算公式如下：

pMem[8] = (pMem[10] + 2 * pMem[9] + 3 * pMem[8]) * pMem[12];

上面的式子是一个正向的式子，结果 pMem[8] 已经存在数组中了，所以我们要求原始的 pMem[8] 的值。

我们把当前的值代入到式子中，当前的值在数组当中，也就是我们找到的第二组真正的结果，数组如下：

uint8_t f1[20] = {
    0x69, 0x45, 0x2A, 0x37, 0x09, 0x17, 0xC5, 0x0B, 0x5C, 0x72,
    0x33, 0x76, 0x33, 0x21, 0x74, 0x31, 0x5F, 0x33, 0x73, 0x72
};

上面的字节数组，是通过 flag 和算法生成的结果。只不过，我们要通过这个结果，也就是这个字节数组和上面的算法，反推出 flag 的值。

把具体的值代入到式子中，代入以后的式子如下：

pMem[8] = (pMem[10] + 2 * pMem[9] + 3 * pMem[8]) * pMem[12];
0x5C = (0x33 + 2 * 0x72 + 3 * x) * 0x33;

其中的 x 就是我们要计算的原始的 pMem[8]。

我们把十六进制转换成十进制，0x33 是十进制的 51，0x5C 是十进制的 92。

按照常规数学来说，应该先用 92 除以 51，也就是下面的式子：

0x5C / 0x33 = (0x33 + 2 * 0x72 + 3 * x);

但是这样对吗？其实是不对的。因为在计算机中 0x5C 的存储是单字节的，也就是相当于是下面这样的式子：

0x5C = ((0x33 + 2 * 0x72 + 3 * x) * 0x33) & 0xFF;

看到最后的按位与运算了吧？也就是说，最后的结果，高位丢失了。但是，并不是无解的，可以使用另外一种计算方法来进行还原。

0x03：单字节存储与乘法逆元

先把上面的计算过程放放，我们先来计算一个值，我们求 51 的乘法逆元。

因为我们是单字节存储，因此这里找 51 模 256 的乘法逆元，即：

51x ≡ 1 (mod256)

要求 51 的逆元，首先需要确定 51 是否有乘法逆元，那么

gcd(51, 256) = 1

说明是有乘法逆元的。

那么，我们就可以求如下方程：

51 * x + 256 * y = 1
=> 1 = 256 + 51 * (-5)
==> 256 - 5 = 251

那么，51 的乘法逆元是 251。

有了乘法逆元可以做什么呢？先看个例子，举个例子。

先看正常的数学例子，例子如下：

// 正常数学情况
x * 51 = 51x
x = 51x / 51
比如 x = 10，代入：
10 * 51 = 510
10 = 510 / 15

正常的数学情况是这样的，但是我们是单字节存储，高位会丢失的。上面的值在实际存储时，我们是无法用单字节存储 510 的。因此实际的存储是这样：

x = 10
x * 51 = 510
// 实际存储是 510 & 255 = 254
// 也可以是 510 % 256 = 254

也就是说，10 * 51 用单字节存储，最终的结果是 254，并不是 510，所以用 254 除以 51 是得不到 10 的。

怎么办呢？这就用到了乘法逆元。用乘法逆元计算 x 的值：

x = 254 * (51 的乘法逆元) % 256
=> x = 254 * 251 % 256
=> x = 10

到这里就明白如何还原上面算法中的式子了。也就是在进行算法逆的时候，除法是不可以使用的，要使用乘法，乘以除数的乘法逆元。

0x03：算法还原

明白了乘法逆元的作用，那么上面的式子就可以写成如下的形式：

pMem[8] = (pMem[10] + 2 * pMem[9] + 3 * pMem[8]) * pMem[12];
0x5C = (0x33 + 2 * 0x72 + 3 * x) * 0x33;
92 = (51 + 2 * 114 + 3 * x) * 51;
=> 92 * 251 % 256 = (51 + 2 * 114 + 3 * x)
=> 52 = (51 + 2 * 114 + 3 * x)
=> 52 - (51 + 2 * 114) = 3 * x
=> -227 = 3 * x

到这一步的时候，我们是不是认为 -227 / 3 就可以求得 x 的值了？不行！这是常规的数学，这里是不能使用除法的，还是需要乘法逆元。3 的乘法逆元是 171。

=> -227 = 3 * x
=> -227 * 17 % 256
==> 95 ===> 它是字符 “_”

和我们的 flag 比对一下：

Y0u_hav3_r3v3rs3_1t!

从 0 开始数第 8 个正好是 “_”。

0x04：C 还原代码

上面介绍完整个乘法逆元的运算了，那么下面给出完整的 C 语言的算法：

#include <stdio.h>
#include <stdint.h>

uint8_t inv51(uint8_t x) 
{
    return (uint8_t)(x * 251);
}

uint8_t inv3(uint8_t x) 
{
    return (uint8_t)(x * 171); 
}

int main() 
{
    uint8_t f1[20] = {
        0x69, 0x45, 0x2A, 0x37, 0x09, 0x17, 0xC5, 0x0B, 0x5C, 0x72,
        0x33, 0x76, 0x33, 0x21, 0x74, 0x31, 0x5F, 0x33, 0x73, 0x72
    };

    uint8_t t;
    t = f1[15]; f1[15] = f1[17]; f1[17] = t;
    t = f1[13]; f1[13] = f1[19]; f1[19] = t;
    t = f1[14]; f1[14] = f1[18]; f1[18] = t;

    uint8_t f[13];

    f[12] = f1[12];
    f[11] = f1[11];
    f[10] = f1[10];
    f[9]  = f1[9];

    uint8_t t8 = inv51(f1[8]);
    f[8] = inv3((uint8_t)(t8 - 2*f[9] - f[10]));

    uint8_t t7 = inv51(f1[7]);
    f[7] = inv3((uint8_t)(t7 - 2*f[8] - f[9]));

    uint8_t t6 = inv51(f1[6]);
    f[6] = inv3((uint8_t)(t6 - 2*f[7] - f[8]));

    for (int i = 5; i >= 0; i--) {
        f[i] = f1[i] ^ f[i + 1];
    }

    for (int i = 0; i < 13; i++) {
        putchar(f[i]);
    }
    for (int i = 13; i < 20; i++) {
        putchar(f1[i]);
    }

    putchar('\n');

    return 0;
}

输出了同样的 flag，flag 如下：