（概率论与数理统计专业论文）概率统计在计算机密码学中的应用.pdf

硕士攀位论爻 m a s t e r st h b $ i s 摘要 密码学中h a s h 函数能够用于数据完整性和消息认证以及数字签名，新近的对 于胁5 ，s h a _ l 等的碰撞攻击晦1 表明在一个h a s h 函数的内部迭代过程中的随机统计 特性对其安全性也有一定程度影响，因此对于h a s h 函数迭代过程中输出序列的随 机性进行分析对于研究h a s h 函数的安全性是有重要意义的。运用概率统计的思想 方法来研究h a s h 函数的一些性质必将为密码分析人员提供一些新的攻击密码方案 的新方法和新思路，也必将使得将概率统计应用于密码学中成为一个新的研究热 点。而5 等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 的密码系统的迫切性和重要性。 s h a 一2 5 6 是使用最广泛的一种h a s h 函数。本文针对s h a 一2 5 6 ，用已有统计检测 方法中的z 2 检验对其进行了随机性测试( 包括频数检验，跟随检验，游程检验) 及雪崩效应的测试，对每种测试都取了两种有代表性的输入：有规律的输入和随机 的输入。最后对测试结果进行了分析讨论，得出结论： 1 s h a 一2 5 6 在进行迭代过程中，随着迭代次数的增加，从整体上来看，所得到 的输出序列的随机性是越来越好的。 2 在随机性逐渐变好的过程中，第2 7 轮，3 0 轮，4 3 轮和5 9 轮与其对应的前 一轮或者后一轮相比随机性很不好。 由以上结论可知，s h a 一2 5 6 算法存在着一定的不足之处，这些结论也将为密码 分析人员提供有用的密码攻击方案的新方法和新思路。 关键词：密码学；h a s h 函数；随机序列；s h a 一2 5 6 ；m d 5 ；随机测试；雪崩效应；频 数检验；跟随测试；游程检验 a b s t r a c t i t it l l ec 聊p t o l o g ) r ，t l l eh a s h 缸戚0 nc 锄b el l s e di i l 也ed a ：c a 硫e 酏y 锄dt h en e w s a u m e n t i c a d o n 勰、e u 硒t h ed i 画t a ls i 印a t u r e ，t h el a t e s tc o l l i s i o na t t a c k 向rmd 5 ，s h a 一1 趾ds oo n h o w e dt h a tt h e 聪m d o m 删s t i c a lp 】口硎e si nt h ei r l t e m a ji t 训v ea 】蕾阮tt 1 1 e s e c u r i 母o fah a s hm n c t i o n s oi t si n l p o n a n tt 0s t l u d yt 1 1 em d o mo u t p u ts e q u c ei nt l l e h a s h 劬c t i o ni t e r a t i v ep r o c e s sf 0 rm es e c u r i t yo ft 1 1 eh a s h 如n c t i o n u s i n go ft h e p r o b a b i l i t ) ，a i l ds t a t i s t i c st os t u d yt h en a t i l 】陀o ft h eh a s h c t i o nw i u 舯to n l yp v i d e s o m en e wm e t l l o d s 锄di d e 勰f o rp a s s w o r d 锄a l y s t s ，b l l ta l s 0b ean e ws t u d yh o t t h e d e c i p h e ro ft i l eh a s hf h n c t i o n ss u c ha sm l 5a l s om e a n s 廿l a ti t su r g e n ta n di m p o n a n tt o s t u d yt l l es h a 一2 2 4 ，s h a 一2 5 6 ，s h a 3 8 4a n ds h a 5 1 2 s h a 2 5 6i so n el ( i n do fh a s h 缸l c h o n sw h i c hi su s 。d 州d e s p r e a d l y 1 1 1 i sa n i c l e a i m sa ts ha 一2 5 6 ，w ec a vo nm er 锄d o mt e s ta sw e l la st h ea y a l a n c h ee f - f e c tt e s tt oi t 州t i l z 2t e x ti 1 1t 1 1 es t a t i s t i c a le x 觚血1 a t i o nm e t l l o d ( i 1 1 c l u m l g 毹q u c yt e s t s ，f o l l o w i i l g t e s t s ，m n l e n g 廿lt e s t ) ，附oi i 印r e s e n t a t i v ei 印u t sw e r eu s e df o re a c ht e s t ：r e g u l a ri n p u ta i l d r l n d o m 证d u t f i n a l l v t h et e s tr e s u l t sw e r ea n a l v z e d 锄dd i s c u s s e 丑c o n c l u d e d ： 1 h li t c r 撕v ep r o c e s sf o rs h a 一2 5 6 ，诵n 1t h ei i l c r e 孙ei nm em 】m b e ro fi t e r a t i v e ，0 n 1 e w h o l e ，m eo u 卸m to f 瑚d o ms e q u e n c ei sm o r ep r o o d 2 i l lm ep r o c e s so f 伊a d u a l l yg o o d 瑚d o 砌e s s ，i t sav e 巧b a dc o m p a r e dt or a n d o m n e s s 州廿lt h ef i l 磷r o u l l do ra f t e rf o rt l l er o u l l do f 2 7 ，3 0 ，4 3 觚d5 9 t h e r ea r cc e r t a i nd e f i c i e n c i e sf o rs h a 一2 5 6a l 舯r i t h m 丘o m 廿l ea b o v ec o n c l u s i o n s t h e s e 丘n 血鼬w i l la l s op r o v i d eu s e m ln e wm e t l l o d sa n dn e wi d e 勰南rm ep a s s w o r da n a l y s t s k e y w o r d s ：c 卿。伊a p h y ；h a s h 缸l 以0 n ；r a n d o ms e q l 塌1 c e ；s h a 一2 5 6 ；m d 5 ；r 锄d o m t e s t i i l g ；a v a l 觚c h ee 侬娥；f r e q u e l l c yo f t e s t 吨；f o l l o wt l l et e s t ；lt e s t 硕士擘位论更 h t a | s t e r s r h e 基i 霉 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：翻碎 日期砌多年厶月岁日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名：乞，) 刁 日期：加萨6 月歹日 导师签名： 日期：渺8 年厶月r 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库一中全文发布，并可按“章程一中的 规定享受相关权益。回童途塞握窑卮澄卮! 旦堂生；旦二生i 旦三生蕉查： 作者签名：友i j 刁 日期：刎泸f 7 月r 日 导师签名：劣水矿 日期i 即吕年易月 项士学位论史 m a s t e r st h b s i s 、 引言 在二十一世纪电子商务和电子政务时代，人们所面临的一个至关重要的问题就 是信息安全问题。密码学是保障信息安全的核心技术，它以很小的代价提供很大的 安全保护，其应用涉及军事、国防、商贸以及人们日常生活中的各方面。 密码学是一门古老而又年青的科学，它用于保护军事和外交通信可追溯到几 千年前。在当今的信息时代，大量的敏感信息如病历、法庭记录、资金转移、私 人财产等常常通过公共通信设施或计算机网络来进行交换，而这些信息的秘密性 和真实性是人们迫切需要的。因此，现代密码学的应用已不再局限于军事、政治 和外交，其商用价值和社会价值也已得到了充分肯定。 密码学是数学、计算机、通信等多学科的交叉。密码学的基础包括数论、概 率论与数理统计、信息论、编码等等。概率统计主要用于对密码算法的统计性能进 行测试和分析，从而给密码编码人员和密码分析人员提供一定的信息。 密码学中的h a s h 函数n 卅( c r y p t o 卿h yh a s h 缸l c t i o n s ) 能够用于数据完整性和 消息认证以及数字签名。其基本思想是把h a s h 函数值看成输入的消息摘要( m e s s a g e d i g e s t ) ，当输入中的任何一个二进制位发生变化时都将引起h a s h 函数值的变化。 关于h a s h 的算法研究，一直是信息科学里面的一个前沿，尤其在网络技术普 及的今天，他的重要性越来越突出，其实我们每天在网上进行的信息交流安全验 证，我们在使用的操作系统密钥原理，里面都有它的身影。目前已经公开的代表性 的h a s h 算法有m d 4 、m d 5 、s h a 一1 、s h a 一2 、r i p e m 沪1 2 8 口1 等。为了满足数据完整性 和消息认证的需要，h a s h 函数必须满足特定的密码学要求，例如单向性和抗碰撞h 1 等。 基于分组密码的h a s h 函数也是最近的研究热点之一。主要用于信息安全领域 中的加密算法。针对h a s h 算法的一些弱点可对h a s h 算法进行攻击，可利用h a s h 算法的代数结构及其所使用的分组密码的弱点来攻击一些h a s h 方案。例如针对d e s 的一些弱点( 即互补性、弱密钥、密钥碰撞等) 来攻击基于d e s 的h a s h 方案。 新近的对于m d 5 等的碰撞攻击陆1 表明在一个h a s h 函数的内部迭代过程中的随机 统计特性对其安全性也有一定程度影响。因此对h a s h 函数迭代过程中输出序列的 随机性进行分析对于研究h a s h 函数的安全性是有重要意义的。故运用概率统计的 思想方法来研究h a s h 函数的一些性质必将为密码分析人员提供一些新的攻击密码 方案的新方法和新思路，也必将使得将概率统计应用于密码学中成为一个新的研究 热点。 本文主要是研究概率论与数理统计在密码学中的应用：对h a s h 函数迭代过程 中输出序列的随机性进行分析。我们无法用数学方法对一个序列是否是真正的随机 比特序列给出证明，但是我们可以通过使样本序列经过不同的统计测试来检测该序 列所具有的某些缺点；统计测试通常用说明随机样本的统计量1 。被选择的统计量 通常易于有效计算，并且近似地服从( o ，1 ) 或z 2 分布。样本输出序列的统计量的 值经过计算，然后与特定的随机序列的期望值进行比较，从而可以对该种h a s h 算 法的安全性做出分析。本文的测试对象主要是针对h a s h 算法中的s h a 一2 5 6 进行的， 通过一系列的统计测试，对s h a 一2 5 6 的安全性做出了分析，并指出了该算法的不足 之处。 章节安排：第一章介绍h a s h 函数；第二章介绍随机序列的统计测试：第三章 介绍了几种密码算法的输出序列的随机性研究；第四章主要是第三章的结论及分 析；第五章是需要进一步解决的问题及展望。 2 硕士学位论文 a 雠t e r st h b s 工s 第一章h a s h 函数的介绍 密码学中的h a s h 函数主要用于数据完整性和消息认证以及数字签名。h a s h 函数 是密码学领域内兴起的一种极其重要的通信工具，并且已成为密码学者最为关注的 焦点之一。 h a s h 函数的研究是密码学和信息安全领域中的一个非常重要的基本组成部分， 但是，自从以m d 5 为代表的系列h a s h 函数被我国学者王小云等人破译后，关于h a s h 函数的研究又重新回到了起步阶段，国际上对h a s h 函数的研究又成了一个热点。 1 1h a s h 函数的概念1 1 2 1 啦0 1 h a s h 函数是一种将任意长度的消息m 压缩到某一固定长度的消息摘要 ( m e s s a g em g e s t ) 函数，可以表示为j l l = 日( m ) ，其中j i l 为输出值，长度为，m 为 输入明文。 定义1 1 若h a s h 函数日( m ) 满足以下性质： ( 1 ) 压缩性：对于任意长度的消息m o ，1 ) ，输出的压缩值j j l = h ( m ) o ，1 ) 。， 并且计算j i l 是容易的。 ( 2 ) 抗计算原象性( p r e i m a g er e s i s t a i l c e ) ：给定 ，计算m 满足日( m ) = 是 计算上困难的。 ( 3 ) 抗计算第二原象性( 2 n d p r e i m a g er e s i s t a n c e ) ：给定肘，要找到另一消息 m 。并满足日( m ) = 日( m ) 是计算上困难的。 则h a s h 函数日( m ) 称为弱单向h a s h 函数( w e a l 【0 n e w a y h a s h 缸l c t i o n ) 定义1 2 若日( m ) 为弱单向h a s h 函数，并且满足下列特性： ( 4 ) 抗碰撞性( c 0 1 l i s i o nr e s i s t a i l c eo rf r e e c o l l i s i o n ) ：寻找任何明文对m 、m ， 并且满足日似) = 日。) 是计算上困难的。 则日) 称为强单向h a s h 函数或者无碰撞h a s h 函数。一般也简称为单向h a s h 函数或散列函数。 1 2h a s h 函数的构造1 1 8 l 在密码学和信息安全领域里，几个比较著名的算法都是通过迭代压缩函数来实 现的，因此，在用迭代方法设计函数时，最关键的是能否找到或设计出一个安全的 压缩函数。通常设计压缩函数有两种方法：一、利用某些数学工具专为h a s h 目的 项士学位论史 m a s 丁e r s r h b s i 墓 而设计一个压缩函数。二、利用现有的密码算法如分组密码来作为压缩函数等。 目前，设计h a s h 函数的基本方法有以下几种： 1 ) 利用某些数学难题比如因子分解问题、离散对数问题等设计h a s h 函数。已设计 出的算法有d a v i e s p r i c e 平方h a s h 算法、c c l l v r 建议、j u e n e 眦nh a s h 算法、d a m g a r d 平方h a s h 算法、d 锄g a r d 背包h a s h 算法、s c h n o r r 的f f th a s h 算法等。 2 ) 利用某些私钥密码体制比如d e s 等设计h a s h 函数。这种h a s h 函数的安全性与所 使用的基础密码算法有关。这类h a s h 算法有r a b i nh a s h 算法、w i n t e r n i t zh a s h 算 法、q u i s q u a t e r g i r a u l th a s h 算法、m e r k l eh a s h 算法、n h a s h 算法等。 3 ) 直接设计h a s h 函数，这类算法不基于任何假设和密码体制。这种方法受到人们 的广泛关注和青睐，是当今比较流行的一种设计方法。美国的安全h a s h 算法( s h a ) 就是这类算法，此类算法还有m d 4 、m d 5 、m d 2 、r i p e m d 、h a v a l 等。 1 3s h a 系列h a s h 函刻1 】( 安全h a s h 算法) 1 3 1 基本介绍 安全h a s h 算法包括s h a 一1 、s h a 一2 5 6 、s h a 一3 8 4 和s h a 一5 1 2 四种( 本文主要以 介绍s h a 一2 5 6 为主) 。这四种算法都是迭代的单向h a s h 函数，这些h a s h 函数可以 作用于一个消息( m e s s a g e ) 从而产生一个消息摘要( m e s s a g ed i g e s t ) 。这些算法 能够保证一个消息的完整性，即：消息的任何一个改变都将导致消息摘要以一个很 高的概率发生改变。而这个性质在数字签名、信息证实代码和产生随机数的应用中 是很有用的。 安全h a s h 算法的每个算法都可以描述成两个步骤：预处理和h a s h 值的计算。 预处理包括：a 、消息填充，b 、将填充后的消息分成若干个块，每个块都具有肌b i t ， c 、设置初值。这些初值将在计算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 算法。 例如：如果一个有正负之分的消息使用了一个提供了1 2 8 位安全比特数的数字签名 算法，那么这个数字签名算法可能就需要使用一个也提供1 2 8 位安全比特数的安全 h a s h 算法( 如s h a 一2 5 6 ) 另外，这四个算法在分块的大小也是不同的。下面的表描述了这四个安全h a s h 4 硕士学位论史 m a s t e r st h b s 硌 算法的一些基本性质： 表1 ：安全h a s h 算法的性质 算法消息长度分块长度字长度消息摘要长度安全位数 ( b i t s )( b i t s )( b i t s )( b i t s ) ( b i t s ) s h a 一1 2 1 2 8 5 1 23 21 6 08 0 s h a 一2 5 6 2 6 4 5 1 23 22 5 61 2 8 s h a 一3 8 4 2 1 2 8 1 0 2 46 43 8 4 1 9 2 s h a 一5 1 2 万) v ( z 以。 1 s h a 一2 5 6 的预处理 填充消息m ； 将填充后的消息分解成个5 1 2 - b i t 的消息块：m ( n ，m 孙，m m 。 给h a s h 值附初值日( m 。 2 s h a 一2 5 6 的h a s h 计算 s h a 一2 5 6 的h a s h 计算分别用到了前面提到的函数和常量。这里的加法( + ) 是 对于模2 3 2 而言的。 在预处理结束后，每个消息m ( n ，m ( ”，m 依次按照下面的步骤进行 处理： f o ri = lt o 1 准备消息表 彬) ： 形= 一2 5 6 ( 形一：) + 形一，+ 以2 5 哪( 形小) + 形- 1 6 2 将第( i 一1 ) 轮的h a s h 值分别附给五个工作变量n ， g ， ： 口= h 6 = 研卜d c = 础。1 d = 叫h p = 碰h 厂= 碰h g = 碰h 办= 碰h 3 f o rt = ot o6 3 ： 6 0 f 1 5 1 6 f 6 3 b ，c ，d ，e f ， 硕士学位论文 m a s t e r st h b s l s 互= + ：2 s 6 ( 力+ 劬( p ，厂，g ) + 耐2 卿+ 形 互= ? ( 口) 十坳( 口，6 ，c ) = g g = = e e = d + 巧 d = c c = 6 6 = 口 口= 石+ 互 4 计算第f 轮的h a s h 值日( o ： h 0 = 口+ h ：一 研o = 6 + 研扣1 雹o = c + 碰卜d 趔o = d + 叫卜d 碰o = p + 日p 日! d = 厂+ 日 日：= g + 日 研o = + 日p ) 在重复卜4 步次后( 即处理m ( 后) ，就会产生一个2 5 6 b i t 的消息摘要m ，即： 硪柳i i 研m1 1 日0 硝mi j 础柳0 叫聊i l 碰ml ih 。 1 3 3 安全h a s h 算法的安全性 m d 5 、s h a 一1 是当前国际上最常用的单向散列函数。近期的研究发现，s h a 一1 算法和肛4 、m d _ 5 等单向散列函数的安全性已经受到了质疑。山东大学信息安全 所所长王小云教授在2 0 0 4 年宣布了她的研究成果：对m d - 5 、h a v a l 1 2 8 、m d - 4 和 r i p e 肋等4 个著名安全散列函数的破译结果。2 0 0 5 年她又宣布了破译s h a 一1 的研究 成果。 n i s t 针对王小云教授的研究发现表示，为配合先进的计算机技术，美国政府5 年内将不再使用s h a 一1 ，并计划在2 0 l o 年改用先进的s h a 一2 5 6 、s h a 一3 8 4 及s h a 一5 1 2 的 7 密码系统。这也就意味着研究s h a _ 2 2 4 、s h a 一2 5 6 、s 姒一3 8 4 及s h a 一5 1 2 的密码系统 的迫切性和重要性。本文的研究主要是针对s h a 一2 5 6 的。 8 第二章随机序列的统计测试 对一个密码算法来说，其输出序列的随机性是其安全性的很重要的一方面。对 基于分组密码算法的h a s h 函数来说，其是否可以用作伪随机数产生器是评价这个算 法的重要指标之一( 可参看a e s 的评选报告) 。所以随机性测试在密码学中占有很 重要的作用。 本章将分以下几部分来介绍：2 1 随机序列的介绍；2 2 随机性测试的重要性； 2 3 随机序列的统计测试。这里，我们将以第三部分为主，主要介绍随机序列统计 测试的定义、统计量及其相关证明。 2 1 随机序列 在许多密码机制中，随机数生成都是一个重要的要素。例如，加密变换的密钥 必须以一种不可被敌手预测的方式产生。而生成一个随机密钥通常涉及随机数或随 机比特序列的选择。 随机序列常被用做密钥管理，其主要功能是产生真随机的序列来用做密钥。产 生随机序列的方法有很多种，既有数学方法产生的，也有物理方法产生的，从而随机 数产生器有真随机和伪随机之分。 2 1 1 真随机数产生器 随机比特生成器：一种能够输出统计上独立且无偏的二进制数字序列的设备或 算法。真随机数产生器产生的随机数是不可重现的，绝大多数真随机序列源都来自 物理方法，产生它们的代价大，速度慢。为此，使用伪随机序列：按一种确定的方 式从一个称为种子的较短序列来构造的序列。通常生成算法是公开的，但种子除了 生成序列的实体外不被人所知。 2 1 2 伪随机数产生器 伪随机比特生成器( p r b g ) ：一种确定性算法( 给定了相同的初始种子时，生 成器将产生相同的输出序列) ，即在给定长度为七的真随机二进制序列时，能够输出 一个长度为，( ， 七) 且看上去“随机的二进制序列。p r b g 的输入称为种子， 输出称为伪随机比特序列。实际上，伪随机数产生器产生的随机数并不是真的随机， 其具有周期性，也就是说，其产生的随机数序列总会产生重复，不过如果产生器的周 期足够长( 至少要远远大于可能采集的随机数的长度) ，那么这个随机数产生器产生 9 的局部的随机序列也就和真随机序列看起来没有什么区别了。如线性同余发生器、 线性反馈移位寄存器、附加式发生器等n 7 1 。 2 2 随机性测试的重要性 不管是真随机数产生器还是伪随机数产生器，都必须通过随机性测试。对一个 密码算法来说，其输出序列的随机性是其安全性的很重要的一方面。对分组密码算 法来说，其是否可以看作伪随机数产生器是评价这个算法的重要指标之一( 可参看 a e s 的评选报告) 。所以随机性测试在密码学中占有很重要的作用。密码学意义 上安全的随机数比其它大多数应用对随机性的要求更严格，要求满足以下3 个基本 的特性： ( 1 ) 不可预测性；也就是说，即使给出产生序列的算法或者硬件设计和以前已 经产生的序列的所有知识，你也不可能通过计算来预测下一个比特是什么。 ( 2 ) 不能重复产生：也就是说，即使在完全相同的操作条件下( 同样的地点、同 样的温度等) 用完全相同的输入对序列产生器操作两次，你也将得到两个完全不同 的、毫不相关的位序列。 ( 3 ) 能通过随机性统计检验。即能通过我们所能找到的所有的正确的随机性检 验，这也是最起码的要求。目前存在的随机性检验约有2 0 0 多个，而且根据参数的改 变一个检验有时可以变换为很多个检验，要让一个算法通过所有的随机性检验是件 很困难的事，但是有些基本的检验是必须得通过的，比如频数检验。算法无法通过某 个随机性检验就表明算法的设计在某些方面有缺陷。这无疑也给密码分析人员或密 码攻击人员提供了一定的信息。本文主要是针对s h a 一2 5 6 的每一轮输出序列进行了 一系列的随机性统计检验，考察了s h a 一2 5 6 的安全性问题。 序列的随机性检测一直是信息安全领域的一个重要研究方向。h a s h 函数输出序 列的随机性如何直接影响到整个系统的安全性叩1 。所以，对h a s h 函数的输出序列进行 随机性研究是有重大意义的。 2 3 随机序列的统计测试 随机序列的统计测试主要是用随机数产生器或者密码算法产生一串二进制序 列，设计一系列的统计测试来检验其是否是真随机的或与真随机的差距。 我们无法用数学方法对一个序列是否是真正的随机比特序列给出证明，但是我 们可以通过使样本序列经过不同的统计测试来检测该序列所具有的某些缺点：统计 测试通常用于说明随机样本的统计量。被选择的统计量通常易于有效计算，并且近 似地服从n ( 0 ，1 ) 或z 2 分布。样本输出序列的统计量的值经过计算，然后与特定的 l o 硕士学位论文 n l a 嚣t e r st h b g l 8 随机序列的期望值进行比较。在统计分析中，常常用z 2 检验来对算法的扩散性能 进行检测。本文在已有的z 2 检验的理论基础上，对密码算法中的s h a 一2 5 6 的每一 轮输出进行了频数检验、跟随测试、游程检验以及雪崩测试，给出了测试结果，并 对测试结果进行了分析讨论，指出了该算法的一些不足之处。 2 3 1 统计检验的基础知识 定义2 3 1 ：( 二进制对称源) 称源s 为二进制对称源，若s 产生的二进制随机数为 r ，r b ，其中曰= o ，1 l ，r 的概率分布满足： 统计检验是用来发现一个随机比特生成器的一个可能的统计缺陷，也就是说， 用统计模型来描述的当一个随机比特生成器的输出序列明显偏离一个二进制对称 源时，可以用统计检验来发现这种情况。 现要检验测试随机比特生成器的一个长度为的样本序列，且当样本序列的某 种性质隐含着一种可能的不随机性时，就拒绝这个随机比特生成器，即认为这个随 机比特生成器所输出的序列不是伪随机序列。 定义统计量丁如下： 丁：b 一 接受，拒绝 函数丁将长度为的二进制序列集合b 映射到一个较小的集合昌，集合 ( b 一研) 去除掉集合b 中随机性不好的序列，而保留随机性好的序列。即： 品= j ：丁o ) = 拒绝 s 口 统计量r 主要有两个参数：样本序列的长度和拒绝概率( 即一个随机比特生 成器被拒绝的概率，在实际进行统计检测时，p 应越小越好。) p = 等。其中，群品 二 表示集合母中的元素的个数。 记：厶：b 一r ：s 斗五0 ) ，则有： p ( 厂r ( r ) f 1 ) + p ( 厂r ( r ) f 2 ) = p 在实际应用中，我们一般取p ( 厂r 似) f 1 ) p ( 厂r ( r ) f 2 ) 等。势为弹品= p 2 的 硕士擘位论文 【a s t e r st h b s i g 随机性不好的序列的集合品就司以定义如f ： 写= s 曰：厂r o ) f l 或厂r ( s ) f 2 l 丁通常会选为一些比较常用的概率分布，大多情况下会选正态分布或自由度 为d ( d 为正整数) 的z 2 。主要是因为这些分布的数值表都是可查的，这样，在给 定拒绝概率p 和序列样本长度的情况下，可以通过查表确定上限f l 和下限f 2 的值。 2 3 2 频数检验 频数检验是最基本的检验，用来检验一个随机比特生成器是否具有无偏性。在 进行随机性测试时，应该首先选择进行频数检验，频数检验通过后再选择进行其它 检验，否则就不必选择进行其它检验了。因为频数检验不通过，其它检验肯定也不会 通过，有一些检验比如线性复杂度检验会耗费大量的时间，而频数检验是速度最快 的，为了节省时间，我们有必要在进行其它检验以前，先选择进行频数检验。频数检 验是用来检验一个位序列中0 和1 的个数是否近似相等，这正是随机序列所应具备 的引。 设频数检验所测试的是长度为的样本序列为：s = & ，毛，。定义： 腓) - 嘉c 善墨一等 定理1 ：当专时，五( s ) = 去( 喜暑一譬) 专( 。，1 ) 证明：长度为的随机序列中1 的个数r = r + r + + 氐，其中r = ：耋三：) ( f = l ，2 ，) 。 因为当l f 时： e ( r ) = 丢，砌旭) = 丢 故r 可以近似的认为是均值为譬，方差为等的正态分布的随机变量。 所以，据中心极限定理可知， 当一时，五o ) = 嘉( 善一警) 一( 。，1 ) 证毕! 即当足够大时，序( 月) 可以近似地认为是均值为0 ，方差为1 的正态分布，且 1 2 硕士学位谚文 m a s t e r st h e s i s 乞= - f l 2 5 3 。 定理2 吲：令刀。和，1 1 分别表示长度为待测位序列s 中0 和l 的个数。这里我们取频 数检验所使用的统计量为：石= 垒与尹兰，若不小于1 。，则统计量筋= 垒与兰 可以看作是近似地服从自由度为1 的z 2 分布。 注：在实际使用中建议样本数量 1 0 0 0 0 。本文采用的是定理2 中的z 2 统计量石。 2 3 3 跟随测试( 又称序列测试或双比特测试) 该测试的目的是判定位序列s 。的子序列0 0 ，0 1 ，1 0 ，1 1 所出现的次数是否近似 相等，这也是一个随机序列所应具备的特性陋1 。 定理3 1 ：令和分别表示s 中0 和l 的个数，且甩，刀。，碍。，z l 。分别表示s 中 子序列0 0 ，0 1 ，l o ，1 1 出现的次数。 ( 注意+ l + ，l l o + _ 。= ( 一1 ) ，因为这些子 序列允许相交) 所使用的统计量为： 筋= 素与( 疗孟+ 一盖+ 磕+ 荫) 一号( 砖+ ，z ；) + 1 若不小于2 1 ，则该统计量近似地服从自由度为2 的z 2 分布。 2 3 4 游程检验 游程是序列的一个子串，由连续的o 或者1 组成，并且其前导和后继元素都与其 本身的元素不同。游程检验主要检验待检序列s 中游程总数是否符合随机性要求。 游程测试可用来判定序列s 中不同长度游程的个数是否与随机序列中所期待的一 样。 定理4 1 ：令忍，g 分别为s 中长度为f 的1 游程和0 游程的个数，所使用的统计量为： 筋= 喜竿嘻华 其中，岛= ( 一f + 3 ) 2 “2 ，七是满足岛5 的最大的f 则统计量近似地服从自由度为 2 七一2 的z 2 分布。 2 3 5 雪崩测试 ( 1 ) 雪崩效应及严格雪崩准则的统计量 雪崩测试是用来测试密码算法的输入与输出的独立性：测试算法的输出是否有 1 3 项士学位谚更 【a s t e 廷st h b 8 t 霹 不依赖于输入的统计特性。主要考虑两方面的测试： 如果输入具有某种明显的统计特征，算法具有较好的输入输出独立性，则输入 与其对应的输出的距离应是随机的：改变输入分组的任一比特，用导致输出分 组中大约一半比特的变化。 如果输入是随机的，则输入与其对应的输出的距离也应是随机的：改变密钥的 任一比特，应导致输出分组中大约一半比特的变化。 雪崩效应是指输入任一比特的改变都应造成输出平均半数比特的改变；所谓严 格雪崩准则是指输入任一比特的改变都应造成输出每一比特以1 2 的概率发生改 变引。 ，h 2 。( z ) = p ( z z ) = 了杀e i 幽表示标准正态分布的分布函数，约定下列符号： ( ) ，向量的第比特 ( ) 向量的汉明重量( 即向量中1 的个数) j i f 集合的势 以) 事件发生的概率 e ( 乃随机变量r 的数学期望 玩，( n随机变量丁的方差 日( )一个刀比特输入肌比特输出的变换函数 工= ( 五，t ，矗)日( ) 的输入向量， 输入向量工的第七比特， o ，1 ，七= l ，2 ，刀 石( 仅改变x 的第f 比特后的输入向量，f = 1 ，2 ，疗 日o )输入向量石对应的二进制输出向量 日( | o ) 输入向量x ( 对应的二进制输出向量 x 函数日( ) 的输入变量的样本子集，且xc 乏 设函数的输入变量取自样本子集比z ：，记 吻= 群缸石i ( 日( 功) ，( 日( 工“”，) ，f = 1 ，2 ，一；_ ，2 1 ，2 ，研 表示x 中的输入向量石和| o 对应的输出向量之间第比特不同的个数； = 撑 x z i 乃0 ( 日( 工) o 日( 工“) ) = ) ，f = l ，2 ，理；- ，2 1 ，2 ，m 。 表示x 中的输入向量x 和| 对应的输出向量之间的差分汉明重量为歹的x 的个数 1 4 硕士学位论文 h t a 嚣t b r st h e s l g ( 即x 中输入向量工和一 对应的输出向量之l 司不同的比特数为歹的工的个数) ； 定理5 ：雪崩效应的度量可以有以下几种口j 0 。1 ： 1 d = ( 日( z ) o 日( 石d ) ) d 即表示分别改变x 中每个石的1 ，2 ，刀比特后，导致输出改变的比特总数。 若算法能满足雪崩效应的准则，则d 苎安竺。 2 吐= 喜( 去萎( 圩( 石) 。日( 一) ) ) 4 即表示分别改变x 中每个x 的1 ，2 ，l 比特后，导致输出改变的平均比 特数。若算法能满足雪崩效应的准则，则4 等。 3 咖一蒋志善2 肾l q 屯专善志否2 鳓。l 其中，丢喜丽去石喜2 坞表示了分别改变x 的1 ，2 ，以比特后，导致输出改变 的平均比特数，若算法能满足雪崩效应的准则，吉喜瓦熹磊喜2 _ ，6 ：f ，丢，故畋1 。 严格雪崩效应的度量为： 4 小，一望塾 去即表示改变x 的第f 比特后，导致输出第比特发生改变的概率，若算法能满足 严格雪崩效应的准则，则以1 。 ( 2 ) 统计量西、畋和喀的分布2 1 1 基于的有关分布 为了简化推导，不妨设拌x 为偶数。 定理6 ：若日( ) 输出随机，记= 窘，则 硕士学位论文 m a s t e r st h b 窖埘 吻一b ( 拌x ，昙) 令丁：1 一e ( ) i ，r 表示勺的偏差，则丁的分布如下： 肛加卜z 。等 【卑肋。 r = o 且当 x 足够大时，罢近似服从单边正态分布。 证明： 口 ，= x x i ( h ( x ) ) ( h ( 石d ) ) ) ， f = 1 ，2 ，刀；，2 l ，2 ，脚。 表示x 中的输入向量石和x o 对应的输出向量之间第比特不同的个 数； 又 p ( ( ( 工) ) = ( 日( 石o ) ) _ ，) = p ( ( 日( x ) ) ，( 日( 工o ”，) l = 一 2 峙垆= 瞅北) 柑1 = 愀扩 ：亟 2 m 即勺一丑( 群x ，丢) ，也就是说勺是服从二项分布的随机变量。 。丁= 1 一e ( 勺) i 表示吩的偏差 丁 o 1 ，簧由前面的证明可知，酬= 等 当z ：o 时，p 仃：z ) ：p 仃：0 ) ：p ( 口驴：竿) ：只j ，：只x 伽： 当z o 时，p ( 丁：z ) ：p ( ：e ( 口矿) z ) ：p ( 口 f ：兰z ) 1 6 项士擘伍论更 m a s t e r st h e 甜s 又因为曰钟x ，三) ，所以的概率分布应关于其均值等对称 所以p ( 铲竿+ z ) ：2 p ( 勺= 警z ) = 2 只肌一： 即当z 0 时，p ( z = z ) = 2 b z ，2 - 。 综合知，z 的分布如下： 肌垆b ：刘 o ) 似扩等，吲嘲= 等 坚譬兰丝型：罂，而当撑x 足够大时，由中心极限定理可知， 肠厂【) 、，荐义 ! 曼三型可近似看作是标准正态分布， 口厂( 口i f ) 以涪叫叫错叫 扑从瑞训 = 以瑞叫州瑞一， = ( 扰) + ( 一“) = 2 ) 一1 故涪的密度函姚m ) ( 2 嘶) - 1 ) i - 2 = 层童， 所以，当撑x 足够大时，告近似服从单边正态分布。证毕2 群y 1 7 设“服从单边正态分布，记y = 暑，则 p ( ) - p ( 嚣z ) - p ( 丁= 警z ) ； 州阻州子一c 涪去，= 訾； 刚脚c 为叫浩击，= 等。 下面来计算e ) 和纥厂 ) 。 脚，= r 居 一层一卅争伊层 脚2 ) - p 居 出= 层肛一譬出= 钉靠譬出 = 一层r 砒 = 一层c 胛一萼譬一r p = 层r f 譬出 = 后压= 。么，( “) = e ( “) 一( e ( 球) ) 帅) = 1 一( 仨) 2 - 等 k 现设有个独立样本k ，匕，足够大，记2 气f ，则由中心极限 常坪知。跗的分布为： 1 8 硕士擘位论文 m a s t e r st h b s l 3 k p ( z ) 叫 z ) = p ( 善k 胞) ：( 擎堡) 纥，( 矿) 。 叫簿， 卸( 南瓜以) ) 由前面的介绍知，统计量矿= 羔反映了随机变量的偏差，而统计量反映的是 什 2 基于的有关分布 m，12 定理7 ：若日( ) 输出随机，令u = 坞，记p 缈= z ) = = 导等，则 u 一础x m ，圭) 令形= l 羔一l i ，则形的分布为： 叫叫= 恶= ：2 。鬻 ( ，= 鹏表示改变x 中的所有输入向量z 的第f 比特所导致的输出向量的总 变的概率都是导，所以 1 9 踹舞 即叫母( 撑? 朋垮妒 = ( 捍? 聊炒“= 务 靴曰饼x m 三) 。 矿= | 了蒉三一1i 表示了随机变量矽的归一化偏差，则 拜五聊 当z = 0 时， 以肚z ) - 咿- 0 ) = 以罴_ 1 ) 叫u = 半) = 胧哦叫删圳：； 当z 0 时， p ( 形= z ) = p ( 1 罴_ 1 l = z ) 叫罴_ 1 - + z ) = 即- ( 1 + z ) 竿) 又因为【，一b ( 撑x 伪吾) ，所以u 的概率分布应关于其均值苎专竺对称 所以 户( u = ( 1 z ) 苎雩竺) = 2 p ( ( ，= ( 1 一z ) 苎雩竺) ：2 曩。一棚x 删： 即当z o 时，p ( = z ) = 2 昂一咖# x 圳2 综合知，形的分布如下： 咿叫= 麓，2