“序列数交换法”是将有规律的数组,通过任意交换数组的序列号,而形成随机数的方法。
理论根据是热力学第二定理的推论“熵增加原理”,在自然作用下,从有序到无序是不可逆过程。例如你整天洗纸牌,也不可能有一天发现是一顺的了。墨水滴到水盆里会逐渐扩散,如果你搅动则会加速扩散,再也没有机会聚成一滴了。
“序列数交换法”的物理模型可以是这样的。将有规律的数组,例如载体可以是大小一样颜色不同的小球,不同颜色代表不同的元素,放到一个滚筒里,滚动均匀,然后一个个拿出来排列,就得到了新次序下的随机数组。
现在我们用计算机来模拟这个过程。以ASCII码组成的数组为例(这在计算机是最基础的,以字节为单位),我们的元素是 0 ~ 255 的数字,共有 256个。
例如造一个有2560个元素的随机数列:
1) 先做一个数值由零到255的循环数列,长度为2560(现在数组周期为256),
2) 随机抽取两的序号使它们的数值交换,
3) 使 2)进行足够多次,检测其效果,直到满意为止。
下面用 C++语言来实现。只写出关键部分。
#define NN 2560 //数组长度
unsigned int k;
unsigned char *str; //定义数组指针
unsigned char ch;
unsigned int n1=0;
str = new unsigned char[NN+1]; //借用内存
for(k=0;k<NN;k++) str[k]=k%256; //形成序列数组
srand(GetTickCount()); //用运行时间做rand()函数的种子
for(k=0;k<NN;k++)
{
n1=(rand()+k)%NN; //随机生成序号以便交换
if(n1==k) goto xia; //序号相同不处理
else
{
ch=str[n1]; //数值交换
str[n1]=str[k];
str[k]=ch;
}
xia: ;
}
delete [] str; //退还内存
以上程序,借助一个随机函数 rand() 来完成挑选交换目标序号的工作,rand() 实际也对应序号从0到NN-1的数组,只不过表现形式比较怪异,我们称此数组为“捡选数组”。此段程序将有序的数组str[]从头到尾处理了一遍。形象的说就是处理了一次或搅动了一次。如果选择的随机函数比较优秀,一次搅动,可以使数组具有随机数组的统计特性,如果用几个好的随机函数,多做几次可能效果更好。如果随机函数不好,多次也能达到目的。
试验证明随机函数在这里不是必需的。用开始形成的序列数组str[]取代rand()作为“捡选数组”,以后每次用上次生成的str[]数组作为“捡选数组”,这样经过许多遍处理后也可以形成真随机数组,过程比较缓慢,是个逐渐打乱次序的过程,可以观察到随着搅动次数的增加从序号小的地方开始逐步由规律排列到不规律排列,变成乱码后,又由有周期的乱码向无周期变化。这种自我激励的变化也从一个侧面印证了“熵增加原理”,说明不管用什么方法有序到无序是不可逆转的。但是使用随机函数可以大大加快进程,尤其是好的随机函数,差一些的效率要降低。随机函数只是个工具,真正起作用的是“熵增加原理”。上述正反馈式的自我激励处理过程,简称自激处理,还有其它用途,当借助随机函数的搅动进行到一定程度时,用此方式来扫尾,可以消除随机函数本身处理的痕迹,并可源源不断的产生新的真随机数组。
如何检测随机数质量。这里是根据随机数组的统计特性来检验它。方法众多仅举一例:
unsigned int n2=0;
for(k=0;k<NN;k++)
{
if(str[k]==(k%256)) n2++;
}
我们知道,元素在特定的位置有 256种可能,所以某元素出现的概率是1/256,元素总数2560乘1/256等于10,当n2接近10时即可,就是再继续搅动,n2将在10 附近震荡,说明均匀度已经饱和。对于真随机数组来说,再多搅性质是不会改变的,只是做无用功罢了。
真随机数组的一大特点是不能重复出现,现在如何保证呢。因为 1)使用了以时间为种子的随机函数,2)过程结束是靠判断自动完成的。由于系统是多任务系统,同样的运算需要的时间是不同的,这和计算机状态相关,而运行时间又和随机函数种子的数值相关,微小的差异就可以使结果不同,自动完成则搅动的次数就是不确定的,所以完成随机数组的建造过程是不可复现的。
真随机数组虽然用处很大,但是对普通加密真随机数并不一定便于应用,还是自己控制随机函数种子好些,只要你加入些不确定因素即可,你可以使用密码来控制种子的数值,而密码是运行后输入的,根本不出现在没有运行的程序里,这样对你来说数组是伪随机数组,而这个数组跟搅动的随机函数没有直接关系,但在破解者那里就是真随机数组了,这样的随机数组可以称为单向真随机数组吧,也是做不出来的。
随机数发生器一例
http://download.csdn.net/down/160961