分组密码和Hash函数是对称密码学领域的两个重要分支,分组密码在数据加密和MAC等领域有着广泛的应用,Hash函数在电子签名、消息认证、防否认等领域有着广泛应用。早在上个世纪九十年代,人们意识到分组密码标准DES已不能满足高速发展的信息时代的加密需求,1997年NIST(美国国家标准与技术研究所)启动了AES(高级加密标准)计划,并最终选用Rijndael作为新一轮加密算法标准。继美国征集AES活动之后,欧洲在2000年启动了NESSIE计划。伴随着AES计划和NESSIE计划的实施,分组密码研究从一种经验设计走向理论设计的道路,分组密码理论得到飞速发展。相比之下人们对在用的Hash函数安全性估计过于乐观,相关研究比较滞后。2004年底山东大学王小云教授和她的工作团队给出了MD5和SHA1算法的碰撞攻击,国际上也陆续推出了系列攻击,给在用的Hash函数带来了重创。Hash函数已成为密码学领域一个热门话题。NIST决定在2008年启动高级Hash函数算法征集活动-AHS计划,预计5年时间。如何设计、分析和评价Hash函数,以及如何给出一个可证明安全的Hash函数等问题将贯穿于整个活动。Hash函数研究深度远远不及分组密码,能否将分组密码理论用于专用Hash函数的设计中,已成为一个热点话题。大多Hash函数均是通过迭代结构对压缩函数进行迭代而实现的。Hash函数设计包括迭代结构的设计和压缩函数的设计两部分。本文目标是设计一个新的Hash函数,这要求对当前分组密码和Hash函数设计原理和攻击方法有充分的认识。本文最终给出了一个Hash函数,命名为Dolly。在该算法设计中,我们给出了一个新的迭代结构FHash,新的压缩函数结构FL-结构和新的压缩函数算法。我们构造的压缩函数同时也是一个加密分组长度为256比特,密钥长度为512比特的分组密码,同时给出了一个不可逆的密钥扩展算法。本文的主要创新成果如下:(1)给出Camellia密码四个等价结构,提出Camellia密码的变种Square攻击,同时改进了Yeom等在FSE2002上给出的Square攻击的界。Camellia相关攻击结果是当时最有效的攻击方法,被日本当年的信息安全年报引用。CRYPTREC关于Camellia算法的2006年年度报告中仍然引用我们的结论作为该算法的安全现状。(2)发现Camellia算法P置换与S盒变换的特殊联系,在特殊明文条件下,P置换导致几个S盒的模加相互抵消。根据这一特性,给出了新的变种Square攻击,将Camellia攻击结果再次改进,这一结果是目前对Camellia算法的最好攻击结果,该结果收录在ICICS2007。(3)引入有向图理论和Game-Based proof方法,将基于分组密码构造的64种压缩函数方案归为四类,并给出了每一类的抗原像、次原像和碰撞攻击的界。这种归类比Black、Rogaway和Shrimpton在Crypto2002上给出的三种分类更加精确,并改进了BRS给出的抗碰撞和原像攻击的界。同时给出了基于固定点多碰撞中碰撞个数、算法复杂度与消息长度之间的关系。(4)我们发现Merkle-Damgard结构迭代过程中不一定能够继承压缩函数的分布特性,并举例说明了这一现象的存在,其中一个几乎均匀分布的函数在Merkle-Damgard迭代结构下,生成的新函数分布上界为1,完全不符合几乎均匀分布。我们进一步证明迭代后函数分布特性与压缩函数分布特性和迭代次数有关,最坏情况下,迭代次数与分布的界构成指数关系。同时给出了其它几个结构的分布特性。我们发现Merkle-Damgard结构下基于分组密码构造压缩函数的64种方案的概率分布特性,只有四个方案的概率分布与迭代次数无关,但这四种方案均是不抗原像攻击的,该结论在文献[87]中给出。(5)Bellare等在AsiaCrypt2006上给出了EMD结构,第一个直接继承压缩函数抗碰撞攻击特性、伪随机预言机(该性质称为indifferentiability)特性和伪随机函数特性的迭代结构,使Hash函数安全性问题归结到压缩函数的安全性问题上。我们认为均匀分布也是一非常重要的性质需要继承。令人遗憾的是EMD结构无法满足这一特性。我们给出了一个新的结构(定义为ECM结构),它满足EMD所有特性且继承了压缩函数分布特性,并给出了详细证明,该结果收录在Indocrypt2007。(6)对Feistel结构进行变形,给出了一个满足单向性要求的压缩函数结构FL-结构,并给出一个Hash迭代结构FHash,同时给出了FL-结构和FHash安全性的形式化证明,在此基础上构造了一个新的Hash函数Dolly。Dolly算法采用了AES的扩散准则,因此继承了AES算法的抗线性和差分攻击特性,同时我们给出了一个不可逆的密钥扩展算法,尽可能地增强了压缩函数的抗碰撞特性。Dolly中的压缩函数轮函数和密钥扩展算法还有待更深入的分析和评价。