一种软件生成真随机数算法的设计和实现

时间：2015-12-21 01:45:33 所属分类：计算机技术 浏览量:

摘 要 本文提出了一种在软件上实现真随机数的方法，该方法根据计算机上的一些随机性事件，来生成一个由0和1组成的随机序列，然后对01序列进行进一步的随机处理，以进一步增强其随机性；根据这个01序列来生成所需要的随机数。基于这种设计方法，本文根据鼠标

摘 要 本文提出了一种在软件上实现真随机数的方法，该方法根据计算机上的一些随机性事件，来生成一个由0和1组成的随机序列，然后对01序列进行进一步的随机处理，以进一步增强其随机性；根据这个01序列来生成所需要的随机数。基于这种设计方法，本文根据鼠标在计算机屏幕上的随机曲线来生成01序列，然后使用线性同余法对其进行进一步处理。
关键词 真随机数；伪随机数；线性同余法；二元序列

1　引言
随机数在信息安全领域有着广泛的应用，比如各种安全认证协议，一次安全通信中使用到的会晤密钥，甚至软件产生RSA密钥对等，这些应用都会使用到随机数。特别是一些安全级别要求比较高的应用，对于随机数的质量提出了很高的要求。随机数的生成一般有两种方式，一种是硬件方式，一种是软件方式。一般情况下，硬件方式生成的随机数质量要好于软件方式生成的随机数。但是对于一般的用户来说，需要每位用户都配备一种硬件设备来生成随机数，这种方式可能不太现实。因此，通过软件方式来寻找高质量的随机数，这是一个很重要而且必要的课题。
2　基础知识
在密码学中，对于一个随机序列的定义如下：
(1) 看起来是随机的。
(2) 这个序列是不可预测的。
(3) 这个序列是不能重复产生的。
随机数生成器有真随机和伪随机之分。真随机数生成器满足以上所有的三点要求，伪随机数生成器只能满足以上的前两点要求。
软件生成随机数的一般方式如下：
(1) 确定一个数学模型或者算法。
(2) 设置一些参数的值。
(3) 按照规定的步骤和算法来生成第一个随机数。
(4) 然后在第一个随机数的基础上，来生成第二个随机数。重复同样的步骤，从而得到一个随机数序列。
很明显，这种软件方式生成的随机数是伪随机数序列。只要知道了其使用的算法和参数值，我们就可以生成同样的随机数序列。因此，真正的随机数是不可能通过具体的算法来生成的。
真正的随机数序列只能来源于随机事件，那么我们可以从计算机系统中存在的大量的随机事件中提取随机事件，经过正确的处理就有可能生成真正的随机数序列。比如，将用户的击键次数，鼠标的操作次数，CPU负载，网络数据包到达次数等随机信息放入到一个被称为“熵池”的缓存区中，“熵池”被均匀地搅拌。当需要取随机数时，我们就从“熵池”中读取随机数源。但是这种方式生成随机数的速度不够理想。
3　设计思想
在信息安全领域，我们经常遇到这样的情况：需要生成8个字节的随机数序列。那么我们可以把这8个字节的随机数序列当成由64个bit所组成的，每个bit位的取值为0或者1。如果我们使用投掷硬币的方式来决定每个bit位应该取0还是1，那么我们投掷64次硬币，就会得到一个由0或者1组成的随机数序列。这个0和1组成的随机数序列每8位组成一个字节，最终我们得到了要求的8个字节的随机数序列。像这种随机数序列的生成方式，它符合了密码学对于随机序列定义的3个特点，从而保证它是一个真正的随机数序列。但是，显而易见地，这种生成随机数序列的方式效率太低下了。
基于这种思想，我们可以利用计算机系统的随机性，提取出0和1组成的随机数序列，然后对这个0和1组成的随机数序列进行组合处理，从而最终得到质量很高的真随机数序列。
我们的算法思想可以总结为如下几步：
(1) 根据计算机系统中的随机事件，得到0和1组成的原始随机数序列。
(2) 对0和1组成的原始随机数序列进行某种处理，获得组合之后的由0和1组成的组合随机数序列。
(3) 继续进行类似于第二步的处理，进行多次的组合处理。
(4) 将最终得到的0和1随机数序列每8个bit组成一个字节，从而得到若干字节的随机数。
在这个设计方法中，关键的是第一步，随机事件的获取。只要能保证原始随机数序列是真正的随机事件生成的，即使我们不进行后续的组合处理，我们也可以得到真正的随机数序列。就好像我们通过投掷硬币来获得8字节的随机数一样。但是，由于计算时间或者计算机系统的精度等各方面的限制，长度很长的原始随机数序列不容易获得。所以，需要对获得的原始随机数序列进行数学上的处理，以便获得长度很长的随机数序列。
对于进一步的组合处理，我们要慎重的选择。如果选择的好，可以进一步的增加序列的随机性，从而可以降低对原始随机数序列采集的要求。但是，特别值得注意的是，如果选择的组合算法存在缺陷，反而有可能降低原始随机数序列的随机性。极端的情况是，比如组合算法生成的结果都是0组成的序列。
4　具体实现
我们选择这样的一种随机事件，当用户拿着鼠标在计算机屏幕上随意滑动时，鼠标滑动的轨迹组成的一条曲线是随机的。也就是说，即使同一个用户也不可能划出这样一条完全一致的曲线。这种方式很类似于我们投掷硬币的方式。就像古希腊一位哲人所说，人生不可能两次踏入同一条河流。
基于上述的随机事件的选择，我们在一定的时间内对这条曲线进行时间的抽样。如果要求生成N bit的01序列，那么我们就对这段曲线进行时间间隔为1/N的取样。这样，我们就会得到N个取样点，每个取样点用其在计算机屏幕上的坐标来表示。接着对每个取样点的横坐标和纵坐标进行相加，取不大于坐标和的最大整数。如果得到的整数是偶数，那么这个取样点就表示为0；如果得到的整数是奇数，那么这个取样点就表示为1。这样，我们最后得到了由0和1组成的随机数序列。假设，我们得到的随机数序列可以表示为：
Seed [i]，其中(i=0，1，…N-1)
然后，我们对得到的随机数序列进行进一步的处理，组成组合随机数生成器，从而进一步增强序列的随机性。
我们使用线性同余法对原始随机数序列进行进一步处理，从而得到新的组合随机数序列。我们使用线性同余法得到N个位于[0，N-1]之间的随机数，它可以表示为：
A [j]，其中(j=0，1，…N-1)，( A [j]的取值在[0，N-1]).
数组A [j]的含义如下：数组下标j表示组合后的随机数序列的第j个位置，数组的值A [j]表示组合后的随机数序列第j个位置的值从原始随机数序列Seed 中A [j]位置取值。
如果得到的随机数序列A [j] 没有重复值，也就是满足：A [j] = A [k]，当且仅当 j = k 。
那么得到的组合随机数序列为：
Seed [ A [0] ]，Seed [ A [1] ]，Seed [ A [2] ]，…Seed [ A [N-1] ].
如果得到的随机数序列A [j] 有重复值，比如A [6] = A [23] = N/2。
假设出现A [j] = A [k](j<k)，那么组合后的随机数序列的第k个位置暂时不做处理，继续下一个位置(k+1)的处理。到最后一个位置处理完毕后，我们把没有取过值的原始随机数重新组成一个序列Seed2，然后把这个序列Seed2中的值依次的填入组合后的随机数序列中没有处理的位置中。
这样，我们得到了组合后的随机数序列R，把每8个bit组成一个字节，结果就得到了我们需要的N/8 个字节的随机数。

在我们使用的线性同余法中，其参数设置如下：
Xi = (a Xi - 1) mod M，(1)
ξi = (Xi / M)*N，i = 1，2，3，.. (2)
其中，a为小于M 的正整数，从实际经验来看，当M =231 -1，a = 16 087 或630 360 016 时得到的随机数ξi的均匀性和独立性较好，因而得到广泛应用。
在这里我们选择M =231 -1，a = 16 087，X0由当时鼠标的位置来决定，取值为不大于坐标之和的最大整数。
这种实现方法首先保证了原始随机数序列的真正随机性，然后采用了线性同余法来打乱序列的排列，得到了组合的随机数序列。这种组合处理是增强了随机性，结果得到的随机序列具有优越的统计特性，其周期可以认为是无穷长的。
4.1　改进
以上的设计方法适合于特定的应用，来生成N字节的随机数。但是如果要求生成一个更长的随机数序列，那么就要对其做出一定的改进。一方面，我们可以取得更长时间范围内的鼠标曲线，来提高取样点的数目，得到一个数量更大的原始随机数序列。一方面，我们可以对组合的方法加以改进。
比如，我们希望得到长度为8N的随机数序列。首先我们得到长度为N的原始随机数序列，然后我们可以使用8组线性同余方法来得到8组组合随机数序列。每组线性同余法的初始化参数X0选择的不一样，它由当时的鼠标位置来决定。这样我们就根据长度为N的原始随机数序列得到了长度为8N的随机数序列。
4.2　试验数据分析
比如我们想得到长度为32字节的随机数，那么我们需要得到长度为256bit的0和1组成的随机数序列。经过鼠标曲线的抽样得到的随机序列如下：
0101010111010100001010100001110011100011110011110010000010000101101001011000010000110011101011010100110010111110111000101010101001001111101101001110111110011001110111110010101100100111001100011010101010010000100100000100111000010111101111001000100111010001

经过组合随机数发生器的运算，得到的最终随机数序列如下：X0 ＝1135。
0011001101000100011111111110001101110100011001000100000000100001000100010001111101111000100000100110100110001111001111110001000001011100101111010001110110100110101011101111110111001011010111111011000000010100100001110000000101101111001111010100010111011010
分析的依据是Golomb提出的二元序列的随机性假设。
游程分析：
游程为1个1的个数是：127 游程为1个0的个数是：129
游程为2个1的个数是：69 游程为2个0的个数是：70
游程为3个1的个数是：40 游程为3个0的个数是：39
游程为4个1的个数是：23 游程为4个0的个数是：19
游程为5个1的个数是：13 游程为5个0的个数是：12
游程为6个1的个数是：8 游程为6个0的个数是：7
游程为7个1的个数是：4 游程为7个0的个数是：4
游程为8个1的个数是：3 游程为8个0的个数是：1
序列的周期自相关函数的计算：
R1 = 0.085938 R2 = 0.058594 R3 = 0.031250
R4 = 0.105469 R5 = 0.031250 R6 = 0.042969
R7 = 0.007813
R8 = 0.003906 R9 = -0.085938 R10 = -0.003906
R11 = 0.062500
R12 = -0.003906 R13 = -0.023438 R14 = -0.035156
R15 = 0.031250
分析结果基本满足Golomb提出的0-1序列的第一条和第二条公理。由于将256作为序列的周期性，所以导致自相关函数值不同，但是可以肯定相关性是很小的。
５ 总结
本文提出了一种软件实现真随机数序列的思想，也就是从随机数的构成的基础01序列来实现真随机数序列。首先根据计算机上的随机性事件来生成01随机数序列，然后使用组合随机数序列发生器对01序列进行处理，从而得到更好的随机数序列。并且提出了通过鼠标的移动曲线来产生01随机数序列的方法，试验结果证明其随机性良好。关键的一点是，从理论上是无法重复生成同样的随机数序列的。
参考文献
[1]周燕. 关于一种新的随机数组合发生器的研究. 华北水利水电学院学报，2002，21(2)：75-77
[2]梁金千，张跃. 在计算机上产生真随机数的探讨. 计算机工程，2003，29(15)：176-177
[3]薛英花，吕述望，郭圣权.随机数发生器分析及其在安全信息系统中的应用. 计算机工程，2003，29(3)：42-44
[4]张传林，林立东. 伪－随机数发生器及其应用. 数值计算与计算机应用，2002年9月第3期：188-208

转载请注明来自：http://www.zazhifabiao.com/lunwen/gcjs/jsjjs/36247.html