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

0xAA55 发表于 2014-8-13 15:10:33

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

首先写一个用到rand函数的小程序。#include<stdio.h>
#include<stdlib.h>

int main(int argc,char**argv)
{
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
printf("%d\n",rand());
return 0;
}
然后编译，开始单步调试。
找到它调用rand函数的地方，继续单步运行，VC6提示找不到rand.c的时候不管，看反汇编。如下图所示。

可以看到这个rand函数很简单，就几条汇编指令。抄出来看，就是这个样子的：push ebp
mov ebp,esp
mov eax,
imul eax,eax,343FDh
add eax,269EC3h
mov ,eax
mov eax,
sar eax,10h
and eax,7FFFh
pop ebp
ret其中，holdrand的初始值是1.
这样一看就简单了。我解释一下它的计算过程就是这样：
holdrand是随机数种子，乘以0x000343FD，加上0x00269EC3，得到的结果作为随机数种子存回holdrand，然后再把刚才得到的结果的高16位去掉最高位作为随机数返回。虽然是这么说的，但是holdrand真的就是随机数种子吗？我们来看看srand函数的反汇编。首先我们写一个简单的程序，然后编译它。#include<stdio.h>
#include<stdlib.h>

int main(int argc,char**argv)
{
srand(0xAA55);
printf("%d\n",rand());
return 0;
}
真是一目了然。holdrand就是随机数种子。srand的反汇编：push ebp
mov ebp,esp
mov eax,dword ptr
mov ,eax
pop ebp
ret它就是改写了holdrand。那么最终，我们还原出来的rand和srand的源码是这样写的：int holdrand=1;

void srand(int seed)
{
holdrand=seed;
}

int rand()
{
holdrand=holdrand*0x000343FD+0x00269EC3;
return(holdrand>>0x10)&0x7FFF;
//反汇编看到它用的是SAR指令进行右移。但是既然结果只保留最低15位那么直接用>>运算符也是可以的。
}真是简单。这就是所谓随机数了吧。我们先验证一下，结果是不是和原始的rand、srand效果一样。#include<stdio.h>
#include<stdlib.h>

int myholdrand=1;

void mysrand(int seed)
{
myholdrand=seed;
}

int myrand()
{
myholdrand=myholdrand*0x000343FD+0x00269EC3;
return(myholdrand>>0x10)&0x7FFF;
}

int main(int argc,char**argv)
{
int i;

fputs("Test1:\n",stdout);

//测试1：不调用srand，看结果
for(i=0;i<999999;i++)//试999999次
{
   int iDifferent=rand()-myrand();
   if(iDifferent)
         printf("Different result:%d\n",iDifferent);
}

fputs("Test1 finished.\n"
   "Test2:\n",stdout);

//测试2：调用一次srand然后看结果
srand(0xAA55);
mysrand(0xAA55);

for(i=0;i<999999;i++)//试999999次
{
   int iDifferent=rand()-myrand();
   if(iDifferent)
         printf("Different result:%d\n",iDifferent);
}

fputs("Test2 finished.\n",stdout);
return 0;
}
好！看来算法是正确的了。
现在的问题是：它真的是“随机数”吗？或者它真的能保证它产生0～32767之间数字的概率是相等的吗？
我们用这样的一份代码来做测试。#include<stdio.h>
#include<stdlib.h>

unsigned short NumGenerated={0};//数字出现的次数

int main(int argc,char**argv)
{
int i;
for(i=0;i<32768;i++)//测试32768次
   NumGenerated++;//统计每个数字出现的次数

for(i=0;i<32768;i++)
{
   if(NumGenerated!=1)//如果不是1
         printf("Number %d appears %u times.\n",i,NumGenerated);
}
return 0;
}这样如果直接运行的话，有可能会产生超过一屏的结果，因此我们用rand>result.txt命令来运行它。

诶？怎么会……

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

重新写了代码：#include<stdio.h>
#include<stdlib.h>

unsigned short NumGenerated={0};

int main(int argc,char**argv)
{
int i;
unsigned short Min=-1,Max=0,MinV,MaxV;

for(i=0;i<16777216;i++)//测试16777216次
   NumGenerated++;//统计每个数字出现的次数

for(i=0;i<32768;i++)
{
   printf("Number %d appears %u times.\n",i,NumGenerated);
   if(NumGenerated>Max)
   {
         Max=NumGenerated;
         MinV=i;
   }
   if(NumGenerated<Min)
   {
         Min=NumGenerated;
         MaxV=i;
   }
}
printf( "Min: Number %d appears %u times.\n"
         "Max: Number %d appears %u times.\n",MinV,Min,MaxV,Max);
return 0;
}然后再运行rand>result.txt命令，看result.txt的结果，基本上每个数字都出现了大约450次到550次之间。

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

噗叽发表于 2014-8-20 09:18:51

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

已扣除一个宅币 发表于 2014-9-8 19:53:24

跪拜

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

0xAA55 发表于 2014-9-8 20:11:17

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

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

没错，就是UTF-8

已扣除一个宅币 发表于 2014-9-8 20:22:55

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

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

页: [1]

技术宅的结界's Archiver

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