文档介绍：第8章 Hash函数
Hash函数的定义
Hash函数H,也称为杂凑函数,是一个公开函数,将任意长度的消息M映射为较短的、固定长度的一个值H(M)
H(M)称为杂凑值、消息摘要,为消息中所有bit的函数,提供了错误检测的能力
Hash函数与数字签名
Hash函数可以用于数字签名。将Hash函数用于数字签名的好处:
(1)可以提高签名的速度;
(2)可以不泄漏签名所对应的消息;
(3)可以将对消息的签名变换与加密变换分开处理
此外,Hash函数还可以用于消息的完整性检测等方面
几个定义
给定一个消息x,如果寻找另外一个与x不同的消息y,使得H(x)=H(y)是计算上不可行的,则称H关于消息x是弱无碰撞的.
如果寻找两个不同的消息x和y,使得H(x)=H(y)在计算上是不可行的,则称H是强无碰撞的.
如果对于任意给定的z,寻找满足H(x)=z的消息x是计算上不可行的,则称H是单向的.
Hash函数的性质
函数的输入可以是任意长,输出是固定长
已知x,求H(x)较为容易
H(x)是单向的
寻找两个不同的消息x,y,使得H(x)=H(y)是难解的
生日攻击
(第I类生日攻击)H有n个输出,H(x)是一个特定的输出,如果对H随机取k个输入,至少有一个y使H(y)=H(x),k有多大?
H(y)=H(x)的概率为1/n,不等的概率为1-1/[1-1/n]- [1-1/n]k,近似等于k/n。,k为n/2。
生日悖论
在一个会场参加会议的人中,?
t个人都不同时生日概率为
,因此,至少有两人于同日生的概率为
解之,当t23时,p>。对于n比特杂凑值的生日攻击,由上式可计算出,当进行2n/。
Hash函数MD5
MD5 Hash Algorithm
算法步骤(1)-分组填充
Ron Rivest于1990年提出MD-4杂凑算法。输入消息可任意长,压缩后输出为128bits。1992年改进为MD-5。
消息
100…0
64bit
消息长度
填充图样
L×512bit
Kbit
消息的填充
设x是一个消息,用二进制表示。M为由x生成的一个数组
M=M[0]M[1]……M[N-1]
其中M[i]是长度为32位的(0,1)序列,N=0(mod16).M[i]称为一个字。M按下述
算法由x生成:
(1)d=(447-|x|)mod512
(2)令L为|x|mod264 的二进制表示,L的长度为64位。如果L的长度不足64位,则在L的左端添0补足.
(3)M=x||1||0d||L
其中|x|表示x的长度,||表示序列的连接。在M的构造中,首先在x的右端添
加一个1,然后填充尽可能多的0使其长度恰好位512的倍数减去64,最后64
,则最后64位
为|x|mod264 的二进制表示。这样M的长度恰好为512的倍数。