h=g*g型布尔函数的星积分解
2022-10-31 18:17:15   来源：    点击：

摘要:串联结构是非线性反馈移位寄存器(简称NFSR)结构研究中的一种重要模型,已应用于许多密码算法的设计中，如Grain v1、Grain-128、Grain-128a、Sprout、Fruit 等.1970年,美国学者Green等人通过引入布尔函数的星积运算，将NFSR的串联结构与特征函数的星积运算一一对应,使得对NFSR的串联结构研究本质上可以转化为对特征函数的星积性质研究．特征函数的星积分解是一个兼具理论和现实意义的问题,同时也是一个富有挑战性的问题,截至目前仅对分解中含有线性布尔函数的情形有较高效的分解算法．本文研究在g 未知的条件下，如何由h = g * g 来求解g.针对两类情形，我们分别给出了求取g的高效算法．在第一类情形中，基于对布尔函数求偏导降次的思想，我们将g * g 的分解问题转化为l * g 的分解问题，其中Ⅰ是线性布尔函数，进而利用现有的高效分解算法求得g．在第二类情形中，我们首先构建关于布尔函数求偏导的函数方程,然后利用按次数进行“分层剥离”的思想依次求取9(u，9[d-1]…﹐9/1],从而最终求取g,其中 g y] 是g 中所有k次项之和, d = deg(g).上述gg的求取也是转化为l*g[k的分解来实现.此外，本文从星积分解的角度给出了两个特征函数较为“接近”的一种刻画，并将较为“接近”的特征函数的星积分解问题转化为h =g * g 的星积分解问题.