密码学上的hash函数研究现状及进展

《密码学上的hash函数研究现状及进展》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、加密技术密码学上的Hash函数研究现状及进展马陵勇1张姗姗2淮北煤炭师范学院数学系安徽235000摘要：本文描述了密码学上Hash函数的现状。比较了不同的Hash函数定义，并且讨论了Hash函数几个理论上的结果，最后提出了几个公开的Hash函数问题。关键词：Hash函数；原像稳固；第二原像稳固；碰撞稳固；攻击0引言的定义由Merkle给出，一个碰撞稳固的Hash函数h是满足下列条件的一个函数h：本文就密码学上的Hash函数作一个概括的总结。用尽可能浅显的语言讨论Hash函数的定义、一般构造和安全结果，（1）自变量

2、x是任意长度的比特串，而结果h(x)是一个具以及常用的Hash函数现状，最后提出了一些公开的问题。有固定长度n的比特串(n≥128,⋯,160);1定义（2）h是单向函数，也即原像稳固和第二原像稳固;（3）h必须是碰撞稳固的，也即找两个不同的消息而他们以下讨论中，我们用h来表示Hash函数，h的自变量也的Hash值一样是难于实现的。就是被保护的消息用x表示，x在h下的像用h(x)表示，并且解决碰撞问题要比解决第二原像问题容易，因此该定义假定关于Hash函数h的描述是公开的，h不需要任何保密的中关于第二原像的条件是

3、多余的，但是原像稳固并不是碰撞信息。关于h的第二个假定是给了输入信息x，计算x在h下稳固的必要条件(这是某些应用上的要求)。的Hash值是容易的。给碰撞稳固下一个正式的定义并不像正式定义单向函数1.1单向hash函数(OUWHF)那样直接，难点在于不能把“不会存在输出碰撞的敌手”这定义1一个单向Hash函数H是一个具有定义域为个问题具体化。因为有许多长度较短的碰撞输入，这将会有，值域为的函数，满足下列条件：许多有效的敌手，他们能输出一对消息在下是碰撞的。避免（1）(原像稳固)假设x是在D中均匀选取的，M是一个敌这

4、种问题出现的一个方法是把碰撞稳固定义为一个Hash函数手，根据输入h(x)，至多运算t次就可以输出M(h(x))∈D，对族H的性质，也就是说，由一个参数s引出的函数集合。为于每一个敌手M有了简化讨论，假定s是取自参数空间的，这样H就是一个从到R的映射。而在该族中，单个的函数用h表示，s这里可能性(概率)要考虑到M的随机选择；hs:D→R。（2）(第二原像稳固)：假设x是在中均匀选取定义2一个碰撞稳固的Hash函数H是一个具有定义域的，M’是一个敌手，它根据输入x，至多运算t次就可以输为，值域为的函数族，满足下列条

5、件。出x’∈D且x’≠x，对每一个敌手M’有（1）函数hs是原像和第二原像稳固(见定义1)；（2）碰撞稳固：假设F是一个寻找碰撞的敌手，它根据这里可能性大小也要考虑到M’的随机选择。上述定义输入，用至多t次运算就可以输出“？”或者一对只在足够大的条件下有意义，显然。满足x’=x，但是有hs(x’)=hs(x)，对每一个F都有1.2碰撞稳固Hash函数(CRHF)Psr{F(H)≠"?"}＜ε，这里概率值也是要考虑到F的随机选择。同样，该定义仅在足够大时有意义。一个函数是单向的并不意味着找两个碰撞输入是困难的。事实

6、上，寻找碰撞所需要的运算次数仅是寻找原像(或第二原1.3泛单向Hash函数(UOWHF)像)运算次数的平方根，因此我们必须给碰撞稳固下一个原始泛单向Hash函数的概念是有Naor和Yung给出的。的定义。定义3一个泛单向Hash函数H是一个具有定义域，CRHF首次的正式定义是由Damgard给出的，而非正式值域为的函数族，满足下列条件：作者简介：马陵勇(1978-)，男，讲师，硕士生，研究方向：信息安全。张姗姗(1981-)，女，硕士生，研究方向：信息安全。2007.1177加密技术ASU族)Hash函数族H是从

7、集合A到集合B的函数族，满足：假设F’=(F’,F’)是一个敌手，F’是首先运行的，它121是一个算法，能够产生x和可能的一些信息描述，这些信息将会（1）和，转给F2’。F2’也是一个算法，它对给定的s,x和由F2’产生的（2）和，信息描述可以产生“？”或者一对x’≠x，满足h(x’)=h(x)，ss对每一个执行次数不超过t的F’都有Pr{F’(H)≠"?"}＜ε。s第一个条件表明：一个给定的x被映射到一个给定的y的该定义与碰撞稳固的主要区别在于，这里输入x是首先固可能性等于，第二个条件意味着：如果x被映射到y，

8、那么定的，而后参数s才被选定，这意味着，对一个给定的s即使11x被映射到y的条件概率以ε为上界，ε的最小可能值是。找到了碰撞也对攻击者没有什么帮助。221.4消息认证码(MAC)2Hash函数的一般结构和常见攻击模型消息认证码在银行系统内已经使用了很长一段时间，但2.1迭代Hash函数的通用模型是，具有较好安全保密性质的MAC算法却是在19世纪80年多数已知的Hash函数