密码学第6章单向散列(Hash)函数.ppt

教学内容 第1章 引论 第2章 古典密码学 第3章 流密码算法与伪随机数产生器 第4章 分组密码算法 第5章 分组密码算法的工作模式 第6章 单向散列(Hash)函数 第7章 公钥密码算法与数字签名算法 第8章 认证与密钥交换协议 第6章 单向散列(Hash)函数 定义：杂凑函数H是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(M)，作为认证符，称函数值H(M)为杂凑值、杂凑码或消息摘要。杂凑码是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生改变。 第6章 单向散列(Hash)函数——杂凑函数应满足的条件 杂凑函数的目的是为需认证的数据产生一个“指纹”。为了能够实现对数据的认证，杂凑函数应满足以下条件： ① 函数的输入可以是任意长。 ② 函数的输出是固定长。 ③ 已知x，求H(x)较为容易，可用硬件或软件实现。 ④ 已知h，求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(x)为单向杂凑函数。 第6章 单向散列(Hash)函数 ——杂凑函数应满足的条件(续) ⑤ 已知x，找出y(y≠x)使得H(y)=H(x)在计算上是不可行的。如果单向杂凑函数满足这一性质，则称其为弱单向杂凑函数。 ⑥ 找出任意两个不同的输入x、y，使得H(y)=H(x)在计算上是不可行的。 如果单向杂凑函数满足这一性质，则称其为强单向杂凑函数。 第⑤和第⑥个条件给出了杂凑函数无碰撞性的概念，如果杂凑函数对不同的输入可产生相同的输出，则称该函数具有碰撞性。 第6章 单向散列(Hash)函数 ——杂凑函数应满足的条件(续) 以上6个条件中，前3个是杂凑函数能用于消息认证的基本要求。第4个条件（即单向性）则对使用秘密值的认证技术极为重要。假如杂凑函数不具有单向性，则攻击者截获M和C=H(S‖M)后，求C的逆S‖M，就可求出秘密值S。第5个条件使得敌手无法在已知某个消息时，找到与该消息具有相同杂凑值的另一消息。这一性质用于杂凑值被加密情况时防止敌手的伪造，由于在这种情况下，敌手可读取传送的明文消息M，因此能产生该消息的杂凑值H(M)。 第6章 单向散列(Hash)函数 ——杂凑函数应满足的条件(续) 但由于敌手不知道用于加密杂凑值的密钥，他就不可能既伪造一个消息M，又伪造这个消息的杂凑值加密后的密文EK[H(M)]。然而，如果第5个条件不成立，敌手在截获明文消息及其加密的杂凑值后，就可按以下方式伪造消息：首先求出截获的消息的杂凑值，然后产生一个具有相同杂凑值的伪造消息，最后再将伪造的消息和截获的加密的杂凑值发往通信的接收方。第6个条件用于抵抗生日攻击。 第6章 单向散列(Hash)函数——生日攻击 已知一杂凑函数H有n个可能的输出，H(x)是一个特定的输出，如果对H随机取k个输入，则至少有一个输入y使得H(y)=H(x)的概率为0.5时，k有多大？ 为叙述方便，称对杂凑函数H寻找上述y的攻击为第Ⅰ类生日攻击。 因为H有n个可能的输出，所以输入y产生的输出H(y)等于特定输出H(x)的概率是1/n，反过来说H(y)≠H(x)的概率是1-1/n。 第6章 单向散列(Hash)函数——生日攻击（续） y取k个随机值而函数的k个输出中没有一个等于H(x)，其概率等于每个输出都不等于H(x)的概率之积，为[1-1/n]k，所以y取k个随机值得到函数的k个输出中至少有一个等于H(x)的概率为1-[1-1/n]k 。 由(1+x)k≈1+kx，其中|x|1，可得 1-[1-1/n]k ≈1-[1-k/n]=k/n 若使上述概率等于0.5，则k=n/2。特别地，如果H的输出为m比特长，即可能的输出个数n=2m，则k=2m-1。 第6章 单向散列(Hash)函数——生日悖论 生日悖论是考虑这样一个问题：在k个人中至少有两个人的生日相同的概率大于0.5时，k至少多大？为了回答这一问题，首先定义下述概率：设有k个整数项，每一项都在1到n之间等可能地取值，则k个整数项中至少有两个取值相同的概率为P(n, k)。因而生日悖论就是求使得P(365,k)≥0.5的最小k，为此首先考虑k个数据项中任意两个取值都不同的概率，记为Q(365, k)。如果k365，则不可能使得任意两个数据都不相同，因此假定k≤365。k个数据项中任意两个都不相同的所有取值方式数为 第6章 单向散列(Hash)函数——生日悖论（续） 即第1个数据项可从365个中任取一个，第2个数据项可在剩余的364个中任取一个，依次类推，最后一个数据项可从365-k+1个值中任取一个。如果去掉任意两个都不相同这一限制条件，可得k个数据项中所有取值方式数为365k。所以可得 第6章 单向散列(Hash)函数——生日悖论（续）