+- WeHack BBS (https://bbs.wehack.space)
+-- 版块： 计算机技术 (https://bbs.wehack.space/forum-5.html)
+--- 版块： 逆向工程讨论区 (https://bbs.wehack.space/forum-9.html)
+--- 主题： 用乘法和移位实现mod 53 (/thread-54.html)
用乘法和移位实现mod 53 - vimacs - 09-09-2018
今天逆向某个程序的时候发现了下面的代码：
代码:
| 0x180000595 4c8b01 mov r8, qword [rcx]
| 0x180000598 48bd53138cb7. movabs rbp, 0x3521cfb2b78c1353
| 0x1800005a2 488bf2 mov rsi, rdx
| 0x1800005a5 4c334108 xor r8, qword [rcx + 8]
| 0x1800005a9 488bc5 mov rax, rbp
| 0x1800005ac 4c8d25cd0b00. lea r12, [0x180001180]
| 0x1800005b3 488bf9 mov rdi, rcx
| 0x1800005b6 49f7e0 mul r8
| 0x1800005b9 498bc0 mov rax, r8
| 0x1800005bc 482bc2 sub rax, rdx
| 0x1800005bf 48d1e8 shr rax, 1
| 0x1800005c2 4803c2 add rax, rdx
| 0x1800005c5 48c1e805 shr rax, 5
| 0x1800005c9 486bc035 imul rax, rax, 0x35
| 0x1800005cd 4c2bc0 sub r8, rax
| 0x1800005d0 4b8b5cc418 mov rbx, qword [r12 + r8*8 + 0x18]注意 movabs 那条指令将一个很奇怪的 64 位立即数赋值给了 rbp，后面又有 mul 指令，可以推测出它是用乘法、加减法和位运算模拟除法或取模指令（可以参考RE4B里面除以9的那章）。
这里我没找到任何线索，于是用 Python 模拟了一下：
代码:
def fn(r64):
rdx = ((r64 * 0x3521cfb2b78c1353) >> 64)
rax = r64 - rdx
rax = rax >> 1
rax = rax + rdx
rax = rax >> 5
rax = rax * 0x35
return r64 - rax然后打出输入为200之内的结果：
代码:
for i in range(200):
print(fn(i))发现其实这个函数就是 r64%53.
这个的实现原理是什么呢？
刚刚再细看了一下，0x35就是53，所以最后两个操作是商 rax 乘 53，然后被除数 r64 减去 rax*53 得到余数，剩下的问题就是前面除以 53 是怎么做的，原理和 RE4B 里面讲的应该一样。
不过有点奇怪的就是移位因子的选择问题，怎样选择移位因子才能保证没有误差？