杂凑函数在现代密码学中占据基础而重要的地位，它将任意长度的消息压缩成固定长度的杂凑值，主要用来保证数据完整性、消息认证、优化数字签名等，目前最常用的一类杂凑函数称为MD4族杂凑函数。杂凑函数的设计属于对称密码算法的设计范畴，但它对效率的要求较分组密码算法更高。在安全性方面，差分分析是当前最有效的杂凑函数攻击方法，它使得一系列MD4族杂凑函数的消息碰撞实际上被找到或理论上计算复杂度大大降低。NIST决定从2007年开始向全世界征集新的杂凑函数标准SHA—3，为期五年。MD6杂凑函数是Rivest等提出的SHA—3候选算法，目前被认为具有较高的安全性和性能。　　 杂凑函数的设计包括压缩函数和工作模式。压缩函数是杂凑函数的核心，由步操作和消息扩展构成，不安全的压缩函数会导致不安全的杂凑函数。步操作通常可以分为非平衡Feistel和SPN两种结构，非平衡Feistel结构的优点是比较简单，通常只需要较少的指令即可实现，不足是扩散性较差。MD4族杂凑函数的步操作可以表示为一个四级或五级移位寄存器，只需要十条左右X86指令即可实现；而其每一步只升级内部链变量的1/4或1/5，导致扩散性下降。MD4族压缩函数的消息扩展通常采用置换或迭代计算的方式，其扩展过程是一维的，灵活性和扩散性受到限制，MD4、MD5、SHA—0、SHA—1消息扩展的扩散性不足也是它们受到攻击的原因。工作模式的设计对于提高杂凑函数的性能和安全性非常重要，随着硬件资源的进步，串行工作模式在效率方面受到限制，并行工作模式逐渐受到人们的重视。　　 本文的主要研究工作及成果总结如下：　　 ●设计了一个符合SHA—3征集规范的杂凑函数，包括压缩函数和工作模式的设计，称为X—Hash算法。在保证整体设计框架安全高效的情况下，充分弥补了MD4族杂凑函数在步操作和消息扩展方面的不足。X—Hash在设计阶段就将实现效率考虑在内，而不是在实现时再研究如何进行性能优化，因此X—Hash在各种软硬件平台上都获得了较好的性能。本文分析了X—Hash压缩函数的伪随机性和差分特性，通过了所有15种常用的伪随机性测试，单条线索两轮差分传播概率要小于生日攻击的概率。在8位、32位、64位处理器和FPGA上进行了算法优化和性能评估。在FPGA和64位处理器上，X—Hash的性能与MD6相当，在8位和32位处理器上，X—Hash的性能要优于MD6算法。　　 ●本文提出了多线索的压缩函数设计方案，多线索比单线索提供给步操作和消息扩展更大的灵活性，在实现时提供了较高的指令级并行性。X—Hash的线索数为8，每条线索的中间状态为32比特，正好为32位处理器寄存器的长度，在实现时可以减少访问内存的次数。　　 ●本文提出了一种分层的步操作设计框架，该框架由三个基本层次构成：非线性变换层、扩散层和数据交换层。非线性变换层负责局部8比特的非线性变换，线性扩散层将其扩散到32比特范围，数据交换层再将其扩展到整个256比特中间状态。分层框架的好处是每个层次都可以独立设计，使设计的复杂度降低，灵活性提高。分层设计的优点还体现在每个层次中的部件可以相对较小。X—Hash的非线性变换层的输入输出为8比特，扩散层的输入输出为32比特(MD4族杂凑函数步操作的输入至少为128比特，输出至少为32比特)，因此步操作的非线性和扩散性可以量化分析。小部件还使得X—Hash在8位处理器上的性能优化更加容易。　　 ●本文提出了一种二维的消息扩展方案，将消息扩展从一维推广到二维。二维消息扩展可以认为消息扩散不是在直线上，而是在平面中进行，消息扩展的灵活性和扩散性都获得提高。在不同的维度上可以使用不同的消息扩展方案，X—Hash的横向消息扩展采用置换的方式而纵向消息扩展采用迭代的方式，同时具有MD5高效和SHA—1扩散性好的的优点。　　 ●本文提出了一个并行工作模式，称为Par工作模式。证明了其抗碰撞性可规约到压缩函数的抗碰撞性，与MD工作模式相比，Par模式理论和实际上都具有线性加速比。与Tree模式相比，Par模式消息填充简单，计算单元间的同步控制少，只在计算最终杂凑值时才需要同步。当加速比同为L时，其所占用的临时存储空间为L乘以压缩值的大小，要小于Tree模式占用的临时存储空间。