密码Hash函数相关问题研究

密码Hash函数是信息安全密码学的一个重要研究内容，是一类广泛应用的密码算法，用于把任意长度的字符串压缩成特定长度的字符串，同时需要在各种应用环境下满足一定的安全要求如抗碰撞，抗原象等。Hash函数广泛应用于数字签名、可证明安全、密码算法的构造以及重要的安全协议中。对Hash函数进行研究、分析Hash函数的安全性、构造安全高效的Hash算法有着重要意义。 本文研究了Hash函数的安全性质、设计结构以及常用分析方法，研究了Hash函数扩散层部件的设计，并且对MAME压缩函数算法进行了分析，取得了如下研究结果： (1) 研究了密码Hash函数的安全性质、设计结构、设计原理和常用分析方法，归纳总结了51个SHA-3候选算法的设计特点、设计原理和实现效率，研究了最新的分析进展，总结了新的攻击方法如REBOUND攻击等。NIST仿照AES的征集过程的SHA-3竞赛，目标是选出新的Hash函数标准SHA-3。进入第一轮的候选算法有51个，经过筛选选出其中的14个作为当前第二轮的候选算法。这些新Hash算法是由世界各国密码学家精心设计，是Hash函数领域最新设计思想的集体展示，当中涌现出很多新的设计结构和设计方法，同时激励密码学家发展新的分析方法。 (2) 设计并实现了了有限域上的扩散层构造算法以及扩散层分支数测试的算法，并针对多元域上的扩散层矩阵，本文使用编码理论，利用GRS码和柯西矩阵等设计了多元域扩散层矩阵的构造算法；使用有限域上的高斯消元法和线性码的性质设计了多元域扩散层矩阵的分支数的检测；设计了高效的二元域扩散层矩阵分支数测试算法。 (3) 针对MAME压缩函数算法进行差分分析，MAME算法是SHA-3候选算法Lesamnta的前身，于CHES 2007上提出的面向硬件有效实现的Hash算法。本文利用差分攻击对MAME算法进行分析，首先针对MAME的结构性质利用对通用Feistel结构的攻击方法构造了22轮差分攻击，碰撞攻击的复杂度为2^97，（第二）原象攻击的复杂度为2^197；对23轮的差分攻击需要的预计算是2^64张表，每张表的大小为2^64；对24轮的差分攻击需要的预计算是2^128张表，每张表的大小为2^64。针对24轮差分攻击很大的内存复杂度，我们利用了算法的细节特性，改进了差分攻击，新的差分不需要预计算的辅助内存，（第二）原象的复杂度为2^224。

一种基于分组密码的hash函数

提出了一个基于分组密码的hash函数体制,它的rate小于1但却具有更高的效率,同时,这个hash函数可以使用不安全的压缩函数进行构造,降低了对压缩函数安全性的要求.首先,在黑盒子模型下对这个新的体制的安全性进行了证明,然后给出了能够用于构造该体制的使用分组密码构造的压缩函数,最后通过实验对比发现,新hash函数的速度比rate为1的hash函数快得多.实验结果表明,除了rate以外,密钥编排也是影响基于分组密码hash函数效率的重要因素,甚至比rate影响更大.该体制只有两个密钥,不需要进行大量的密钥扩展运算,大大提高了基于分组密码hash函数的效率,而且该体制可以使用现有的分组密码来构造.

压缩函数局部平衡度与Hash函数平衡度的关系研究

主要探讨了基于MD方式构造hash函数时平衡度的保持问题，说明了压缩函数满足何种条件时hash函数能够取得最好的平衡度，提出了局部平衡度的概念，并利用此概念解决了压缩函数局部平衡度与hash函数平衡度的关系问题．这对于未来的hash函数的设计有非常重要的意义．

A NEW SCHEME FOR ASSIGNMENT OF A CANONICAL CONNECTION TABLE

A new algorithm for deriving canonical numbering of atoms in a molecular graph has been developed. Some graph invariants, such as node properties, degree (connectivity), topological path, the smallest node ring index, etc., are encoded together to partit

Simple Load Balancing for Distributed Hash Tables

Distributed hash tables have recently become a useful building block for a variety of distributed applications. However, current schemes based upon consistent hashing require both considerable implementation complexity and substantial storage overhead to achieve desired load balancing goals. We argue in this paper that these goals can b e achieved more simply and more cost-effectively. First, we suggest the direct application of the "power of two choices" paradigm, whereby an item is stored at the less loaded of two (or more) random alternatives. We then consider how associating a small constant number of hash values with a key can naturally b e extended to support other load balancing methods, including load-stealing or load-shedding schemes, as well as providing natural fault-tolerance mechanisms.

Cluster-Based Optimizations for Distributed Hash Tables

We consider the problem of performing topological optimizations of distributed hash tables. Such hash tables include Chord and Tapestry and are a popular building block for distributed applications. Optimizing topologies over one dimensional hash spaces is particularly difficult as the higher dimensionality of the underlying network makes close fits unlikely. Instead, current schemes are limited to heuristically performing local optimizations finding the best of small random set of peers. We propose a new class of topology optimizations based on the existence of clusters of close overlay members within the underlying network. By constructing additional overlays for each cluster, a significant portion of the search procedure can be performed within the local cluster with a corresponding reduction in the search time. Finally, we discuss the effects of these additional overlays on spatial locality and other load balancing scheme.

Efficient Hash-Consing of Recursive Types

Efficient storage of types within a compiler is necessary to avoid large blowups in space during compilation. Recursive types in particular are important to consider, as naive representations of recursive types may be arbitrarily larger than necessary through unfolding. Hash-consing has been used to efficiently store non-recursive types. Deterministic finite automata techniques have been used to efficiently perform various operations on recursive types. We present a new system for storing recursive types combining hash-consing and deterministic finite automata techniques. The space requirements are linear in the number of distinct types. Both update and lookup operations take polynomial time and linear space and type equality can be checked in constant time once both types are in the system.