毕业设计（论文）简述大随机数生成程序的开发与测试.doc

简述大随机数生成程序的开发与测试摘要大随机数已经在当今社会的各个领域中都频繁使用，特别是在加密技术中已经成了不可缺少的一部分，像RSA，MD5中随机数成为加密技术的关键。本设计主要为第3代移动通信系统（3G）提供符合要求的随机数（1024位），首先取得系统时间和RAND（）函数所产生的随机数作为最初的随机初值，经过三重DES（两密钥通过MD5算法得来）和异或的变换，保证其随机数的足够随机，然后通过16次的循环得到一个组合起来的1024位随机数，设计还提供一个检验随机数是否随机的平台，采用了均匀性检测，即频率检测的方法检测随机数的随机性，通过检测发现，所产生的随机数能够达到我们所期望的随机性。设计还对常见的随机数的生成方法进行了检析，提供多种随机数的生成方法，并且也提供了多种随机数的检测方法供大家参考，希望对大家有所帮助。关键字：随机数；RSA；MD5；加密技术；均匀性检测Big Random Number Generator Algorithm Research and ImplementAbstractThe big random number is used everywhere in modern society especially in the encryption technology. The random number is the key technology of the encryption.This design mainly provides the request random number (1024) for 3rd Generation of mobile communication system. The way to provide the number is discussed in this article, and the Randomness test is discussed too. There are many ways to finish the task which are shown in this paper. We hope these techniques can be useful. Key words: Random number; RSA; MD5; Encryption technology; Even line of examination目 录论文总页数： 19页1 引言11.1随机数的概念11.2课题背景11.3 国内外研究现状11.4 本课题研究的意义11.5 本课题的研究方法12常见随机数生成方法简析22.1 迭代取中法22.2 乘同余法22.3 混同于法22.4 反变换法32.4.1 平均分布 :32.4.2 指数分布 :42.4.3 正态分布随机变量的生成 :42.5 离散型随机变量43随机数的检验54 大随机数产生的机理64.1 流程图64.2 DES算法简介75 算法实现86 检验随机数137 系统测试14结 论16参考文献17致 谢18声 明191 引言1.1随机数的概念在现今的计算机中所产生的随机数，都是伪随机数。即，可以通过一定手段和方法发现或破译其中的规律。真随机数，也有了一定的研究，比如：通过声音或原子衰变等所产生的随机数。伪随机数可以通过一定的数学算法，近似真随机数但仍然不是真随机数。1.2课题背景随机数已经在当今社会的各个领域中都频繁使用，特别是在加密技术中已经成了不可缺少的一部分，甚至很多加密技术的保密程度就取决于随机数。像RSA，MD5需求大量随机数的密码技术正需求一个好的随机数发生器的产生。如今很多随机数产生器已经存在，但那些都存在很多的不足，比如产生的随机数位数不够，不是足够随机等等问题，所以编制一个能够产生我们需要足够大的且足够随机的随机数的随机数产生器就变得很重要。1.3 国内外研究现状通过查阅质料和在网上了解，国外对随机数的研究领先于国人对随机数的研究，但是总体来说对随机数的研究都还不够深入与透彻，都还不能脱离伪随机数的阴影，但的确目前的技术支持与环境配置等方面都还制约着我们大多数只能在研究伪随机数的层面，我们只可能的尽量地做到无限接近真随机数，而不能达到真正的随机。特别在随机数的检测这方面，虽然检测的方法很多，但是都不够完善，没有一个很公用很全面的检测方法诞生，所以在随机数的研究中还有很深的东西需要我们去挖掘。1.4 本课题研究的意义保证我们能够很快速的得到需要的随机数，而且随机数能够足够大足够随机，尽量能够实用在需要用到随机数的任何地方，特别是在科研领域，比如第3代移动通信系统（3G）中需要的1024随机数，就能满足它的要求，我们所要做的就是使产生的随机数尽量的靠近真随机数。1.5 本课题的研究方法工作任务：1.大致了解随机数产生器的发展过程和现阶段的大概情况，认识现阶段随机数产生器的产生方式和所用到的知识，结构体系是怎样的。2.分析他们的优点和缺点，能够保留的优点就要尽量用到，如果有不足应该怎样改正，加上自己的理解和题目的要求做一个满意的随机数产生器。要求： 使用VC+平台，编写一个能产生1024位的随机数发生器，而且随机数还要是足够随机的，并且还要编制一个检验平台，能在该平台上检验该随机数是足够随机的。设计思路：采用VC+6.01使用VC+实现控件的开发与界面的设计，尽量使外观简单容易实用，输出结果方便易看2借鉴其他随机数产生器的产生方法，参阅AES，DES中随机数的产生方法，借鉴出其中的精华，补上自己的构思与想法尽量使随机数不出现重复。2常见随机数生成方法简析2.1 迭代取中法这里在迭代取中法中介绍平方取中法 , 其迭代式如下 : Xn+1=(Xn2/10s)(mod 102s) Rn+1=Xn+1/102s 其中， Xn+1 是迭代算子，而 Rn+1 则是每次需要产生的随机数。 第一个式子表示的是将 Xn 平方后右移 s 位，并截右端的 2s 位。 而第二个式子则是将截尾后的数字再压缩 2s 倍，显然 :0=<Rn+1<=1. 迭代取中法有一个不良的性就是它比较容易退化成 0。2.2 乘同余法乘同余法的迭代式如下 : Xn+1=Lamda*Xn(mod M)   (Lamda 即参数 ) Rn+1=Xn/M 各参数意义及各步的作用可参 2.1。当然，这里的参数的选取至关重要。 经过前人检验的两组性能较好的素数取模乘同余法迭代式的系数为 : 1 ）    lamda=55,M=235-31 2 ）    lamda=75,M=231-12.3 混同于法 混合同余法是加同余法和乘同余法的混合形式 , 其迭代式如下 : Xn+1=( Lamda*Xn+C )%M Rn+1=Xn/M 经前人研究表明，在 M=2q 的条件下，参数 lamda,miu,X0 按如下选取，周期较大，概率统计特性好 : Lamda=2b+1,b 取 q/2 附近的数 C=(1/2+sqrt(3)/M X0 为任意非负整数 它的一个致命的弱点，那就是随机数的生成在某一周期内成线性增长的趋势，显然，在大多数场合，这种极富“规律”型的随机数是不应当使用的。实现 : 1 double   _random( void ) 2 3 int   a; 4 double   r; 5 6 a = rand() % 32767 ; 7 r = (a + 0.00 ) / 32767.00 ; 8 9 return   r; 10 11 2.4 反变换法它首先需要使用均匀分布获得一个 (0,1) 间随机数 , 这个随机数相当于原概率分布的 Y 值 , 因为我们现在是反过来求 X. 哎 , 听糊涂了也没关系 , 只要知道算法怎么执行的就行 . 采用概率积分变换原理 , 对于随机变量 X 的分布函数 F(X) 可以求其反函数，得 : 原来我们一般面对的是概率公式 Y=f(X). 现在反过来 , 由已知的概率分布或通过其参数信息来反求 X. Xi=G(Ri) 其中 ,Ri 为一个 0-1 区间内的均匀分布的随机变量 . F(X) 较简单时，求解较易，当 F(X) 较复杂时，需要用到较为复杂的变换技巧。 2.4.1 平均分布 :2.4.2 指数分布 : 2.4.3 正态分布随机变量的生成 : 2.5 离散型随机变量3 随机数的检验随机数的统计检验，就是根据（0，1）上均匀总体简单子样式的性质来研究所产生的随机数序列的相应性质，进行比较鉴别，视其差异显著与否，决定取舍。如果所产生的伪随机数经过各类检验，其差异均不显著，我们即接受其为均匀总体随机数的子样。需要指出的是，若所产生的伪随机数序列通过某种随机性检验，只是说它与随机数的性质和规律不矛盾，我们不能扛绝它，并不是说它们已经具有随机数的性质与规律。因此检验所产生的伪随机数序列时，所通过的检验越多，随机数序列就越靠得住。随机数的检验方法有：参数检验，检验其分布参数的观察值与理论值的差异显著性。均匀性检验，又称频率检验，意在检验伪随机数的经验频率与理论频率的差异是否显著。独立性检验，即检验所产生的伪随机数的独立性和统计相关是否异常，包括相关关系检验和联列表检验等。组合规律检测，按随机数出现的先后次序，根据一定的规律组合，检验其组合的观察值与理值是不否有显著差异，包括距离检验和配套检验等。游程检验，把随机数序列按一定的规则进行分类，分为正负游程检验和升降游程检验等。4 大随机数产生的机理4.1 流程图图1 1024位随机数产生原理图伪随机数产生器的产生过程:输入： 输入为两个64比特的伪随机数DTi和Vi，其中DTi表示当前的日期和时间,每产生一个数Ri后，DTi都更新一次；Vi是产生第i个随机数时的种子，其初值可任意设定，以后每次自动更新。密钥： 产生器用了3次三重DES加密，3次加密使用相同的两个56比特的密钥K1和K2，这两个密钥必须保密且不能用作他用。输出： 输出为一个64比特的伪随机数Ri和一个64比特的新种子Vi+1Step_1: 使用两个56比特的密钥K1和K2,对伪随机数DTi进行一次三重DES加密(EDE),得到Result_1;step_2: 任意设置一个值为Vi的初值,将Vi和Result_1进行异或,得到Result_2;step_3: 使用密钥K1和K2对Result_2进行一次三重DES加密(EDE),得到一个64bit的Ri和Result_3;（公式1）(说明: EDE表示两个密钥的三重DES)step_4: 异或Result_1和Result_3,得到Result_4;step_5: 使用密钥K1和K2对Result_4进行一次三重DES加密(EDE),得到Result_5,即得到一个64bit的新种子V(i+1).（公式2）(说明: EDE表示两个密钥的三重DES)step_6: V(i+1)将作为下一轮的输入Vi,再次循环完成step_1到step_5的过程,直到完成16轮迭代加密.本方案具有非常高的密码强度，这是因为采用了112比特长的密钥和9个DES加密，同时还由于算法由两个伪随机数输入驱动，一个是当前的日期和时间，另一个是算法上次产生的新种子。而且即使某次产生的随机数Ri泄露了，但由于Ri又经一次EDE加密才产生新种子Vi+1，所以别人即使得到Ri也得不到Vi+1，从而得不到新随机数Ri+1。随机数产生为1024位，即16组64位2进制数，且有最高为（第1024位2进制数）为1，所以该随机数高位在（16进制）10000000与FFFFFFFF之间。4.2 DES算法简介自DES算法1977年公诸于世以来，人们一直对DES的安全性持怀疑态度，对密钥的长度、迭代次数及S盒的设计众说纷纭。从技术上说，对DES的批评主要集中在以下3个方面：作为区组密码，DES的加密单位仅有64位二进制，对于数据传输来说太小；密钥仅有56位二进制未免太短，各次迭代中使用的密钥K(i)是递推产生的，这种相关性降低了密码体制的安全性；实现替代函数Si所用的S盒的设计原理尚未公开，其中可能留有隐患。针对以上DES的缺陷，人们提出了几种增强DES安全性的方法，主要有以下3种：1） 三重DES算法用3个不同密钥的三重加密，即为：C=Ek3(Dk2(Ek1P)P=Dk1(Ek2(Dk3C) 该方法为密码专家默克尔（Merkle）及赫尔曼（Hellman）推荐。据称，目前尚无人找到针对此方案的攻击方法。2）具有独立子密钥的DES算法每一轮迭代都使用一个不同的子密钥，而不是由一个56位二进制的密钥产生。由于16轮迭代的每轮使用一个48位二进制的密钥，所以这一方法可以增强DES的加密强度。3）带有交换S盒的DES算法比哈姆和沙米尔证明通过优化S盒的设计，甚至S盒本身的顺序，可以抵抗差分密码分析，以达到进一步增强DES算法的加密强度的目的。5 算法实现函数名: get_SystemStatus_W32函数功能: 得到系统状态输入: 无输出: 系统状态字符串,ni:得到的字符串长度流程图：进程ID的句柄标实符线程的句柄标实符CPU脉冲值内存状态字凡是长度大于maxlen ,ni等于ni加上其长度，返回ni图2 得到系统状态的方法示意图buf: 用以保存系统状态字符中，maxlen:字符串长度int CCreRndNum:get_SystemStatus_W32(int maxlen) int ni = 0; /保存得到的字符串长度DWORD dwRes;MEMORYSTATUS ms;dwRes = GetCurrentProcessId(); /返回长整型(DWORD)if (maxlen >= sizeof(DWORD)memcpy(&bufni, &dwRes, sizeof(dwRes);ni += sizeof(dwRes);maxlen -= sizeof(dwRes);dwRes = GetCurrentThreadId();if (maxlen >= sizeof(DWORD)memcpy(&bufni, &dwRes, sizeof(dwRes);ni += sizeof(dwRes);maxlen -= sizeof(dwRes);dwRes = GetTickCount();if (maxlen >= sizeof(DWORD)memcpy(&bufni, &dwRes, sizeof(dwRes);ni += sizeof(dwRes);maxlen -= sizeof(dwRes);ms.dwLength = sizeof(MEMORYSTATUS);GlobalMemoryStatus(&ms);if (maxlen >= sizeof(MEMORYSTATUS)memcpy(&bufni, &ms, sizeof(MEMORYSTATUS);ni += sizeof(MEMORYSTATUS);maxlen -= sizeof(MEMORYSTATUS);return ni;void CCreRndNum:GetKey() int sysInfoLen = get_SystemStatus_W32(300);CString sKey32; /字符串型int iKey3232; /转换后的整型 sKey32 = CMD5Checksum:GetMD5(buf,sysInfoLen);/字符串for(int i = 0; i < 32; i+)/字符串转化为整型iKey32i = CharToInt(sKey32i);for(i = 0; i < 64; i+) /取出每一位KK1i = iKey32i / 4 >> (i % 4) & 0x01; KK2i = iKey3216 + i / 4 >> (i % 4) & 0x01; 函数名: GetTime函数功能: 得到64bit的当前日期和时间的二进制输入: 系统时间输出: btime64算法示意图：通过移位异或把系统时间转换成二进制数并放到DTi的高32和低32位中去通过摸除2得到64位的二进制随机数ViDTi和Vi都将作为主程序的输入随机数输入系统时间Rand()产生的随机数图3 分别得到产生大随机数的输入随机数void CCreRndNum:GetTime()int i;FILETIME ft;GetSystemTimeAsFileTime(&ft);for (i = 0; i < 32; i+) DTi31 - i = (char)(ft.dwHighDateTime >> i) & 0x01); / 取得各位的值 DTi63 - i = (char)(ft.dwLowDateTime >> i) & 0x01);void CCreRndNum:GetVi() /得到64位的二进制随机数int i; srand(unsigned)time(NULL); for (i = 0; i < 64; i+)Vii = rand()%2;函数名: Step_1函数功能: 产生随机数第1步(见图1)输入: DTi(时间),K1,K2(密钥)输出: Result_164调用函数: MyDes:EDE()void CCreRndNum:Step_1()GetTime(); /得到时间二进制并保存在DTi中 GetKey(); /产生密钥并保存在KK1,KK2中CDES MyDes;MyDes.EDE (DTi, KK1, KK2, Result_1); /三重DES加密(EDE)函数名: Step_2函数功能: 产生随机数第2步(见图1)输入: Result_1,Vi(第一次输入的随机数)输出: Result_264void CCreRndNum:Step_2()int i;/之前已得到V0for (i = 0; i < 64; i+)Result_2i = Vii Result_1i;函数名: Step_3函数功能: 产生随机数第3步(见图1)输入: Result_2,K1,K2(密钥)输出: Result_364调用函数: MyDes:EDE()void CCreRndNum:Step_3()CDES MyDes;MyDes.EDE(Result_2, KK1, KK2, Result_3);函数名: Step_4函数功能: 产生随机数第4步异或(见图1)输入: Result_1,Result_3输出: Result_464void CCreRndNum:Step_4() int i; for (i = 0; i < 64; i+) Result_4i = Result_1i Result_3i; 函数名: Step_5函数功能: 产生随机数第5步(见图1)输入: Result_4,K1,K2(密钥)输出: Result_564调用函数: MyDes:EDEvoid CCreRndNum:Step_5()CDES MyDes;MyDes.EDE (Result_4, KK1, KK2, Result_5);函数名: GetRandNumber函数功能: 产生随机数,保存在dwRndNum33中.输入: 无输出: dwRndNum33备注: 输出1025位二进制,故用33个DWORD型的数存放随机数.BOOL CCreRndNum:GetRandNumber(DWORD dwRndNum) GetVi(); int i,m;for (m = 0; m < 17; m+) /17轮产生1088(取1025)位的RiStep_1(); Step_2(); Step_3(); for (i = 0; i < 64; i+) Ri(m << 6) + i = Result_3i; /保存到1024bit的Ri中 Step_4(); Step_5(); for (i = 0; i < 64; i+) /Vi+1自动赋给Vi Vii = Result_5i; / end for UINT temp;for ( i = 0; i < 1024; i+) /取第11024位temp = (UINT)(i / 32);if(i % 32 = 0) dwRndNumtemp = dwRndNumtemp | (DWORD)Rii; else dwRndNumtemp = dwRndNumtemp << 1 | (DWORD)Rii;for(i=0;i<32;i+)while(dwRndNumi<2147483648)dwRndNumi+=dwRndNumi; dwRndNum32 &= (DWORD)Ri1024; /取第1025位,其余位为0return TRUE; 6 检验随机数随机数检验方法有如下几种：参数检验，检验其分布参数的观察值与理论值的差异显著性。均匀性检验，又称频率检验，意在检验伪随机数的经验频率与理论频率的差异是否显著。独立性检验，即检验所产生的伪随机数的独立性和统计相关是否异常，包括相关关系检验和联列表检验等。组合规律检测，按随机数出现的先后次序，根据一定的规律组合，检验其组合的观察值与理值是不否有显著差异，包括距离检验和配套检验等。游程检验，把随机数序列按一定的规则进行分类，分为正负游程检验和升降游程检验等。本程序采用了均匀性检测，即频率检测。由于随机数是由16次循环得来。并且存放在32个数组中，所以取其中高位数组的值就可以判断是否满足均匀性检测。算法示意图： 随机数除于当前随机数产生的次数如果第一次产生随机数，平均值为随机数本身平均值除于随机数产生次数与次数-1的积两者相加得到随机数的平均值得到生成器产生的随机数 图4 检验随机数足够随机Int bb=0;bb+; char s40;for (int i =0;i<33;i+)sprintf(s,"(%2d) %10lXrn",i,dwni);m_show.ReplaceSel (s);cc=cc/bb*(bb-1)+dwn31/bb;sprintf(s,"第%2d次前位平均值为：n%10lXn",bb,cc);m_show.ReplaceSel (s);7 系统测试 第一次多次运行程序，如图：图5 第一次测试结果第二次多次运行程序，如图：图6 第2次测试结果第三次多次运行程序，如图：图7 第3次测试结果结 论因为主导程序对本身就是随机的数经过多次的三重DES和异或等运算，所以能保证随机数的足够随机性，通过16次的循环也能得到一个组合的大随机数，所以能满足设计的需求界面是用VC+实现与设计的一个随机数发生器，该随机数发生器能够通过点击产生随机数按钮而相映产生1024位的随机数，并且该产生器还记录每次产生的随机数而求其平均值，能够很直观的让我们检测到随机数是否随机。随机数产生器界面简单，随机数足够随机并且保证随机数范围满足1024位2进制数。由于时间关系，程序也有一定瑕疵。对程序改进的方法：对检测的方法增加其他的种类，例如参数检验，游程检验等方法，毕竟，通过的检测越多随机数的可靠性就越高。参考文献1王锐.网络最高安全技术指南M.北京:机械工业出版社,1998。2 (美)克鲁格林斯基(Kruglinski,D.J.).Visual C+ 技术内幕M.北京:清华大学出版社，1999。3云巅工作室.Visual C# 中文版全面剖析M.北京：中国水利水电出版社，2003。4 Bruce Schneier.应用密码学协议，算法与C源程序M. 北京：机械工业出版社，2000。5冯登国著.密码分析学M.北京：清华大学出版，2000。 6（美) Steven John Metsker.C#设计模式M. 北京：中国电力出版社，2005。7 林元烈，梁宗霞.随机数学引论M.北京：清华大学出版社，2003。8 J.S. 贝达特，A.C. 皮尔索.随机数据分析方法M.北京：北京国防工业出版社，1976。