PC逆向之代码还原技术,除法代码还原以及原理第二讲,被除数是正数 除数非2的幂
PC逆向之代码还原技术,除法代码还原以及原理第二讲,被除数是正数 除数非2的幂
目录
- 一丶简介
- 二丶代码还原讲解
- 1.被除数无符号 除数非2的幂
- 2.被除数无符号 除数为特例7
- 三丶代码还原总结
一丶简介
上一篇博客说的除2的幂. 如果被除数是有符号的,那么会进行调整,并使用位操作进行优化 本片博客专门讲解除数不是2的幂
二丶代码还原讲解
1.被除数无符号 除数非2的幂
高级代码:
Release汇编
.text:0040101A mov eax, 38E38E39h
.text:00401023 mul [esp+10h+var_8]
.text:00401027 shr edx, 1除数怎么还原 代码定式:
.text:0040101A mov eax, M
.text:00401023 mul x 此指令等价于 mul x,M
.text:00401027 shr edx, N还原公式 : (2^(32 +n)) / M = 2^n / M 最后结果向上取整. 代入公式: 2^33 / 38E38E39 = 8589934592 / 954437177 = 8.9999999989522621036795594143123 = 向上取整(8.999...) = 9 得出被除数是9
原理: 如果不感兴趣可不看,或者你有<<C++ 与反汇编与逆向分析揭秘>>这本书,可以观看第67页. 原理分析: 首先那么大数是怎么来了. 由于除法指令周期比乘法指令周期长.所以编译器会使用较短的乘法指令来代替除法. 数学证明公式: 设被除数为 x 除数为o 则有下面公式:
由于除数o是一个常量.且2^n次方由编译器选择. 所以 2^n / o 可以在编译期间就算出来. 算出来的结果就是那个很大的数. 为什么是很大的数,在VC++中,n的取值是大于32的. 也就是大于 2^32次方.所以参与运算就会很大了.这样的好处就是 可以直接使用乘法的高位了. 既然我们知道那么最大的数就是 2^n / o(除数) 的出来的.所以我们要求除数o 我们设 2^n/o 为c 则有以下公式:
可以看到最后优化成了 (x * c) >> n 等价于 (x * M) /2^n次方啊. 这里说一下,为什么是2^n次方.因为使用mul的时候,n的取值是大于32的.也就是2^32次方. 然后下面 使用了 sar edx,N 直接使用了edx,我们说过 eax,edx用于乘法.那么eax就是高位.edx就是低位.这里直接对 edx 右移了一位. 那么是不是就是相当于 (eax,edx) >> 1位. 而eax是2^32次方.这里直接对edx移动了.默认就是操作了eax. 所以隐含的eax不要忘记. 所以我们有了公式: (x * c) / (2^(32 + n)次方.这也跟我们上面的汇编指令相对应. 此时我们求o,进行反推: 2^n / c . 求出除数 所以还原公式为: 2^n / c.
2.被除数无符号 除数为特例7
高级代码:
int main(int argc, char* argv[])
{
unsigned int nValue = 16;
scanf("%d",&nValue);// 防止优化.核心代码不是这个
int nTemp = nValue / 7; //核心代码 一会观看反汇编
scanf("%d",&nTemp); //防止优化
return 0;
}Debug下的汇编
.text:00401040 mov eax, [ebp+var_4]
.text:00401043 xor edx, edx
.text:00401045 mov ecx, 7
.text:0040104A div ecx
.text:0040104C mov [ebp+var_8], eaxDebug下的汇编很简单. 获取被除数,因为被除数是无符号.所以edx为0.所以会使用指令 xor edx,edx 进行清零. 这条语句也可以是 cdq.因为是无符号.所以使用cdq符号扩展那么edx也是0.可能xor指令周期 比xor周期长.所以没有使用. 虽然Debug不进行有效优化. 注意不进行有效优化是方便我们调试.但是也会 进行优化.当然不会影响你的调试. 比如 xor 也可以是cdq 如下:
.text:00401040 mov eax, [ebp+var_4]
.text:00401043 cdq
.text:00401045 mov ecx, 7
.text:0040104A div ecx eax = eax / ecx 等价于 eax = eax / 7;
.text:0040104C mov [ebp+var_8], eaxDebug下直接进行还原即可.很简单.
Release下的汇编
.text:0040101A mov ecx, [esp+10h+var_8]
.text:0040101E mov eax, 24924925h
.text:00401023 mul ecx
.text:00401025 sub ecx, edx
.text:00401027 shr ecx, 1
.text:00401029 add ecx, edx
.text:0040102B shr ecx, 2
.text:0040102E mov [esp+10h+var_4], ecxRelease下的汇编就比较烦了.为什么指令是这样. 有一个超大的数, 还有各种乘法, 减法. 移位 加法. 其实这都是有数学原理进行支撑了.而且这个还是个特例.如果不想知道数学原理.直接记住汇编顺序
乘 减 移 加 移. 也算是特征. 正好对应 mul sub shr add shr
还原方法: 还原的时候我们可以设置未知数.这样直接给一个公式进行还原 如下:
.text:0040101A mov ecx, [esp+10h+var_8]
.text:0040101E mov eax, M 设最大数为M
.text:00401023 mul ecx
.text:00401025 sub ecx, edx
.text:00401027 shr ecx, N 设移位为N
.text:00401029 add ecx, edx
.text:0040102B shr ecx, N 设置移位为N
.text:0040102E mov [esp+10h+var_4], ecx还原方法: 2^N/(2^32+M)的商向上取整 可以带入公式: M = 24924925h 十进制 = 613566757 n 有两个,一个是1 一个是2 两个n相加就是3, 因为使用edx.没有使用eax 除法会使用 eax,edx. 所以使用edx变相的相当于以及有了2^32次方了. 代入公式: 2^35 / (2 ^32 + M) = 34359738368 / (4294967296 + 613566757) = 34359738368 / 4908534053 = 6.9999999993888195604619552997935 = 商向上取整 (6.9999999993888195604619552997935) = 7 所以得出了除数为7 代码还原的时候直接还原成 Var_8 / 7 即可.如果想看原理,且向下看.
三丶代码还原总结
学习了新的两种定式: 第一种,被除数为正数, 除数为正数. MUL是无符号,所以不需要进行调整.直接套用公式还原
.text:0040101A mov eax, M
.text:00401023 mul x 此指令等价于 mul x,M
.text:00401027 shr edx, N还原公式 : (2^(32 +n)) / M = 2^n / M 最后结果向上取整. 第二种 被除数为正数 除数是特例 特征: 汇编中出现 乘 减 移 加 移
.text:0040101A mov ecx, [esp+10h+var_8]
.text:0040101E mov eax, M 设最大数为M
.text:00401023 mul ecx ecx = ecx * M
.text:00401025 sub ecx, edx
.text:00401027 shr ecx, N 设移位为N
.text:00401029 add ecx, edx
.text:0040102B shr ecx, N 设置移位为N
.text:0040102E mov [esp+10h+var_4], ecx还原方法: 2^(32 + N)/(2^32+M)的商向上取整 简化公式: 2^N / (2^32 + M) 一定注意隐藏的N大于32.