高效适配NLBF型序列密码的全局定向搜索算法

Global directional search algorithm adapting NLBF sequence cryptogram efficiently

针对序列密码中非线性布尔函数(NLBF)适配算法不具普遍性及资源消耗较多的问题,提出一种基于NLBF与项和真值表相结合的全局定向搜索算法。首先,通过NLBF中与项比率的分析,得出合理的查找表(LUT)适配形式;随后,提出布尔函数归类算法,归类算法从高次到低次搜索NLBF中全部与项,并对各与项进行"吸收"及"合并"处理;最后,提出基于真值表的配置信息生成算法,该算法通过遍历真值表的方式,生成LUT存储的配置信息以完成NLBF的运算。对序列密码进行适配发现,布尔函数归类算法能完成现有NLBF型序列密码的适配,且对常用的ACH-128、Trivium及Grain等算法更易适配;同时从对比结果可以看出,全局定向搜索算法的资源消耗较基于Shannon分解定理的适配算法及遗传算法明显要少;同时从资源消耗情况来看,4输入LUT消耗最多,6输入LUT消耗最少。

In view of the absence of universality and high consumption of sequence cryptogram adaptation algorithms, a global directional searching algorithm based on AND terms of Non-Linear Boolean Function （NLBF） and truth table was proposed. Firstly, adaptive and reasonable models of Look-Up Table （LUT） were gotten by analyzing the ratio of terms in NLBF. Then a classification algorithm for Boolean function was established which can search all AND terms from high-order ones to lows and ＂absorb＂ or ＂unite＂ the terms. Finally, a configuration generating algorithm was obtained on the basis of truth table, which can generate the configuration information to fulfill the computation of NLBF by traversing truth tables. The existing NLBF sequence cryptograms can be adapted by the proposed classification algorithm, and it is more easy to adapt to the commonly used algorithms such as ACH-128, Trivium and Grain. At the same time, the resource consumption of LUT is obviously less than the adaptation based on Shannon decomposition theory and genetic algorithm; meanwhile, the consumption results show that the adaptation consumes the most in 4-input look-up tables and the least in 6-input ones.