（基础数学专业论文）关于随机数生成算法的研究.pdf

摘要 随着计算机网络迅速的发展，人们越来越依赖于互联网络这个开 放式的平台来进行讯息的交换和传递。如何既能利用互联网络的快捷、 有效，又能保证所传输的数据安全、隐秘，一直是学术界重要的研究 方向。随着单向函数和非对称密钥理论的出现，在方法上构造了较为 安全的加密方法，但是这些方法的有效性在很大程度上取决于所使用 的随机数质量的高低。随机数在密码学、信息学等多个应用领域中所 占据的地位也越来越重要。 本文在结合随机数、随机过程及随机性等基本理论之后，研究了 伪随机数算法和真随机数发生器各自的原理，并分析了两类方法的优 缺点。针对实际应用的需要，提出了一种结合两类常规生成方法优点 的算法。这种算法首先基于信息论中的熵值概念，通过选择新的物理 参数来提高生成系统的熵，在算法实现的过程中，采用新的动态数据 结构动态数据缓冲池p d 肋，并通过读写保护机制来保证数据的安 全。 本文还对这种算法进一步地进行改进，引入了数据保存机制、混 沌映射步长、初值系统及并行算法。通过多个无关联系统的并行运行， 使得生成的随机序列的质量得到了很大的提高。实验测试表明，此方 法能兼顾安全性和生成速率两方面的要求，适宜实际应用的需要。 关键词：随机过程，生成方法，熵，动态数据，并行算法 a b s t r a c t w i t hc o m p u t e rn e 锨，o r kr a p i dd e v e l o p m e n t ，t h ep e o p l em o r ea n d m o r er e l yo ni ni n t e m e tt h i so p e ns t y l ep l a t f o r mc a n yo nm ei n f o m l a t i o n t h ee x c h a n g ea n dt h et r a n s m i s s i o n h o wb o mc a nu s em ei n t e m e tq u i c k l y ， e f f e c t i v e l y ，a n dc a ng u a u r a n t e e 胁s m i t st h ed a t as e c 砸t y ，t h es e c r e t ， a l w a v s a r et h ea c a d e m i cc i r c l e si m p o r t a n tr e s e a r c hd i r e c t i o n s w i t h u n i d i r e c t i 叽a 1劬c t i o na n da s y m m e t r i c a lk e yt h e o 巧印p e a r a n c e ， i n m e t h o ds t m c m r es a f e re n c d 审t i o n ，b u tt h e s em e t h o d sv a l i d i t ) ，i sd e c i d e dt o a 铲e a te x t e n tb yt h em d o m n u m b e rq u a l i t yh e i g h tw h i c hu s e s r a n d o m n u n l b e rt h es t a t l j sw h i c hi nt h ec 聊t 0 1 0 9 y ，t h ei n f o n n a t i o ns t l l d ya n ds oo n i nm a n ya p p l i c a t i o nd o m a i n so c c u p i e sm o r ea n dm o r ei sa l s oi m p o r t a n t t h i sa n i c l ec o r n b i n ew i ms o m eb a s i ct h e o r ya b o u tr a n d o mn u m b e r s ， s t o c h a s t i cp r o c e s s e sa n dr a n d o n l ， r e s e a r c ht h e i rp i l i n c i p l e s o f p s e u d o r a n d o mn u m b e ra l g o r i t h m sa n dt r u e r a n d o mn u m b e rg e n e r a t o r ， a n da n a l y s i so ft h et w ot y p e sm e t h o do ft h ea d v a i l t a g e s 锄dd i s a d v 狐t a g e s f o rp r a c t i c a l 印p l i c a t i o n s ， m i sa n i c l e p r o p o s e s a 1 1 a l g o r i t l l l i lw h i c h c o m b i n a t i o nm ea d v 锄t a g e so fp s e u d o - r a n d o mn u m b e ra l g 嘶t h i n sa n d t m er a l l l o mn um _ b e rg e n e r a t o r t h i s a l g o n t h m b a s eo ne n 仃o p yo f i n f 砷m a t i o nt h e o 巧i nt h ep r o c e s so ft h ea l g 面m mi m p l e m e n t a t i o n ，b y c h o o s i n gan e wg e n e r a t i o no fp h y s i c a lp a r a m e t e r st oi m p r o v et h ee n 仃o p y o fs y s t e m ，t h i sr e s e a r c hu s e san e wd y n 枷cd a t as t m c n i r e t h ep o o lo f d y n 锄i cb u f f e dd a t ap d b d ，t h r o u g hr e a d i n ga n dw r i t i n gp r o t e c t i o n m e c h a n i s 峪t oe n s u r ed a t as e c u r i t y t 1 1 i sa n i c l ea l s oi m p r o v e st h ea l g o n t h m ，a n di n 仃o d u c e sd a t as a v e d m e c h a n i s m ，b u c h a n go fc h a o t i c ， i n i t i a lv a l u e s y s t e n l s a n dp a r a l l e l a l g o r i t h m t h r o u 曲m o r et h e 彻eu n r e l a t e ds y s t e m sr u n n i n gi np a r a l l e l ， t h eq u a l i t yo fg e n e r a t e dr a n d o ms e q u e n c eh a sb e e n 伊e a t l yi m p r o v e d e x p 嘶m e n t a lt e s t ss h o wt h a tt h i sm e t h o dc a nt a k ei n t oa c c o u n tt h es a f e t y a n ds p e e d s u i t a b l ef o rm ea c m a la p p l i c a t i o nn e e d s k e y w o rd ：r a n d o m - p r o c e s s ，g e n e r a t i o n ，e n 订o p i e ，d y n a m i c - d a t a ，p 2 u r a l l e l a l g o r i t h r n s h 附录3 学位论文原创性声明与版权使用授权书 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 诌翻乃孑年iz 月弓日 f 。 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ ”) 作者签名：扔捌日期：沙矿年f 2 月； 日 导师签名：善夏参日秘年忽月7 日 关丁随机数生成算法的研究 1 1 随机数的背景及意义 1绪论 随机数由性质相同的数组成，单个或几个数不能说是随机数，所 以随机数一般又叫随机数组或随机序列。随着科技的发展，随机数在 各个方面的应用也越来越广泛，如：通信安全、模拟测试、数字签名、 智能计算、随机性能的仿真、数字系统的内建自检测、游戏以及电子 商务【1 】等等。 随着计算机技术、互联网以及其他数字技术的发展，开放式的信 息共享系统得到了很大发展，人们在享受网络带来的方便、快捷的同 时，却在信息安全方面遇到了黑客、木马等不安全冈素的挑战，随即 就产生了对信息的生成、传输、存储等各个方面进行保护的要求。而 这种保护通常采用信息加密来实现。随机数生成算法( 发生器，r n g ) 则是信息加密设备中一个重要的组成部分，它产生的不可预知、不可 再现的密钥数字串对信息加密有着重要的作用【2 】。在密码学的领域里， 随机数的作用更是被提到了核心的位置，比如密钥管理、众多的密码 学协议、数字签名和身份认证等都要用到随机数。随机数是作为密钥 的补充信息，辅助信息和初始化向量来使用的，无论是在非对称算法 中的私钥，还是对称算法中的密钥，为了保证其密码系统的安全性， 原始钥匙都需要由独立的随机数算法来生成。所以在把安全性放在首 位的密码系统中，使用好的随机数生成算法对每一个密码系统来说都 至关重要。因此，如何方便、快速的生成统计性能良好的高质量的随 机数已成为一个重要的研究课题。 一般在强调安全及使用密码的场合，都希望其所使用的随机数是 真正的、完全不可预测的随机序列【3 】。一般将这种物理的随机序列称 为真随机数，并将其序列生成的机制( 算法) 称为真随机数发生器 ( t r n g ) ，它不同于一般程序中调用的伪随机数发生器( p r n g ) ，因为 高校教师订：职硕i ：学位论义 后者多是基于算术程序，使用函数算子而生成的。两种随机数发生器 各有特点：真随机数质量高，但是获取和使用( 生成的数据量较小) 相对困难；而伪随机数则恰好相反，随机值虽然是计算得出，但是使 用却是极其的方便。但是，不管采用哪种随机数生成方法，其都由两 个基本功能单元构成，一个是非确定性单元，它是整个系统不可预测 性的来源，也就是信息学中所说的熵，是在随机数中用来作为随机源 的信号源，也称为熵源。另一个是确定性算法，它借由随机源提供的 随机信号，进一步地生成均匀、独立、数据稳定的输出序列。一般熵 源是整个随机生成系统中获取随机性的唯一来源，因此好的熵源对于 一个随机数发生器的统计性、安全性、数据稳定性起着至关重要的作 用。 1 2 随机数生成的方法及研究现状 生成随机数的方法繁多，究其生成机理来说，一般分为数学计算 方法和物理采样方法两大类别，其所生成的随机数分别被称之为伪随 机数( 序列) 和真随机数( 序列) 。两类随机序列各有优势，伪随机序 列容易获得且方便使用，一般用于测试、仿真等场合；而真随机序列 取自物理世界的真实随机源，难以破解，主要应用在数据加密、密钥 管理、身份鉴定等对安全性要求高的领域。但这并不不是说基于物理 采样方法生成的随机序列质量就真的很高，衡量随机序列的质量主要 是取决于生成算法是如何利用这个物理随机源。相反的，许多用数学 计算方法生成的随机序列在很多方面的测试中显示其特性更好。 1 2 1 伪随机序列的研究 对于伪随机数的研究，可以按时间大致分为三个阶段： 1 9 4 8 年以前为纯理论研究阶段，当时研究伪随机序列的理论仅仅 是因为其优美的数学结构。最早的研究可以追溯到1 8 9 4 年，作为一个 关于随机数生成算法的研究 组合问题来研究的所谓的d eb r u i j n 序列；上个世纪3 0 年代，环上的 线性递归序列则成为人们的研究重点【4 】。 在1 9 4 8 年s h a n n o n 信息论诞生后，就进入了研究m 序列的黄金 阶段。从那时起伪随机序列已经被广泛的应用在通信以及密码学等重 要的技术领域。s h a i l n o n 证明了“一次一密 是无条件安全的，无条 件保密的密码体制要求进行保密通信的密钥量至少与明文量一样大。 因此在这之后的一段时间内，学者们一直致力于寻找具有足够长周期 的伪随机序列。如何找到这样的序列成为了2 0 世纪5 0 年代早期的研 究热点。线性反馈移位寄存器( l f s r ) 序论成为这个时期研究最多的 一种方法，因为一个n 级l f s r 可以产生周期为2 n 一1 的最大长度序列， 而且满足g o l o m b 随机性假设的随机特性【3 】。 非线性生成器的研究阶段( 1 9 6 9 一至今) ，1 9 6 9 年m a s s e y 发表了 “移位寄存器综合与b c h 译码 【5 】一文，引发了序列研究根本方向的 变革，b e r l e k 觚l p m a s s e y 算法( 简称b m 算法) 指出：如果序列的线 性复杂度为n ，则只需要2 n 个连续比特就可以恢复出全部的序列。从 这个结论可以看出m 序列是一种“很差”的序列，他的线性复杂度太 小，因而不能直接用来做流密码系统的密钥流序列，从此伪随机序列 的研究进入了构造非线性序列生成器的阶段。 目前对构造伪随机序列的研究，从大方法上可以分成两种：一类 是基于数学理论构造的伪随机序列，这类序列在理论上容易分析序列 的随机性质但难于实现，很多理论随机序列往往因其构造难度太大， 造成无法实现或代价过高。另一类就是前面提到的基于l f s r 构造的 伪随机序列。这类序列与理论序列恰好相反，在工程上容易实现且实 现成本较低，但是不太容易分析其随机性质。现在，基于数学理论构 造的伪随机序列是当前学术界研究的重点，一般分为两种理论：基于 数论的方法和基于有限域的方法。数论法利用的主要是二次剩余定理 和割圆定理等数理工具，像l e g e n d r e 序列、j a c o b i 序列、差集序列和 割圆序列等就是属于此类方法。有限域法主要利用的是迹函数，像b e n t 高校教师确：职硕i ：学位论文 序列、g m w 序列、w r e l c h g o n g 序列以及椭圆曲线序列等就是此类方 法的代表。就现有文献中的序列构造方法来看，构造具有理想互相关 特性的序列一直是构造理论伪随机序列的基础【6 1 。很多具有良好随机 特性的序列，如w r e l c h g o n g 序列等都是在寻找到具有理想的互相关 特性之后，再应用w g 等方法变换而来的。但是很多具有这些理想互 相关特性序列的构造方法，大多都是依赖专家的经验来拼凑系数，然 后依靠智能算法搜索而来的，不俱备理论上的操作性和可移植性。为 了寻找更好的伪随机数算法，学术界一直还在研究如何构造具有理想 互相关特性的方法。 1 2 2 真随机数发生器的研究 由于随机序列发生器在信息安全、军事、商业等应用领域中发挥 的作用越来越重要。统计独立性更好的真随机数成为应用领域最受关 注的一个研究方向，国内外对真随机数发生器( t l g ) 的研究也越 来越重视【_ 7 1 。很多这方面的文献资料显示在国外，这些项目多有政府、 金融机构、军方的资助，发展速度很快。 早在1 9 8 5 年i n t e l 公司在研究访问受控e e p r o m 芯片时就曾采用 过一个简单的片上随机数发生器，后来它的一个科研小组利用电阻上 热噪声设计了一种随机数发生器，是采用的双振荡器结构【8 1 。1 9 9 7 年 g e o 略i ai n s t i t u t eo f t e c i l l l o l o g y 采用1 2 微米b i c m o s 工艺开发了基于 运算放大器噪声的随机数发生器芯片。 2 0 0 2 年前后瑞士日内瓦大学根据量子效应开展随机数发生器的 研究。相应地中国科学院研究院的冯凯锋、吕述望等人也开展量子随 机数发生器的研究工作 9 1 。北京工业大学的冯艳、杨镇海等人也提出 了利用无理数无限不循环的特性建立随机序列产生的模型。 在2 0 0 3 年，中科院研究生院的苏桂平等人根据小波分析理论为数 字物理噪声源的随机性建立数学模型【10 1 ，利用电路内部噪声信号研制 关丁随机数生成算法的研究 随机序列发生器。同年成都电子科技大学的张传武、彭启宗等人在 s w o l f r a m 提出的利用细胞自动机产生随机数方法【l l 】的基础上，进行 了深化研究，提出了基于具有本原多项式的9 0 1 5 0 加性细胞自动机的 随机数发生器模型【l2 1 。通过查阅最近的研究文献后发现，目前对真随 机数发生器的研究开始越来越多地关注于优化物理随机源的设计。这 其中便于采用纯数字电路实现的振荡环采样法成为当前的研究热点。 由于各种物理环境变化的影响，基于硬件实现的随机序列源通常 具有一定的相关性。在2 0 0 0 年时c s p e t n e 和j a c o n n e l l v 通过将放 大后的噪声源、采样振荡环噪声、离散时间混沌映射这三个熵源进行 结合【13 1 ，很好地解决了这个相关性的问题。 在2 0 0 3 年m b u c c i 等人通过放大热噪声构建慢时钟驱动d f f 对 一个稳定的快速时钟采样【l4 1 ，设计了一种数模混合的熵源。解决了基 于振荡环采样的随机源因为抖动密度不够而造成的输出速率低、随机 性能差等问题。后经o 1 8 u m c m o s 工艺实现后，验证了该设计输出速 率高且性能良好。 2 0 0 4 年h b o c k 与m b u c c i 等人合作，提出了一种带有补偿环 ( c o m p e n s a t i o nl o o p ) 的振荡采样源【1 5 】，当慢时钟的抖动密度不够时， 可以自动降低慢时钟的采样速率，从而提高输出的统计性能，且该设 计可以全部用数字电路进行实现。 2 0 0 6 年j o v a nd j g o l i c 等提出了2 种新的结构：斐波那契( f i b o n a c c i ) 和伽罗华( g a l o i s ) 结构【1 6 】。这两种新结构在通常的振荡环上引入了数学 上的l f s r 概念，从而将具有真随机性的时钟抖动与具有伪随机性的 l f s r 结合起来。同年b u c c i ，l g i a n c a n e 等人采用了延迟模块和m o s 开关，构造了一种新颖的耦合振荡器【l7 1 ，这种振荡器实现了约为 1 3 m b i t s 的高数据输出率。现如今，真随机序列生成算法和硬件随机 序列发生器不断涌现，呈现出百家争鸣的态势。 虽然真随机数发生器在密码、密钥的应用中起着重要作用，但是 目前大多数真随机数发生器还是基于一种理想状况来分析其输出的随 高校教师订i 职硕 ：学位论文 机序列的性能。实际中以上这些方法中仍存在一些弱点，如产生的随 机数的分布特性较差、稳定性不佳等缺点，所以在实际使用中，通常 还需要对其发生器的输出序列进行后期的算法处型1 ，1 4 ，15 1 ，才能使其输 出的序列能够通过各种随机性的测试。 1 3 本文各部分的主要内容 本文主要内容分六章，第一章是绪论部分，简单的介绍了随机数 背景及随机数的生成方法。 第二章介绍随机序列的理论知识和生成过程，同时也包含了随机 序列在密码学、信息学中的用途和要求，以及其他的与生成随机序列 密切相关的理论。 第三章介绍了伪随机数以及常用的伪随机数算法等。 第四章介绍了真随机数的概念，物理随机源的选取及捕捉的方法 笙 寸。 第五章是本论文的核心部分，本文在结合真、伪2 种随机生成方 法优点的基础上，提出一种基于动态数据结构并引入新的物理随机事 件的随机序列生成算法。其中包含了生成器的基本原理，主要的设计 过程，测试的结果以及对结果的分析。 第六章对本文的研究结果进行了总结和展望。 关于随机数生成算法的研究 2 1 密码学 2 随机原理及其他基础理论 1 9 4 9 年，信息论之父c e s h a n n o n 发表了密码系统的信理论， 密码学正式走上理论科学的道路。密码学是以研究秘密通信为目的， 即对所要传送的信息采取一种秘密保护，以防止第三者对信息的窃取。 整个密码通信的过程可用下图来表示： 2 1 1 加密算法 图：2 1 密码通信过程示意图 加密算法是信息安全的核心，通常称待加密的消息为明文用p 表 示；加密后的消息为密文用c 表示；将明文变换到密文的过程称为加 密，用e 表示；加密的逆过程，即由密文恢复到明文的过程称为解密， 用d 表示；称对明文进行加密时所采用的转变方法为加密算法，称对 密文进行解密时所采用的转变方法为解密算法；般来说，加解密都 是在一组密钥( k e y ) 的控制下进行的，密钥用k 表示，一般称加密时采 用的密钥为加密密钥，解密时采用的密钥为解密密钥。那么就有： 色l ( 尸) = c ， 二1 。l d 女2 ( c ) = 尸 并且e 和d 必须满足 取2 ( l ( 尸) ) = p ( 2 1 2 ) 高校教师d ! 职硕i j 学位论文 2 1 2 对称密码算法( s 舯m e t r i ca l g o r i t h m ) 有时又称单钥( o n ek - e y ) 密码算法或私钥( p r i v a t ek e y ) 密码算法， 通常私钥密码算法的加密密钥和解密密钥相同或者两者之间可以通过 互相变换而得到。因此，信源和信宿在进行信息的传输与处理时，必 须共同持有该密码。在对称密钥密码算法中，加密运算与解密运算使 用同样的密钥。通常所采用的加密算法比较简便、高效，密钥较为精 简便于记忆，但破译密钥极其困难。整个加密系统的保密性主要取决 于密钥本身的安全性。 2 1 3 非对称密码算法( a s y m m e t r i ca l g o r i t h m ) 也称双钥( t w ok e y ) 密码算法或公钥密码算法，其理论最早是由 w d i 师e 和h e l l m a n 于1 9 7 6 年提出的。不同于以往的加密技术，非对 称加密技术是建立在数学函数基础上的，而不是建立在对位的操作方 式上的。与只使用单一密钥的传统加密技术相比，它在加、解密时， 分别使用了两个不同的密钥：一个可对外界公开，称为“公钥；一个 只有所有者知道，称为“私钥”。公钥和私钥之间具有紧密联系，用公 钥加密的信息只能用相应的私钥解密，反之亦然。同时，要想由一个 密钥推算出另一个密钥，在计算量上是不合理的。非对称密码技术可 以提供对称密码技术无法或很难提供的服务，如：与哈希函数联合运 用后可组成数字签名，来用于零知识证明等。 2 2 随机及随机序列理论 因为随机序列在密码学、通信理论以及计算机安全等领域中占据 着核心地位，所以有关随机序列生成方法的研究工作一直是密码学和 信息学中重要的研究方向，学者们对随机本身及随机现象也不断进行 关r 随机数乍成掉法的研究 着列论例究。 221 随机过程 随机过程的般概念。介纠随机过程的概念之前，我仃j 先术看 f 布刚运动( b r o w n i a nm o v e m e n t ) 的例子： 图：2 2 和朗运动过程模型图 l8 2 7 年，英国植物学家rb r o w n 发现，悬浮在液体或者2 t 体中的 微粒由于连续的受到周围分干的碰撞而不停顿的作不规则的运动，人 们把这种现象称为布朗运动。1 9 0 5 年，ae i n s t e i n 指出，不管运动在 表面卜如何不规则，这些粒子的移动是可以用概率规律来分析的。到 了1 9 2 3 年，美国数学家n 、v i e n e r 开始把布朗运动作为随机过程来研 究，而且很快由l e v y 等数学家将之作了很大的发展。 w i e n e r 和l e v y 如f 定义布朗运动： 布朗运动b ( t ) 足这样一种运动，它的初始位置b ( 0 ) = o ，其后的位 移b ( t ) 一b ( o ) 服从n ( 0 ，q t ) 分布，q 是一个反映布朗运动强度的参数， 而i i 在两段不相交箍的时间段( f ：f ) ，( f 。一，3 ) 其运动距离 【口( ，2 ) 一占( f i ) 儿启( ) 一口( 岛) j 不相关，即： 占【( 占( 2 ) 一口( f i ) ) ( 口( 如) 一口( f 。) ) = o ( 2 2 一1 ) 对所_ 仃微利来说，其位移大小b 足一簇时问函数，记为b ( t ) ，这簇时 高校教师在职硕i ：学位论文 间函数就是“随机过程”，簇中每一时间函数称为随机过程的样本函数。 由此，我们对随机过程的定义如下： 随机过程是依赖于时间参量t 变化的随机变量的总体或集合；也 可以叫做样本函数的总体或集合【l8 1 。习惯用f ( f ) 表示，具有以下特点： 1 ) 随机过程虽然是t 的函数，但是在任一时刻上观察到的值却是 不确定的，它是一个随机变量，同时具有随机变量和时间函数的特点。 2 ) 随机过程也可看成是由全部可能实现构成的总体，每个实现都 是一个确定的时间函数，而随机性就体现在出现哪一个实现是不确定 的。随机过程描述的信号称为随机信号，随机信号是随时间变化的随 机变量，具有函数的特点，所以可以用概率函数进行描述。 2 2 2 随机过程的统计特性 随机过程的两重性使我们可以用于描述随机变量相似的方，来描 述它的统计特性。也就是说随机过程的统计特性可以用分布函数或概 率密度函数来描述。 分布函数和概率密度，设f ( f ) 表示一个随机过程，在任意给定的 时刻t i t ，其取值孝( ) 是一个一维随机变量。则孝( ) 小于或等于某一 数值x i 的概率为： e ( ，) = 尸 孝( ) t 】 ( 2 2 2 ) 上式称为随机过程孝( f ) 的一维分布函数。如果f i ( x i ，t i ) 对x i 的偏 导数存在，即有： 掣= z ( ，) ( 2 2 - 3 ) 傩f 则称f ；( x i ，t i ) 为善( f ) 的一维概率密度函数。 同理，任给，乞，乙丁，则孝( f ) 的n 维分布函数被定义为： e ( ，恐，毛； ，乞，乙) = p 孝( 九) 而，孝( f 2 ) 娩，孑( 乙) ) ( 2 2 4 ) 孝( f ) 的n 维概率密度函数为： 关丁随机数生成算法的研究 塑避笔丛掣= 厂( w 2 ，铂 ， ( 2 2 - 5 ) 铂出2 优h n 越大，对随机过程统计特性的描述就越充分，但问题的复杂性也随 之增加。 2 2 - 3 随机过程的数字特征 用随机过程的数字特征来描述随机过程的统计特性，更为简单和 直观。 数学期望：表示随机过程的n 个样本函数曲线的摆动中心，即平 均值。 研孝( f ) 】_ k ( x ，f ) 出= 以( f ) ( 2 2 - 6 ) 方差函数：表示随机过程在时刻t 对于均值a ( t ) 的偏离程度。即均 方值与均值平方之差。 仃2 ( f ) = d 孝( f ) 】 = e 【善( f ) 一口( f ) 】z ：e 嘭2 ( f ) 卜e 2 吼) 】 ( 2 2 7 ) = 卜2 石( x ，f ) 出一( 以( f ) ) 2 协方差函数： b ( f l ，t 2 ) = e 孝( f 1 ) 一口( ) 孝( f 2 ) 一口( f 2 ) 】) = jk 毗) 】【吃叫u 埘u 出。如 q 二8 相关函数： 尺( ，乞) = e 【孝( ) 孝( f 2 ) 】 o o = li x l x 2 厶( 而，娩；f l ，f 2 ) 出l 如 ( 2 2 9 ) 商校教师心：职硕 ：学位论义 2 2 4 随机序列 离散参数的随机过程称为随机序列。该序列是任意的、不能预测 的、不可获知的。若给定一个关于时间的随机序列源x ( t ) ，无法确定 它的取值，只能研究它在某些概率范围的统计特性。即可以从随机序 列源的时域和频域两方来面进行分析和描述。 l ) 对随机序列时域的分析和描述： 在实际中，主要研究随机序列的数字特征。随机序列在时域上常 用的数字特征有：数学期望、方差和相关函数。其中相关函数最能较 完整的表征随机信号的统计特征。 2 ) 对随机序列频域的分析和描述： 随机序列源足时域非周期能量无限信号，只能在一定的频段进行 傅立叶变换。一般用具有统计特性的功率谱密度来做谱分析。功率谱 密度：反映了单位频带信号功率的大小，是频谱的函数。它是从功率 这个角度描述随机序列源x ( t ) 的统计规律的最主要的数字特征。随机 序列源x ( t ) 的功率谱密度恰好是自相关函数的傅立叶变换。 3 ) 用描述复杂性理论对随机序列进行研究： 描述复杂性是一个关于随机性的基础理论。它起源于概率论、信 息论以及对随机性的哲学思考。描述复杂性作为新兴学科己在许多领 域得到应用，如：组合理论、算法复杂性分析、物理学中的混沌学、 生物学中的d n a 序列的复杂性等。关于随机性的描述，从不同的角 度有许多不同的说法。用描述复杂性的语言来描述随机序列是：随机 有限序列是指那些没有描述会比自身的直接描述更短的序列。如果某 无限序列的初始段都在这种意义上是随机的，则认为它是一个随机无 限序列。 关丁二随机数生成算法的研究 2 2 4 1 伪随机序列 伪随机序列一般都有比较好的随机统计特性，但它具有周期。伪 随机序列用数学算法生成，它在一些统计特性方面接近真随机序列， 但却是周期的和可预测的。在计算机中，当程序员需要一个或一组随 机数时，必须通过各种算法近似地生成随机数。现在在使用高级语言 编程时，常常通过调用r a n d o m ( ) 来获取随机序列。通常指令调用 r a n d o m ( ) ，实际上是调用伪随机数生成程序。 2 2 4 2 真随机序列 真随机序列虽然有难以预测、不能重复的特性，但随机统计却不 很理想。真随机序列用物理方法生成，通过选取真实世界的自然随机 性，所生成的随机数称为真随机数。真随机数生成器的输出是非确定 的，即使知道生成设备所使用的算法也无法“猜测 到设备的下一个 输出。例如，如果设备输出一系列o 和1 ，o 和l 在任何特定输出中出 现的机会应该相等。即使掌握了生成设备工作的全部知识，任何猜中 的可能性也只有5 0 。 2 2 5 随机序列的重要参数 1 ) 单比特熵 假设一个o 、l 随机序列中，l 出现的概率p ( 1 ) = p ，o 出现的概率 为p ( o ) = 1 一p ( 1 ) ，则l 比特随机序列的熵为： 日= 一 p ( 1 ) 1 0 9 尸( 1 ) + p ( o ) 1 0 9 p ( o ) ( 2 2 1 0 ) = 一尸l o g 尸一( 1 一尸) l o g ( 1 一尸) 从上式可以看出，只有当随机序列满足p ( o ) = p ( 1 ) = o 5 的时候， 1 比特随机序列的熵才能达到最大值l 。也可以说，单比特随机序列的 熵的大小直接反映了随机数发生器输出序列中o 、1 的均衡程度。 2 ) 随机性偏差 高校教师n ：职硕。 ：学位论文 实际的随机数算法( 发生器) 往往不可能做到o ，l 出现的概率完 全相等，因为实际系统总是或多或少的有些偏差，这就引出了另外一 个重要的参数：随机性偏差。随机性序列的o ，l 偏差定义为： s = i p ( 1 ) 一尸( o ) i ( 2 2 - 1 1 ) ( 2 2 1 2 ) 随机性偏差的定义和前面单比特随机序列的熵值的定义是一致 的，当o ，1 出现的概率越接近的时候，也就是二者的概率越接近o 5 的时候，序列的随机性越好。有了偏差的定义，一方面在设计随机数 发生器的时候，通过对参数的调整使得偏差尽量减小，也可以通过对 算法进行一些后期的数学处理来减小随机性偏差。 3 ) 相关函数 任何一个随机数算法( 发生器) 总可以用一个数学函数来表示， 如果这个数学函数的相关性比较小，说明函数的输出序列每一比特之 间的独立性较好。相关函数有如下定义： 尽砂【f 】= 少【，z 】，虹刀+ f 】) = x 【，l + f 】j ，【，z 】 ( 2 2 1 3 ) 这里f 是离散的时间时移变量，求和变量进行变换又可以得到： 如 r 】一x 以】y m f 】 ( 2 2 - 1 4 ) 相关函数是衡量随机数算法( 发生器) 的重要函数，通过计算相 关函数，我们可以判断随机数算法( 发生器) 的输出的相关性如何， 并以此为依据判断输出序列的随机性的好坏。 2 2 6 随机序列的评价 什么样的随机序列才是高质量的随机序列? 又该如何评价一个随 机算法( 发生器) 的好坏? 因为研究的对象是具有不确定性的系统， 就不可能有任何模式化、公式化的结论。但是在实际应用中，我们也 关丁随机数生成算法的研究 确实需要一个较为合理的评价体系。 2 2 6 1 随机序列的测试工具 不管是真随机数序列还是伪随机数序列，要想用于实际都必须通 过随机性测试。目前仅常用的随机性测试工具就有2 0 0 多个，但每一 个测试工具也仅仅可以代表随机性的一个方面，绝对无法代表随机性 的所有方面。即使由任何由有限个检验组成的子集也无法代表，所以 不管是谁，都无法设计出一个检验工具，只要某个随机序列通过了这 个工具的检验就可以说这个序列是随机的了。 2 - 2 - 6 2 随机测试工具的意义 首先，可以帮助评价一个随机数算法( 发生器) ，并对最终确认该 随机数算法( 发生器) 所生成的随机序列的质量的高低【1 9 】。 其次，有助于检查随机数算法( 发生器) 实现上的错误，比如对 一个加密码算法来说，其确实是安全的，但是随机源的实现出了错， 导致出现了不随机的序列，而通过随机性测试就可以发现这类问题。 目前有许多随机性测试工具软件，比较常用的如澳大利亚昆士兰 理工大学信息安全研究中心设计的c 帅t x s 随机性测试工具；美国佛 罗里达州州立大学设计的d i e h a r d 随机性测试工具；d o n a r dk j l u t h 在其t h ea r to f c o m p u t e rp r o g r 锄m i n g 一书中提出的随机性测试； 美国国家标准技术研究所( n i s t ) 推出的f i p sp u b1 4 0 1 、1 4 0 2 随 机性测试工具【2 0 2 1 ，2 2 】等等。 2 2 7 基本的随机序列测试方法 这里为了更加具体，以目前使用得最多的测试工具集n i s tf i p s p u b1 4 0 2 为例，来介绍基本的测试方面。 高校教师4 ：职硕i ：学位论文 2 2 - 7 1 均匀性检验( 频率检验) 1 ) m o n o b i t 测试：计算从测试位流中提取的2 0 ，o o o 位中的o 和 1 的个数。若0 和l 的个数都在9 ，6 5 4 1 0 ，3 4 6 范围之内，则通过 m o n o b i t 测试。 2 ) 序偶测试：计算位流中o o ，0 1 ，1 0 ，l l 这4 个比特对出现 的概率是否近似相等。设位流长度为n ，在所有相邻两项中，分别统 计o o ， 0 l ，l o ， 1 1 出现的次数，依次记为n 0 0 、n o l 、n l o 、n l l 计 算统计量，其中n o 与n 。分别为在此比特流中o 与l 出现的数目。 7 7 = 三( 碥+ 孵i + 碥+ 碥) 一兰( 斫+ 砰) + l ( 2 2 1 5 ) r i l，i 设标准水平为a o 0 0 5 o o l o ，若7 7 z ( 2 ) ，则通过序偶测试。 2 - 2 7 2 独立性检验 1 ) 长度m 的扑克测试：计算位流中每个长度为m 的不重叠子块 出现的次数是否近似相等。设序列长度为n ，令m 是一个满足 i 旦i 5 木2 m 的正整数，= i 旦i ，将此位流依次拆分成厂个不相交的 l ，咒jl ，玎j 部分，每部分长为m ，并令z 表示第i 种长度为m 的子块出现的次数 ( o i 2 m 1 ) ，计算统计量 ， 埘 7 7 = 每z 2 一， ( 2 2 - 1 6 ) 上 f 设标准水平为a o 0 0 5 o o l o 】，若7 7 z ( 2 历一1 ) ，则通过长度m 的扑 克测试。 2 ) 游程测试：计算提取的2 0 ，o o o 位的比特流中各种游程的个数 ( 游程长度指的是由位构成的数据流中各个位符连续重复出现而形成 的位符串长度) ，长度大于6 的按6 记，若统计数据与( 表2 1 ) 相一 致时，则通过游程测试。 关丁随机数生成算法的研究 表2 1 各种游程的合理数目 游程长度通过数目 1 2 3 4 5 6 + 2 ，3 1 5 2 ，6 8 5 l ，1 1 4 1 ，3 8 6 5 2 7 7 2 3 2 4 0 3 8 4 1 0 3 2 0 9 1 0 3 2 0 9 2 3 熵( e n t r o p y ) 在人们认识世界的过程中，先后发现了物质、能量与信息，其中 关键的几个物理量有质量、能量、信息量。人们认识能量的本质是从 热力学开始的，并在对可逆与不可逆过程的研究中，定义了一个非常 重要的物理量墒2 3 1 。熵概念的提出，极大的扩展了人类的视野， 其后信息论的创始人s h a n n o n 对熵进行了泛化，提出了信息熵的概念。 在信息论中，熵值的大小用作对某事件不确定度( 混乱程度、复杂程 度) 的度量。 2 3 1 熵的概念 假定事件五，发生时的信息量为i ( 置) ，发生概率p ( 鼍) ，那么 对其信息量的定义为： ，( 置) = 一l 0 9 2 尸( 五) 单位为( b i t ) ( 2 3 一1 ) 由上式( 2 3 1 ) 我们可以看出事件发生的概率越低所含有的信息 量越多。设事件集x = k i 江1 ，2 ，z j ，t 出现的概率为尸( t ) o ，且 厅 尸( t ) = l 。那么对于事件x 的熵的定义为： j = 1 疗 日( x ) = 一尸( 葺) l 0 9 2p ( t ) 单位为( b i t ) ( 2 3 _ 2 ) f = l 上式( 2 3 2 ) 表明进行排列的所有事件的平均信息量，在事件发 生概率相等时为最大。其中h ( x ) 表示事件集x 中事件出现的平均不 确定性，或者为确定事件集x 中出现一个事件平均所需要的信息量( 观 赢校教师a 职硕i ：学位论义 测之前) ，或事件集x 每出现一个事件平均给出的信息量( 观测之后) 。 那么事件集x 相对于事件y ，y 的条件熵为： h ( x i y j ) = 一尸( 一陟，) l 0 9 2 尸( t l 少_ ，) ( 2 3 3 ) f = l 而事件集x 相对于事件集y 的条件熵定义为： h ( x 陟) = 一尸( 巧) h ( x i 少，) = 一尸( 乃) j p ( i 乃) l 0 9 2 尸( t i 少- ，) = i_ ，= lf - l ( 2 3 4 ) 上式( 2 3 4 ) 表示观测到集y 后集x 还保留的不确定性。如果将x 视为一个系统的输入空间，则y 视为系统的输出空间。在通信中，通 常将条件熵h ( x 陟) 称为含糊度( e q u i v a c a t i o n ) 。 2 3 2 信息熵 熵的概念起源于对热力学的研究，最早提出这一名称的是物理学 家克劳修斯，现在称为热力学熵。它是热力学系统的一个状态函数， 即： s = 阵 ( 2 3 - 5 ) j 1 1 其中q 是热量，t 是绝对温度。物理学家玻尔兹曼，在统计热力 学的研究中发现了热力学熵的统计意义，即热力学熵与热力学概率的 关系： so cl nq ( 2 3 6 ) 其中q 是指一个物理系统在特定宏观态条件下所对应的微观状态数。 1 9 0 0 年普朗克常数发现之后得到了玻尔兹曼关系式： s = 尼l n q ( 2 3 7 ) 热力学熵的统计意义是：它是系统无序度的度量，一个系统状态的有 序度越低，那么它的熵值就越高；反之，一个系统越有序，它的熵值 就越低。 关丁随机数生成算法的研究 2 3 3 熵值的最大化 对信息熵度量的意义是：当确定一个随机变量的值之后，我们就 获得了信息，我们获得的信息量的大小与随机变量的随机性强弱有关， 随机变量的随机性越小我们获得的信息量就越大；信息量越大，体系 结构越规则，功能越完善，熵值就越小。反之，随机变量的随机性越 大我们获得的信息量就越小，熵值就越大。 所以为了从现行计算机体系中( 精确有序) 获取高质量的随机序 列，就必须在现行计算机体系以外尽可能多地引