与未知 dx 的反向乘法 - 在多个 mul/add 常数步骤后求解原始 AX

Question

我在 16 位 x86 asm 中有这个重复的迭代过程

rec_loop:
  mul bx          ; constant value of 0x11bf
  add ax, 0x4743
  loop rec_loop

它是运行几次，但对于我们的例子来说，假设它运行了 3 次，现在在它完成后我得到 dx:ax 并且需要恢复这个程序的初始 ax （初始dx为0）。乍一看，我们可以看到有关 dx 的信息在此过程中正在丢失，因为 mul 用新的覆盖了最后一个 dx。

我正在寻找一种方法来扭转这个过程，如果可能的话，当然假设上面的代码不能改变。

如果我忘记解释某事或没有提供有关问题的足够详细信息，请告诉我，我会回答。

Answer 1

计算x_n+1 := (a * x_n + c) mod m，其中a = 0x11bf, c = 0x4743, m= 2¹⁶ 组成一个pseudo-random 数生成器。具体来说，周期为 2¹¹ 的 linear congruential generator。所以显然不是 high-quality PRNG，但对于只需要看起来有点随机的数据的用例来说可能就足够了。我注意到问题没有说明使用此代码的上下文。

x_i的序列（这里是在AX中连续生成的）可以通过使用mod元乘法逆a[=28=来反转]inverse 像这样：x_n-1 = a_inverse* (x_n - c) mod米。在这种情况下 mod 元乘法逆是 0xde3f.

请注意，在反向计算中不需要 DX 的值，如果需要，序列中的任何一点都可以很容易地从 AX 确定。下面乘法逆的确定使用了基于定义的 naive 方法。对于较大的操作数大小，这是非常低效的，人们会想改用扩展欧几里得算法。

简单的 C99 代码，用于试验计算乘法逆和反转 AX 中的值序列：

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

#define X_0   (0xc001)
#define ITERS (3)

uint32_t modular_inverse (uint32_t a, uint32_t m)
{
    for (uint32_t x = 1; x < m; x++) {
        if (((a % m) * (x % m)) % m == 1) {
            return x;
        }
    }
    printf ("no inverse found\n");
    return 0;
}

uint16_t umul16_lo (uint16_t a, uint16_t b)
{
    return (uint16_t)(a * b);
}

uint16_t umul16_hi (uint16_t a, uint16_t b)
{
    return (uint16_t)(((uint32_t)a * b) >> 16);
}

int main (void)
{
    const uint16_t a = 0x11bf;   // multiplier of PRNG
    const uint16_t c = 0x4743;   // additive offset of PRNG
    const uint32_t m = 0x10000U; // modulo of PRNG
    uint16_t a_inverse;

    a_inverse = modular_inverse (a, m);

    printf ("a_inverse = %04x\n", a_inverse);

    const uint16_t bx = a; 
    uint16_t dx = 0;
    uint16_t ax = X_0;

    printf ("starting values:    ax=%04x  dx=%04x  bx=%04x\n", ax, dx, bx);
    printf ("forward computation\n");

    for (int i = 0; i < ITERS; i++) {
        dx = umul16_hi (ax, bx);
        ax = umul16_lo (ax, bx) + c;
    }
    printf ("after %d iterations: ax=%04x  dx=%04x  bx=%04x\n", ITERS, ax, dx, bx);
    printf ("backward computation\n");

    for (int i = 0; i < ITERS; i++) {
        ax = umul16_lo (ax - c, a_inverse);
    }

    printf ("after %d iterations: ax=%04x\n", ITERS, ax);

    return EXIT_SUCCESS;
}

与未知 dx 的反向乘法 - 在多个 mul/add 常数步骤后求解原始 AX

Reverse multiplication with unknown dx - solve for original AX after multiple mul/add constant steps

x86

assembly

reverse-engineering

lcg