基于鼠标移动轨迹的真随机数产生方法
胡亮;裴莹;初剑峰;袁巍;王文博;樊丽;刘建男
【摘 要】This article implements the algorithm of using a random event-the mou movement tracks to produce real random numbers. Compared with the usual random-number-producing algorithm bad on mou, this one enjoys a higher randomicity in the process of sampling and getting original data. In addition, it does not need the extra circuit or facilities that other physical process, the algorithms producing real random number. As a result, its costs will be reduced and the problem of a high expan to produce real random numbers will be solved. The result of testing the uniformity and independence of the random numbers generated shows that the numbers produced by this algorithm have a fine statistical property. Moreover, the result of testing its program execution time proves that its time expending is very short.%给出一种运用计算机中鼠标移动轨迹这一随机事件产生真随机数的算法,与传统基于鼠标的随机数生成算法相比,在采样原始数据过程中,该方法得到的数据随机性更高,与其他用物理过程产生真随机数的算法相比,
不用接额外的电路和设备,成本较低,从而解决了产生真随机数开销过大的问题.通过对产生的随机数进行均匀性和独立性检验,结果表明该方法所产生的随机数具有较好的统计性质；同时测试该方法的程序执行时间结果表明,该方法时间开销较小.
【期刊名称】《吉林大学学报（理学版）》
【年(卷),期】2011(049)005
【总页数】5页(P890-894)
【关键词】随机数;伪随机数;鼠标移动轨迹锦上添花是什么意思
【作 者】胡亮;裴莹;初剑峰;袁巍;王文博;樊丽;刘建男
【作者单位】吉林大学计算机科学与技术学院,长春130012;吉林大学计算机科学与技术学院,长春130012;吉林大学计算机科学与技术学院,长春130012;吉林大学计算机科学与技术学院,长春130012;吉林大学计算机科学与技术学院,长春130012;吉林大学计算机科学与技术学院,长春130012;吉林大学计算机科学与技术学院,长春130012
【正文语种】中 文
【中图分类】TP391
随机数在网络环境中应用广泛, 如服务器之间或服务器与路由器在建立TCP连接时生成的TCP序列号、 对称加密算法中会话双方会话密钥的产生[1]以及RSA公钥加密算法中密钥的产生等. 此外, 在一些安全协议和数字签名算法中也用到了随机数. 这些应用对随机数的产生提出了3个不同的要求[2]： 1) 序列是随机的, 没有规律可循. 随机序列应具有如下统计特性: ① 分布一致性： 序列中的随机数分布是一致的, 即出现频率大约相等； ② 独立性： 序列中任何数不能由其他数推导出; 2) 序列是不可预测的. 3) 要重复产生该序列是不可能的.
满足1),2)要求的随机数称为伪随机数, 而真随机数需要满足1)～3). 例如投掷硬币, 每次投掷都可能产生两种结果： 正面向上或向下, 它们的概率均为1/2. 投掷结果没有规律可循, 不能准确预测下一次投掷结果, 两次投掷产生完全相同随机序列的可能性也极小. 如果把正面向上的结果赋值为1, 正面向下的结果赋值为0, 产生的0,1序列即为真随机序列. 显然, 用投掷硬币方法产生的随机数是绝对随机的, 而在计算机上几乎无法实现. 通常在计算机上使用的随机数产生方法(e.g.rand()), 所产生的序列都是伪随机的. 如令函数rand()的种子固定不变,
则其每次产生的序列都相同.
一般真随机数发生器(TRNG)都以一种称为熵源的不确定性源为基础, 如放射性衰变、 电子设备的热噪音、 宇宙射线的出发时间等[3], 而伪随机数发生器(PRNG)则利用种子, 采用某种固定的算法产生类似于随机数序列的方法[4]. 显然, 真随机数发生器的安全性比伪随机数发生器的安全性高很多, 当安全级别较高时一般都采用TRNG. 但要产生真随机数一般需要在计算机上连接额外辅助的电路和仪器[5-6]. 操作繁琐且成本也较高. 而伪随机数的产生相对成本较低, 但安全性也低, 只有通过统计随机性检验, 才可以应用到网络安全体系中.
1 预备知识
密码学意义上安全的随机数比一般的随机数要求更高, 一般要求通过统计随机性测验, 通常运用均匀性检验和独立性检验进行随机统计性测验[5].
1.1 均匀性检验
均匀性检验[7]用于检验由某个发生器产生的随机序列是否均匀地分布在[0,1]区间上, 即检验经验频率与理论频率的差异是否显著. 常用的方法有χ2检验、 K-S检验和序列检验, 本文分解的英文
采用χ2检验, 过程如下：
1) 用随机数发生器产生随机序列{rn};
2) 将[0,1]区间分成10等份, 统计{rn}落在第i个小区间的个数ni(i=1,2,…,10);
3) 计算统计量的值, V渐近服从χ2(9)分布；
4) 给定显著水平α, 查χ2表得到临界值λ. 如果V≤λ, 则检验通过, 即认为产生的随机数均匀分布在[0,1]区间内. 否则, 检验不通过.
1.2 独立性检验
独立性检验[7]主要检验随机序列r1,r2,…,rn间的统计相关性是否显著. 试验中选取相关系数检验Ⅱ的方法. 过程如下：
郭裕禄1) 用随机数发生器产生随机序列{rn}；
2) 计算 其中k=(i+j)mod n;
3) 计算渐近服从标准正态分布；
4) 给定显著水平α, 查标准正态分布表得λ, 如果|Tj|≤λ(j=1,2,…,n), 则检验通过, 即认为产生的随机数之间统计相关性显著. 否则, 检验不通过.
2 满足正态分布的伪随机数产生算法绍的组词
高斯分布也称为正态分布或常态分布. 对于随机变量X, 其高斯分布记为N(μ,σ2), 其中μ和σ2为分布参数, 分别为高斯分布的期望和方差[8]. 特别地, 当μ=0, σ2=1时, X的分布为标准正态分布. 高斯分布概率密度函数为：
简介英语本文用二次产生法产生近似正态分布的随机数[9], 过程如下：
1) 用线性同余法产生随机数: u(i)=b·u(i-1)(mod M1), k(i)=4·u(i)+5;
2) 以k(i)做乘子, 用混合同余法产生一个随机数: vi(j)=k(i)·vi(j-1)+c(mod M2);
救生锤
3) 用近似抽样法变换成随机数:
x(i)即为第i次产生的随机数. 选定初值u(0),b,M1,vl(0),c和M2, 且当i>1时, 取vi(0)=vi-1(l), 利用上述方法可递推产生x(i), 易证x(i)在理论上近似服从标准正态分布. 因此, 该方法产生的随机数只能称为伪随机的. 若将这种方法产生的伪随机数应用到网络安全中, 必须通过统计随机性检验.
3 基于鼠标运行轨迹的真随机数产生算法模型
3.1 算法原理
由于鼠标运行轨迹具有随机性和不确定性的特点, 即同一个人两次对鼠标的操作轨迹完全相同的可能性很小. 但同一个人两次对鼠标的操作具有相似性, 为了避免这种相似性, 必须对初始鼠标轨迹做预处理, 基于鼠标移动轨迹的性质和预处理过程, 本文把鼠标运行轨迹作为获得随机数的熵源[10].
3.2 算法整体过程描述
假设需要的二元随机序列长度为n.
1) 根据需要采样鼠标坐标数据. 在鼠标移动时采样鼠标坐标(x,y), 将一系列坐标值保存在二维数组R[N][2]中, R[i][0]保存横坐标, R[i][1]保存纵坐标(i=0,1,…,N-1).
2) 对已经获得的坐标进行再处理, 使其消除相似性. ① 用rand()函数产生N个随机数; ② 将产生的N个随机数, 映射到[0,N-1]区间内, 存放在数组S[N]中; ③ 去掉S[N]中的重复数据, 产生N个没有重复的并且在[0,N-1]区间内的数据; ④ 将R[i][0]按照S[N]重新排序(i=0,1,…,N-1).
3) 对随机排好序的坐标值进行操作, 从而获得一系列的随机数.
3.3 捕获原始数据
每当鼠标移动时就捕获鼠标的坐标值, 直到捕获到的鼠标坐标数量达到要求为止.
精神文明3.4 对初始鼠标坐标值的再处理
为了消除两次鼠标运行轨迹的相似性, 需要对初始的坐标值进行再处理. 本文主要是将得到的横坐标序列随机打乱顺序, 即产生N个在[0,1]区间内没有重复的随机整数序列, 存放在数组S[N]中, 并将产生的初始横坐标序列按照数组S[N]中的值改变顺序, 即初始横坐标序列中第一个位置的数被第S[0]位置的数代替, 第二个位置的数被第S[1]位置的数代替, 以此类推.
3.4.1 产生[0,N-1]区间内随机数序列的方法 产生随机数步骤如下：
1) 用当前系统的时间作种子, 使用rand()函数产生任意N个随机数, 存放在中间数组S[N]中. 此时的数据在0x7fff范围内, 还不能满足要求.
2) 将产生的N个随机数对应到[0,N-1]区间内. 不用rand()%N直接产生[0,N-1]区间内的数, 假设有两个数10和22, 要产生0～3之间的数. 10%3=22%3=1, 破坏了数据的随机性. 本文采用的方法用s[i]=⎣表示.
此外, 如果经过四舍五入计算后S[i]=N, 则令S[i]=N-1, 从而获得了N个在[0,N-1]区间内的数. 虽然[0,N-1]区间内的数已经产生, 但不能保证他们完全没有重复, 需要去掉重复的数字, 最后得到S[N].
3.4.2 对初始横坐标序列按S[N]中的数据重新排序 本文按已经产生的S[N]中的数据对存放在R[N][0]中的初始横坐标序列进行重新排序, 即R[0][0]用R[s[0]][0]代替,R[1][0]用R[s[1]][0]代替,…,R[N-1][0]用R[s[N-1]][0]代替.
至此, 已完成了对捕获坐标序列的再处理, 下面将坐标中的二维数据转换为一维数据, 以获
得一系列的随机数.
