序列密码是对称密码的一种,特点是便于软硬件实现,加解密速度快。序列密码脱胎于“一次一密”密码体制。由于序列密码并不给出与明文等长的真随机密钥流,而是由少量真随机的密钥生成密钥流,因此如何保证密钥流的强度,使得加密算法不会被小于穷举的复杂度攻破,是序列密码设计与分析中需要解决的问题。本文围绕基于线性反馈移位寄存器（LFSR）的序列密码的相关攻击方法展开研究,针对构造具有高相关优势或容度的线性逼近这一核心步骤,提出了将有记忆变换的线性逼近等价地转化为对一个复合函数的线性逼近的原理和方法,从而将对有记忆变换的线性逼近问题转化为复合函数的线性逼近问题,进而提出了这类序列密码算法最大相关优势和安全性的评估方法。本文的主要工作如下:1.本文首次提出了将对序列密码的线性逼近等价地转化为复合函数的特定形式的线性逼近的原理和方法,从而将对有记忆变换的线性逼近问题等价地转化为对复合函数的线性逼近问题。这不仅使我们可以从复合函数的线性逼近单链入手,获得有记忆变换的线性逼近单链,还可以通过对优势非零的线性逼近单链的穷举,借助复合函数的Walsh谱计算定理,获得二元线性逼近的真实优势。2.本文首次给出了8比特S盒线性分布表和差分分布表的基于SAT/SMT的精确刻画,从而使我们可以利用8比特S盒线性分布表和差分分布表的细节,采用SAT/SMT工具来搜索密码算法的高优势线性逼近链和高概率差分传递链。3.在上述理论的支持下,本文给出了针对SNOW-V的SAT/SMT技术的自动搜索模型,并搜索出了SNOW-V的一系列高相关线性逼近单链,证明了可以在远低于248的时间复杂度下穷举这类二元线性逼近中包含的所有优势非零的单链的相关系数,获得其相关系数的真实值。对于SNOW-V,本文找到了相关系数为-2-47.76的二元线性逼近,由此给出了时间复杂度为2246.53、存储复杂度为2238.77、数据量2237.5的相关攻击。对于SNOW-Vi,本文证明了上述针对SNOW-V的相关攻击的方法和结论对SNOW-Vi同样适用。这是对SNOW-V和SNOW-Vi的首个时间复杂度低于密钥穷举的攻击方法。此外,借助上述理论与方法,本文还给出了SNOW-V的区分攻击区分器。这一区分攻击区分器不必知道和利用LFSR反馈多项式的少项倍式,不仅可以使用一个IV产生的密钥流进行攻击,还可以综合利用不同IV产生的密钥流进行攻击。4.利用转化为复合函数的方法给出了SNOW3G基于SAT/SMT的自动搜索模型,从而首次在不对线性逼近添加任何约束的条件下,给出了基于单链的SNOW3G相关攻击区分器的全覆盖搜索,得到了SNOW3G的线性逼近单链的相关优势上确界为2-23.415的结论。这是迄今为止对SNOW3G的线性逼近单链的最大相关优势的首个安全性结论。在得到高相关单链的基础上,本文提出了在其他单链中搜索高相关优势的单链的原理和方法,进而提出了对高相关单链的相关系数求和来得到二元线性逼近的真实相关系数近似值的逐步求精法,该方法给出了在线性逼近链的中间mask数量太大而无法穷举时求解其真实相关系数近似值的原理和方法。本文对该方法得到的近似值与二元相关优势的真实值进行了对比,结果显示与精确计算的结果非常近似。此外,针对二元扩域上多比特容度和二元相关优势的关系,本文给出了这二者之间的结构对应,并首次提出了将二元线性逼近扩充为二元扩域上线性逼近的原理和方法,由此说明了Yang等人[50]基于字节逼近获得的8比特线性逼近的容度主要由其中的大优势二元逼近决定,再次印证了Gong等人在[51]中的结论。5.为解决基于LFSR设计的序列密码算法有两个连续时刻密钥字参与的相关攻击区分器中线性逼近单链的最大相关优势计算的通用原理和方法问题,本文给出了将这类区分器等价地转化为由一些简单函数组成的复合函数的线性逼近的原理、方法和算法,从而使我们借助该方法,可以将任意基于LFSR的序列密码的两个连续时刻密钥字参与的区分器转化为复合函数的线性逼近,获得优势最大的线性逼近单链,并借助复合函数的Walsh谱理论,获得二元线性逼近的真实相关优势。作为例子和应用,我们将上述结果应用到了SNOW2.0和ZUC算法。对SNOW2.0,本文证明了其线性逼近单链的相关优势上确界为2-15.415,并得到了新的与已知最大优势2-14.41相等的区分器。对于ZUC序列密码算法,本文首次给出了其线性逼近单链的相关优势上确界为2-21.608且有多条链可达的结论,并证明了计算这类二元线性逼近的真实相关系数的时间复杂度低于225。此外,本文计算了目前已有结果和本文中新的结果的真实相关系数均为-2-21.084,同时证明了这类包含目前已知高优势结果的区分器的真实相关优势上确界为2-21.084。6.针对基于LFSR设计的序列密码算法有k个连续时刻密钥字参与的相关攻击区分器的一般情形,为解决其有记忆变换的线性逼近单链的最大相关优势计算的通用原理和方法问题,本文给出了将连续k个时刻密钥字参与的对有记忆变换的线性逼近等价地转化为一些简单函数组成的复合函数的线性逼近的原理、方法和算法,从而使我们借助该方法,可以对任意基于LFSR设计的序列密码的有记忆变换进行线性逼近。进一步地,本文证明了在对这类线性逼近区分器进行搜索时,我们只需考虑状态刷新函数和密钥字输出函数中涉及的LFSR元素的一组极大线性无关组的mask非零的情形,其他优势非零的区分器均为这类线性逼近的不同表现形式。作为例子和应用,我们将上述结果应用到了SNOW-V,Sosemanuk和Grain-128算法,分别给出了与SNOW-V三个连续时刻、Sosemanuk四个连续时刻和Grain-128的129个连续时刻输出参与的区分器等价的复合函数逼近过程,并利用复合函数的线性逼近优势计算方法,从另一种途径证明了Todo等人给出的Grain-128的现有最优相关优势以及达到该优势的线性逼近个数。此外,当复合函数的部分输出变量和输入变量存在双射关系时,本文也给出了另一类更加简洁的复合函数逼近的构造。本文给出的复合函数逼近的构造方法适用于任意二元线性逼近方程,是一种通用的构造方法。