文献标识码： A
文章编号： 0258-7998(2014)07-0061-04
摘 要： 为了提升密码算法中非线性布尔函数实现效率，设计了串行与电路和以查找表为基础的并行化低次布尔函数实现架构，分别实现高次与项和低次与项。分析了不同并行化查找表实现密码算法中低次布尔函数的效率。结果表明，结合香农分解定理提出的并行化查找表架构处理性能可以达到1.02 GHz，不仅能够灵活适配密码算法中的非线性布尔函数，而且能够节省资源占用。
关键词： 非线性布尔函数；查找表；并行化；适配
在对称密码算法中，非线性布尔函数起着举足轻重的作用，其实现效率直接决定密码算法的处理效率。非线性布尔函数的实现主要有基本逻辑运算组合实现、可编程的与-异或阵列和查找表3种方式实现。其中基本逻辑运算组合实现主要应用于通用处理器中，通过多种基本运算组合，可以实现任意形式的非线性布尔函数。可编程与-异或阵列[1-2]采取对阵列进行遍历的方式实现不同的布尔函数，通过增加阵列的维度以适配更多变量的布尔函数。查找表[3-4]采取将真值表预存的方式实现布尔函数，通过增加存储资源来适配更多变量的布尔函数，也可以将高次布尔函数分解，通过多级运算的方式实现。
可编程与-异或阵列和查找表的出现，虽然在一定程度上缓解了非线性布尔函数实现效率低下的问题，但针对密码算法中的非线性布尔函数，以上两种方式均没有充分利用密码算法中非线性布尔函数的特点，也未充分开发可编程与-异或阵列和查找表的并行性，导致存储资源的利用率低，适配能力不足。
本文通过对密码算法中的非线性布尔函数特点进行分析，分别针对大与项少和小与项多的特点，设计了并行化的查找表架构，能够适配最大与项次数为6的非线性布尔函数；针对高次与项少的特点，设计了专门的串行与运算，可以适配任何次数的与项，能够有效提升非线性布尔函数的实现效率。
1 非线性布尔函数特征分析
1.1 非线性布尔函数操作特征分析
分别从非线性布尔函数的状态序列长度、变量个数、与项最高次数以及与项个数等方面对密码算法中的非线性布尔函数操作特征进行了统计分析和总结归纳，如表1[5-7]所示。
结合表1和非线性布尔函数多项式的表示形式，可以得出密码算法中的非线性布尔函数具有以下几个特点：
(1)状态序列长度，即可能出现在非线性布尔函数中的所有变量个数，不同算法中差异较大。
(2)变量个数。非线性布尔函数状态序列较长，并不是所有变量均参与非线性布尔函数的运算，如在Grain128算法中，参与运算的变量只有总变量的7.8%左右，但变量位置比较分散。
(3)与项次数。参与非线性布尔函数运算的与项次数差异较大。
(4)与项个数。算法中的非线性布尔函数中出现的与项种类在变量可能组成的与项种类中所占比例较小。
(5)与项之间关系。与项之间均为异或关系，不同的与项中可能重复出现相同的变量，与项之间的变量通常具有交叉或包含关系。
1.2 非线性布尔函数的分类
由图1可知，密码算法中的非线性布尔函数具有参与运算的变量占所有变量比例小、变量位置分散、高次与项少、低次与项多的特点。将不同的变量组成的与项进行组合可以发现，整个非线性布尔函数可以拆分为多个包含较少变量的非线性布尔函数(少变量布尔函数)，只是变量的表现形式和变量之间的组合不同。若对非线性布尔函数进行拆分，则能够有效地减少实现介于低次与项和高次与项中间布尔函数消耗的资源，降低路径延迟。需要针对少变量布尔函数的运算进行专门的设计。高次与项较少，需设计专门的串行与电路实现。
与-异或阵列实现方式虽然不需要关心变量的形式，但当与项较多时，需要的配置信息量十分庞大，极大地降低了实现的灵活性。查找表实现方式不需要关心变量的位置，只需要考虑变量的个数，且配置信息量较小，比较适合实现少变量非线性布尔函数。只需将多个少变量布尔函数的结果相异或，即可实现布尔函数中所有低次与项计算。但常见的非线性布尔函数实现方式不能支持多个布尔函数的同时输出，造成了资源的浪费和性能的降低。基于此，为充分开发设计的布尔函数架构的并行性，将低次布尔函数中与项的种类分为两类，并以此为基础，研究低次与项的并行化实现架构：
(1)无公共变量
无公共变量指的是各与项之间不存在公共变量，与项之间相互独立。如日本的TOYOCRYPT-HS1算法中非线性布尔函数，包含63个二次与项，与项之间无公共变量。
(2)有公共变量
有公共变量指的是各与项之间存在公共变量，且公共变量的个数差异较大，与项之间的公共变量差异也较大。如Grain80算法中滤波函数，包含3个二次与项，每两个与项之间都有一个相同的变量，包含4个三次与项，存在有两个共有变量的情况。
2 并行化非线性布尔函数实现架构
结合密码算法中非线性布尔函数中与项的特点，分别针对布尔函数中不同与项的特点，提出相应的布尔函数实现方式。
2.1 高次与项实现
密码算法中非线性布尔函数高次与项数量较少，因此设计了专门的串行与电路实现，如图1所示。可以通过控制序列C中1选择源序列S相应的数据，将保留的数据进行相与，即可得到高次与项的结果。当与项次数i大于N时，可以将控制序列C中填充为全1，i(mod N)不为0时，最后一组控制序列不需要为全1，按照实际需求进行配置。
2.2 低次与项实现
低次与项的布尔函数其与项之间的关系主要包含无公共变量、有公共变量2种，分别对两类与项的实现进行了研究，并在此基础上提出了改进的并行化实现架构。
2.2.1 无公共变量类与项实现
无公共变量类与项中各与项之间无化简的空间，可以采用传统的查找表方式实现。由于与项的次数不固定，因此对查找表实现方式进行了并行化设计，以提高资源的利用率。
采用单一查找表方式实现变量数位n的非线性布尔函数需要的存储空间为2n，即可以满足两个变量为n-1的布尔函数所需存储空间，满足4个变量数为n-2的布尔函数所需存储空间，依此类推可以满足2n-m个变量数为m的布尔函数所需存储空间。结合密码算法中布尔函数的特点，本文以6为例，对布尔函数的并行化设计进行分析。
通过分析在26存储空间上如何实现4变量、5变量、6变量函数，提出了并行化布尔函数设计电路，包含输入端口和配置端口，通过不同的配置，可以支持4个无公共变量的4变量布尔函数，2个无公共变量的5 变量布尔函数，1个6变量的布尔函数，如图2所示。可以充分利用电路中的存储资源，尤其是当要实现的布尔函数具有变量个数多、与项次数低的特征时，可以将布尔函数分别实现，然后将函数的运算结果进行异或即可。
2.2.2 有公共变量类与项实现
无公共变量的并行化架构灵活性高，实现布尔函数种类多，但输入端口数较多，不利于处理器中集成。密码算法的布尔函数中与项存在大量的公共变量，若充分利用公共变量的特点，则能够有效降低布尔函数实现中所需的端口。如以6变量布尔函数为例，支持图2所具有的功能，公共变量数为n(n<6)，则输入端口数减少为19-3n。
基于此提出了具有2个公共变量的并行化架构，如图3所示。以具有2个公共变量的6变量布尔函数的实现为例，可以支持4组具有2个公用变量的4变量布尔函数，分别为f(a，b，c，d)，f(a，b，g，h)，f(a，b，m，n)，f(a，b，p，q)；支持2组具有2个公用变量的5变量布尔函数，分别为f(a，b，c，d，e)，f(a，b，m，n，s)；支持一个6变量布尔函数f(a，b，c，d，e，f)。
2.2.3 改进的布尔函数的实现结构
具有2个公共变量并行化架构能够有效地减少输入端口的数量，但不能减少存储资源的消耗。若能充分利用密码算法中非线性布尔函数具有0、1因子的特点，可以有效地降低实现所需的资源消耗。基于此，结合香农分解定理和低次与项具有公共变量的特点，提出了改进的具有2个公共变量的并行化架构。
由式(1)可知，当一个n变量布尔函数存在代数1、0因子时，n变量的布尔函数可以分解为n-1变量和n-2变量的两个非线性布尔函数，从而可将一个n变量布尔函数所需的2n比特存储资源降少到2n-1+2n-2比特资源，如图4所示并行化架构，以具有2个公共变量的6变量布尔函数的实现为例，可以同时支持3组具有2个公用变量的4变量布尔函数，分别为f(a，b，c，d)，f(a，b，f，g)，f(a，b，m，n)；支持具有一个公用变量的5变量布尔函数和一个4变量布尔函数，分别为f(a，b，c，d，e)，f(a，b，m，n)；支持一个具有代数0、1因子的6变量布尔函数f(a，b，c，d，e，f)。
图4中的非线性布尔函数实现方式虽然有效降低了输入端口数和存储资源的占用，但其支持的所有布尔函数均存在公共变量。为了在接口数量不变的情况下支持更多类型的布尔函数种类，对图4进行了改进，如图5所示，可以支持支持3组具有2个公用变量的4变量布尔函数，分别为f(a，b，c，d)，f(a，b，e，f)，f(a，b，g，h)；支持无公用变量的5变量布尔函数和4变量布尔函数，分别为f(a，b，c，d，i)，f(e，f，g，h)；支持一个具有代数0、1因子的6变量布尔函数f(a，b，c，d，h，i)。
3 函数适配与性能分析
为了验证所设计架构的正确性和高效性，对密码算法中的非线性布尔函数进行了适配，选取了grain-80算法中的非线性布尔函数。设初始的序列已经按照布尔函数的要求将变量进行排列：
如表2所示，可以看出，4种并行化架构都能高效地适配密码算法中的非线性布尔函数，而密码算法中的非线性布尔函数具有代数0、1因子的特征比较明显，两种改进的非线性布尔函数架构就可以很好地满足密码算法中布尔函数的需求，最高处理速度可以达到1.02 GHz，资源占用是其他实现方式的75%。由于其端口数和存储资源占用均较小，特别适合集成到专用的密码处理器中。
结果表明，本文设计的非线性布尔函数并行化架构有效满足了密码算法中非线性布尔函数的特点，不仅可以灵活地适配密码算法中的非线性布尔函数，同时具有较高的处理性能。
通过分析密码算法中非线性布尔函数的特点，对布尔函数中与项进行分类；针对不同类别的与项，提出了相应的并行化布尔函数实现架构。在此基础上，结合香农定理，提出了改进的并行化非线性布尔函数实现架构，能够在较少的输入端口和资源占用情况下灵活适配密码算法中的非线性布尔函数。
下一步需要针对不同应用场景下非线性布尔函数的特点，设计相应的并行化架构，提高不同场景下非线性布尔函数的处理速度。
参考文献
[1] HUTTON M，Sshilecher J.Improving FPGA performance and area using an adaptive logic module[C].Berlin Heidelberg：J Becker，2004：135-144.
[2] Xu Liqing，Chen Hao.Some results on the algebraic immunity of Boolean functions[J].The Journal of China Universities of Posts and Telecommunications，2011，18(2)：102-105.
[3] KAVUT S，YUCEL M D.9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class[J].Information and Computation, 2010，208(4): 341–350.
[4] GANGOPADHYAY S，SARKAR S.Telang R.On the lower bounds of the second order nonlinearities of some Boolean functions[J].Information Science， 2010，180(2)：266-273.
[5] CHASKHKM A V.Local complexity of Boolean functions[J].Discrete Applied Mathematics[J].2004，135(1): 55-64.
[6] COUCEIRO M，MARICHAL J L.Locally monotone Boolean and pseudo-Boolean functions[J].Discrete Applied Mathematics，2012，160(12)：1651-1660.
[7] 徐建博,戴紫彬.面向序列密码抽取与插入单元可重构设计研究[J].电子技术应用，2011，37(7)：65-67.