关键词:
哈希算法
并行化
信息安全
硬件设计
摘要:
安全哈希算法是密码学的基础算法,广泛用于数据完整性校验、密码保存、文件识别、伪随机数发生器、数字签名等,具有重要的应用价值。常见的哈希算法结构包括Merkle-Damgard结构、HAIFA结构、Sponge结构和宽管道结构,通过对常见的哈希算法结构的考察发现,它们在整体上都是线性的,也就是说,消息块总是按照顺序被依次处理,后面的消息块的处理要依赖于前面消息块的计算结果,无法提前进行计算。当消息长度很大时,线性的结构成为限制计算效率的瓶颈,线性哈希结构使得多核处理器无法使用多个计算单元对消息并行处理,多核处理器的处理能力无法得到充分的发挥。针对这一问题,Skein算法定义了树形哈希模式,使得算法的并行性大大提高。
本文致力于研究树形哈希模式的并行处理结构。以Skein算法为例,进行了算法分析,系统建模,硬件架构设计等各项工作,提出了一种实现树形哈希模式的并行处理平台。该平台以互连网络为中心,由若干个运算单元、若干个存储单元和一个控制器组成。每个运算单元都能够独立完成线性哈希运算,控制器通过控制总线向运算单元分配任务,协调运算单元的工作,通过基本的线性哈希运算的组合,能够完成树形哈希算法的运算。互连网络的设计允许多对多的并发访问,结合分立存储单元的设计,使得多个运算单元可以同时访问存储系统的不同位置。总体来说,该并行架构的设计解决了并行处理系统设计中面临的存储、互连和任务调度三个方面的问题。
该平台不仅能够高效执行Skein算法,而且在任务划分与调度、片上存储与互连、硬件加速等方面对于树形模式的各类哈希算法具有普遍的借鉴意义。本文提出的并行架构经过FPGA功能验证,并且在TSMC65nm工艺下进行综合,结果显示,系统占用的面积为1.3mm2,最高工作频率达到833MHz,功耗66mW,估计吞吐率约为40Gbps,各项指标均达到预期。研究并行哈希的性能提升是本文的另一个重点,为此,本文根据系统中的任务调度情况,提出了Skein树形哈希算法的性能模型。模型分析显示,和传统的线性哈希相比,使用多个运算单元来完成树形哈希运算,随着消息长度的增长,其加速比趋近于运算单元的数量。