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

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

摘要本文提出了一种在软件上实现真随机数的方法，该方法根据计算机上的一些随机性事件，来生成一个由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具体实现

我们选择这样的一种随机事件，当用户拿着鼠标在计算机屏幕上随意滑动时，鼠标滑动的轨迹组成的一条曲线是随机的。也就是说，即使同一个用户也不可能划出这样一条完全一致的曲线。这种方式很类似于我们投掷硬币的方式。就像古希腊一位哲人所说，人生不可能两次踏入同一条河流。

基于上述的随机事件的选择，我们在一定的时间内对这条曲线进行时间的抽样。如果要求生成Nbit的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个位置暂时不做处理，继续下一个位