在程序集中整數乘法中隔離數字？

Question

如果我的EAX寄存器是0xFC000000和我的ESI寄存器是0xF9FDEFF3，這樣做的：

IMUL ESI，EAX

將存儲在0x34000000 ESI寄存器。 乘法的結果是0xF615F83334000000，但由於程序在32位，它將截斷爲0x34000000，它是無符號的。現在我的問題是，如果我只有ESI寄存器（0xF9FDEFF3）和乘法（0x34000000）的截斷結果，我將如何去尋找我的EAX寄存器？

在此先感謝

注：EAX和ESI的值是完全隨機的，我用這些數字，是想說明一個例子。

Answer 1

一般來說，你不能「不乘法」，但在某些情況下，你可以：那些你認爲知道的數字是奇數的情況。 （當然，也就是說你知道沒有溢出的情況，所以你可以用普通的舊分區不乘法，但imul不會告訴你無符號溢出）

奇數有modular multiplicative inverse模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可以是任何東西。