华中科技大学硕士学生数理统计课程论文密码算法输出序列随机性的检验学 生：张 强学 号：M201272456学生类型：硕 士 专 业：控制工程华中科技大学图像所二 O 一二年十二月华中科技大学硕士学生数理统计课程论文 密码算法输出序列随机性的检验第 1 页密码算法输出序列随机性的检验1 密码学的背景在二十一世纪电子商务和电子政务时代，人们所面临的一个至关重要的问题就是信息安全问题密码学是保障信息安全的核心技术，它以很小的代价提供很大的安全保护，其应用涉及军事、国防、商贸以及人们日常生活中的各方面密码学是一门古老而又年青的科学，它用于保护军事和外交通信可追溯到几千年前在当今的信息时代，大量的敏感信息如病历、法庭记录、资金转移、私人财产等常常通过公共通信设施或计算机网络来进行交换，而这些信息的秘密性和真实性是人们迫切需要的因此，现代密码学的应用己不再局限于军事、政治和外交，其商用价值和社会价值也己得到了充分肯定密码学是数学、计算机、通信等多学科的交叉密码学的基础包括数论、概率论与数理统计、信息论、编码等等概率统计主要用于对密码算法的统计性能进行测试和分析，从而给密码编码人员和密码分析人员提供一定的信息。
密码学中的 Hash 函数 (cryptography Hash functions)能够用于数据完整性和消息认证以及数字签名其基本思想是把 Hash 函数值看成输入的消息摘要(message digest)，当输入中的任何一个二进制位发生变化时都将引起 Hash 函数值的变化关于 Hash 的算法研究，一直是信息科学里面的一个前沿，尤其在网络技术普及的今天，他的重要性越来越突出，其实我们每天在网上进行的信息交流安全验证，我们在使用的操作系统密钥原理，里面都有它的身影目前己经公开的代表性的 Hash 算法有 MD4、MD5、SHA-1、SHA-2、RIPEMD-128 等为了满足数据完整性和消息认证的需要，Hash 函数必须满足特定的密码学要求，例如单向性和抗碰撞等基于分组密码的 Hash 函数也是最近的研究热点之一主要用于信息安全领域中的加密算法针对 Hash 算法的一些弱点可对 Hash 算法进行攻击，可利用Hash 算法的代数结构及其所使用的分组密码的弱点来攻击一些 Hash 方案例如针对 DES 的一些弱点(即互补性、弱密钥、密钥碰撞等)来攻击基于 DES 的Hash 方案新近的对于 MDS 等的碰撞攻击就表明在一个 Hash 函数的内部迭代过程中的随机统计特性对其安全性也有一定程度影响。
因此对 Hash 函数迭代过程中输出序列的随机性进行分析对于研究 Hash 函数的安全性是有重要意义的故运用概率统计的思想方法来研究 Hash 函数的一些性质必将为密码分析人员提供一些华中科技大学硕士学生数理统计课程论文 密码算法输出序列随机性的检验第 2 页新的攻击码方案的新方法和新思路，也必将使得将概率统计应用于密码学中成为一个新的研究热点本文主要是研究概率论与数理统计在密码学中的应用：对 Hash 函数迭代过程中输出序列的随机性进行分析我们无法用数学方法对一个序列是否是真正的随机比特序列给出证明，但是我们可以通过使样本序列经过不同的统计测试来检测该序列所具有的某些缺点;统计测试通常用说明随机样本的统计量被选择的统计量通常易于有效计算，并且近似地服从 N(0,1)或分布样本输出序2列的统计量的值经过计算，然后与特定的随机序列的期望值进行比较，从而可以对该种 Hash 算法的安全性做出分析本文的测试对象主要是针对 Hash 算法中的 SHA-256 进行的，通过一系列的统计测试，对 SHA-256 的安全性做出了分析，并指出了该算法的不足之处。
2 Hash 函数的介绍密码学中的 Hash 函数主要用于数据完整性和消息认证以及数字签名Hash 函数是密码学领域内兴起的一种极其重要的通信工具，并且己成为密码学者最为关注的焦点之一Hash 函数是一种将任意长度的消息 M 压缩到某一固定长度的消息摘要(message digest)函数，可以表示为 h=H(M)，其中 h 为输出值，长度为 l，M 为输入明文定义 1.1 若 Hash 函数 H(M)满足以下性质：(1) 压缩性:对于任意长度的消息，输出的压缩值，*{01}M ， hH M{01}l，并且计算 h 是容易的2) 抗计算原象性 (Preimage resistance)：给定 h，计算 M 满足 H(M)=h 是计算上困难的3) 抗计算第二原象性(2nd-Preimage resistance)：给定 M，要找到另一消息M’并满足是计算上困难的 H MH M'则 Hash 函数 H(M)称为弱单向 Hash 函数 (weak one-way Hash function)定义 1.2 若 H(M)为弱单向 Hash 函数，并且满足下列特性：(4)抗碰撞性 (Collision resistance or Free-eollision):寻找任何明文对 M、，并且满足是计算上困难的。
M' H MH M'则 H(M)称为强单向 Hash 函数或者无碰撞 Hash 函数一般也简称为单向Hash 函数或散列函数在密码学和信息安全领域里，几个比较著名的算法都是通过迭代压缩函数来实现的，因此，在用迭代方法设计函数时，最关键的是能否找到或设计出一个安全的压缩函数通常设计压缩函数有两种方法：一、利用某些数学工具专华中科技大学硕士学生数理统计课程论文 密码算法输出序列随机性的检验第 3 页为 Hash 目的而设计一个压缩函数二、利用现有的密码算法如分组密码来作为压缩函数等目前，设计 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-l、SHA-256、SHA-384 和 SHA-512 四种(本文主要以介绍 SHA-256 为主)这四种算法都是迭代的单向 Hash 函数，这些 Hash函数可以作用于一个消息(message)从而产生一个消息摘要 (message digest)这些算法能够保证一个消息的完整性，即:消息的任何一个改变都将导致消息摘要以一个很高的概率发生改变而这个性质在数字签名、信息证实代码和产生随机数的应用中是很有用的安全 Hash 算法的每个算法都可以描述成两个步骤：预处理和 Hash 值的计算预处理包括：a、消息填充，b、将填充后的消息分成若干个块，每个块都具有 m bit，c、设置初值。
这些初值将在计算 Hash 值的运算中用到Hash 值的计算可以从填充后的消息中产生一个消息列表，使用这个表，连同函数，常量和字操作可以反复的产生一系列的 Hash 值由 Hash 计算产生的最终的 Hash值是用来决定消息摘要的这四个算法在为混乱后的数据提供的安全比特位数上是有明显的不同的这主要与消息摘要的长度有关当一个安全的 Hash 算法与另一个算法一起使用时，可能需要一些特定的条件:需要使用一个具有一定安全比特位数的安全 Hash算法例如:如果一个有正负之分的消息使用了一个提供了 128 位安全比特数的数字名算法，那么这个数字签名算法可能就需要使用一个也提供 128 位安全比特数的全 Hash 算法(如 SHA-256)华中科技大学硕士学生数理统计课程论文 密码算法输出序列随机性的检验第 4 页3 随机序列的统计测试对一个密码算法来说，其输出序列的随机性是其安全性的很重要的一方面对基于分组密码算法的 Hash 函数来说，其是否可以用作伪随机数产生器是评价这个算法的重要指标之一(可参看 AES 的评选报告)所以随机性测试在密码学中占有很重要的作用。
3.1 随机序列在许多密码机制中，随机数生成都是一个重要的要素例如，加密变换的密钥必须以一种不可被敌手预测的方式产生而生成一个随机密钥通常涉及随机数或随机比特序列的选择随机序列常被用做密钥管理，其主要功能是产生真随机的序列来用做密钥产生随机序列的方法有很多种，既有数学方法产生的，也有物理方法产生的，从而随机数产生器有真随机和伪随机之分随机比特生成器、：一种能够输出统计上独立且无偏的二进制数字序列的设备或算法真随机数产生器产生的随机数是不可重现的，绝大多数真随机序列源都来自物理方法，产生它们的代价大、速度慢为此，使用伪随机序列:按一种确定的方式从一个称为种子的较短序列来构造的序列通常生成算法是公开的，但种子除了生成序列的实体外不被人所知伪随机比特生成器(PRBG)：一种确定性算法(给定了相同的初始种子时，生成器将产生相同的输出序列)，即在给定长度为 k 的真随机二进制序列时，能够输出一个长度为且看上去“随机”的二进制序列PRBG 的输入称()l lk为种子，输出称为伪随机比特序列实际上，伪随机数产生器产生的随机数并不是真的随机，其具有周期性，也就是说，其产生的随机数序列总会产生重复，不过如果产生器的周期足够长(至少要远远大于可能采集的随机数的长度)，那么这个随机数产生器产生的局部的随机序列也就和真随机序列看起来没有什么区别了。
如线性同余发生器、线性反馈移位寄存器、附加式发生器等 3.2 随机性测试的重要性不管是真随机数产生器还是伪随机数产生器，都必须通过随机性测试对一个密码算法来说，其输出序列的随机性是其安全性的很重要的一方面对分组密码算法来说，其是否可以看作伪随机数产生器是评价这个算法的重要指标之一(可参看 AES 的评选报告)所以随机性测试在密码学中占有很重要的作用密码学意义上安全的随机数比其它大多数应用对随机性的要求更严格，要求满足以下 3 个基本的特性：(1) 不可预测性;也就是说，即使给出产生序列的算法或者硬件设计和以前己经产生的序列的所有知识，你也不可能通过计算来预测下一个比特是什么2) 不能重复产生;也就是说，即使在完全相同的操作条件下(同样的地点、同样华中科技大学硕士学生数理统计课程论文 密码算法输出序列随机性的检验第 5 页的温度等)用完全相同的输入对序列产生器操作两次，你也将得到两个完全不同的、毫不相关的位序列3) 能通过随机性统计检验即能通过我们所能找到的所有的正确的随机性检验，这也是最起码的要求目前存在的随机性检验约有 200 多个，而且根据参数的改变一个检验有时可以变换为很多个检验，要让一个算法通过所有的随机性检验是件很困难的事，但是有些基本的检验是必须得通过的，比如频数检验。
算法无法通过某个随机性检验就表明算法的设计在某些方面有缺陷这无疑也。