数理统计论文_张强_下载.doc

华中科技大学硕士学生数理统计课程论文密码算法输出序列随机性的检验学 生：张 强 学 号：M201272456 学生类型：硕 士 专 业：控制工程华中科技大学图像所二0—二年十二月密码算法输出序列随机性的检验1密码学的背景在二十一世纪电子商务和电子政务时代，人们所面临的-•个至关重要的问题 就是信息安全问题密码学是保障信息安全的核心技术，它以很小的代价提供很 大的安全保护，其应用涉及军事、国防、商贸以及人们口常生活中的各方面密码学是一门古老而又年青的科学，它用于保护军事和外交通信可追溯到几 千年前在当今的信息吋代，大量的每攵感信息如病历、法庭记录、资金转移、私 人财产等常常通过公共通信设施或计算机网络來进行交换，而这些信息的秘密性 和真实性是人们迫切需要的因此 现代密码学的应用己不再局限于军事、政治 和外交，其商用价值和社会价值也己得到了充分肯定密码学是数学、计算机、通信等多学科的交叉密码学的基础包括数论、概 率论与数理统计、信息论、编码等等概率统计主要用于对密码算法的统计性能 进行测试和分析，从而给密码编码人员和密码分析人员提供一定的信息密码学中的Hash函数(cryptography Hash functions)能够用于数据完整性和 消息认证以及数字签名。

其基本思想是把Hash函数值看成输入的消息摘要 (message digest),当输入中的任何一个二进制位发生变化时都将引起Hash函数 值的变化关于Hnsh的算法研究，一直是信息科学里面的-•个前沿，尤其在网络技术 普及的今天，他的重要性越來越突出，其实我们每天在网上进行的信息交流安全 验证，我们在使用的操作系统密钥原理，里面都有它的身影F1前己经公开的代 表性的 Hash 算法有 MD4、MD5、SHA-K SHA・2、RIPEMD-128 等为了满足 数据完整性和消息认证的需要，Hash函数必须满足特定的密码学要求，例如单 向性和抗碰撞等基于分组密码的Hnsh函数也是最近的研究热点之一主要用于信息安全领 域中的加密算法针对H“sh算法的一些弱点可对Hash算法进行攻击，可利用 Hash算法的代数结构及其所使用的分组密码的弱点來攻击一些Hash方案例如 针对DES的一些弱点(即互补性、弱密钥、密钥碰撞等)來攻击基于DES的Hash 方案新近的对于MDS等的碰撞攻击就表明在一个Hash两数的内部迭代过程中 的随机统计特性对其安全性也有一定程度影响因此对Hnsh函数迭代过程中输 出序列的随机性进行分析对于研究Hnsh两数的安全性是有重要意义的。

故运用 概率统计的思想方法來研究Hnsh函数的-些性质必将为密码分析人员提供-•些 新的攻击码方案的新方法和新思路，也必将使得将概率统计应用于密码学中成为 一个新的研究热点本文主要是研究概率论与数理统计在密码学中的应用：对Hnsh函数迭代过 程中输出序列的随机性进行分析我们无法用数学方法对一个序列是否是真正的 随机比特序列给出证明，但是我们可以通过使样本序列经过不同的统计测试来检 测该序列所具有的某些缺点;统计测试通常用说明随机样本的统计量被选择的 统计量通常易于有效计算，并且近似地服从N(O,1)或分布样本输出序列的 统计量的值经过计算，然后与特定的随机序列的期望值进行比较，从而可以对该 种Hnsh算法的安全性做出分析本文的测试对象主要是针对H“sh算法中的 SHA-256进行的，通过一係列的统计测试，对SHA-256的安全性做出了分析， 并指出了该算法的不足之处2 Hash函数的介绍密码学中的Hnsh函数主要用于数据完整性和消息认证以及数字签名Hash 函数是密码学领域内兴起的一种极其重要的通信工具，并且己成为密码学者最为 关注的焦点之一Hash函数是一种将任意长度的消息M压缩到某一固定长度的消息摘要 (message digest)函数，可以表示为h=H(M),其中h为输出值,长度为1, M为输 入明文。

定义1」若Hash函数H(M)满足以下性质：(1) 压缩性:对于任意长度的消息M g {0,1}*,输出的压缩值h = H(M)e {0,球, 并且计算h是容易的2) 抗计算原象性(Preimage resistance)：给定h,计算M满足H(M)=h是计 算上困难的3) 抗计算第二原象W：(2nd-Preimage resistance)：给定M,要找到另一消息 M，并满足H(M)= H(M*)是计算丄困难的则 Hjsh 函数 H(M)称为弱单向 Hash 函数(weak one-way Hash function)o 定义1.2若H(M)为弱单向Hash函数，并且满足下列特性：⑷抗碰撞性 (Collision resistance or Free-eollision):寻找任何明文对 M、M,并且满足H(M)= H(M)是计算上困难的则H(M)称为强单向Hash函数或者无碰撞Hash函数般也简称为单向 Hash函数或散列函数在密码学和信息安全领域里，儿个比较著名的算法都是通过迭代压缩函数来 实现的，因此，在用迭代方法设计函数时，最关键的是能否找到或设计出一个安 全的压缩函数通常设计压缩函数有两种方法：一、利用某些数学工具专为Hash H的而设计一个压缩函数。

二、利用现有的密码算法如分组密码来作为压缩函数 等H前，设计Hash函数的基本方法有以下几种：1) 利用某些数学难题比如因子分解问题、离散对数问题等设计Hash函数已设 计出的算法有DavieS-Price平方Hash算法、CCITT建议、Jueneoan Hash算 法、Damgard 平方 Hash 算法、Damgard 背包 Hash 算法、Sehnorr 的 FFT Hash 算法等2) 利用某些私钥密码体制比如DES等设计Hash函数这种Hash函数的安全性 与所使用的基础密码算法有关这类Hash算法有Rabin Hash算法、 Winternitz Hash 算法、Quisquater-GiraultHash 算法、Merkle Hash 算法、N-Hash 算法等3) 直接设计Hash函数，这类算法不基于任何假设和密码体制这种方法受到人 们的广泛关注和青睐，是为今比较流行的一种设计方法美国的安全Hash 算法(SHA)就是这类算法，此类算法还有MD4、MDS、MnZ、RxpE・MD、 HAVAL 等安全Hash算法包括SHA-K SHA-256. SHA-384和SHA-512四种(本文主要 以介绍SHA-256为主)。

这四种算法都是迭代的单向Hash函数，这些Hash函数 可以作用于一个消息(message)从血产生一个消息摘要(message digest)o这些算 法能够保证一个消息的完整性，即:消息的任何一个改变都将导致消息摘要以一 个很高的概率发生改变而这个性质在数字签名、信息证实代码和产生随机数的 应用中是很有用的安全Hnsh算法的每个算法都可以描述成两个步骤：预处理和Hash值的计 算预处理包括：a、消息填充，b、将填充后的消息分成若干个块，每个块都具 有mbit, c、设置初值这些初值将在计算Hash值的运算中用到Hash值的计 算可以从填充后的消息中产生一个消息列表，使用这个表，连同函数，常量和字 操作可以反复的产生一系列的Hash值由Hash计算产生的最终的Hash值是用 来决定消息摘要的这四个算法在为混乱后的数据提供的安全比特位数上是有明显的不同的这 主要与消息摘要的长度有关为一•个安全的Hash算法与另一个算法一起使用时， 可能需要一些特定的条件:需要使用-•个具有一定安全比特位数的安全Hash算法 例如:如果-•个有正负Z分的消息使用了-•个提供了 128位安全比特数的数字名 算法，那么这个数字签名算法可能就需要使用-•个也提供128位安全比特数的全 Hash 算法(如 SHA-256)O3随机序列的统计测试对一个密码算法来说，其输出序列的随机性是其安全性的很重要的一方面。

对基于分组密码算法的Hash函数来说，其是否可以用作伪随机数产生器是评价 这个算法的重要指标Z—（可参看AES的评选报告）所以随机性测试在密码学中 占有很重要的作用3.1随机序列在许多密码机制中，随机数生成都是一个重要的要素例如，加密变换的密 钥必须以一种不可被敌手预测的方式产生血生成-•个随机密钥通常涉及随机数 或随机比特序列的选择随机序列常被用做密钥管理，其主要功能是产生真随机 的序列来用做密钥产生随机序列的方法有很多种，既有数学方法产生的，也有 物理方法产生的，从而随机数产生器有真随机和伪随机Z分随机比特生成器、：一种能够输出统计上独立且无偏的二进制数字序列的设 备或算法真随机数产生器产生的随机数是不可重现的，绝大多数真随机序列源 都来自物理方法，产生它们的代价大、速度慢为此，使用伪随机序列:按一种 确定的方式从一个称为种子的较短序列来构造的序列通常生成算法是公开的, 但种子除了生成序列的实体外不被人所知伪随机比特生成器（PRBG）：-利确定性算法（给定了相同的初始种子吋，生 成器将产生相同的输出序列），即在给定长度为k的真随机二进制序列吋，能够 输出一个长度为/（/>>）且看上去“随机”的二进制序列。

PRBG的输入称为种 子，输出称为伪随机比特序列实际丄，伪随机数产生器产生的随机数并不是真 的随机，其具有周期性，也就是说，其产生的随机数序列总会产生重复，不过如 果产生器的周期足够长（至少要远远大于可能采集的随机数的长度），那么这个随 机数产生器产生的局部的随机序列也就和真随机序列看起来没有什么区别了如 线性同余发生器、线性反馈移位寄存器、附加式发生器等3.2随机性测试的重要性不管是真随机数产生器还是伪随机数产生器，都必须通过随机性测试对一 个密码算法来说，其输出序列的随机性是其安全性的很重要的一方面对分组密 码算法来说，其是否可以看作伪随机数产生器是评价这个算法的重要指标之一 （可参看AES的评选报告）所以随机性测试在密码学中占有很重要的作用密码 学意义上安全的随机数比其它大多数应用对随机性的要求更严格，要求满足以下 3个基本的特性：（1） 不可预测性;也就是说，即使给出产生序列的算法或者硬件设计和以前己经产 生的序列的所有知识，你也不可能通过计算來预测下一个比特是什么2） 不能重复产生;也就是说，即使在完全相同的操作条件下（同样的地点、同样 的温度等）用完全相同的输入对序列产生器操作两次，你也将得到两个完全不 同的、毫不相关的位序列。

3) 能通过随机性统计检验即能通过我们所能找到的所有的正确的随机性检验， 这也是最起码的要求H前存在的随机性检验约有200多个，而且根据参数 的改变—•个检验有时可以变换为很多个检验，要让一个算法通过所有的随机 性检验是件很困难的事，但是有些基本的检验是必须得通过的，比如频数检 验算法无法通过某个随机性检验就表明算法的设计在某些方而有缺陷这 无疑也给密码分析人员或密码攻击人员提供了一定的信息本文主要是针对 SHA-256的每一轮输出序列进行了一系列的随机性统计检验，考察了 SHA-256的安全性问题序列的随机性检测一直是信息安全领域的一个重要研究方向Hash函数输 出序列的随机性如何直接影响到整个系统的安全性所以，对Hash函数的输出 序列进行随机性研究是有重大意义的随机序列的统计测试主要是用随机数产生器或者密码算法产生一审二进制 序列，设计一系列的统计测试来检验其是否是真随机的或与真随机的差距我们 无法用数学方法对一个序列是否是真正的随机比特序列给出证明，但是我们可以 通过使样本序列经过不同的统计测试来检测该序列所具有的某些缺点;统计测试。