在汇编中隔离整数乘法中的数字？

Question

如果我的 EAX 寄存器是 0xFC000000 并且我的 ESI 寄存器是 0xF9FDEFF3，则执行以下操作：

伊穆尔ESI,EAX

将在 ESI 寄存器中存储 0x34000000。乘法的结果是 0xF615F83334000000，但由于程序是 32 位的，因此会将其截断为 0x34000000，并且它是无符号的。现在我的问题是，如果我只有 ESI 寄存器（0xF9FDEFF3）和乘法的截断结果（0x34000000），我将如何找到我的 EAX 寄存器？

提前致谢

注意：EAX 和 ESI 的值是完全随机的，我使用这些数字只是为了展示一个例子。

Answer 1

一般来说，您不能“取消乘法”，但在某些情况下您可以：您知道的数字是奇数的情况。（当然，在您知道没有溢出的情况下，您可以用普通的旧除法进行取消乘法，但imul不会告诉您有关无符号溢出的情况）

奇数具有模乘逆模 2 ³²（实际上是对任何 2 的幂取模，因为 2 的幂在分解时只包含 2，而奇数不包含 2，所以它们的 gcd 将为 1）。

因此，假设我们知道esi是 0xF9FDEFF3 并且乘法的结果是 0x34000000，我们可以这样计算 0xF9FDEFF3 的逆：（edi是输入）

lea ecx, [edi + 1]
mov eax, 2
mov esi, eax
imul    ecx, edi
sub ecx, 1
mov edx, ecx
imul    edx, edi
sub esi, edx
imul    ecx, esi
mov esi, eax
mov edx, ecx
imul    edx, edi
sub esi, edx
mov edx, esi
imul    edx, ecx
imul    edi, edx
sub eax, edi
imul    eax, edx

结果是0x657f413b。现在 0x657f413b * 0x34000000 = 0x149DD93FFC000000，被截断为 0xFC000000。

如果您知道的数字是偶数，您仍然可以求解known * x == output，x但可能没有解，或者有很多解，从来没有一个。您可以将其视为实际上是output = (k * x) << d，其中已知 = 2 ^d k （其中 k 为奇数），那么应该清楚的是，d输出的低位最好为零，否则将无解，如果它们为零，则d的高位可以x是任何东西。