【算法】通过逆向VC6的rand函数研究随机数算法

0xAA55

原帖：http://www.0xaa55.com/thread-785-1-1.html
版权所有(C) 2013-2014 技术宅的结界
转载请保留出处。

首先写一个用到rand函数的小程序。

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. int main(int argc,char**argv)
   
5. {
   
6.     printf("%d\n",rand());
   
7.     printf("%d\n",rand());
   
8.     printf("%d\n",rand());
   
9.     printf("%d\n",rand());
   
10.     printf("%d\n",rand());
    
11.     printf("%d\n",rand());
    
12.     printf("%d\n",rand());
    
13.     printf("%d\n",rand());
    
14.     printf("%d\n",rand());
    
15.     printf("%d\n",rand());
    
16.     printf("%d\n",rand());
    
17.     printf("%d\n",rand());
    
18.     printf("%d\n",rand());
    
19.     printf("%d\n",rand());
    
20.     printf("%d\n",rand());
    
21.     printf("%d\n",rand());
    
22.     return 0;
    
23. }

复制代码

然后编译，开始单步调试。
找到它调用rand函数的地方，继续单步运行，VC6提示找不到rand.c的时候不管，看反汇编。如下图所示。

可以看到这个rand函数很简单，就几条汇编指令。抄出来看，就是这个样子的：

1. push    ebp
   
2. mov     ebp,esp
   
3. mov     eax,[holdrand]
   
4. imul    eax,eax,343FDh
   
5. add     eax,269EC3h
   
6. mov     [holdrand],eax
   
7. mov     eax,[holdrand]
   
8. sar     eax,10h
   
9. and     eax,7FFFh
   
10. pop     ebp
    
11. ret

复制代码

其中，holdrand的初始值是1.
这样一看就简单了。我解释一下它的计算过程就是这样：
holdrand是随机数种子，乘以0x000343FD，加上0x00269EC3，得到的结果作为随机数种子存回holdrand，然后再把刚才得到的结果的高16位去掉最高位作为随机数返回。虽然是这么说的，但是holdrand真的就是随机数种子吗？我们来看看srand函数的反汇编。首先我们写一个简单的程序，然后编译它。

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. int main(int argc,char**argv)
   
5. {
   
6.     srand(0xAA55);
   
7.     printf("%d\n",rand());
   
8.     return 0;
   
9. }

复制代码

真是一目了然。holdrand就是随机数种子。srand的反汇编：

1. push    ebp
   
2. mov     ebp,esp
   
3. mov     eax,dword ptr[seed]
   
4. mov     [holdrand],eax
   
5. pop     ebp
   
6. ret

复制代码

它就是改写了holdrand。那么最终，我们还原出来的rand和srand的源码是这样写的：

1. int holdrand=1;
   
2. 
   
3. void srand(int seed)
   
4. {
   
5.     holdrand=seed;
   
6. }
   
7. 
   
8. int rand()
   
9. {
   
10.     holdrand=holdrand*0x000343FD+0x00269EC3;
    
11.     return(holdrand>>0x10)&0x7FFF;
    
12.     //反汇编看到它用的是SAR指令进行右移。但是既然结果只保留最低15位那么直接用>>运算符也是可以的。
    
13. }

复制代码

真是简单。这就是所谓随机数了吧。我们先验证一下，结果是不是和原始的rand、srand效果一样。

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. int myholdrand=1;
   
5. 
   
6. void mysrand(int seed)
   
7. {
   
8.     myholdrand=seed;
   
9. }
   
10. 
    
11. int myrand()
    
12. {
    
13.     myholdrand=myholdrand*0x000343FD+0x00269EC3;
    
14.     return(myholdrand>>0x10)&0x7FFF;
    
15. }
    
16. 
    
17. int main(int argc,char**argv)
    
18. {
    
19.     int i;
    
20. 
    
21.     fputs("Test1:\n",stdout);
    
22. 
    
23.     //测试1：不调用srand，看结果
    
24.     for(i=0;i<999999;i++)//试999999次
    
25.     {
    
26.         int iDifferent=rand()-myrand();
    
27.         if(iDifferent)
    
28.             printf("Different result:%d\n",iDifferent);
    
29.     }
    
30. 
    
31.    
    
32.     fputs("Test1 finished.\n"
    
33.         "Test2:\n",stdout);
    
34. 
    
35.     //测试2：调用一次srand然后看结果
    
36.     srand(0xAA55);
    
37.     mysrand(0xAA55);
    
38.    
    
39.     for(i=0;i<999999;i++)//试999999次
    
40.     {
    
41.         int iDifferent=rand()-myrand();
    
42.         if(iDifferent)
    
43.             printf("Different result:%d\n",iDifferent);
    
44.     }
    
45. 
    
46.     fputs("Test2 finished.\n",stdout);
    
47.     return 0;
    
48. }

复制代码

好！看来算法是正确的了。
现在的问题是：它真的是“随机数”吗？或者它真的能保证它产生0～32767之间数字的概率是相等的吗？
我们用这样的一份代码来做测试。

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. unsigned short NumGenerated[32768]={0};//数字出现的次数
   
5. 
   
6. int main(int argc,char**argv)
   
7. {
   
8.     int i;
   
9.     for(i=0;i<32768;i++)//测试32768次
   
10.         NumGenerated[rand()]++;//统计每个数字出现的次数
    
11.    
    
12.     for(i=0;i<32768;i++)
    
13.     {
    
14.         if(NumGenerated[i ]!=1)//如果不是1
    
15.             printf("Number %d appears %u times.\n",i,NumGenerated[i ]);
    
16.     }
    
17.     return 0;
    
18. }

复制代码

这样如果直接运行的话，有可能会产生超过一屏的结果，因此我们用rand>result.txt命令来运行它。


诶？怎么会……

诶？？
好像全部范围都出现过数字，有重复的，也有没出现过的。。
我测试过，如果测试次数是16777216，那么0到32767之间所有数字都出现过至少一次，没有0出现。有图为证。

重新写了代码：

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. unsigned short NumGenerated[32768]={0};
   
5. 
   
6. int main(int argc,char**argv)
   
7. {
   
8.     int i;
   
9.     unsigned short Min=-1,Max=0,MinV,MaxV;
   
10. 
    
11.     for(i=0;i<16777216;i++)//测试16777216次
    
12.         NumGenerated[rand()]++;//统计每个数字出现的次数
    
13.    
    
14. 
    
15.     for(i=0;i<32768;i++)
    
16.     {
    
17.         printf("Number %d appears %u times.\n",i,NumGenerated[i ]);
    
18.         if(NumGenerated[i ]>Max)
    
19.         {
    
20.             Max=NumGenerated[i ];
    
21.             MinV=i;
    
22.         }
    
23.         if(NumGenerated[i ]<Min)
    
24.         {
    
25.             Min=NumGenerated[i ];
    
26.             MaxV=i;
    
27.         }
    
28.     }
    
29.     printf( "Min: Number %d appears %u times.\n"
    
30.             "Max: Number %d appears %u times.\n",MinV,Min,MaxV,Max);
    
31.     return 0;
    
32. }

复制代码

然后再运行rand>result.txt命令，看result.txt的结果，基本上每个数字都出现了大约450次到550次之间。


出现次数最少的数字是31509，出现了418次
出现次数最多的数字是16291，出现了618次
从以上结果看出来，这个随机数还真是不够随机呀。。

噗叽

{:soso_e113:}233看起来此站不算太火哦＝ｗ＝
这么久没人回...

已扣除一个宅币

跪拜

（他说要10个字节才能发送呢，那用的是UTF-8吧）

0xAA55

已扣除一个宅币 发表于 2014-9-8 11:53
跪拜

（他说要10个字节才能发送呢，那用的是UTF-8吧）

没错，就是UTF-8

已扣除一个宅币

0xAA55 发表于 2014-9-8 20:11
没错，就是UTF-8

UTF8 ->(1110 xxxx  10xx xxxx 10xxx xxxxx)
（为了防止装逼失败，瞅了一样源代码）