杂凑技术和信息安全

所谓杂凑技术就是利用杂凑函数把任意长的输入串转化为固定长输出串的一种技术方法，又称哈希技术或信息摘要技术，其独特的单向性使其成为在电子商务、网上银行等利用网络信息技术进行业务处理的新兴行业模式中广为采用的安全技术，在信息的保密性、完整性、不可否认性等方面发挥了不可或缺的作用。     

密码杂凑函数及其安全性分析

文章提出了针对密码杂凑函数及其安全性进行研究的重要意义,列举了单向杂凑函数、MD5、SHA-1等技术原理进行了技术分析,并从攻击手段入手,分析了密码杂凑函数的安全性,提出对SHA-1与MD-5的＂破解＂应客观看待的观点。     

对104步杂凑函数HAVAL的原根攻击

针对杂凑函数HAVAL的第1圈中圈函数的性质和消息字的顺序,结合使用穷举搜索等方法,给出对前104步HAVAL压缩函数的原根攻击。其计算复杂度是2224次杂凑运算,需要存储238个字节,而穷举攻击的计算复杂度是2256次杂凑运算。分析结果对杂凑函数HAVAL安全性的评估有重要的参考价值。     

Keccak类非线性变换的置换性质研究

Keccak杂凑函数是通过SHA-3最后一轮筛选的五个杂凑函数之一。通过对Keccak杂凑函数的非线性环节进行研究,提出了n元Keccak类非线性变换,并逐比特分析了其变换规律,通过分类研究,给出了两个原象不相等时,象不相等的充分条件和象相等的必要条件;进一步证明了当n为奇数时,n元Keccak类非线性变换是一个置换;当n为偶数时,不是一个置换。最后,证明了当n为奇数时,n元Keccak类非线性变换不是全向置换、全距置换和正形置换,为进一步应用这类编码模型奠定了理论基础。     

一类SHA-x改进杂凑算法的设计及分析

在SHA-1和SHA-2标准算法的基础上,提出一类SHA-x改进杂凑算法的设计。该算法重新设计了杂凑函数Hash值的生成方法,将输出消息摘要的长度从SHA-1的160bit提高到192bit,同时保留了SHA-1模2^32加法的计算特性,以保证整个算法的加密速度。安全性分析表明,新设计的杂凑算法在不过分减慢加密速度的前提下,具有较SHA-1更好的抗攻击能力。     

CRCLA的杂凑算法优先级决策映射方法

为解决杂凑算法在粗粒度可重构阵列上的映射问题,通过对杂凑算法的特征分析,为提高映射的能效,采用空间展开操作并行的映射手段;针对某一操作在映射时往往存在多种候选方案难以选取最佳方案的情况,提出一种优先级决策机制,对5种开销值进行优先级排序,选择出最佳方案.在阵列芯片上对多种典型杂凑算法的映射结果进行实测分析,相较于其它不同决策机制的映射方法,该映射方法在能效上提升了约10％ ～20％,具有良好的能效特性.     

控制文件在信息管理系统中的作用及构造方法

在信息管理系统中引入控制文件以取代直接代码编程是一种延长程序生命周期的有效方法.控制文件的作用就是定义输入输出数据间的关系,输入数据及报表的结构、用户的权限及性质等.构造控制文件的方法就是构造一个杂凑函数来映射这些数据关系、结构、性质等等.     

S-RFSB算法*

杂凑算法是信息安全领域的常用工具之一。现有杂凑算法的压缩函数多是迭代型的,优点是速度快,缺点是难以进行安全性证明。针对已有算法的基础上进行了研究,并提出了S-RFSB杂凑算法方案。新的方案采用Sponge结构,该结构在运行效率上比传统MD结构高,变换函数设计采用编码理论的困难问题,即伴随式译码问题,变换函数使用矩阵的大小缩小了2b倍。这种密码方案具有抵抗量子计算攻击,可证明安全性,实现速度较快等优点,而且仅涉及简单的矩阵运算。     

SM3杂凑算法的软件快速实现研究

杂凑算法是密码学中最基本的模块之一,可广泛应用于密码协议、数字签名、消息鉴别等领域。我国国家密码管理局在2010年发布了SM3密码杂凑算法,该算法适用于商用密码应用中的数字签名和验证、消息认证码的生成与验证以及随机数的生成等。该文重点研究SM3密码杂凑算法的软件快速实现,根据算法本身的特点,尤其是压缩函数的特点,给出一种更加适用于软件的快速实现方式。实验表明利用此方法可以将算法的效率提升60%左右。     

一个基于PSO和DE的杂凑全局优化算法

结合粒子群优化算法和差分进化算法思想提出了一个杂凑的全局优化算法——PSO-DE,通过对4个基准测试函数的实验测试,并与PSO和DE算法比较,证明新算法在低维（≤10维）搜索空间可以获得更高质量的解。     

基于HEVC屏幕图像编码的哈希表的优化算法

仿2维匹配算法对屏幕图像中的非连续色调区域有很好的压缩性能,但该算法中哈希表的空间开销较大,不利于硬件实现。为了减小哈希表的空间,通过对原算法优化提出了一种3字节计算哈希值方法,将源数据看作是一个由以YUV三元组为元素组成的数据集合,然后以YUV三元组为单位计算哈希值,这样不但减少了哈希值的计算量,而且使哈希表的存储空间得到很大的节省。实验结果表明,3字节计算哈希值方法使哈希表的存储空间减少为原算法的1/3,所测试屏幕图像的BD-rate性能也有所提高。     

Optimal design of multiple hash tables for concurrency control

In this paper, we propose the approach of using multiple hash tables for lock requests with different data access patterns to minimize the number of false contentions in a data sharing environment. We first derive some theoretical results on using multiple hash tables. Then, in light of these derivations, a two-step procedure to design multiple hash tables is developed. In the first step, data items are partitioned into a given number of groups. Each group of data items is associated with the use of a hash table in such a way that lock requests to data items in the same group will be hashed into the same hash table. In the second step, given an aggregate hash table size, the hash table size for each individual data group is optimally determined so as to minimize the number of false contentions. Some design examples and remarks on the proposed method are given. It is observed from real database systems that different data sets usually have their distinct data access patterns, thus resulting in an environment where this approach can offer significant performance improvement     

一种基于哈希链表的高效概念漂移连续属性处理算法

本文重点研究了数据流挖掘中存在概念漂移情形的连续属性处理算法。数据流是一种增量、在线、实时的数据模型。VFDT是数据流挖掘中数据呈稳态分布情形下最成功的算法之一;CVFDT是有效解决数据流挖掘中概念漂移问题的算法之一。基于CVFDT,本文提出了有效地解决数据流挖掘中存在概念漂移情形的连续属性处理问题的扩展哈希表算法HashCVFDT。该算法在属性值插入、查找和删除时具有哈希表的快速性,而在选取每个连续属性的最优化划分节点时解决了哈希表不能有序输出的缺点。     

散列表方法在交换控制芯片地址表设计中的应用

研究了散列表方法在交换控制芯片地址表设计中的应用，采用了分桶散列的方式解决散列冲突问题，用高效的并行CRC结构产生散列索引，实现了对地址表的快速查找。     

基于流应用中的哈希查表性能研究

基于流应用中采用哈希查表进行报文分类具有成本低、扩展性好等优点,但是其查表性能受到诸多因素影响,制约了它的应用范围。该文采用理论分析和仿真的方法研究了在均匀映射和非均匀映射情况下,哈希查表性能的一些规律,对于具体应用具有一定的指导作用。     

Using a Two‐Level Structure to Manage the Point Location Problem in Explicit Model Predictive Control

The problem of determining the state region in which the current state point lies is referred to as the point location problem in the explicit model predictive control. In this paper, a two‐level structure to store the state regions is proposed and two efficient methods for solving the point‐location problem are developed; these are the two‐level grid (TLG) method and the grid‐BST method. The TLG method uses a tow‐level hash table. Before building the two‐level structure, the synonymy partitions are merged to reduce the memory storage demand. By setting each parameter in a triplet, the two‐level hash table can reach its optimal state and balance the complexity among the memory storage, reprocessing (offline computation) and the online computation. The grid‐BST method uses hash table as the first‐level structure and builds the binary search tree in the hash grid in which there are many partitions. This two‐level structure reduces reprocessing time significantly especially when the state partitions and the piecewise affine control laws (PWA control laws) are in a large number. Using the hyperplane (HP) as the node (not leaf node) of the tree, the method only stores all the different PWA control laws instead of the state partitions. The two proposed methods overcome the quick complexity growth when the number of polyhedral partitions increases and 2 numerical examples show the advantages of the proposed two methods.     

Fast and deterministic hash table lookup using discriminative bloom filters

Hash tables are widely used in network applications, as they can achieve O(1) query, insert, and delete operations at moderate loads. However, at high loads, collisions are prevalent in the table, which increases the access time and induces non-deterministic performance. Slow rates and non-determinism can considerably hurt the performance and scalability of hash tables in the multi-threaded parallel systems such as ASIC/FPGA and multi-core. So it is critical to keep the hash operations faster and more deterministic.This paper presents a novel fast collision-free hashing scheme using Discriminative Bloom Filters (DBFs) to achieve fast and deterministic hash table lookup. DBF is a compact summary stored in on-chip memory. It is composed of an array of parallel Bloom filters organized by the discriminator. Each element lookup performs parallel membership checks on the on-chip DBF to produce a possible discriminator value. Then, the element plus the discriminator value is hashed to a possible bucket in an off-chip hash table for validating the match. This DBF-based scheme requires one off-chip memory access per lookup as well as less off-chip memory usage. Experiments show that our scheme achieves up to 8.5-fold reduction in the number of off-chip memory accesses per lookup than previous schemes.     

测试向量的周期化关键技术研究与实现

提出了一种将状态取样法和波形提取法结合使用的测试向量周期化方法，在该周期化方法中，需要一个逐拍匹配生成新定时组的过程，为了减少生成定时组时间，实现了一种基于哈希表的周期化算法。它不仅在速度上得到优化，同时也减少了波形失真度。实验结果表明，该周期化方法是一种行之有效的测试向量转换方法。     

基于局部坐标系和哈希技术的空间曲线匹配算法

针对三维物体识别领域中的问题,提出了一种基于局部坐标系和哈希技术的空间曲线匹配算法,该方法通过提取一条曲线的恒定特征点,构造局部坐标系;然后再计算局部坐标系中的相似不变量,构造哈希表;采哈希技术对这些不变量进行比较,达到匹配曲线的目的。此算法应用于计算机辅助文物复原系统中,经实验表明,给所方法具有运行稳定,高效和适用性强等优点。     

HCAA:一种哈希冲突过度的动态解决算法

HASH表作为一种快速查询的数据结构,在防火墙等网络安全应用中得到了广泛的应用。然而,攻击者可能通过一些手段对这些应用发动HASH攻击使其失去响应,从而使某些恶意的数据流能够逃脱网络安全应用的管理和控制。提出一种动态的哈希冲突过度的解决算法—HCAA(Hash Collision-Acceptable Algorithm)算法,该算法在哈希冲突过于集中时通过动态申请HASH表并使用不同哈希函数来对冲突数据流进行处理,使冲突在可接受的范围内。实验结果表明,与已有方法相比,HCAA算法能在使用更少HASH表项的情况下获得更均衡的HASH效果,从而能对数据流进行更快的HASH操作。