首页
论坛
课程
招聘
[讨论]奇偶判断的逆向
2012-7-6 09:31 6304

[讨论]奇偶判断的逆向

2012-7-6 09:31
6304
以下类似代码是我们常用的:
if (n % 2)
          printf("Odd");
else
          printf("Even");


先来看一下VC6中Debug版的汇编代码:
[QUOTE][/QUOTE]
10:       if (n % 2)
; 把n的值放入ecx中
00401039   mov         ecx,dword ptr [ebp-4]
; 80000001h十进制为10000000000000000000000000000001,与其余运算即保留n的末位和符号位
0040103C   and         ecx,80000001h
; 如果n不是负数就直接跳到00401049的检测,如果n是负数下面特殊处理
00401042   jns         main+39h (00401049)
00401044   dec         ecx
; VC上写的是0FEh,其实是0FFFFFFFEh,不知为何。
; 即与11111111111111111111111111111110进行与运算,即把前31位设置为1:
00401045   or          ecx,0FEh
; 再加上1
00401048   inc         ecx
; 检测ecx是否为0,为0则跳转打印Even否则打印Odd
00401049   test        ecx,ecx
; je(jump if zero or equal)
0040104B   je          main+4Ch (0040105c)
11:           printf("Odd");
0040104D   push        offset string "Odd" (00425028)
00401052   call        printf (004010b0)
00401057   add         esp,4
12:       else
0040105A   jmp         main+59h (00401069)
13:           printf("Even");
0040105C   push        offset string "Even" (00425020)
00401061   call        printf (004010b0)
00401066   add         esp,4


代码不是很好理解,首先考虑n为正数的情况,不难知道,偶数的二进制末位为0,奇数的二进制末位为1,解释如下:
设某二进制数为......a5a4a3a2a1a0,则二进制数转为十进制数为:
a0*2^0 + a1*2^1 +a2*2^2……
单看系数,得到一个数列:
1 2 4 8 16
可以看到除了数列首项因为是2^0是1,是奇数,后面的项由于都是2^n(n>=1, N∈Z),所以都是偶数。
而偶数+偶数=偶数,偶数+奇数=奇数(设偶数为2n,奇数为2n+1,n∈Z,不难证明,这里略)。
所以偶数的二进制末位为0,奇数的二进制末位为1。

由于n是正数,所以符号位为0,与80000001h后只剩下了最后一位,其值要么为0要么为1,所以通过判断其减1后的值是否等于0可以知道它的奇偶性。

现在来看当n是负数时的情况,举两个例子,-3和-6:
-3的补码二进制表示为:
11111111111111111111111111111101
与与80000001h后保留了最后一位和符号位:
10000000000000000000000000000001
然后减1得:
10000000000000000000000000000000

11111111111111111111111111111110
得:
11111111111111111111111111111110
然后再加1得:
11111111111111111111111111111111
而11111111111111111111111111111111不等于0,所以之后用test ecx, ecx和je判断ecx得出结果不为0,打印Odd。

-6的补码二进制表示为:
11111111111111111111111111111010
与与80000001h后保留了最后一位和符号位:
10000000000000000000000000000000
然后减1得:
01111111111111111111111111111111

11111111111111111111111111111110
得:
11111111111111111111111111111111
然后再加1得:
10000000000000000000000000000000
超出32位,首位截去,结果得0:
0000000000000000000000000000000
而后用test ecx, ecx和je判断ecx是否得0,这里得0,打印Even。

可见,负数的奇偶性判断,都是利用偶数末位为0,奇数末位为1的特征以及利用
11111111111111111111111111111110的或运算,通过是否进位而忽略首位来判断奇偶性。

注意
if (n % 2)如果写成if (n % 2 == 1)就不能正确检测负数的奇偶性了,想想为什么。

VC6中的Release版和Debug版无甚区别,只是把test删除,直接通过前面运算结果对标志位的影响来判断是否跳转,这里不再赘述。
总结:
mov         ecx,dword ptr [ebp-4]
and         ecx,80000001h
jns         main+39h (00401049)
dec         ecx
or          ecx,0FEh
inc         ecx
jz          main+4Ch (0040105c)
; 跳转成功为偶数,否则为奇数
以后遇到这样的代码块时,就可以确认这是通过%2在判断整数的奇偶性,以还原为高级代码。

【公告】【iPhone 13、ipad、iWatch】11月15日中午12:00,看雪·众安 2021 KCTF秋季赛 正式开赛【攻击篇】!!!文末有惊喜~

收藏
点赞0
打赏
分享
最新回复 (1)
雪    币: 39
活跃值: 活跃值 (10)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
MDebug 活跃值 2012-7-6 09:37
2
0
分析的不错。。
游客
登录 | 注册 方可回帖
返回