【算法】通过逆向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,[holdrand]
imul eax,eax,343FDh
add eax,269EC3h
mov [holdrand],eax
mov eax,[holdrand]
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[seed]
mov [holdrand],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[32768]={0};//数字出现的次数
int main(int argc,char**argv)
{
int i;
for(i=0;i<32768;i++)//测试32768次
NumGenerated[rand()]++;//统计每个数字出现的次数
for(i=0;i<32768;i++)
{
if(NumGenerated[i ]!=1)//如果不是1
printf("Number %d appears %u times.\n",i,NumGenerated[i ]);
}
return 0;
}

复制代码

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

诶？怎么会……

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

重新写了代码：

#include<stdio.h>
#include<stdlib.h>
unsigned short NumGenerated[32768]={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[rand()]++;//统计每个数字出现的次数
for(i=0;i<32768;i++)
{
printf("Number %d appears %u times.\n",i,NumGenerated[i ]);
if(NumGenerated[i ]>Max)
{
Max=NumGenerated[i ];
MinV=i;
}
if(NumGenerated[i ]<Min)
{
Min=NumGenerated[i ];
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 xxxx 10xx xxxx 10xxx xxxxx)
（为了防止装逼失败，瞅了一样源代码）

账号		自动登录	找回密码
密码			立即注册→加入我们

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

欢迎访问技术宅的结界，请注册或者登录吧。

相关帖子