（电路与系统专业论文）基于tdercs混沌系统的hash函数的设计与分析.pdf

硕士学位论文 摘要 2 0 0 4 年以来，我国学者相继成功碰撞了国际上广泛应用的两大 传统h a s h 算法m d 5 和s h a - 1 ，引起密码学界严重关注，掀起了新 一波h a s h 算法的研究热潮。本文在基于切延迟椭圆反射腔映射混沌 系统( t a n g e n t - d e l a ye l l i p s er e f l e c t i n gc a v i 纱m a ps y s t e m ，t d - e r c s ) 的理论分析和随机性检测实验基础上，精心构造了一个混沌h a s h 算 法t h a ( t d - e r c s h a s ha l g o r i t h m ) ，理论分析和实验测试表明，t h a 是目前可以取代m d 5 和s h a - 1 的一种理想算法。本文的主要研究成 果为：1 ) 采用n i s t 随机性测试软件包全面测试了t d - e r c s 原始混 沌序列每一位的随机性，结果表明大部分位的随机性很好，有几位随 机性较差，针对这种情况，提出了序列生成方法的改进措施，使得改 进后的混沌序列每一位都具有很好的随机性，为构造t h a 算法提供 了坚实的安全基础；2 ) 详细规划地描述了t h a 算法，以便算法的软 硬件实现；3 ) 针对现有的两种测试碰撞性方法的不完整性，分别提 出了描述碰撞性的两个理论模型，从理论上证明了两个碰撞性量化定 理，给出了两个碰撞性量化准则，并完善了这两种量化测试方法，增 加了测试的可比较性：4 ) 应用第二碰撞性量化准则，分析了h a s h 取值的合理位置，结果与n i s t 随机性测试十分吻合，从实验上证明 了第二准则的准确性；5 ) 应用提出的这两个碰撞性量化准则，比较 分析了t h a 算法与其他传统h a s h 算法以及现有混沌h a s h 算法的抗 碰撞性，同时也比较分析了t h a 算法与传统h a s h 算法的初值敏感性、 混乱散乱性和运算速度，结果表明，t h a 算法拥有更好的抗碰撞性、 混乱散乱性，很好的初值敏感性和较快的计算速度，是一种比较理想 的安全h a s h 算法。 关键词c h a o s ，t d e r c s ，h a s h ，n i s t 统计测试，碰撞性 硕士学位论文 s i n c e2 0 0 4 ，t w ot r a d i t i o n a lh a s hf u n c t i o n s ，m d 5a n ds h a 1 ，w h i c ha r e a p p l i e di n t e r n a t i o n a l l 3 , h a v eb e e nc o l l i d e ds u c c e s s f u l l yo n ea f t e ra n o t h e r b ys c h o l a r s 丘- o mo u rc o u n t r y , w h i c hh a sc a u s e dw i d ep u b l i cc o n c e mi n c r y p t o g r a p h y , a n dc a l l e df o rc o n c e r t e de f f o r tt od e v e l o pn e wh a s h a l g o r i t h m s i nt h i sd i s s e r t a t i o n an e w c h a o t i ch a s ha l g o r i t h m , t d e r c s h a s ha l g o r i t h m , 删f o rs h o r t , i sc o n s t r u c t e de l a b o r a t e l yb a s e do l lt h e t h e o r e t i ca n a l y s i sa n dr a n d o mt e s t so ft a n g e n t - d e l a ye l l i p s er e f l e c t i n g c a v i t ym a ps y s t e m 。1 1 t c sf o rs h o r t t h e o r e t i ca n a l y s i sa n d e x p e r i m e n tt e s t ss h o wt h a tt h ai sa ni d e a la l g o r i t h mt h a tc a nr e p l a c e m d 5a n ds h a - 1 1 1 l em a i nr e s e a r c hr e s u l t sa r e ：1 1r a n d o m n e s so fe a c h b i ti no r i g i n a lc h a o t i cs e q u e n c eo f t d e r c si sc o m p l e t e l yt e s t e dt h r o u g h n i s tr a n d o ms t a t i s t i ct e s ts u i t e t h er e s u l ts h o w st h a tt h em o s tb i t s r a n d o m n e s si sv e r yg o o d , b u tt h e r ea r eaf e wb i t so fw o l - 跎r a n d o m n e s s t h eg e n e r a t i v em e t h o do fs e q u e n c ei si m p r o v e d , s ot h a te a c hb i to f i m p r o v e dc h a o t i cs e q u e n c eh a sg o o dr a n d o m n e s s ，w h i c hp r o v i d e ss o l i d s a f e l yf o u n d a t i o nf o r1 h a ：2 ) d e t a i l e da n ds t a n d a r d i z e dd e s c r i p t i o no f t h ai s 百v e i l ，f o rr e a l i z a t i o no f a l g o r i t h mi ns o f to rh a r d w a r e ；3 ) f o rt h e i n c o m p l e t eo f t w oe x i s t i n gc o l l i s i o nt e s tm e t h o d s ，t w ot h e o r e t i c a lm o d e l s o fc o l l i s i o nd e s c r i p t i o na r ei n t r o d u c e d , t w oc o l l i s i o nq u a n t i f i c a t i o n t h e o r e m sa r ep r o v e dt h e o r e t i c a l l y , t w oc o l l i s i o nq u a n t i f i c a t i o ns t a n d a r d s a r eg i v e n , a n dt h e s et w ot e s tm e t h o d sa r ci m p r o v e db yi n c r e a s i n gt h e i r c o m p a r i s o n ；钔1 1 他r e a s o n a b l ep o s i t i t ot a k ea sh a s hv a l u ei sa n a l y z e d w i t ht h ea p p l i c a t i o no ft h es e c o n dc o l l i s i o nq u a n t i f i c a t i o ns t a n d a r d t h e r e s u l ti si na c c o r d a n c ew i t hn i s ts t a t i s t i ct e s tr e s u l lw h i c hp r o v e dt h e a c c u r a c yo f 也es e c o n ds t a n d a r di ne x p e r i m e n t ；5 1t h ec o l l i s i o no ft h a w i t ho t h e rt r a d i t i o n a lh a s ha l g o r i t h m sa n de x i s t i n gc h a o t i ch a s h a l g o r i t h m si sa n a l y z e dr e l a t i v e l yw i t ht h ea p p l i c a t i o no ft h e s et w o c o l l i s i o nq u a n t i f i c a t i o ns t a n d a r d s ，s oa ss e n s i t i v i t yo fi n i t i a lv a l u e s ， d i f f u s i o n , c o n f u s i o na n dc a l c u l a t i o ns p e ；e do fn aw i t ho t h e rt r a d i t i o n a l h a s ha l g o r i t h m s n l er e s u l t ss h o wt h a tt h ah a sb e t t e rc o l l i s i o n , d i f f u s i o na n dc o n f u s i o n , v e r yg o o ds e n s i t i v i t yo fi n i t i a lv a l u e sa n dq u i c k s p e e d ，i sam o r ei d e a lc r y p t o g r a p h yh a s hf u n c t i o n 旺yw o r d s c h a o s 。t d - e r c s ，h a s h , n i s ts t a t i s t i ct e s t , c o l l i s i o n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。论文主要是自己的研究所得，除了己注明的地 方外，不包含其他人已经发表或撰写过的研究成果，也不包含为获得 中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献，已在论文的致谢语中作了说明。 作者签名：盔熏丕堡吼2 1 1 2 年芏月卫日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，l i p 学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其他手段保存学位论文； 学校可根据国家或湖南省有关部门的规定，送交学位论文。对以上规 定中的任何一项，本人表示同意，并愿意提供使用。 储躲燃聊妣些掣期：坦吐月鲨日 硕士学位论文第一章绪论 第一章绪论 随着电子商务的发展，网上银行、网上合同、电子签名等应用越来越广泛， 网络已经成为我们生活中不可或缺的一部分。但是，电子商务在给我们的工作生 活带来便捷的同时，也不可避免存在着安全隐患。 安全h a s h 函数是目前国际电子签名及其他密码应用领域中的关键技术之 一。在现代密码学中，安全h a s h 函数广泛应用于完整性检测、数字认证，结合 公钥算法用于数字签名。安全h a s h 函数是构筑现代安全基础设施的基石当前 几乎所有的安全应用都在使用着安全h a s h 函数。绝大多数加密协议都依赖着 h a s h 函数的安全性。 然而，一直受到广泛应用的两大安全h a s h 函数m d 5 、s h a _ i 2 ，分别于 2 0 0 4 年8 月和2 0 0 5 年1 月，相继被山东大学王小云教授带领的密码学研究小组 成功“碰撞”【3 朋。这一密码分析的重大突破，再次敲响了电子商务安全的警钟， 在国际社会尤其是国际密码学领域引起极大反响。 国际密码学会议( c r y p t o 2 0 0 4 ) 的总结报告如此写道【5 】：“我们该怎么办? m d 5 被重创了；它即将从应用中淘汰。s h a - i 仍然活着，但也见到了它的末日。 现在就得开始更换s h a - i 了。但是选用什么样的算法，这需要密码研究人员达 到共识。” 1 1 传统h a s h 函数概述 传统h a s h 函数是相对混沌h a s h 函数而言的。本节简要介绍安全h a s h 函数 的一般定义及应用，传统h a s h 函数的经典算法结构以及安全性问题。 1 1 1 密码学的两种基本功能：保密性与真实性 密码学的基本功能之一是提供保密性，让非授权者无法知道消息的内容。此 外，密码学还能对消息的许多其他属性提供保证，这实质上就是密码学的另一基 本功能，提供真实性主要包括【6 j ： l 、鉴别：消息的接受者应该能够确认消息的来源。 2 、完整性：消息的接受者应该能够验证消息在传输过程中没有被篡改。 3 、不可否认性：发送方不能否认已发送的消息。 保密性自密码学创立以来一直是研究的重点，而真实性则是在计算机发展起 来之后，特别是多用户系统以及网络蓬勃发展之后，才受到重视【7 一。今天，网 硕士学位论文 第一章绪论 络已经普及到社会的各个领域，技术上对消息真实性的保护显得尤为重要。而安 全h a s h 函数在保护真实性的过程中担当了一个主要角色。在真实性的三大内容 中，鉴别和完整性校验是安全h a s h 函数的主要功能；尽管不可否认性主要是由 数字签名提供的，但安全h a s h 函数却是数字签名中提高运算速度和处理海量数 据不可或缺的基础成分之一。 1 1 2 安全h a s h 函数 安全h a s h 函数是满足一定安全性条件的单向压缩函数。所谓单向性，是指 不能从函数的像找到它的原像，也不必恢复原像，故可以采用压缩函数。 压缩函数有许多优点，如节省存储空问、减少后续算法的数据量，具有高速 处理海量数据的能力等。然而，由于压缩性，必然会导致碰撞，即不同的原像可 能产生相同的像。所以安全h a s h 函数必须满足一定的安全性条件。 安全h a s h 函数是一个从无限集到加b i t 有限集的映射忍即 h ： o ，1 ) 。斗 o ，l 。 其中的，就是h a s h 值的长度，满足三个安全性要求睁1 1 1 ： 1 、单向性( p r e i m a g e - r e s i s t a n c e ) ；对任何给定的h a s h 值h ，找到满足麒曲= h 的j 在计算上不可行。对其进行穷举攻击的计算复杂度为z ； 2 、抗弱碰撞性( 2 n d - p r e i m a g e - r e s i s t a n c e ) ：对任何给定的消息x ，找到满足 y x 且h ( x ) = h f y ) 的y 在计算上不可行对其进行穷举攻击的计算复杂度为矿； 3 、抗强碰撞性( c o l l i s i o n - r e s i s t a n c e ) ：找到任何满足x y 且域炉硬y ) 的偶 对o ，y ) 在计算上不可行。可对其进行一般的生日攻击，计算复杂度为z 晚。根据 目前的分布式计算能力，在设计新的安全h a s h 函数时，其h a s h 值的长度至少 应为1 6 0 b i t 。 三个安全性要求中，单向性是必要的，而弱碰撞攻击与强碰撞攻击，可用“生 日悖论( b i r t h d a y p a r a d o x ) ” 1 2 1 原理进行解释。“生日悖论”表述为：如果你想找 出某人和你的生日相同，需要询问2 5 3 人，其中至少能找到一人的概率是5 0 ； 但是如果你只想找到某两个人具有相同的生日，而不管这两人是谁，那么你只需 询问2 3 人，其中两人具有相同生日的概率是5 0 。前者对应抗弱碰撞性，后者 对应抗强碰撞性。 1 1 3 传统h a s h 函数的算法结构 传统h a s h 函数均具有 如r 材p d 聊g 删迭代结构f 1 1 1 3 ，1 4 1 ，如m i m 堋，m d 5 t l i ， 2 硕士学位论文 第一章绪论 r i p e m d - 1 6 0 旧，s h a 1 嘲等等。m e r k l e - d a m g a r d 结构类似于迭代分组加密中的 乘积加密，如图1 1 所示，具体算法流程为： l 、消息报文处理阶段该阶段可以细化为3 个步骤： a 、将消息报文转化为二进制序列； b 、在二进制序列末尾填充p a d d i n g ，即一个l 和多个0 ，即“1 0 0 0 ”， 以及原始消息长度的二进制编码，使填充后的二进制序列总长度是h a s h 值 长度的三倍。这个操作通常又称为“m d 增强”； c 、将填充后的消息进行分组，得到分组序列：m ，m 2 ，m l 。 2 、迭代压缩阶段。首先设置压缩函数的初始值( 1 n i t i a lv a l u e ) ，即令h o = i v ；然后不断迭代中间的压缩函数日= c ( z t l ，m ) ，f = i ，三。 3 、取h a s h 值阶段。简单地取迭代压缩阶段的输出结果为h a s h 值，即日( 肘) 。吼。 1 1 4 密码分析的新突破 c 7 q i 厂一 - 叶 m d 5 t l 】和s h a 1 1 2 是当前国际通行的两大安全h a s h 函数标准算法，应用广 泛。m d 5 由国际著名密码学家、图灵奖获得者、公钥加密算法r s a 创始人r i v e s t 设计，s h a - 1 是由美国标准技术所n i s t 与美国国家安全局n s a 推出的标准 2 0 0 4 年8 月，山东大学王小云教授带领的密码学研究小组，成功“碰撞”了 m d 5 和m d 4 、h a v a l 1 2 8 、r i p e m d 等一系列h a s h 算法【3 】这种攻击已经能 够产生对m d 5 的实际碰撞，尽管只是所谓的理论上无意义的随机碰撞。但是， 最近l e n s t r a 、王小云和w e g e r i ”】利用m d 5 的随机碰撞，成功伪造了符合x 5 0 9 标准的数字证书，进一步说明m d 5 碰撞不仅仅是理论结果，而且可以导致实际 的攻击。m d 5 的退出已迫在眉睫 2 0 0 5 年2 月，同一个研究小组，首次1 4 】将“碰撞”s h a - 1 算法( 1 6 0 位h a s h 值) 的计算复杂度从理想值2 舶锐减到2 卯。随后，改进的攻击方法【1 研将复杂度 进一步降低到2 6 ，尽管还没有产生对s h a 1 的实际碰撞，但是2 6 3 的计算复杂 度已经可以用现在的分布式计算能力进行暴力攻击了。这一系列密码分析上的突 硕士学位论文 第一章绪论 破，引起了国际社会、尤其是国际密码学界的极大关注。 对此，美国国家技术与标准局( n 1 s t ) 部署了三个对策【1 9 1 。 首先，计划2 0 1 0 年之前在数字签名中采用s h a - 2 系列的h a s h 函数( 即 s h a 2 2 4 、s h a - 2 5 6 、s h a - 3 8 4 和s h a - 5 1 2 等1 2 】) 来逐步淘汰s h a 1 。 第二，鼓励h a s h 函数研究者更好地理解h a s h 函数的设计和攻击，以备选 择其它安全性能更好的h a s h 函数。n i s t 举办的h a s h 函数w 移疏疏捌也正如火 如茶地进行着。 最后，就是开始一场选择新的安全h a s h 函数标准的竞赛，像当年成功选出 a e s ( a d v a n c e d e n c r y p t i o ns t a n d a r d ) 一样。 因此，安全h a s h 函数理论和密码分析正处在一个快速发展时期，本课题的 研究具有重大的理论意义和实际应用价值。 1 2 混沌与h a s h 函数 1 2 1 混沌与密码学的对应关系 自从二十世纪8 0 年代以来，应用数字化混沌系统构造新型密码系统的想法 受到了越来越多的关注。这种想法来自于混沌理论与纯粹密码学之间存在着的天 然联系：强混沌系统的动力学特性大致对应着高强度密码系统的某些安全特征。 具有良好混合性的传统密码系统又暗示着拟混沌现象。一些研究者深入研究过这 两者之间的紧密联系 2 3 , 2 4 1 许多混沌系统的基本特性，如遍历性( e r g o d i c i 纱) 、 确定性( e x a c t n e s s ) 和对初始条件的敏感性等等，都可以和密码学中的混乱 ( c o n f u s i o n ) 和散布( d i f f 谜i o n ) 概念联系起来。表1 1 列出了两者之问各特性 的对应关系刚。 表1 - 1 混沌与密码学的特性对应关系 事实上，在密码学中使用混乱的想法可以追溯到s h a n n o n 在1 9 4 9 年发表的 经典论文( c o m m u n i c a t i o nt h e o r yo f s e c r e c ys y s t e m s 2 5 1 。文中指出，好的保密 4 硕士学位论文 第一章绪论 系统需要好的混合变换( m i x i n gt r a n s f o r m a a o n ) ，即基本的。r o l l e d - o u ta n d f o m e d - o v e r ”操作得到。这显然与可以引发混沌的“拉伸并折叠( s t r e t c h - a n d - f o l d ) ” 操作极为类似 1 2 2 混沌h a s h 函数的研究现状 基于计算复杂度假设的传统h a s h 函数需要大量复杂的异或等逻辑运算。由 于状态空间有限以及不可分析性，潜伏着某些设计者难以发现的安全漏洞 混沌系统天然具有的密码学特性，使得应用混沌系统构造密码算法成为一大 研究热点由于混沌系统产生的伪随机序列天然拥有构造h a s h 函数所要求的很 好的混乱散布性、初值敏感性、单向性，故人们尝试用混沌系统来构造安全h a s h 函数。近年来，已有不少有关混沌h a s h 函数的研究报告下面从三个方面来简 要介绍下相关的研究进展。 首先从发表的论文情况分析。图1 2 和图1 3 分别是在凹( e n g i n e e r i n g i n d e x ) 上同时检索“h a s h ”和“c h a o ”两个关键字的论文发表结果的年份分布图和语言 分布图。从图1 - 2 中可以看出，混沌h a s h 函数从1 9 9 9 年以来逐渐有人开始研究， 最近3 年论文数量不断上升。从图l - 2 中可以看出，用中文发表的论文超过了l 3 ， 而且英文论文中也不乏有国内研究者发表的，说明国内研究者是混沌h a s h 函数 研究的主要力量之一 图1 - 2 日检索结果的年份分布图 图1 - 3 日检索结果的话言分布图 其次，是混沌h a s h 函数的算法设计方案。主要集中在两个方面，一个是基 于的混沌系统，另一个就是h a s h 算法的设计方案 混沌系统是混沌h a s h 函数的基本结构，用于构造混沌h a s h 函数的混沌系统 有：l o g i s t w 映射口纯硐、分段线性映射例、h e n o n 映射嗍、时空混沌系统【3 1 3 3 1 、 二维超混沌系统凹、逐段非线性混沌映射嗍、复合离散混沌动力系统嗍等也 5 硕士学位论文 第一章绪论 有试图通过在多个混沌系统之间切换1 3 7 来提高安全性能的设计方案。但是这些 混沌系统的安全性大多还不够充分，有的还尚待进一步安全性分析。 至于现有混沌h a s h 函数的算法设计方案，王继志等人在一类基于混沌映 射构造h a s h 函数方法的碰撞缺陷1 3 8 】中证明文献【2 7 ，3 0 ，3 2 ，3 4 ，3 7 】中的方案都存 在着碰撞缺陷。该文中没有研究过的其它方案与这五种设计方案大致相似，可能 也存在着类似的问题。实际上，这类碰撞缺陷在传统h a s h 匾数设计中就被人认 识了，在消息报文处理阶段采用“m d 加强”，通过在原始数据末尾填充p a d d i n g 与原始长度的二迸制表示就是为了消除这类碰撞缺陷。 最后，是h a s h 函数的安全性测试方法。h a s h 函数的安全性测试主要包括混 乱与散乱性测试、碰撞性测试。混乱与散乱性测试是所有加密算法共有的一种安 全性测试，已经有成熟的理论基础i t , s l 。碰撞性测试是h a s h 函数安全性分析的主 要测试之一，目前测试理论还不成熟。现有的两种碰撞性测试方法0 0 - 3 5 ) 7 t 棚1 绘出 的测试结果还不能从理论上判断h a s h 函数抗碰撞性的好坏 1 2 3t d - e r c s 混沌系统的安全性 用混沌系统构造综合性能优异的h a s h 函数，关键取决于混沌系统自身对应 算法安全性的特质，这些特质可称为混沌的安全性条件。盛利元等人已经归纳出 了五项安全性条件t 3 9 1 ；1 ) 离散映射；2 ) 全域混沌；3 ) 全域零相关；4 ) 巨大 的参数和初值空间；5 ) 极强的抗退化能力。目前还没有发现一个自然的混沌系 统能够同时满足这五个充分条件。 切延迟椭圆反射腔映射系统 1 0 0 0 ) ，则可认定所测试算法为信任度高的随机序列 表2 1 脚的1 5 项核心统计测试 2 、p - v a l u e 分布的均匀性( u n i f o r m i t y ) 测试算法独立生成的m 组随机序列，依据各项测试所得p - v a l u e 值，按下式 。一芒一焉) 2 z 2 = 善半 扣d 三 ( 2 2 ) 其中，只是在子区间附一1 ) x o 1 ，i x o 1 ) 的p - v a l u e 的数目，m 是测试序列的数目 然后，计算p - v a l u e s 的p - v a l u e ，即 刚卿= 咖c ( 三9 ，争( 2 - 3 ) 其中，i g a m c ( n ，x ) 是不完全g a m m a 函数。 最后，判断均匀性。如果p - v a l u e r 0 0 0 0 1 ，则测试序列可以认为是均匀分 布的。 9 硕士学位论文第二章t d - e r c s 混沌系统的n i s f 随机性测试 本章采用n i s t 的这两种方法解释测试结果，由s t s 软件包自动完成。 2 2t d - e r c s 混沌系统的随机性 本节先对原序列生成方法产生的序列进行测试，然后根据其随机特性存在的 缺陷，改进序列的生成方法。 2 2 1 原序列生成方法 根据t d - e r c s 混沌系统模型【小) 7 ，4 l 】，其正常态迭代可得到两个相互独立的 归一化实值序列z ( 即 一) 序列) 和k ( 即 t ) 序列) 其中，每个和t 都属于 【o ，l 】区间由于计算机有限精度，只考虑t 和t 小数点后面5 2 - b t 二进制数。 对于【o 1 ) 问的实数，紧跟小数点后面5 2 - 6 豇二迸制数可表示为 o b l b “b b s l b 站b j o l ，j = l 2 , s l ，5 2 显然，1 也可以表示为l b 2 矿扩铲，其中每个6 都是0 。由于每个一和毛都 属于【o ，l 】区间，故其小数点后5 2 6 f ，二进制数可以表示成 o ，l 串，即 分别异或可得 而要1 2 2 0 3 ：5 。1 盖5 2 彩，吖 o ，1 ) ，：l 2 ，5 l ，5 2 l k j 争科女? 砰鬈1 铲 1 ”1 ”。“” x tk j 碱域瑶斌 x 皆娃j - x 8 k | ，j 4 工& ，5 2 取_ 中从第s 位开始连续m 位，依次连接起来得到测试序列，记为置， 置，= 彳”1 蔓蔓”1 z ；巧s “一 同理，可构造测试序列e ，和异或的测试序列磁，即 e ，= 群鲜”。1 ”。1 k 3 。g “。 x k s 。= x k ；x k ；“x 皖x k 4 “x k ；x k 。“ 随机改变t d - e r c s 混沌系统的初始值和参数1 0 0 0 次，可分别得到1 0 0 0 组 相应的测试序列置，、丘，和异或麒。 1 0 硕士学位论文 第二章t d - e r c s 混沌系统的n i s t 随机性测试 2 2 2n 1 s t 测试结果分析 用统计测试软件包髓苫对置，、墨，和异或j 巧，进行统计测试。测试结果 中的测试编号所对应表2 1 中的统计测试项目。 1 通过率分析。 取m = 1 0 0 0 ，根据式( 2 1 ) ，前面1 3 项测试的通过率下界计算均为9 8 0 5 6 1 。第1 4 、1 5 项测试有不同的值，由测试软件给出 图2 1 分别给出了3 组测试序列x k o l j 2 、x k o l ，5 l 和x k 5 2 , o l 的1 5 项核心测试 的通过率测试表明；x k 0 1 5 2 没通过第1 、3 、4 、7 项测试，第8 项测试中也有 几个没通过。尤其是第l 项测试，即频率测试，通过率只有6 9 8 。这说明小数 点后连续5 2 砌组成的序列随机性不好；j a f 0 1 ，t 只有第4 、7 项测试没有通过， 第8 项测试中也有几个没通过，但是这三项的通过率都高于9 5 5 这说明小数 点后连续5 1 6 i f 组成的序列随机性转好，即x k o l s l 的随机性远优于x k o i 5 2 的随 机性：x k s 2 , 0 1 除了第6 、1 3 项测试通过了之外，其他的都没通过，而且第1 4 、 1 5 项根本无法测试，这说明最后1 6 f ，的随机性最差。 鼍1 翅 舅0 8 * 捌0 , 9 6 鲤0 舶 鬟帖 囊 o o2488 o1 21 1 6 碣w o24b 8 t 01 2 1 6 m ，m 0 24b81 01 21 6 翻试蝈号 图2 - 1 - , f f ( - 0 1 , s 2 船岛i j t 和j 蜀鲫l 的通过率 结论：1 ) 薯和屯的最后1 - b i t 是误差位，说明在计算机运算中实数的进位导 致了f 2 和妒的随机性下降，即计算机进位存在系统误差；2 ) 和t 的最后1 - b i t 导致刃岛l 觉没有通过第l 、3 项测试，但由于1 - b i t 在5 2 - b i t 中比重较小，故对其 他1 3 项测试的影响不大。 硕士学位论文 第二章t d - e r c s 混沌系统的n i s t 随机性测试 图2 - 2 分别给出了3 组测试序列x k s ，0 1 、x k 0 6 , 晒和x k 0 5 4 7 的1 5 项核心测试 的通过率。测试表明：x k s l | 0 l 全部通过所有测试，说明小数点后第5 1 础组成的 序列随机性非常好；x k 0 6 全部通过所有测试，这说明小数点后第到516fr46 6 - b i t 的连续二进制串组成的序列随机性非常好；x c o s 其通过率很接近于可接受通过率的最低边界，这说明小数点后第5 - b i t 到5 1 晰 的连续二进制串组成的序列随机性也是可以接受的。 图2 1 与图2 - 2 给出的测试结果表明：x k 0 1 5 2 未能通过第4 、7 、8 项测试， 可能原于小数点后前4 位j ? 和i j 有较差的随机性。 * 捌 舅。舶 * 翊 复o 船 * 1 翅 舅0 9 6 * 甜 02881 01 21 41 6 碣 o246801 21 1 8 巧m o24681 01 21 4 1 8 翻试翁号 图2 - 2x k s l m ，甄崩和j 口岛 7 e j l i 率 图2 3 分别给出了3 组测试序列x k o i o l 、x k i g , 0 l 和朋譬地o l 的1 5 项核心测试 的通过率。测试表明：x k 0 1 o l 除了第l 、2 、3 和1 3 项测试通过了之外，其他的 都没通过，且软件还不能进行第1 4 、1 5 项测试。这说明第1 - b i t 的随机性非常差； x k t 9 0 1 只有第8 项测试没有通过，但其通过率很接近于可接受通过率的最低边 界；x k 2 0 0 i 已经完全通过了所有的测试；这说明第2 0 6 f f 是个临界位，之后的每 都能,1-bit完全通过所有测试。 结合图2 - 2 给出的麒5 i o l 测试结果，可以发现一种变化趋势：小数点后第l ，6 f ， 的随机性最差，但随位的增加，随机性越来越好，到第2 0 6 f f 时完全通过所有的 测试。这个趋势可称为随机性递增趋势，其原因有待进一步的研究。 对于“勰的标准双精度浮点数来说，随机性递增趋势只包括第1 - b i t 到 5 1 船，不包括第5 2 船。如前所述，最后1 研可能是由于计算机进位引入了系 1 2 统误差，导致许多项测试未能通过。 萎0 5 爱 o * 1 翊 翻0 9 0 * 期 曩0 9 8 o2 6b1 01 21 4 ) 吗 o2 篓0 8 囊 o b * 1 辅 鲤0 9 8 681 01 2 1 4 冲 o24 * 奠 鲤0 9 6 6 8 1 0 1 21 4 刮试编号 图2 - 3 x k o l 1 艇l ”lx k 2 0 , o l 的通过率 1 b 0 28 8 1 0 1 21 6 n288 01 21 巧 o2681 01 21 4 翻试编号 图2 - 4 如岛i 脚，硒，雌扣咒 凶脚的通过率 1 6 由于图2 - 3 展示的随机性递增趋势，结合图2 - 2 的艇& 撕和域- 0 5 4 7 ，可以得 到类似于x k 5 2 , o l 对j 岛l j 2 影响的结论：小数点后前4 位和杉的随机性较差， 导致x 硒l , 5 2 的第4 、7 、8 项没有通过测试，也由于它们在5 2 6 打中比重较小，对 硕士学位论文 第二章t d - e r c s 混沌系统的n i s t 随机性测试 x k 0 6 等序列的影响不大。, 4 6 图2 4 分别给出了3 组测试序列x k o l 瑚、x k o s , 0 8 和x c 0 9 0 8 的1 5 项核心测试 的通过率。测试表明：x k o l , 0 5 除了第l 、2 、3 和1 3 项测试通过了之外，其他的 都没通过；x 玛8 0 8 只有第8 和1 5 项测试没有通过；x k 0 9 - 0 8 通过了所有的测试， 这说明，小数点后第9 个连续8 6 豇是第一个能完全通过测试的测试序列。 圈2 4 的这三组数据，测的是连续8 跚组成的序列的随机性。这也进一步体 现了随机性递增趋势，并在第四章的第二碰撞性量化测试中得到了另一种形式的 验证。 2 p - v a l u e 的均匀性分析 x k 5 i o l 、x k 2 0 , o l 、x k 0 6 郑和x k 0 9 通过前述的所有测试项目，其p - v a l u e 的均 匀性测试自然也能通过：x k l 9 , o l 、x k 0 5 , 4 7 和x k o s , 惦略为逊色一些，但也都都通过 了p - v a l u e 的均匀性测试，说明这些数据的均匀性都很好。而随机性比较差的 x k o l , o l 、x k o l j 2 、j ，捌和x k s 2 o l 及x e o l , o g 均未能通过该项测试，即它们的均 匀性不好。 3 针对b l o c k f r e q u e n c yt e s t ( 编号为2 ) 的p - v a l u e 的均匀性分析 唯一例外，序列x k o t , o l 、x k 0 1 5 2 、x k o t ，5 t 和x k o i o s ，针对b l o c k f r e q u e n c yt e s t ， 其测试的通过率都在可接受区间内，而其p - v a l u e 的均匀性却都没有通过。图2 5 给出了这四组序列b l o c k f r e q u e n c y t e s t 的p - v a l u e 分布。可以看出，四组序列都 是由于区问【0 9 ，l 】之间的频率过大，导致了p - v a l u e 的均匀性测试没有通过。 图2 - 5x 碥l , o l 、躏i , 0 s ，x k o l , ，l 和x k o l , 5 2 的b l o c k f r e q u e n c y t e s t 的均匀性 1 4 硕士学位论文 第二章t d - e r c s 混沌系统的n s 随机性测试 图2 - 6 给出了x k 0 2 , o l 、x 酗, o i 、静如o l 和x k 0 2 , 5 0 的b l o c kf r e q u e n c yt e s t 的 p - v a l u e 分布。可以看出，x k 0 2 , o l 、x k 0 4 , o l 这两组序列也是由于区间【o 9 ，1 】之间的 频率过大，导致了p - v a l u e 的均匀性测试没有通过。而j 硒5 0 l 和朋娜则是序列 的通过率在可接受区间内，也通过了p - v a l u e 的均匀性测试。 图2 - 6 朋嘞j i x k 0 4 t 硒5 o i 和翔翔的b l o c k f r e q u e n c yt e s t 的均匀性 图2 - 6 的x k 0 2l 、i 和，结合图2 5 的 ，可以看出,o x k 0 4 , ox k o s , o l- j l 磁l , o lx k s , o ! 序列( s = 1 ，2 ，5 1 ) 的b l o c kf r e q u e n c yt e s t 的均匀性，随着s 的增大，也存在 着一个类似于通过率的递增趋势，可简称为b l o c k f r e q u e n c yt e s t 的均匀性递增趋 势。s - - - - 5 是个临界位，之后的每个1 - b i t 序列都能通过b l o c k f r e q u e n c y t e s t 的均 匀性测试当然，这个趋势同样不包括第5 2 6 豇。 对比图2 - 6 的斌旺如和图2 - 5 的x k o i j l ，结合b l o c k f r e q u e n c y t e s t 的均匀性 递增趋势，可以得出类似于通过率的结论：正是由于小数点后前4 位0 和杉的 b l o c k f r e q u e n c yt e s t 的均匀性比较差，导致黝南l j l 的均匀性测试未能通过。 2 2 3 序列生成方法的改进与测试结果分析 根据2 2 节的测试结果，由2 1 节描述的测试序列存在两种随机性缺陷：一 是存在着随机性递增趋势和b l o c k f r e q u e n c yt e s t 的均匀性递增趋势，即随机性分 布不均匀；二是最后1 6 f ，的随机性很差。 仔细分析，前者与t d - e r c s 混沌系统的参数的取值范围有关，发现太 硕士学位论文第二章t d - e r c s 混沌系统的n i s t 箍机性铡试 小时，系统的状态值工的均匀分布被破坏【柏】，可以通过改变系统的参数取值范围 来改善其随机性；后者是由计算机实数进位的系统误差所致，需改进序列生成方 法来隐蔽这种缺陷。 首先，改变系统的参数范围。将t z 的取值范围由原来的理论值域( 仉l 】缩小到 ( o 0 5 ，1 】。仍然采用2 1 节的序列生成方法，生成的序列用j 盔表示。 图2 5 给出了麒0 的测试结果，分别为3 组测试序列x k g , 5 i 、砼磋o l 和 朋0 i 的1 5 项核心测试的通过率。测试表明：艇矗朋和璐0 1 通过了所有的测 试；x k 6 。，仅第8 项中的个别测试没有通过，且其通过率十分接近可接受通过率 的下限。 弼 要 舅。舶 * 翊 爱0 j 8 * 1 捌 咧0 9 8 02_681 021 8 叫0 0288 0 21 4 b 02881 01 21 8 翻试编号 田2 - 5 x k a 曩、艘墨 o t 和积矗o l 的通过率 显然，的取值范围缩小到( o 0 5 ，l 】后，小数点后5 1 6 豇串0 和卅均能通过 各种测试，每个1 船的x f 和t ? ，完全能通过测试的序列上升到第1 2 6 豇，随机 性得到了较大幅度的改善，各项测试的通过率的上升了5 。但是，由于测试要 求极高，小数点后4 位掣和l ，及第5 2 6 f ，仍均未能完全通过测试，故需进一步 改进序列生成方法。改进方法如下 将墨的小数点后5 2 刍f f 循环右移2 跚并倒序，再与t 小数点后5 2 跚依次异 或，得到5 2 船的t ，即 f = # ho ，j = l ，2 ，3 ，4 9 ，5 0 巧”= 妒o f 2 = 彳1 0 砰2 硕士学位论文 第二章t d - e r c s 混沌系统的n i s