0 引言

非线性布尔函数(Non-Linear Boolean Function, NLBF)是构造序列密码的基本编码模块，如Trivium、Grain-80/-128等算法中均采用NLBF以破坏m序列的线性制约性，并保持周期长和统计特性好的优点^[1]。现场可编程门阵列(Filed Programmed Gate Array, FPGA)中的查找表(Look-Up Table, LUT)可根据移存器中的非线性变换需求配置存储数据，能高效灵活地实现不同结构的序列密码。

目前基于LUT实现NLBF型序列密码已相当普遍，eCRYPT工程每年都会公布多种序列密码在通用FPGA上的性能报告^[2-5]。但针对NLBF型序列密码适配算法的研究却相对匮乏，文献[6]采用遗传算法可解决NLBF的适配问题，但容易使适配结果陷入局部最优解，并且从其适配结果来看，消耗的LUT资源明显太多；文献[7]提出了布尔函数的适配问题，并且适配后的资源也相对较少，但只是针对固定的密码算法或某几个特定的NLBF进行了简单的适配，没有提出一种具有普遍适用意义的、可操作的适配算法或适配流程；文献[8]提出一种拆分适配方法，能够完成大多数NLBF的适配，其适配所消耗的资源也有所降低，但仍没一个实际的处理方法。事实上适配算法的优劣直接决定着NLBF型序列密码硬件实现时消耗的LUT资源数目，也间接影响算法运算速度及系统功耗。因此，研究一种高效适配NLBF型序列密码的适配算法已十分必要。

适配NLBF型序列密码的关键在于布尔函数的归类和LUT配置信息的生成。本文通过分析NLBF型序列密码中的非线性布尔表达式，设计并实现了一种能够高效适配NLBF型序列密码的全局定向搜索算法。该算法对序列密码的布尔函数从高次与项(AND item)到低次与项进行定向搜索，能够以较少的资源占用将布尔表达式分别映射到4输入、5输入和6输入的LUT中，可保证适配的效率；并且通过遍历真值表的形式可完成不同布尔表达式配置信息的生成。

1 序列密码NLBF特征分析

在序列密码中NLBF的使用非常普遍，非线性反馈移位寄存器的反馈函数、非线性滤波生成器和非线性组合函数都是NLBF，且每个布尔函数可唯一表示成最小项之和形式：

$\begin{array}{l} f = {c_{{a_{n-1}}{a_{n-2}} \cdots a0}} = \\ \;\;\;\;\;\;{x_{n-1}}{x_{n - 2}} \cdots {x_0} + \cdots + \sum\limits_{i > j} {{c_{{a_i}{a_j}}}{x_i}{x_j} + \sum\limits_i {{c_{{a_i}}}{x_i} + {c_0}} } \end{array}$

其中：系数c_ai表示对应最小项的有无；x_i表示布尔变量；“+”表示异或运算；x_ix_j表示“与”运算。每个最小项为一个与项，与项中变量的个数称为该与项的次数，所有与项次数的最大值称为该布尔函数的次数，且当次数大于1时称该布尔函数为NLBF^[9]。

本文对文献[10-12]欧洲NESSIE工程、eSTREAM计划以及常用的序列密码算法如A5-1、Grain、Trivium等中的NLBF的810个与项进行统计整理，计算出了不同次数与项占总与项的比率，如表 1所示。

从表 1中可以看出：绝大多数NLBF表达式中的与项最高次次数不高于6(事实上，在统计的NLBF型序列密码中只有TOYOCRYPT_HS1包含一个63次和一个17次的高次与项)，并且尽管1次、2次及3次与项在序列密码所占比率较高，达76.6%，但大都能够采取一定的处理方式(“吸收”或“合并”处理，“吸收”与“合并”的概念见2.1节)采用4输入、5输入或6输入LUT来实现，故在进行NLBF的LUT适配时，本文只考虑不高于6次的与项适配，并且本文采用的LUT类型为LUT-4，LUT-5和LUT-6(分别表示4输入、5输入和6输入LUT)。

2 全局定向搜索算法

NLBF的适配过程包括布尔函数与项的分类和LUT配置信息的生成两个过程，因此全局定向搜索算法也分为布尔函数归类算法和适配信息生成算法。归类算法遍历布尔函数中各与项，且从高次与项到低次与项进行定向搜索，先进行与项的“吸收”，再进行与项的“合并”；信息生成算法对LUT真值表进行全局搜索，同时先适配“吸收”项，再适配“合并”项。

2.1 布尔函数归类算法

定义1   由于LUT-k能够实现任意k个变量的布尔表达式，若布尔函数中两个或多个与项所含变量均包含在这k个变量中，则称这些与项可以进行归类。如对于输入变量为a、b、c、d的4输入LUT，记为LUT-4，布尔函数为f=a+bc+bcd+abce，则与项a、bc、bcd都能归到该LUT中，而abce是不能进行归类的。同时称与项bc可以被与项bcd“吸收”，bcd为“吸收项”，bc为“被吸收项”；同时a、bcd(bc)可以“合并”为4变量的布尔表达式。

由于LUT-k可以实现k输入的任意布尔函数，因此为节省适配时的资源必须首先进行“吸收”处理，而对于无法吸收的与项并且其输入变量个数少于k个的则必须进行“合并”处理，这样可以使一个k输入的LUT能够同时实现多个布尔函数，并且必须首先进行“吸收”处理然后再进行“合并”处理。如一个包含以下与项的NLBF:

x₁x₂x₃x₄;

x₁x₂x₄x₅;

x₁x₂;

x₃x₅;

x₄x₆;

可以看出：

1)进行“吸收”处理时，首先高次与项x₁x₂x₃x₄要对低次与项进行定向搜索，即x₁x₂, x₃x₅, x₄x₆，并且x₁x₂被“吸收”，x₃x₅和x₄x₆不能被x₁x₂x₃x₄吸收；对其他高次与项进行类似的处理。

2)“吸收”处理完成后，进行“合并”处理，同样需要对未能被“吸收”的低次与项进行遍历，最终得到合并项f(x₃, x₄, x₅, x₆)。

3)先进行“吸收”后进行“合并”的原因是“吸收”后，低次与项的个数会明显减少，能够减少“合并”的次数，有效降低归类算法的运算时间。

布尔函数的归类以节约LUT资源、降低序列密码算法运算功耗和提高密码算法运算速度为目标，同时要兼顾FPGA内的LUT类型。由于布尔函数归类算法采取先“吸收”再“合并”的处理策略，故可将归类算法可分成“吸收”和“合并”处理流程，“吸收”处理流程的伪代码可表示如下：

 BEGIN

   Sort(F_and);

    for(i=0;i < F_and_num-1;i++)

     for(j=i+1; j < F_and_num; j++)

      if(F[j]⊂F[i])

                          //若F[j]包含在F[i]中

        F[i]Absorb F[j] & Backup F[j];

                           //F[i]“吸收“F[j]并备份F[j]

      Delete F[j]From F_and;

                          //将F[j]从布尔函数与项队列中删除

    else if Having Traversed All F[j];

      Break the Inner Loop;

    if Having Traversed All F[i];

      Break the External Loop.

END

其中：F_and表示布尔函数与项，F_and_num为布尔函数与项的个数，F[i/j]代表第i或第j个布尔函数与项。

NLBF中的与项要尽可能地适配成4输入、5输入和6输入的布尔函数(采用LUT-4，LUT-5和LUT-6来实现布尔函数)，完成序列密码中NLBF的“吸收”处理后，需要将未能被“吸收”的低次与项(这里指低于4次的与项)进行“合并”处理，其处理过程的伪代码如下:

BEGIN

    for(s=0;s < UF_num-1;s++)

      for(t=s+1;t < UF_num; t++)

        var_num=UF[s]_var+UF[t]_var-samevar;

                                  //提取出两个与项中变量的个数

        if((var_num < 4) & (t < UF_num-1))

          s++;

        else if(var_num=4/5/6)

                            //若两个与项变量个数为4个、5个或6个

          Unite UF[s] & UF[t];                //直接合并

          Backup UF[s] & UF[t];                  //并备份原有与项

          Delete UF[t] From UF_and;

                              //从原始与项中将合并的两个与项删除

          var_num=0;

          Break The Inner Loop;

        else if(var_num < 4) & (t=UF_num-1)

                              //若最后两个与项变量总数小于4

      Unite UF[s] & UF[t];

      Backup UF[s] & UF[t];

      Delete UF[t] From UF_and;

      Break The Inner Loop;

    end for

  end for

END

其中:UF_and表示参与合并的布尔函数与项，UF_num

为参与合并处理的与项个数；var_num为多个合并与项的变量个数，UF[s/t]_var是第s或第t合并与项的变量个数; samevar则表示与项相同的变量个数。

以ACH-128中的非线性布尔函数A₀为例介绍布尔函数归类算法的处理流程。ACH-128是一个典型的NLBF型序列密码算法，共有13个非线性布尔函数A₀~A₁₂，其中A₀为：

$\begin{array}{l} {A_0}\left( {{x_0},{x_1}, \cdots ,{x_{20}}} \right) = {x_0} + {x_2} + {x_3} + {x_4} + {x_5} + {x_6} + {x_8} + \\ \;\;\;\;{x_{11}} + {x_{15}} + {x_1}{x_{11}} + {x_2}{x_{11}} + {x_2}{x_{12}} + {x_4}{x_6} + {x_4}{x_7} + {x_5}{x_6}{\rm{ + }}\\ \;\;\;{x_1}{x_2}{x_{11}} + {x_1}{x_2}{x_{12}} + {x_1}{x_9}{x_{11}} + {x_9}{x_{10}}{x_{11}} + {x_1}{x_2}{x_6}{x_{13}} + \\ \;\;\;{x_1}{x_2}{x_9}{x_{11}} + {x_1}{x_2}{x_9}{x_{12}} + {x_2}{x_9}{x_{10}}{x_{11}} + {x_2}{x_9}{x_{10}}{x_{12}} + \\ \;\;\;{x_1}{x_2}{x_6}{x_9}{x_{13}} + {x_2}{x_6}{x_9}{x_{10}}{x_{13}} \end{array}$

图 1给出了A₀的吸收处理流程(这里以下标表示对应变量，图中各与项左侧标号表示该与项的标号，不同形状对应不同的次数，从5次与项到1次与项对应的形状分别为正方形、圆、三角形、六边形和八边形；右侧标号则为对应与项被“吸收”到的与项标号)。从图 1中可以看出：

1)图 1(a)中为5次与项中标号为0的与项处理流程：首先从5次与项1, 2, 6, 9, 13进行遍历，共可遍历得到4次与项1, 2, 6, 13、1次与项2及6能够被其吸收，将被吸收与项从列表中删除，同时备份以在进行配置信息生成时调用。

2)同理，图 1(b)中遍历与项发现5次与项2, 6, 9, 10, 13无可吸收项，则跳过，同时进行1, 2, 9, 11可吸收与项的搜索，最终得到被吸收与项：1, 2, 11；1, 9, 11；1, 11；2, 11；11。

3)经过多次全局定向搜索最终得到不可吸收的与项有：1, 2, 6, 9, 13；2, 6, 9, 10, 13；1, 2, 9, 11；1, 2, 9, 12；2, 9, 10, 11；2, 9, 10, 12；4, 6；4, 7；5, 6；0；3；8；15。

从“吸收”处理的最终结果可以知道，仍有部分2次或1次布尔表达式，则需进行“合并”处理，A₀的合并处理流程如图 2所示。

图 2中A₀进行合并处理的最终结果为2个4变量布尔表达式：4, 6, 7, 5；0, 3, 8, 15。但需要注意的是，合并处理前要进行公共变量的搜索，最终变量的个数为两个或多个要合并项的变量数目之和减去相同变量的个数。如在合并4, 6；4, 7；时，因为含有公共变量6，最终变量的个数为2+2-1=3，合并结果为4, 6, 7，如图 2中(a)、(b)所示。

2.2 配置信息生成算法

配置信息的生成与LUT要完成的运算功能及配置信息的存储形式(真值表)紧密相关。图 3给出了4输入LUT的框图及其一种对应的真值表，其中R[0]~R[15]∈{0, 1}。

配置信息生成算法依据真值表的组织形式进行遍历，按照“吸收项”→“被吸收项”→合并项的顺序进行定向搜索，最终实现整个NLBF配置信息的生成。

由于每个NLBF所包含的与项是不同的，即所完成的运算功能是不同的，而每个布尔函数均可表示成最小项的形式，为此在进行配置信息生成时，必须对真值表进行遍历。

在配置信息生成的过程中，在对真值表进行遍历时，有效的最小项地址位置存储为1，但由于包含“吸收”项、“合并”项及一般与项，在处理时必须对三者分别处理。以一个顺序编址的LUT-4来说就是从0000遍历到1111分别配置生成存储信息。

配置信息生成算法处理流程的伪代码如下所示(以LUT-4为例，输入的高位为a，低位为d；LUT-5及LUT-6的处理与之类似)。

BEGIN

  for(var=0;var < 15;var++)

    //LUT-4的真值表为0000到1111，即0到15

    d=var%2;

    c=(var > > 1)%2;                  //var右移1位并对2取余

    b=(var > > 2)%2;

    a=(var > > 3)%2;

    fx=0;and_term=0;

    for(i=0;i < f4_num; i++)

      for(j=0; j < 4; j++)

        if f4 is AND term;                   //f4仅是与项，则直接适配

          if f4[i, j]=a/b/c/d

            and_term=and_term*a/b/c/d;

          end if

          fx=fx+and_term;

        else if f4 includes absorb terms;           //若f4包含吸收项

          if f4 or fa=a/b/c/d;

            absorb_term=absorb_term*a/b/c/d;

          end if

          fx=fx+absorb_term;

        else if f4 is unite term;               //若f4是合并而来

          detect the absorb terms;

          if fa or fu=a/b/c/d;

            unite_term=unite_term*a/b/c/d;

          end if

          fx=fx+unite_term;

      end for

    end for

    cfg[var]=fx%2;//适配相加的结果对2取余即为LUT中

                              //var地址单元要存储的配置信息

  end for

END

其中: f4代表 4变量函数；fa为被吸收与项；fu是合并而成的与项；f4_num表示4变量函数的个数；cfg[var]表示真值表中存储的第var个配置信息，fx, and_term, absorb_term, unite_term均是程序运算时用到的中间变量。

这里同样以ACH-128中A₀归类处理后的4变量布尔函数f(x₄, x₆, x₇, x₅)来说明配置信息的生成流程，如图 4所示。

配置信息生成流程如下：

1)检测为何种类型的布尔函数：该布尔函数f(x₄, x₆, x₇, x₅)为合并项。

2)搜索合并项由哪些低次项组成：由4, 6;4, 7;5, 6组成。

3)逐项进行真值表由0000~1111检索并生成配置信息：共生成3×16b的配置数据(由于配置信息由最初设计时决定，故这里以XXXX来表示)。

4)逐项检测是否吸收其他与项：4, 6吸收1次与项4，4, 7无吸收与项，5, 6吸收1次与项5。

5)对吸收与项逐项检索真值表并生成配置信息：共生成2×16b的配置信息。

6)最后将两次生成的配置信息进行处理生成最终的配置信息：5组16b配置数据对应位相加模2求余。对于无吸收项且不是合并而来的与项、只含吸收项的与项或只是合并而来的项，其处理与之类似，这里不再赘述。

3 性能评估

本章对全局定向搜索算法的NLBF型序列密码适配性能进行评估。由于配置信息生成算法与LUT对应的真值表相关，对于不同的真值表将会有所不同，故这里仅对布尔函数归类算法进行消耗LUT资源的评估。本文从硬件资源消耗的角度给出归类算法所消耗的LUT数目，结果见表 2。

由表 2可以看出，归类算法能够很好地适配不同类型序列密码的NLBF，并且由于ACH-128、Trivium和Grain-80含有的4输入、5输入或6输入变量布尔表达式较多，对于其归类的处理也更加容易；同时序列密码算法中LUT-4和LUT-5的使用频率较高，这对序列密码的硬件设计也有一定的指导作用。

此外，将全局定向搜索算法与文献[6]方法和文献[7]方法进行了性能对比，对比如表 3所示。对比结果表明，在部分布尔函数的适配上，全局定向搜索算法在适配Grain-128算法时所消耗的LUT资源较文献[6]方法多，但算法具有更大的通用性，能够完成具有不同表达式、不同运算功能非线性布尔函数的适配；并且文献[6]只是对布尔函数进行了分类，并没有针对布尔函数的分类进行LUT配置信息的生成。与文献[7]相比，都能够适配不同的NLBF型序列密码算法(文献[7]ACH-128算法只给出了A₁₁的适配结果，其他如Trivium、A5-1、A5-2及LILI等算法的NLBF的适配虽未列出，但从其算法角度来讲是可以适配的)，但是本文消耗的LUT资源明显要少，而且文献[7]采用遗传算法有可能使适配结果陷入局部最优解，致使LUT资源消耗很大。

4 结语

本文首先对NLBF型序列密码算法进行特征分析，提取出LUT常用的适配形式；利用从高次到低次对NLBF中与项进行定向搜索，对其进行“吸收”和“合并”处理，能够解决布尔函数的归类问题；通过遍历真值表的形式，提出一种LUT配置信息的生成方法。通过对多种NLBF型序列密码进行适配结果表明，本文提出的全局定向搜索算法适用于不同形式的NLBF型序列密码，具有通用性，并且对硬件设计也具有一定的参考意义。但本文依然存在一些不足，比如只针对4输入、5输入及6输入这些常用的LUT结构进行了适配，但在一些可重构系统中为提升资源的利用率，多个LUT间通常会存在采用共享变量，其适配方法将会有一定的改变。接下来的研究中，可以通过分析一些设计中共享变量的形式，针对性地提出对共享变量进行适配。