C中的乘法溢出
我正在做一些安全性CTF练习，并且遇到了这个问题。 这是已编译程序的C源代码：
int main(int i, long **a) { if(*a[1] * 0x1064deadbeef4601u == 0xd1038d2e07b42569u) //exec shell return 0; } 困扰我的事情：
-
当我关闭gcc标志时，长**主参数将无法编译，因此我无法在计算机上重现问题。 这是一个使用不同的编译器吗？ 编译程序在CTF服务器上运行正常。
-
在测试相等性之前，程序在乘法过程中反复溢出。 我尝试使用线性同余方程（mod 2 ^ 64）和扩展的欧几里德算法来找到所需的x输入，但这对我不起作用。
有人可以帮我解决这个问题吗？ 我试图找到* a [1]，正确的程序参数。
在gdb中反汇编主要给出：
(gdb) disas main Dump of assembler code for function main: 0x000000000040050c : push %rbp 0x000000000040050d : mov %rsp,%rbp 0x0000000000400510 : sub $0x10,%rsp 0x0000000000400514 : mov %edi,-0x4(%rbp) 0x0000000000400517 : mov %rsi,-0x10(%rbp) 0x000000000040051b : mov -0x10(%rbp),%rax 0x000000000040051f : add $0x8,%rax 0x0000000000400523 : mov (%rax),%rax 0x0000000000400526 : mov (%rax),%rax 0x0000000000400529 : mov %rax,%rdx 0x000000000040052c : movabs $0x1064deadbeef4601,%rax => 0x0000000000400536 : imul %rax,%rdx 0x000000000040053a : movabs $0xd1038d2e07b42569,%rax 0x0000000000400544 : cmp %rax,%rdx 0x0000000000400547 : jne 0x400562 0x0000000000400549 : mov $0x0,%edx 0x000000000040054e : mov $0x40061c,%esi 0x0000000000400553 : mov $0x40061f,%edi 0x0000000000400558 : mov $0x0,%eax 0x000000000040055d : callq 0x4003f0 0x0000000000400562 : mov $0x0,%eax 0x0000000000400567 : leaveq 0x0000000000400568 : retq End of assembler dump.
这里没有真正的溢出 – 它只是做一个乘法mod 2 64并测试结果是预期的。 要想出所需的输入，你只需要找到因子0x1064deadbeef4601的逆（mod 2 64 ），然后乘以0xd1038d2e07b42569
对于2次幂模数，使用欧拉公式通常最容易找到逆：
x -1 （mod m）≡xφ （m）-1 （mod m）
当m是2的幂时， φ（2 k ）= 2 k-1 ，所以你可以用2（k-1）次乘法来计算。