NBC分组密码算法的FPGA高速实现

孟祥兴,曹 欣

(北京电子科技学院电子与通信工程系, 北京 100070)

密码是我们党和国家的命脉,是我国重要的战略资源.在智能物联背景下的大数据信息时代,数据的保密性与安全性显得更加重要.在全球各国密码科研人员的努力下,近年来涌现出各种各样实现方式的机密性、完整性、真实性和不可否认性皆优秀的高性能密码算法.NBC分组密码算法就是我国自主研发的最新密码算法.

可编程逻辑器件(programmable logic device,PLD)是20世纪70年代发展起来的一种新型器件,PLD在简化电路设计、降低开发成本、提高系统可靠性等方面起到了重要的作用.现场可编程门阵列(field programmable gate array,FPGA)是美国Xilinx公司于1985年推出的采用单元型结构的PLD器件.FPGA采用CMOS、SRAM工艺制作,其内部由许多独立的可编程逻辑单元构成,各逻辑单元之间可以灵活地相互连接,具有密度高、速度快、编程灵活、可重新配置等优点,是目前主流的PLD器件之一.

分组密码算法是一种对称加密算法,其明文信息具有良好的可扩展性,不需要密钥同步,具有较强的适用性.但是,加密速度慢、错误扩散传播等缺点使其在互联网的应用较少.因此,快速实现分组密码算法成为分组密码工程应用必须解决的问题.结合FPGA器件的优点和分组密码算法的不足,用FPGA实现分组密码算法成为解决分组密码算法加密速度慢的有效手段,并在工程领域得到了广泛应用.

本文研究NBC分组密码算法的FPGA高速实现.针对分组密码特点,结合有限状态机技术、非阻塞赋值技术和流水线技术,用分时钟、分块明文、密钥输入的方式对NBC密码算法进行FPGA编程实现.

1 NBC算法介绍

NBC算法[1]采用改进的第二类广义Feistel结构,轮函数和F函数如图1和图2所示,其中S为16比特的S盒.NBC算法以16比特为基本处理单元,将分组长度为128比特、密钥长度为128比特的NBC算法记为NBC 128/128.

图1 NBC算法轮函数

图2 F函数(0≤l≤3)

1.1 轮函数

为保证加解密的一致性,最后一轮不进行块置换.输入明文为P=X0,输出密文为C=X32.置换块为π8=(30147256),其中,3表示输入的第0块移到输出的第3块的位置,其余依此类推.

1.2 S盒

NBC算法的S盒由基于16级的非线性反馈移位寄存器(NFSR)来构造.记S盒的16比特输入为S0,S1,…,S15,将该16比特从左至右依次填充至16个寄存器内,寄存器迭代20拍后的全体内部状态即为S盒的输出.

(1)

(2)

(3)

(4)

{13,14,15}

(5)

寄存器迭代20拍可以保证S盒各分量的代数次数都达到最大值15,并且具有好的差分盒线性性质.

1.3 密钥扩展算法

NBC 128/128密钥扩展算法的设计与S盒类似,采用基于8比特的16级非线性反馈移位寄存器,引入模28加法代替比特与,增加循环移位以保证不同字之间的充分混淆,增加轮常数以避免出现弱密钥(如全零子密钥).密钥扩展算法中用到的非线性反馈移位寄存器的状态字wj(0≤j≤15)和常数cl(0≤l≤3)中各比特都是按照高位在前、低位在后的顺序存放.

初始种子密钥为128比特,分成16个8比特字K=(k0‖k1‖…‖k15).用它们填充密钥寄存器的初始状态,即有wj=kj,0≤j≤15.提取密钥寄存器前64比特作为初始轮的子密钥,之后寄存器每迭代4拍,输出一轮轮子密钥,每次选取密钥寄存器前64比特作为轮子密钥.要产生r轮加密的所有轮子密钥,密钥寄存器总共需要迭代4(r-1)拍.轮子密钥的具体产生方式为:对0≤j≤15,令wj=kj;输出密钥寄存器的前64比特作为第0轮的轮子密钥K0;对1≤i≤r-1,顺序执行下列步骤,产生后r-1轮的轮子密钥Ki.

1) 寄存器迭代4拍,按下列方式更新寄存器状态:

(w4<<<3)⊕c1

(6)

w7⊕(w9<<<7)⊕c2

(7)

(w14>>>3)⊕c3

(8)

(w3<<<2)⊕c4

(9)

{9,10,11}∪{13,14,15}

(10)

2) 选取密钥寄存器的前64比特作为第i轮的轮子密钥:

Ki=(w0‖w1‖w2‖w3‖w4‖w5‖w6‖w7)=

运用到的符号说明见表1.

表1 符号说明

1.4 算法改进

为了方便密码算法的C语言实现,原始NBC 128/128算法采用大端字节序设计.本文使用小端字节序对NBC 128/128密码算法进行FPGA实现,更节省时钟资源[2]、降低逻辑资源耗用.

2 NBC算法的FPGA高速实现

NBC算法的FPGA实现主要需要解决以下问题:1) 输入、输出数据占用引脚过多问题[3];2) 算法各个过程时钟配合问题;3) 逻辑资源块占用问题;4) 系统整体运行频率问题.本文使用数据分块输入技术、有限状态机技术、流水线技术设计一种高稳定性、高频率、逻辑资源占用少、综合速度快的NBC 128/128密码算法FPGA实现.

2.1 分时钟输入设计

本研究的输入明文数据为128比特、输入初始密钥为128比特.考虑用4个时钟,每次时钟输入32比特明文和32比特密钥,实现数据分块输入效果,效果图如图3所示.

图3 数据分块输入效果图

除了输入数据分块,还考虑输出数据分块[4],输出数据分块需要严密的时钟控制,要求计算好在特定的时钟下进行数据输出.将NBC 128/128的FPGA系统在同一个时钟下重复调用n(n∈Z+)次实现明文为128比特的n倍数据加密,也可以在n个时钟下分时实现明文为128比特的n倍数据加密.本文提出的NBC算法系统频率高,推荐使用在n个时钟下分时实现明文为128比特的n倍数据加密的方法以减少硬件的耗用.

2.2 有限状态机设计

NBC 128/128密码算法的复杂性主要体现在32次迭代轮数与20次S盒迭代次数[5].将每一个迭代轮数都用FPGA实现将会导致FPGA逻辑资源块占用量过大、系统综合时间过长、系统运行频率低等缺点.因此,使用有限状态机技术,用状态来控制32次迭代轮数,每一次迭代轮数实现一次轮函数,解决了密码算法的复杂性问题,将整个系统轮廓用有限状态机技术有效实现.系统结构框图如图4所示.

图4 有限状态机状态设计流程图

本文使用摩尔型有限状态机,整体系统设计具有速度高、结构清晰、可靠性高[6]等优点.

2.3 流水线设计

NBC 128/128分组密码算法采用迭代非线性反馈移位寄存器(nonlinear feedback shift register,NFSR)实现S盒与密钥扩展.因此S盒与密钥扩展两个模块本身无法采用流水线结构设计.在S盒与密钥扩展模块之间进行流水线设计,使得S盒模块与密钥扩展模块能够高速实现,流水线设计主要就是把密钥扩展算法的第n+1轮的4次迭代与S盒的第n轮的前4次迭代一起执行.S盒第n轮的前5次迭代取出第n+1轮的密钥,使得密钥扩展算法的实现在S盒实现的时钟内部进行,省掉了密钥扩展算法占用的时钟,提高了整个NBC 128/128系统的运行频率.

3 系统仿真及结果分析

使用Quartus Ⅱ对NBC 128/128系统进行综合运算,得到系统综合性能参数如图5所示,本设计使用更少的逻辑块实现了更好的分组加密效果,且NBC分组密码算法较AES算法更优.

图5 系统综合性能参数图

采用时钟分段数据输入方法,大大提高了具有同数量级端口引脚硬件电路的数据吞吐量,整体设计电路如图6所示.电路端口声明如表2所示.

图6 整体电路设计图

表2 电路端口声明

本研究使用流水线技术和非阻塞赋值技术[7-8],系统时钟频率得到显著提高,最高频率可达245.58 MHz.将该设计模块并联使用时将达到更高速的加密效果[9],这在实时性要求高的特定工作环境下有非常高的使用价值.

在完成FPGA电路设计后,利用仿真工具对该电路模块进行了功能性时序仿真[10],如图7所示.结合C语言程序的运行结果,可以看出该电路模型运行结果准确无误.

(a) 数据输入部分

4 结语

本文通过FPGA高速实现了国内自主研发的分组密码算法NBC 128/128的加密过程,对NBC 128/128算法的字节序进行了更适用于FPGA的优化[11],从算法层面缩减了硬件逻辑块资源的占用.在FPGA设计过程中使用分时、分块数据输入技术、有限状态机技术、流水线技术和非阻塞赋值技术实现了NBC128/128的高速电路,电路的可扩展性能够满足明文与密钥长度的倍数增加,大大提高了密码算法的工作效率及其安全保障[12].本文通过硬件电路时序仿真工具验证了整体设计的可行性和准确性.