100…0
报文长度(K mod 264)
512 bits
512 bits
512 bits
512 bits
Y0
512 128 128
Y1
512 128
Yq
512 128
M
M
D
Bob
提供认证 提供保密
Alice
认证函数：Hash函数（续）
哈希函数的基本用法（b）
H M H E
K Bob EK(H(M)) K ||
M
D
比较
Alice
提供认证
认证函数：Hash函数（续）
哈希函数的基本用法（c）
H M H D
K’b Bob DK’b(H(M)) Kb ||
M
E
比较
Alice
哈希函数
实际性质：哈希函数
函数 y=H(x)满足
（1）将任意长度的比特串x压缩成为固定长度的比特串y。
（2）已知x，计算y=H(x)很容易；已知y，找一个x满足
y=H(x)却很困难。这一性质称为单向性。 （3）找(x1，x2)，x1≠x2，H(x1)= H(x2)，很困难。这一性质 称为无碰撞性。 这样的函数称为哈希函数。
Hash函数的安全性
中间相遇攻击（in-the-middle attack） 用于攻击一类具有特殊结构的Hash函数 分析Hash函数运算的中间值相等的概率 讨论一类利用加密变换构造的Hash函数
攻击方式: 假设攻击者要找出一个假消息M=(M1, M2)，
使得M与m是一个碰撞。设m的散列值都为d。攻击者首 先产生消息M1的r个变形，消息M2的R个变形.
Hash函数的安全性
生日攻击法 分别把消息m和M表示成r和R个变形的消息
Hash函数的安全性
生日攻击法 计算真消息m的变形与假消息M的变形发生碰撞的概率 由于n比特长的散列值共有2n个，所以对于给定m的变 形mi和M的变形Mj，mi与Mj不碰撞的概率是1-1/2n。由 于M共有R个变形，所以M的全部变形都不与mi碰撞的 n R 概率是： 1 1/ 2 .


因为消息m共有r个变形，因此m的变形与M的变形都不碰 撞的概率是： n rR 1 1/ 2 .


m的变形与M的变形发生碰撞的概率是：
1 P ( n ) 1 1 n 2
rR
1 e

rR 2n
.
Hash函数的安全性
生日攻击法 当r=R=2n/2时，P(n)=1e10.63。对于Hash值长度为64 比特的Hash函数，生日攻击的时间复杂度约为232，所以 是不安全的。 为了抵抗生日攻击，建议Hash值长度至少为128 比特.
Hash函数的安全性
中间相遇攻击（in-the-middle attack） 用于攻击一类具有特殊结构的Hash函数 分析Hash函数运算的中间值相等的概率 讨论一类利用加密变换构造的Hash函数 设加密体制为：
K M n , EK : K M n
对于消息m=(m1, m2)，其散列值的计算分以下两步： （1） h1= EK(m1, IV)； （2） d=h(m)=EK (m2, h1)， 其中IV是加密变换的初始值。 这类Hash函数将遭受中间相遇攻击。
双方知道的秘密密钥K来控制。此时，散列值称作 MAC(消息认证码 )。 不带秘密密钥的Hash函数：消息的散列值的产生 无需使用密钥。此时，散列值称作MDC(消息检 测 码 )。
认证函数：Hash函数（续）
哈希函数的基本用法（a）
M
H H(M) || K E K EK(M|H(M)) H M 比较
提供认证
认证函数：Hash函数（续）
哈希函数的基本用法(d)
M H
D DK’b(H(M)) K’b Bob 比较 E 提供认证 提供保密 |DK’b(H(M)) H
M
Alice
认证函数：Hash函数（续）
哈希函数的基本用法（e）
S || M || H H(M||S) Alice 提供认证 M
消息认证概念
三元组（K,T,V)
密钥生成算法K
标签算法T 验证算法V
攻击者 信源 认证编码器
T
信道
认证译码器
V
信宿
安全信道
K
密钥源
认证函数
鉴别编码器和鉴别译码器可抽象为认证函数 认证函数 产生一个鉴别标识（Authentication Identification） 给出合理的认证协议(Authentication Protocol) 接收者完成消息的鉴别（Authentication）
||
H
比较
S
Bob
认证函数：Hash函数（续）
哈希函数的基本用法（f）
M || H || M E K H(M||S) E (M||H(M||S) K S || H 比较 M K D
S
M
Bob
提供认证 提供保密
Alice
Hash函数用于数字签名
2013-12-26
西安电子科技大学计算机学院
20
杂凑函数应满足的条件
1 2 k 1 P (365 , k ) 1 1 1 ...1 . 365 365 365
有P(365,23)=0.5073。即在23个人中，至少有两个人 生日相同的概率大于0.5，这个数字比人们直观猜测的 结果小得多，因而称为生日悖论。
函数的输入可以是任意长 函数的输出是固定长 已知x,求H(x)较为容易 已知h，求H(x)＝h的在计算上不可行，即单向杂凑函数. 已知x，找出y(y≠x)使得H(y)=H(x)在计算上是不可行 的。满足这一性质，则称其为弱单向杂凑函数。 找出任意两个不同的x,y，是H(x)=H(y)在计算上不可行， 满足这一性质，称为强单向杂凑函数.
Hash函数的安全性
变形 假消息的 第1部分 M1 M1,1 M1,2 M 1,r IV EK EK 中间值集合
EK
假消息的 第2部分 M2
M2,1 M2,2 M 2,R
DK DK
DK
h1= EK(m1, IV) d=h(m)=EK(m2, h1)
目标摘要
d
Hash函数的安全性
压缩函数（compression function）
f : {0,1}mt {0,1}m (t 1)
迭代技术
设x是一个长 度为L的比特串。 重复应用压缩函 数f，对消息x进 行多次压缩，最 后得到x的散列 值
Hash函数的迭代构造法
计算消息x的散列值h(x)的步骤 预处理: 用一个公开算法在消息x右方添加若干比特， 得到比特串y，使 得y的长度为t的倍数。即有 y= x || pad(x) = y1 || y 2 || … || yr , 其中| yi|=t (i =1, 2,…, r)，pad(x)称为填充函数。典型 的填充函数是先添加x长度| x|的值，再添加若干比特 （例如0）。 迭代过程: 设H0=IV是一个长度为m的初始比特串， 重复使用压缩函数f，依次计算 Hi= f (Hi1|| yi) (i =1, 2,…, r). 输出变换: 设g: {0,1}m{0,1}t是一个公开函数，令
迭代型杂凑函数的一般结构
Y0 b b Y1 明文M被分为L个分组 Y0,Y1,…,YL-1 b:明文分组长度 n:输出hash长度 CV：各级输出，最后 一个输出值是hash值
YL-1 b
f
n IV=CV0 CV1
n
f
n
n CVL-1
f
CVL n
无碰撞压缩函 数f是设计的 关键
Hash函数的迭代构造法
计算 : H1 h1,i EK ( M 1,i , IV ) | i 1,2,..., r, 令:
M
1,i
| i 1,2,..., r, M 2, j | j 1,2,..., R .
H 2 h2, j DK ( M 2, j , d ) | j 1,2,..., R .
2013-12-26
西安电子科技大学计算机学院
7
Message Authentication
Message Authentication：报文鉴别（消息认证， 消息鉴别） Message：消息、报文。 Authentication： 鉴别、认证。 认证：消息的接收者对消息进行的验证 真实性：消息确实来自于其真正的发送者， 而非假冒； 完整性：消息的内容没有被篡改。 是一个证实收到的消息来自可信的源点且未被 篡改的过程。它也可以验证消息的顺序和及时 性
第八讲 密码学hash函数
哈希函数（杂凑函数）
（1）Hash编码； （2）Hash函数； （3）散列编码： （4）散列函数； （5）单向压缩函数。
哈希函数
在公钥密码的内容中，已经介绍了“单向函 数”的概念。而哈希函数是一类特殊的单向函数。 设数据文件是任意长度的比特串x 。在密码应 用中，希望有这样的函数 y=H(x)，满足： （1）将x压缩成为固定长度的比特串y。 （2）不同的x一定要生成不同的y。 （3）由y的值无法倒算x的值。
算法描述
MD4是MD5杂凑算法的前身，由Ron Rivest于 1990年10月作为RFC提出，1992年4月公布的 MD4的改进（RFC 1320，1321）称为MD5。
MD5
MD5产生报文摘要的过程
L512 bits=N 32bits K bits 报文
填充 (1 to 512 bits)
Hash函数的安全性
对Hash函数的攻击是指寻找一对碰撞消息的过程 生日悖论（birthday paradox） 生日问题：假设每个人的生日是等概率的，每年有365 天，在k个人中至少有两个人的生日相同的概率大于1/2， 问k最小应是多少？ k人生日都不同的概率是：