h=g∗g型布尔函数的星积分解

摘要：

串联结构是非线性反馈移位寄存器(简称NFSR)结构研究中的一种重要模型,已应用于许多密码算法的设计中,如Grain v1、Grain-128、Grain-128a、Sprout、Fruit等.1970年,美国学者Green等人通过引入布尔函数的星积运算,将NFSR的串联结构与特征函数的星积运算一一对应,使得对NFSR的串联结构研究本质上可以转化为对特征函数的星积性质研究.特征函数的星积分解是一个兼具理论和现实意义的问题,同时也是一个富有挑战性的问题,截至目前仅对分解中含有线性布尔函数的情形有较高效的分解算法.本文研究在g未知的条件下,如何由h=g?g来求解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的星积分解问题.

关键词：序列密码、非线性反馈移位寄存器、NFSR的串联、h=g∗g型星积分解

所属期刊栏目：9

分类号：TP309.7(计算技术、计算机技术)

资助基金：国家自然科学基金61872383

在线出版日期：2022-07-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共16页

页码：468-483