（信号与信息处理专业论文）基于统计随机性的hash函数安全评估模型研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着网络技术的发展和普及，人类社会已经进入到互联网时代，人们的生 活也越来越离不开网络，网络购物、网上交易、电子政务、电子税务、电子商 务等的普及为人们带来了巨大的便利，但是也对信息的安全性提出了更高的要 求，因此提高数据的安全性已经成为日益紧迫的研究课题。h a s h 函数在保证 信息安全方面有着重要的作用，因此选用安全的单向h a s h 函数有着重要的意 义，而安全的h a s h 函数在理论上是很难证明的，但是在理论上最重要的两点 是单向性和伪随机性。 本文就是对h a s h 函数的随机性评估进行研究，提出了一个随机性评估的 指标体系和模型，利用模糊数学中的隶属度函数将测得的指标值定量信息模糊 化，然后以模糊综合评估为基础，利用层次比较法和信息熵的方法对指标或者 子特性进行权重分配，最后经过层层评估，得到对h a s h 函数随机性的综合量 化评估结果。 论文首先介绍了关于密码随机性检验的背景和意义，国内外研究现状，针 对传统迭代结构的h a s h 函数和混沌结构的h a s h 函数的随机性检验方法都给予 了介绍。 其次，简要介绍了随机性检测基础知识，对于h a s h 函数随机性检测的测 试项进行分类，建立h a s h 函数随机性评估指标体系，对于单个指标的测试值 采用模糊数学中的隶属度函数方法将定量信息模糊化，然后按照模糊综合评估 模型，自下而上逐层进行评估，最后得到对h a s h 函数的综合量化评估结果， 并且应用此评估模型对s h a 1 的随机性进行了评测。 然后，对评估模型中权重赋值的方法进行了改进，应用层次比较法和信息 熵赋权相结合的方法，对指标项或者子特性的权重进行赋值，应用此改进的评 估方法，对s h a 1 的随机性进行了评测，评测效果得到了改善，此外还对于 较新的s k e i n 函数和一个典型的混沌h a s h 函数进行了评估。 最后，对本文的研究内容和主要工作进行总结，指出其中的不足和需要改 进的方面，对下一步的研究方向和内容进行规划。 关键词t随机性；h a s h 函数；隶属度函数；a h p ；信息熵 a bs t r a c t w i t ht h ed e v e l o p m e n to fs c i e n c ea n d t e c h n o l o g y ，h u m a ns o c i e t yh a se n t e r e d t h ei n t e m e ta g e ，p e o p l e sl i v e sa r en o w d e p e n d e n to nt h en e t w o r k ，t h ep o p u l a r i t y o fo n l i n es h o p p i n g ，o n l i n et r a n s a c t i o n s ，e g o v e r n m e n t ，e t a x ，e c o m m e r c ea n d o t h e r s t h a t p r o v i d e sc o n v e n i e n c et op e o p l el i v e sh a sd r a m a t i c a l l yi n c r e a s e d i nd o i n g s o ， t h ed e m a n df o r i n f o r m a t i o n s e c u r i t yo r d a t a s e c u r i t yh a sa l s ob e c o m ea n m c r e a s l n g l yu r g e n tr e s e a r c ht o p i c h a s hf u n c t i o n p l a y s a n i m p o r t a n tr o l ei n e n s u n n g1 n f o r m a t i o ns e c u r i t y ，c h o o s es a f eo n e w a yh a s hf u n c t i o ni s i m p o r t a n t ， a n dt h es e c u r eh a s hf u n c t i o n ，i nt h e o r yi ti sd i f f i c u l tt op r o v e ，b u ti nt h e o r vt h em o s t i m p o r t a n tp o i n t si sas i n g l ei s o t r o p i ca n dp s e u d o r a n d o m n e s s ， jn 坫t h e s i sl st os t u d yt h er a n d o m n e s sa s s e s s m e n to ft h eh a s hf u n c t i o n , w h e r e ar a n d o m n e s sa s s e s s m e n t i n d e x s y s t e ma n dm o d e li s p r o p o s e d ，q u a n t i t a t i v e 1 n f o 啪a t i o no ft h ei n d e xv a l u ew i l lb em e a s u r e db yt h em e m b e r s h i pf u n c t i o ni n f u z z ym a t h e m a t i c s ，t h e nb a s e do n f u z z yc o m p r e h e n s i v ee v a l u a t i o n al e v e l c o m p a r a t l v el a wa n da ne n t r o p yl a wi su s e dt o a s s i g nw e i g h t st ot h ei n d i c a t o r so r s u b - f e a t u r e s ，f i n a l l yt h r o u g hl a y e r so fa s s e s s m e n t ，c o m p r e h e n s i v e q u a n t i t a t i v e a s s e s s m e n to ft h er e s u l t so ft h eh a s hf u n c t i o nr a n d o m n e s si s m a d e f 1 r s t t h et h e s i si n t r o d u c e st h eb a c k g r o u n da n ds i g n i f i c a n c eo ft h e p a s s w o r d r a n d o m n e s st e s t ，t h e ng i v et h e r e s e a r c hs t a t u s ，t h e r a n d o m n e s st e s t i n gm e t h o d s f o rt r a d l t l o n a li t e r a t i v es t r u c t u r eo fh a s hf u n c t i o n sa n d t h ec h a o t i cs t r u c t u r ea r e a l s oi n t r o d u c e d s e c o n d l y ，ab r i e fi n t r o d u c t i o ni s g i v e na b o u tt h eb a s i ck n o w l e d g eo ft h e r a n d o m n e s st e s t ，t h e n ，t h eh a s hf u n c t i o nt e s to ft h er a n d o m n e s st e s ta r ec l a s s i f i e d s e tu pt h er a n d o m n e s se v a l u a t i o ni n d e xs y s t e mo fh a s hf u n c t i o n ，t h er a n d o m t e s t r e s u l t sa r ec h a n g e di n t of u z z y u s i n gt h ef u z z ym a t h e m a t i c sm e m b e r s h i pf u n c t i o n ， a n dt h e nb ee v a l u a t e di n a c c o r d a n c ew i t ht h ef u z z yc o m p r e h e n s i v ee v a l u a t i o n m o d e j ，b o t t o m u pl a y e rb yl a y e r ，a n df i n a l l yg e tac o m p r e h e n s i v eq u a n t i t a t i v e a s s e s s m e n to fr e s u l t so ft h eh a s h f u n c t i o n ，t h e na p p l yt h i se v a l u a t i o nm o d e lt o e v a l u a t et h er a n d o m n e s so fs h a 1 1h e n , 1 r e p r o v et h ea s s e s s m e n tm o d e lw e i g h ta s s ig n m e n t m e t h o d ，c o m b i n et h e a p p l i c a t i o nl e v e lc o m p a r i s o na n di n f o r m a t i o ne n t r o p y ，e m p o w e rt h ei n d e xi t e mo r s u b c h a r a c t e r i s t i c so f r i g h t s r e - a s s i g n m e n t ， a p p l i c a t i o no ft h i si m p r o v e d a s s e s s m e n tm e t h o do nt h es h a - ， r a n d o m n e s se v a l u a t i o n ，t h ee v a l u a t i o no ft h e 西南交通大学硕士研究生学位论文第l ll 页 e f f e c th a sb e e ni m p r o v e d ，i na d d i t i o nr e c e n t l yt h es k e i nf u n c t i o na n dat y p i c a l c h a o t i ch a s hf u n c t i o nw e r ea s s e s s e d f i n a l l y ，s u m m a r i z et h ec o n t e n ta n dm a j o rw o r ko ft h i ss t u d y ，p o i n t i n go u tt h e d e f i c i e n c i e sa n da r e a sf o ri m p r o v e m e n t ，ap l a nf o rf u t u r er e s e a r c hd i r e c t i o n sa n d c o n t e n ti sg i v e n k e yw o r d s ：r a n d o m n e s s ；h a s hf u n c t i o n ；m e m b e r s h i pf u n c t i o n ；a h p ； i n f o r m a t i o ne n t r o p y 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 论文研究背景和意义 随着计算机、通信以及网络技术的不断进步，互联网已经成为人们日常生 活中密不可分的一部分，网络购物、网上交易、电子政务、电子税务、电子商 务等越来越普及，为人们的生活带来了巨大的便利，但是也对信息的安全性提 出了更高的要求，因此提高数据的安全性已经成为日益紧迫的研究课题。而密 码学作为保障可信环境的支撑性学科，在信息安全领域发挥着越来越重要的作 用。作为密码学三大原语之一的h a s h 函数，是保证数据完整性、合法性及不 可否认性的关键技术。因此选用相对安全的h a s h 函数，是构建安全信息系统 的核心要素，是保证信息与数据机密性、完整性、真实性最重要的技术之一。 随机序列在密码学中有非常重要的作用，比如密钥的生成，现在所有公开 的加密算法的安全性都依赖于密钥的安全性，而密钥的安全与否和随机序列的 随机性程度密切相关。除此之外，身份认证、数字签名、和众多的通信协议中 都要用到随机序列，著名的密码学家b r u c es c h n e i e r 曾经说：“随机序列是人 们谈论最少的密码学问题，但是没有哪个问题比这个问题更加重要从某种 意义上讲，序列的随机性直接决定了整个系统的安全性好坏。但是由于应用环 境的复杂性，对其优劣进行严格评估非常困难，因此，如何通过对随机序列 的随机性进行研究来评测出高质量、随机性好的随机序列就成为了信息安全领 域的重点研究的问题。 h a s h 函数是一种单向函数，一般翻译为“散列9 99 也可以直接译为哈希， 就是将任意长度的输入通过散列算法，变换成固定长度的输出，输出就是h a s h 值，h a s h 函数是可以分为带密钥的h a s h 函数和不带密钥的h a s h 函数，带有 密钥的h a s h 函数多用于密钥共享、认证和软件保护等方面，而不带有密钥的 h a s h 函数一般用于数字签名、完整性验证等。 单向函数定义：如映射日：卜y 对于所有的x x ，h ( x ) 都容易计算，但 是反过来，给定一个h ( x ) 要求x 在计算上是困难的，满足以上条件的函数称之 为单向函数。单向h a s h 函数是一种特殊类型的单向函数，它要满足以下4 个 条件【2 】： 1 )输入为任意长度的序列，但是输出长度固定； 2 )不可逆性：即已知c = h a s h ( m ) ，求m 计算上很困难，除穷举外没有其 西南交通大学硕士研究生学位论文第2 页 3 ) 4 ) 他有效方法； 防伪造性：已知c = h a s h ( m ) ，求刀使h a s h ( n ) = c 计算困难； 初值敏感性：c = h a s h ( m ) q bc 的每一b i t 都与聊的每一b i t 相关联，并 且具有高度的敏感性，即每改变m 的任一b i t 位，都将对c 产生明显 的影响。 h a s h 函数随机性的检测评估技术是h a s h 算法研究的重要组成部分，它为 h a s h 函数的分析、设计和选择提供了客观的量化指标和技术参数，对h a s h 函 数的应用具有重要的指导意义1 3j 。随机性测试技术在密码学中具有很重要的作 用4 儿5 1 ，随机序列的安全性决定了整个密码系统的安全性【6 】f 7 】【8 1 ，密码算法的 随机性是衡量算法好坏的一个重要指标1 5 儿9 1 ，因此对密码的随机性检测评估进 行研究具有重要的意义，也具有一定的实用价值i l0 1 。 1 2 课题研究的国内外研究现状 密码算法的安全性包括几个方面【3 】，首先是算法数学基础的稳健性，其次 是算法的抗攻击性，我们可以用现有的攻击方法对密码算法进行攻击以发现密 码算法设计的缺陷，接着要考察算法的相对强度，可以将算法与现有公认的安 全的算法进行比较，以取得算法安全强度量上的认知，最后是用已知的统计检 测原理来检测算法输出序列是否随机。 密码算法应用环境和条件的复杂性使得对算法的评估存在多种不同的准 则，对密码算法的优劣进行严格意义上的评估是一件很困难的事情。对于传统 的h a s h 算法的测试方法有几种常见的方法【l ，比如生日攻击，中途相遇攻击， 差分攻击以及模差分攻击等，这类评测方法能够比较深刻的反映h a s h 函 数的安全性，对密码安全性的评测也较为有效，但是这要求较高的专 业知识和智力水平，并且评价的周期也较长。 对于混沌h a s h 函数的测试，因为混沌h a s h 函数的研究起步较晚，现在主 要是统计分析最小比特变化数，最大比特变化数，平均变化比特数等。王继志 等【1 2 】对一类混沌h a s h 函数方案进行了密码分析和碰撞攻击，王小敏【”】对两个 基于变参数的混沌h a s h 函数进行了安全性分析，并总结了混沌h a s h 函数设计 的一些基本准则。如：对消息分组不足时的处理是需要添加原始消息的信息， 可借鉴传统h a s h 函数的迭代结构来加快消息的混淆和扩散能力，以及最好的 方式是将消息映射到参数空间而不是值空间。但是对混沌h a s h 函数的测试存 在着用实验仿真、统计分析代替理论安全性分析的通病。如张翰【1 4 】等的关于时 空混沌的单向h a s h 函数构造，刘光杰【l5 】等的基于混沌神经网络的单向h a s h 函数，均存在这样的现象。这类的评测方法是能对混沌h a s h 函数的安全性给 西南交通大学硕士研究生学位论文第3 页 出一般性的评测结果，但是由于其选择采用有限样本的h a s h 值比特变化数作 为安全性指标，缺点是样本数太少，指标太单一，难以给出有效的安全性评估。 密码算法的随机性是衡量算法好坏的很重要的一个指标，一个安全的密码 算法的输出需要是随机的，而密码算法及密码协议中用到的密钥和一些参数也 需要是随机的，随机性检测在密码应用及其相关领域起到重要作用。针对密码 算法的随机特性，目前有多种不同的检测算法和检测工具，但是对各种随机性 的检测结果，现在还没有一个完整实用的量化评估体系和模型【l6 1 。而此次研究 提出了一个针对密码随机性的评估指标体系，拟采用模糊数学中的隶属度函数 方法，对随机性检测结果进行模糊化处理，并以模糊综合评估为基础，给出一 个实用的随机性评估模型。该模型能够反映出来随机性的连续和渐变特点，避 免了单纯的阈值方法引起的评价信息丢失问题，能够对密码的随机性提供综合 的量化评估结果。 1 3 论文主要研究工作 随机序列在密码学中有重要的作用，应用于许多方面，因此随机性检验对 于密码学来讲是至关重要的一个研究问题，密码算法的随机性检验是衡量一个 算法好坏的一个重要指标，而h a s h 函数是一类应用广泛的单向函数，本文就 是通过对h a s h 算法的随机性进行评测，来判断h a s h 函数随机性的好坏，为进 一步的研究和评估提供参考。 首先是对当前使用的检测项目进行比较和筛选，确定检测的项目，运用层 次结构模型，通过自上而下的逐层分解，建立起来针对h a s h 函数的随机性评 价指标体系，然后利用模糊数学中的隶属度函数，对各个指标的随机性检测结 果进行模糊化处理，对于各个指标的权重因子，通过层次分析比较法和基于信 息熵的权重赋值来分配，根据建立的随机性综合评估模型，进行自下而上的逐 层评估，最后给出被测h a s h 函数的随机性综合量化评估结果。 1 4 论文的组织结构 目前对于随机性的检验有多种不同的检测算法和检测工具，但是对各种随 机性的检测结果，现在还没有一个完整实用的量化评估体系和模型。而h a s h 函数作为一个重要的单向函数，在许多方面有重要的应用，因此对h a s h 函数 进行随机性评估是目前需要解决的难题。 本文主要研究了如何对h a s h 函数的随机性进行综合评估。各章具体内容安 排如下t 西南交通大学硕士研究生学位论文第4 页 第一章，首先介绍了本文研究的背景和意义，国内外对随机性评估的研究 现状，对于传统的h a s h 和混沌结构的h a s h 都给予了介绍，接下来是对本文主 要研究内容的一个总结。 第二章，主要是随机性检测基础知识介绍，首先是密码算法随机性的定义 和在各个方面的用途，然后介绍了随机性检测所需要的数学基础知识，主要是 随机性检测用到的概率知识，常见的几种分布和分布检验方法，接着是在实际 应用中，衡量随机性的3 种检验方法，为以后的检验打下数学基础，接下来是 关于n i s t 的对于密码算法的随机性提出的16 个检验项，分别给予简要介绍检 验的目的是什么，以及检测的大致流程和步骤，为下一章阐述本篇论文的核心 部分，关于h a s h 函数的随机性评估模型做好准备。 第三章，主要介绍了随机性综合评估模型，首先是介绍了模糊数学的相关 知识，对本文中将要在量化评估单个指标时所用到的隶属度函数给予了重点介 绍，接下来介绍了分层次的指标体系，在本章的第三部分也是本文的核心部分， 详细叙述了随机性模糊综合评估模型，介绍了实现的步骤和过程，先是关于单 个指标评估的方法和步骤，接着是将各个指标综合起来的综合评价方法，即随 机性的综合评估过程。最后是应用此评估方法和模型，来评测h a s h 函数中的 s h a 1 函数和s k e i n 函数，在进行综合评估时是将各个指标看做同等重要的， 即平均分配权重系数，最后对评价出的结果进行了分析。 第四章，首先介绍了层次分析法，通过此方法可以实现对部分特性和子特 性的权重赋值，接着在第二节主要是介绍了用信息熵的方法来实现权重的分 配，这种方法对于项数比较多，而不便于使用层次分析比较法的情况是很适用 的，而且通过这种方法进行权重的赋值，也是比较客观的，在第三节就是将上 述两者的权重赋权方法进行结合，在第三章的随机性评估模型的基础上，提出 了基于a h p f u z z y 信息熵的综合评估方法，将客观和主观的权重系数赋权方 式结合起来，既能反映出客观情况又能参考专家的意见。在最后的第四节本文 选择了几个代表性的h a s h 函数进行测评，用来检验本评估模型的评测效果和 适用范围，并对评测结果进行了分析。 最后一部分是总结和展望，对全文工作做了相应的总结，并分析了论文工 作中还存在的问题，同时对论文未来的工作内容和方向进行了探讨。 西南交通大学硕士研究生学位论文第5 页 第2 章随机性检测技术概述 2 1 密码算法的随机性简介 随机序列从某种意义上可以理解为“随机地选择 的数，在实际中有多种 不同类型的应用，例如一个安全的算法的输出需要是随机的序列，密码算法、 身份认证、安全服务及密码协议都离不开高质量的随机序列。所以如何通过检 测来甄别出高质量的随机序列显得十分重要。 随机比特序列是指长度是甩的比特序列，序列的元素值取为0 ，或者为 1 。用符号表示为： 以= o ，1 ) n ，刀1 而随机数尺则是一个取自于广义随机序列r 。的数字。该广义随机数序列 r n 的元素取值范围是实际应用中要求的定义域内任一数值。用符号表示为： r j 0 ，尺0 = 厂 几，d e f ，刀1 随机数有许多种不同类型的应用【17 1 。例如： a ) 仿真当使用一台计算机仿真自然现象时，就需要使用随机数使事情 变得逼真。仿真涉及从核物理( 如粒子受到随机的碰撞) 直到运筹学( 比如， 人们在随机的时间里进入一个机场) 的许多领域。 b ) 抽样通常，要考察所有可能的情况是不太实际的，而随机的抽样则 可以使我们能了解“典型”的行为。 c ) 数值分析利用随机数已经想出了很多巧妙的技术来解决复杂的数值 问题。 d ) 计算机程序设计为了验证计算机算法的有效性，随机值乃是数据的 好来源。更重要的是，随机值对于随机化算法的运算是很重要的，随机化算法 经常比确定性算法要优越的多，在实际中有广泛的应用。 e ) 决策据说，有许多决策人是通过抛硬币或掷飞镖等等来做出他们的 判断，所以有时做出这样无偏见的判断是重要的。随机性也是矩阵游戏理论中 优化策略必不可少的组成部分。 f ) 美学一点儿随机性就会使计算机生成的图形和音乐似乎更加活泼。 g ) 娱乐摇骰子、洗扑克牌、转轮盘等，是人们喜爱的娱乐方式。随机 数的这些传统用法，已经被命名为“蒙特卡洛方法 ，它已成为描述任何使用 随机数的算法的通用术语。 西南交通大学硕士研究生学位论文第6 页 在实际应用中，要产生足够多并且高质量的随机序列是比较困难的，或者 是在某些情况下需要重现这个随机序列，在这些情况下，需要使用伪随机序列， 但是我们在使用伪随机序列时也要保证其有良好的随机性，所以常常在应用中 用真随机数作为初始条件，或者作为一个输入，即将真随机数当作伪随机发生 器的种子。 2 2 随机性测试数学基础 本节分为两个小节，一方面介绍随机性测试用到的概率知识，另一方面是 介绍随机性测试方面数学上的一些原理和方法。 2 2 1 随机性测试概率知识 2 2 1 1 二项分布 如果随机变量孝所有可能取值为o ，1 ，l ，并且有 p k = p 毛= 七) = 群p 七q n k t k = o ，1 ，刀，o p 1 ，q = l p ， 则称善服从参数为，z ，p 的二项分布【18 1 ，记为孝一b ( n ，p ) 。 2 2 1 2 正态分布 假如孝的密度函数为： 1毒( 型) ： 厂( z ) 2 孺p 2 。盯，一 o 假设总体善是一个离散型随机变量，假设可能取值为x l ，x 2 ，靠。为了检验 假设： h o ：p 善= 工，) = p f ，江1 ，2 ， 抽取容量大小为刀的样本得出刀个样本数据，将样本数据按照取值的不同进行 分组整理，列出下表2 1 所示的频数分布表。 表2 1 频数分布表 i 三兰三!i 1 2i ! ： 互 频数”，靠1n 2 n 3 堡 其中n i o ，f ：1 ，i 圭n i ：甩 i = 1 若风为真，孝的概率分布可以用下表2 - 2 表示： 表2 - 2f 概率分布表 i 三互苎三2兰2： 量 由大数定律知，当以充分大时，事件 x i ) 发生频率为n i ，其与理论概率p f 的 咒 差距应该很小，于是可以构成反映这个差异的一个统计量： 。一喜甩( 詈刊2 = 卫一 ：k ( n i _ n p i ) 2 i = 1 n p i 其中k ，称之为实际分组数。这个统计量是实际测得频数n i 与理论组频数印f 离差平方的加权和，它是反映了样本实际测的组频数n f 与理论组频数印f 之间 差异的大小，称这个统计量为皮尔逊矿统计量。当风为真时，矿统计量的值 应较小，所以皮尔逊统计量的值大到某个临界值五时，就要质疑月。的正确性而 拒绝h o 。所以拒绝假设h o 的拒绝域为：z z 旯。五的确定取决于皮尔逊z 2 统计量 的分布，而它的精确分布是难以确定的，但是皮尔逊给出了它的近似分布1 3 j 。 二2一坠o 羔峥 旦乒ir 西南交通大学硕士研究生学位论文第8 页 2 2 2 随机性测试的理论基础 序列的随机性测试，实质上就是检验序列是否是真随机的或者是与真随机 。 序列的差距，假设检验是随机性检测技术中的基本理论。在检验时，提出一个 待检验的假设，称之为原假设或零假设，记为凰，还有个与原假设相反的， 称之为备择假设，记为日l 。对每一个检验来说，其检测后的结果是否接受原 假设也就意味着待检测数据是否是随机的【”】。 假设检验会产生2 类检验类型的错误，如表2 3 所示。 表2 3 检验错误类型 1 4 0判断结果犯错误的概率 接受正确 0 真 拒绝犯第一类错误 a 接受n o , 第二类错误8 假 拒绝正确 0 在实际的应用中，衡量随机性的方法通常有3 种：门限值法，设置一个取 值范围和p v a l u e 值法1 2 引。 这里以测试统计量x 服从分布为例来进行说明。 1 ) 门限值法，先做出分布的概率密度曲线，如图2 一l 所示，根据给定的 显著性水平a ( 图2 1 中阴影部分的面积) 查出它的及分位点磋，然后再拿统 计量x 与磊进行比较，最后确定是拒绝还是接受原假设。 2 ) 取值范围法，就是设置一个取值范围，然后再看统计结果是否落在这个 取值范围内，如果在则支持原假设，否则就拒绝原假设。f i p s1 4 0 1 就是采用 了这种方法，比如其频数检验，规定采样位数为2 0 0 0 0 ，那么在这个序列中l 的个数刀l 必须要满足9 6 5 4 2 5 。 6 ) 计算出统计量s = k ( v i i _ _ z n t c i ) 2 ，s x 2 ( k ) ，此处k = 6 ，根据参考文献【3 。1 得到 i = 0 i 、兀i 理论上乃的值： = 1 9 6 ，乃= 0 0 3 1 2 5 ，死= 0 1 2 5 ，乃= o 5 ，x 4 = 0 2 5 ，乃= 0 0 6 2 5 ，= 1 4 8 7 1 算出可接受水平尸值： 西南交通大学硕士研究生学位论文第1 8 页 尸= 枷所c 巨詈) 8 ) 决策规则( 0 0 1 ) ： 如果计算出来的值小于0 0 1 ，这就意味着序列是非随机的，否则可以判定 序列是随机的。 2 3 1 2 序列检验 本检验主要是看整个序列中所有可能的重叠? p - b i t 模式的频率，目的是判 定2 朋个忉- b i t 重叠模式的数目是否跟随机情况下预期的值近似，随机序列具有 均匀性，也就是说对于每个m - b i t 模式其出现的概率应该是一样的，注意，当 m = l 时，序列检验等价与前面讨论的频数检验。 1 ) 构建扩张序列7 ：将序列的第一个( 聊1 ) b i t s 加到整个序列的末尾。 2 ) 确定所有可能的重叠m - b i t 、( 聊1 ) b i t 、( 聊2 ) b i t 模式的频数，对于扩张 序列每一次移动1 比特重叠计数，统计出所有长度为m ，( m 1 ) ，( 朋2 ) 的子块在整个序列中出现的次数，分别用、矗，一乇一，、一k 表示。 3 ) 计算求可接受水平尸值时用到的中间量： 2 = i 2 m 矗h 一参) = 百2 m 矗厶2 一刀， 吒= i 2 m - 1 。乏一h 。一南) 2 = 了2 m - 1 。乏叫2 蠊f 了2 m - 2 烈u ：一壶2 = 了2 m - 2 o 。，z 。娠f 了烈u ：一寿= 了j i 搿锄 4 ) 计算出v 以和v 2 缘：