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