第3章_单向散列函数讲义

单向散列函数(HASH函数)基本原
Hash函数H(m)也名单向散列函数，它是现代密码学的核心。

散列函数一直在计算机科学中使用，散列函数就是把可变的输入长度串转换成固定长度输出值(叫做散列值)的一种函数。

而单向散列函数是在一个方向上工作的散列函数，从预映射的值很容易计算机其散列值，但要使其散列值等于一个特殊值却很难。

好的散列函数也是无冲突的：难于产生两个预映射的值，使他们的散列值相同。

散列函数是公开的，对处理过程并不保密，单向散列函数的安全性是它的单向性，其输出不依赖于输入。

平均而言，预映射值的单个位的改变，将引起散列值中一半位的改变。

已知一个散列值，要找到预映射的值，使它的值等于已知的散列值在计算上是不可行的，可把单向散列函数看作是构成指纹文件的一种方法。

如果你验证某人持有一个特定的文件(你同时也持有该文件)，但你不想他将文件传给你，那幺，就要通知他将该文件的散列值传给你，如果他传送的散列值是正确的，那幺可以肯定他持有那份文件。

散列函数可用于数字签名、消息的完整性检测、消息起源的认证检测等。

常见的散列算法有MD5、SHA、Snefru和HVAL等。

【C#集合】Hash哈希函数散列函数摘要算法希函数定义哈希函数（英語：Hash function）⼜称散列函数、散列函数、摘要算法、单向散列函数。

散列函数把消息或数据压缩成摘要，使得数据量变⼩，将数据的格式固定下来。

该将数据打乱混合，重新创建⼀个（哈希函数返回的值）称为指纹、哈希值、哈希代码、摘要或散列值（hash values，hash codes，hash sums，或hashes）的指纹。

散列值通常⽤⼀个短的随机字母和数字组成的字符串来代表。

好的散列函数在输⼊域中很少出现。

完美哈希函数就是指没有冲突的哈希函数。

如今，散列算法也被⽤来加密存在数据库中的（password）字符串，由于散列算法所计算出来的散列值（Hash Value）具有不可逆（⽆法逆向演算回原本的数值）的性质，因此可有效的保护密码。

使⽤哈希函数为哈希表编制索引称为哈希或分散存储寻址。

单向散列函数（one-wayhash function），也就是通俗叫的哈希函数。

第⼀个特点：输⼊可以任意长度，输出是固定长度第⼆个特点：计算hash值的速度⽐较快第三个特点，冲突特性（Collision resistance）：找出任意两个不同的输⼊值 x、y，使得 H （x）= H （y）是困难的。

（这⾥称为「困难」的原因，是消息空间是⽆穷的，⽽是有限的，因此⼀定会存在碰撞，只是对寻找碰撞的算⼒需要有难度上的约束以哈希函数SHAI （输出为 160-bit）为例：其输出空间为（0，2^160），假设输出范围⼀万亿个哈希值，发⽣碰撞的概率仅为 3×10-25。

被碰撞的概率太低，⼏乎不可能。

第四个特点：隐藏性（Hiding）或者叫做单向性（one-way）：哈希函数的单向性意味着，给定⼀个哈希值，我们⽆法（很难）逆向计算出其原像输⼊。

第五点：谜题友好（puzzlefriendly）HashTable定义哈希表时保存数据的表。

通过哈希函数使得数据和存储位置之间建⽴⼀⼀对应的映射关系。

散列函数及其应⽤散列函数 散列，英⽂Hash，也有直接⾳译为“哈希”的，就是把任意长度的输⼊（⼜叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。

这种转换是⼀种压缩映射，也就是，散列值的空间通常远⼩于输⼊的空间，不同的输⼊可能会散列成相同的输出，所以不可能从散列值来确定唯⼀的输⼊值。

简单的说就是⼀种将任意长度的消息压缩到某⼀固定长度的信息摘要的函数。

散列函数的应⽤ 在算法竞赛中，我所接触到的主要有字符串hash⽤于把字符串“索引”为⼀个值，然后对复杂字符串进⾏操作，来加快遍历速度，降低算法复杂度。

把字符串匹配转移到了值匹配。

但是散列函数属于⼀种“概率型算法”，对于模的取值有⼀定概率出现碰撞。

所以在算法竞赛中不常使⽤，或者要多次测验避免碰撞。

在信息安全⽅⾯的应⽤主要体现在以下的3个⽅⾯： 1）⽂件校验 我们⽐较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能⼒，它们⼀定程度上能检测并纠正数据传输中的信道误码，但却不能防⽌对数据的恶意破坏。

MD5 Hash算法的"数字指纹"特性，使它成为⽬前应⽤最⼴泛的⼀种⽂件完整性校验和（Checksum）算法，不少Unix系统有提供计算md5 checksum的命令。

2）数字签名 Hash 算法也是现代密码体系中的⼀个重要组成部分。

由于⾮对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了⼀个重要的⾓⾊。

对 Hash 值，⼜称"数字摘要"进⾏数字签名，在统计上可以认为与对⽂件本⾝进⾏数字签名是等效的。

⽽且这样的协议还有其他的优点。

3）鉴权协议 如下的鉴权协议⼜被称作"挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是⼀种简单⽽安全的⽅法。

散列函数的安全性 两个不同的输⼊，经过哈希算法后，得到了同样的哈希值，就叫做哈希碰撞。

单向散列函数算法（Hash算法）：一种将任意长度的消息压缩到某一固定长度（消息摘要）的函数（过程不可逆），常见的单向散列算法有MD5,SHA.RIPE-MD,HAVAL,N-Hash由于Hash函数的为不可逆算法，所以软件智能使用Hash函数作为一个加密的中间步骤MD5算法：即为消息摘要算法（Message Digest Algorithm），对输入的任意长度的消息进行预算，产生一个128位的消息摘要简易过程：1、数据填充..即填出消息使得其长度与448（mod 512）同余，也就是说长度比512要小64位（为什么数据长度本身已经满足却仍然需要填充？直接填充一个整数倍）填充方法是附一个1在后面，然后用0来填充..2、添加长度..在上述结果之后附加64位的消息长度，使得最终消息的长度正好是512的倍数..3、初始化变量..用到4个变量来计算消息长度（即4轮运算），设4个变量分别为A,B,C,D（全部为32位寄存器）A=1234567H,B=89abcdefH,C=fedcba98H,D=7654321H4、数据处理..首先进行分组，以512位为一个单位，以单位来处理消息..首先定义4个辅助函数，以3个32为双字作为输入，输出一个32为双字F(X,Y,Z)=(X&Y)|((~X)&Z)G(X,Y,Z)=(X&Z)|(Y&(~Z))H(X,Y,Z)=X^Y^ZI(X,Y,Z)=Y^(X|(~Z))其中，^是异或操作这4轮变换是对进入主循环的512为消息分组的16个32位字分别进行如下操作：（重点）将A,B,C,D的副本a,b,c,d中的3个经F,G,H,I运算后的结果与第四个相加，再加上32位字和一个32位字的加法常数（所用的加法常数由这样一张表T[i]定义，期中i为1至64之中的值，T[i]等于4294967296乘以abs(sin(i))所得结果的整数部分）（什么是加法常数），并将所得之值循环左移若干位（若干位是随机的？？），最后将所得结果加上a,b,c,d之一（这个之一也是随机的？）（一轮运算中这个之一是有规律的递增的..如下运算式），并回送至A,B,C,D，由此完成一次循环。

单向散列函数简单散列函数每个分组按比特异或(简单奇偶校验)：改进：针对可预测数据，每次循环左移一位将数据和散列值再异或。

结果：随机化、去格式化i i1i2imC b b ...b =⊕⊕⊕单向散列函数：Hash Function ，哈希函数、杂凑函数将任意长度的消息M 映射成一个固定长度散列值h 的函数：h=H(M)其中，h 的长度为m 。

用途：消息认证、数字签名。

单向散列函数散列函数要具有单向性，则必须满足如下特性：●给定M，很容易计算h，便于软硬件实现。

●给定h，根据H(M)=h反推M很难。

（单向性）●给定M，找到另一M’满足H(M)=H(M’)很难。

（弱抗攻击性）在某些应用中，单向散列函数还需要满足抗碰撞(Collision)的条件：要找到两个随机的消息M和M’，使H(M)=H(M’)满足很难。

（强抗攻击性）还要求：能产生定长输出；寻找任意的M和M’，会满足H(M)=H(M’)很难。

实现：单向散列函数是建立在压缩函数之上的：…MD 表示消息摘要(Message Digest),单向散列函数输入：给定一任意长度的消息输出：长为m 的散列值。

压缩函数的输入：消息分组和前一分组的输出(对第一个函数需初始化向量IV)；输出：到该点的所有分组的散列，即分组M i 的散列为h i =f (M i , h i −1)循环：该散列值和下一轮的消息分组一起作为压缩函数下一轮的输入，最后一分组的散列就是整个消息的散列。

3.1 MD5 算法3.1.1 算法MD5对输入的任意长度消息产生128位散列值：填充位消息长度(K mod 264)…MD5算法五个步骤：1) 附加填充位2) 附加长度3) 初始化MD 缓冲区处理1) 附加填充位填充消息，使其长度为一个比512的倍数小64位的数。

填充方法：在消息后面填充一位1，然后填充所需数量的0。

填充位的位数从1～512。

2) 附加长度将原消息长度的64位表示附加在填充后的消息后面。

⽹络安全-安全散列函数，信息摘要SHA-1，MD5原理-----------------------------------------------欢迎查看⽹络安全连载博客--------------------------------------------------------------------------------------------------------------------------------------------------------本⽂绝⼤部分内容来⾃《⽹络安全基础——应⽤与标准》第五版——清华⼤学出版社。

当中蓝⾊部门是⾃⼰加⼊安全散列函数单向散列函数或者安全散列函数之所以重要，不仅在于消息认证(消息摘要。

数据指纹)。

还有数字签名（加强版的消息认证）和验证数据的完整性。

常见的单向散列函数有MD5和SHA散列函数的要求散列函数的⽬的是⽂件、消息或者其它数据块产⽣“指纹”。

为满⾜在消息认证中的应⽤，散列函数H必须具有下列性质：（1）H可适⽤于随意长度的数据块。

（2）H能够⽣成固定长度的输出。

（2）对于随意给定的x，计算H(x)相对easy，⽽且能够⽤软/硬件实现。

（4）对于随意给定的h，找到满⾜H(x)=h的x在计算上不可⾏。

满⾜这⼀特性的散列函数称之为：具备抗原像攻击性。

（5）对于随意给定的数据块x，找到满⾜H(y)=H(x)的y ≠ x在计算上是不可⾏；满⾜这⼀特性的散列函数称之为：抗弱碰撞性。

（6）找到满⾜H(x) = H(y)的随意⼀对(x,y)在计算上是不可⾏的。

满⾜这⼀特性的散列函数称之为：抗碰撞性。

前三个性质是使⽤散列函数进⾏消息认证的实际可⾏要求。

第四个属性，抗原像攻击，防⽌攻击者能够回复秘密值。

抗弱碰撞性保证了对于给定的消息。

不可能找到具有同样散列值的可替换消息。

满⾜上⾯前5个性质的散列函数称之为弱散列函数。

假设还满⾜第6个性质则称之为强散列函数。

收稿日期:2001204228基金项目:国家重点科技项目(攻关)计划资助课题(20002A31201205)单向散列函数的原理、实现和在密码学中的应用3辛运帏,廖大春,卢桂章(南开大学信息技术科学学院,天津300071)摘　要:简要介绍了单向散列函数的有关理论及实现情况,并且以密码学中广泛应用的单向散列函数M D5为例,详细介绍了它的原理和实现过程。

最后简要介绍了单向散列函数在当前的应用,并且提出了一种利用单向散列函数实现的新的用户密钥管理方案。

关键词:单向散列函数;密码学;邮摘散列算法;M D5中图法分类号:TP309.3 文献标识码:A 文章编号:100123695(2002)022*******　The Principle and Implement of One 2way Hash Functions andTheir Cryptographic ApplicationXI N Y un 2wei ,LI AO Da 2chun ,LU G ui 2zhang(College o f Information Technology &Science ,Nankai Univer sity ,Tianjin 300071,China )Abstract :The paper introduces the theory and im plement of one 2way hash functions ,and using the M D5Alg orithm which is extensively used in cry ptography as an exam ple ,introduces its principle and im plement in detail.At last ,we research the application of them ,and pre 2sent a new schedule of user key management.K ey w ords :One 2way Hash Function ;Cry ptography ;Message Digest Hash Alg orithm ;M D51　单向散列函数简介密码学中使用的单向散列函数将任意长度的消息压缩到某一固定长度的消息摘要。

4）单向散列函数介绍（Hash Function,哈希函数）：将任意长度的消息M映射/换算成固定长度值h(散列值，或消息摘要MD, Message Digest)，最大的特点为其具有单向性。

h=H(M)Hash函数用于消息认证（或身份认证）以及数字签名。

特性：(1)给定M，可算出h.(2)给定h，根据H(M)=h反推出M是非常困难的。

(3)给定M，要找到另外一个消息M*，使其满足H(M*)=H(M)=h 是非常困难的。

注（见参考E，p75）：－从理论上说，有很多消息能生成相同的消息摘要。

因为消息的长度是任意的，而摘要的长度是固定的。

－对于固定1000 bit的消息和固定128 bit的摘要，平均来说，有2872个消息与之对应，测试似乎不可能成功。

－对于一个128 bit的消息摘要算法，大约需要尝试2128个（长短不一的）消息，才能找到一个消息摘要与给定的摘要数值相吻合（作为攻击，当然该消息可为经篡改后的消息）。

注：这里是用无数次的“尝试”，而非简单从h反推出M。

－对于一个128 bit的消息摘要算法，需要尝试264个消息才能找到两个具有相同摘要的消息。

－为什么将消息摘要定为128 bit? 因为消息摘要为m bit，任何人想要得到两个具有相同摘要的消息，大约需要尝试2m/2个消息。

若m=64, 则需检查232个消息，这在计算上是可行的。

所以使m=128, 检查264个消息目前在计算上是不可行的。

应用举例讲解：（i）存储于银行计算机内的用户密码采用散列值，用于保密。

（ii）Alice要Bob写一份关于解雇Fred的报告，而Bob是Fred的朋友，想做“双面人”。

（iii）为文档和程序生成“指纹”或“DNA”。

在实际应用中，Hash函数是基于压缩函数的。

（RefC_p42_Hash函数）给定任意长度的消息，Hash函数输出长度为m的散列值（即消息摘要）。

压倒函数的输入为（1）明文消息分组Ｍi。

（2）前一压缩数据的输出CV i-1（Compressed Vector）。