TOYOCRYPT-HS1算法高速实现研究

摘 要： 提出了一种TOYOCRYPT-HS1算法高速实现架构，不仅能够满足算法中LFSR特征多项式可变的要求，而且实现了LFSR和非线性布尔函数的并行化设计，显著提高了算法的处理性能。最后通过实验验证和性能比较可以看出，该TOYOCRYPT-HS1算法高速实现架构具有较大的性能优势，最大吞吐率达到1.54 Gb/s。
关键词：序列密码； TOYOCRYPT-HS1； 线性反馈移位寄存器； 非线性布尔函数； 并行处理

序列密码[1]又称流密码，是现代密码学的一个重要分支，利用不断变化的加密变换对明文消息进行逐字符（通常为二进制数）的加密变换，是“一次一密”的密码体制。因其具有实现简单、加解密速度快、密文传输中的错误不会在明文中产生大范围扩散等特点，已成为新一代通信系统的主流加密算法[2]。
前馈模型是一种典型的序列密码结构模型，一般由1~n个反馈移位寄存器和前馈函数构成[3]。反馈移位寄存器的状态值不仅参与自身反馈函数的计算，实现状态更新，同时要输出到前馈函数中完成密钥的计算生成。TOYOCRYPT-HS1算法[4-7]是提交给日本技术信息促进机构密码研究评估委员会的一个序列密码算法，是一种典型的前馈模型序列密码。其线性反馈移位寄存器LFSR（Linear Feedback Shift Register）基于Galois配置，第i级输出序列由第i+t级的输出序列右移d位形成，d的值只能通过求解GF(2n)上的一个离散对数问题才能得到，且d的值一般都很大[8]。可见，无论从安全性方面还是高效性方面，Galois配置的LFSR（下文中的LFSR特指Galois配置的LFSR）都是一种非常重要的计算结构，因而TOYOCRYPT-HS1算法具有一定的典型性，研究其高速实现方法具有重要的理论意义和实用价值。

寄存器堆是架构的重要部件，根据存储信息的不同用途，可划分为密钥寄存器、配置寄存器以及数据寄存器。密钥寄存器用来存储算法的128 bit主密钥；配置寄存器用来存储由特征多项式决定的128 bit反馈抽头，以满足算法中反馈抽头位置可变的要求；数据寄存器用来存储运算中产生的临时数据，既可以实现小于等于d的可变步数的LFSR并行更新操作，又能够支持密钥的并行生成。
根据LFSR的并行更新原理，依据提出的LFSR状态转移矩阵列向量预计算算法，LFSR并行更新电路根据LFSR的反馈抽头、LFSR的状态序列、并行更新时每一步对应的状态转移矩阵首列反馈抽头和首位状态信息等,在一个时钟周期内计算生成1~d步的并行更新数据。
算法中非线性布尔函数f(x0,x1,…，x127)中有1个1次项、63个2次与项、1个4次与项、1个17次与项和1个63次与项。分析各种与项的构成，考虑输入变量数量、与项的次数和个数，2次、4次低次与项可以采用查找表的方式实现，17次、63次高次与项可以采用与阵列的方式实现，所有与项的计算结果与1次项一起经由“异或”运算产生1 bit密钥输出。架构中共设置d个非线性布尔函数单元，每个单元与某一时刻LFSR状态序列中的某些状态位连接，能够同时计算输出d bit密钥。
4 实现结果与性能分析
4.1实现结果
本文采用Verilog HDL硬件描述语言对TOYOCRYPT-HS1算法高速实现架构进行RTL级建模，并选用Altera公司Stratix III系列FPGA中的EP3SL340F1760C3芯片作为目标器件，在Quartus II 9.0环境下进行编译和综合。表1给出了该架构在不同并行更新步数下基于FPGA的实现结果。

4.2 性能分析
图3给出了本文提出的高速架构与参考文献[4]中TOYOCRYPT-HS1算法实现的性能比较。参考文献[4]没有进行并行处理，每个时钟周期内LFSR更新1步，同时输出1 bit密钥。而本文提出的高速架构采用了并行化设计技术，LFSR的并行更新和非线性布尔函数的密钥生成分别在1个时钟周期内完成，所有该架构能够在2个时钟周期内输出d bit密钥。比较发现，通过采用并行化的设计方法,本文提出的高速架构大大提升了TOYOCRYPT-HS1算法的处理性能,具有明显的性能优势。