流密码[序列密码]（stream cipher）的基本概念
流密码（stream cipher）也称序列密码，流密码每次加密处理数据流的一位或一个字节，加解密使用相同的密钥，是对称密码算法的一种。 流密码的思想主要来源于一次一密算法
一次一密（one-time pad）
- 一种理想的加密方案，叫做一次一密密码（one-time pad），由Major Joseph Mauborgne和AT&T公司的Gilbert Vernam1917年发明的
- 明文：$x = x_0x_1x_2...$
- 密钥：$k = k_0k_1k_2...$
- 密文：$y = y_0y_1y_2...$
- 加密函数：$y_i = x_i + k_i(mod\ 26)$
- 解密函数：$x_i = y_i - k_i(mod\ 26)$
- 注：密钥为随机产生的，而且只使用一次
在现代的信息技术处理中，数据使用01串来表示，所以一次一密使用01串进行加密和解密，在明文和密码中，使用逐比特的异或来进行加解密的。
| xor | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
在逻辑运算中，设$a$为明文，$b$为密钥，$c$为加密后的密文，$a,b,c$之间由以下关系：
$$a \oplus b = c，c \oplus b = a$$
一次一密的特点
- 优点：
- 密钥随机产生，仅使用一次
- 无条件安全
- 加密和解密为加法运算，效率极高
- 缺点：
- 密钥长度至少和明文长度一样，密钥共享困难，实用性低
流密码（stream cipher）
流密码的思想来源主要来源于一次一密算法，针对一次一密密钥长度至少和明文长度一样的特点，流密码的思想是产生一小段密钥，由者一小段密钥可以推导出完整的密钥，解决一次一密实用性较低的特点。流密码概况
- 密钥长度至少和明文长度一样，密钥共享困难，实用性低
- 流密码（stream cipher）是一种重要的密码体制
- 明文消息按字符或比特逐位加密
- 流密码也称为序列密码（sequence cipher）
- 流密码在20世纪50年代得到飞跃式发展
- 密钥流可以用移位寄存器电路来产生，也促进了线性和非线性移位寄存器发展
- 流密码主要是基于硬件实现
流密码的基本思想
- 流密码的基本思想
- 利用密钥$k$产生一个密钥流$z = z_0z_1z_2...$，并使用如下规则对明文串$x = x_0x_1x_2...$加密：
$$y = y_0y_1y_2... = Ez_0(x_0)Ez_1(x_1)Ez_2(x_2)...$$
- 利用密钥$k$产生一个密钥流$z = z_0z_1z_2...$，并使用如下规则对明文串$x = x_0x_1x_2...$加密：
- 密钥流：
- 由密钥流发生器$f$产生：$z_i = f(k, \sigma_i)$
- $\sigma_i$是加密器中的记忆元件在时刻$i$的状态
- $f$是由$k, \sigma_i$产生的函数
- 内部记忆元件由一组移位寄存器构成
同步流密码
内部记忆元件的状态$\sigma_i$独立于明文字符的叫做同步流密码，否则叫做自同步流密码。
在同步流密码中，由于$z_i = f(k, \sigma_i)$与明文字符无关，因而此时密文字符$y_i = E_{zi}(x_i)$也不依赖于此前的明文字符。因此，可将同步流密码的加密器分为密钥流产生器和加密变换器两个部分。
同步流密码体制模型
二元加法流密码是目前最为常用的流密码体制，其加密变换可表示为$y_i = z_i \oplus x_i$。
流密码的需求
- 一次一密密码是加法流密码的原型
- 如果密钥用作滚动密钥流，则加法流密码就退化成一次一密密码。
- 密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：
- 极大的周期
- 良好的统计特性
- 抗线性分析
有限状态自动机
有限状态自动机
有限状态自动机模型
有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成：
- 有限状态集$S = \{ s_i | i = 1, 2, ..., l\}$
- 有限输入字符集$A_1 = \{ {A^{(1)}}_j | j = 1, 2,...,m \}$和有限输出字符集$A_2 = \{ {A^{(2)}}_k | k = 1, 2,...,n \}$
- 转移函数${A^{(2)}}_k = f_1(s_i, {A^{(1)}}_j)$，$S_h = f_2(s_i, {A^{(1)}}_j)$，即在状态为$s_i$，输入为${A^{(1)}}_j$时，输出为${A^{(2)}}_k$，而状态转移为$S_h$。
有限状态自动机的表示
有限状态自动机的有向图表示
- 有限状态自动机可用有向图表示，称为转移图。
- 转移图的顶点对应于自动机的状态，若状态$s_i$在输入${A^{(1)}}_i$时转为状态$s_j$，且输出一字符${A^{(2)}}_j$，则在转移图中，从状态$s_i$到状态$s_j$有一条标有$({A^{(1)}}_i, {A^{(2)}}_j)$的弧线。
- 转移图的顶点对应于自动机的状态，若状态$s_i$在输入${A^{(1)}}_i$时转为状态$s_j$，且输出一字符${A^{(2)}}_j$，则在转移图中，从状态$s_i$到状态$s_j$有一条标有$({A^{(1)}}_i, {A^{(2)}}_j)$的弧线。
有限状态自动机的矩阵表示
设$S = \{s_1, s_2, s_3\}$，$A_1 = \{
{A^{(1)}}_1, {A^{(1)}}_2, {A^{(1)}}_3\}$，$A_2 = \{
{A^{(2)}}_1, {A^{(2)}}_2, {A^{(2)}}_3\}$，则该有限状态自动机的矩阵表示如下：
| | | | | |
|---|---|---|---|---|
| $f_1$ | ${A^{(1)}}_1$ | ${A^{(1)}}_2$ | ${A^{(1)}}_3$ |
| $s_1$ | ${A^{(2)}}_1$ | ${A^{(2)}}_3$ | ${A^{(2)}}_2$ |
| $s_2$ | ${A^{(2)}}_2$ | ${A^{(2)}}_1$ | ${A^{(2)}}_3$ |
| $s_3$ | ${A^{(2)}}_3$ | ${A^{(2)}}_2$ | ${A^{(2)}}_1$ |
| $f_2$ | ${A^{(1)}}_1$ | ${A^{(1)}}_2$ | ${A^{(1)}}_3$ |
| $s_1$ | $s_2$ | $s_1$ | $s_3$ |
| $s_2$ | $s_3$ | $s_2$ | $s_1$ |
| $s_3$ | $s_1$ | $s_3$ | $s_2$ |
有限状态自动机实例
若输入序列为：${A^{(1)}}_1{A^{(1)}}_2{A^{(1)}}_1{A^{(1)}}_3{A^{(1)}}_3{A^{(1)}}_1$，初始状态为$s_1$，则得到的序列：
$$s_1s_2s_2s_3s_2s_1s_2$$
输出字符序列：${A^{(2)}}_1{A^{(2)}}_1{A^{(2)}}_2{A^{(2)}}_1{A^{(2)}}_3{A^{(2)}}_1$
密钥流生成器
- 密钥流产生器：参数为$k$的有限状态自动机
- 一个输出符号集$Z$、一个状态集$\Sigma$、两个函数$\varphi$和$\psi$以及一个初始状态$\sigma_0$组成。
- 状态转移函数$\varphi: \sigma_i \rightarrow \sigma_{i + 1}$，将当前状态$\sigma_i$变为一个新状态$\sigma_{i + 1}$
- 输出函数$\psi: \sigma_i \rightarrow z_i$，当前状态$\sigma_i$变为输出符号集中的一个元素$z_i$
密钥流生成器设计的关键
- 关键在于：找出适当的状态转移函数$\phi$和输出函数$\varphi$，使得输出序列$z$满足密钥流序列$z$应满足的随机性条件，并且要求在设备上是节省的和容易实现的。
- 一般采用线性的$\phi$和非线性的$\varphi$，这样将能够进行深入的分析并可以得到好的生成器。
密钥流生成器的分解
- 密钥流生成器可分成驱动部分和非线性组合部分
- 驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列
- 非线性组合部分要利用这些序列组合出满足要求的密钥流序列
常见的密钥流生成器
- 目前最为流行和实用的密钥流产生器，其驱动部分是一个或多个线性反馈移位寄存器。
- 前者称为滤波生成器，或前馈生成器
- 后者称为非线性组合生成
- 还有钟控生成器，缩减生成器，停走生成器等
二元序列的伪随机性
二元序列
二元序列的定义
- $GF(2)$上的一个无限序列$\mathop{a}\limits_{\rightarrow} = (a_1, a_2,..., a_n,...)$称为二元序列，其中$a_i \in GF(2)$。
- 周期：对于二元序列$\mathop{a}\limits_{\rightarrow}$，如果存在正整数$l$，使得对于一切正整数$k$都有$a_k = a_{k + l}$，则称$\mathop{a}\limits_{\rightarrow}$是周期的。
- 满足上述条件的最小正整数称为$\mathop{a}\limits_{\rightarrow}$的周期，记为$p(\mathop{a}\limits_{\rightarrow})$
周期的性质
设$GF(2)$上的一个无限序列$\mathop{a}\limits_{\rightarrow} = (a_1, a_2,..., a_n,...)$是周期为$p(\mathop{a}\limits_{\rightarrow})$的二元序列，并设正整数$l$对任何非负整数$k$都有$a_k = a_{k + l}$，则一定有$p(\mathop{a}\limits_{\rightarrow})|l$证明：
设$l = qp(\mathop{a}\limits_{\rightarrow}) + r$，其中$q, r$为正整数，且$0 \leqslant r < p(\mathop{a}\limits_{\rightarrow})$，则有：
$$ > a_k = a_{k + l} \\ > \Rightarrow a_k = a_{qp(a) + r + k} \\ > \Rightarrow a_k = a_{r + k} > $$
又由于$0 \leqslant r < p(\mathop{a}\limits_{\rightarrow})$，根据$p(\mathop{a}\limits_{\rightarrow})$的极小性可知$r = 0$，因此$p(\mathop{a}\limits_{\rightarrow})|l$。游程的定义
设$\mathop{a}\limits_{\rightarrow}$是$GF(2)$上周期为$p(\mathop{a}\limits_{\rightarrow})$的周期序列。将$\mathop{a}\limits_{\rightarrow}$的一个周期$(a_1, a_2,...a_{p(\mathop{a}\limits_{\rightarrow})})$依次排列在一个圆周上使$a_{p(\mathop{a}\limits_{\rightarrow})}$与$a_1$相连，把这个圆周上形如$\begin{matrix} \underbrace{ 011 \cdots110 } \\ 都是1 \end{matrix}$或$\begin{matrix} \underbrace{ 100 \cdots001 } \\ 都是0 \end{matrix}$的一连串两两相邻的项分别称为$\mathop{a}\limits_{\rightarrow}$的一个周期中一个1游程或一个0游程。而1游程中的1的个数或0游程中0的个数称为游程的长度。
游程的例子
周期为15的二元序列
- 满足上述条件的最小正整数称为$\mathop{a}\limits_{\rightarrow}$的周期，记为$p(\mathop{a}\limits_{\rightarrow})$
- 10001为0的3游程
- 011110为1的4游程
自相关函数
$GF(2)$上周期为$T$的序列$\{a_i\}$的自相关函数定义为：
$$ R(t) = \sum_{k = 1} ^ T (-1)^{a_k}(-1)^{a_{k + l}}, 0 \leqslant t \leqslant T - 1 $$
当$t = 0$时，$R(t) = T$，当$t \ne 0$时，称$R(t)$为异相自相关函数。伪随机序列
Golomb伪随机公设
3各随机性公设： - 在序列的一个周期内，0与1的个数相差至多为1
- 说明$\{a_i\}$中0与1出现的概率基本上相同
- 在序列的一个周期内，常委$i$的游程占游程总数的$\frac{1}{2^i}(i = 1, 2,...)$，且在登场的游程中0的游程个数和1的游程个数相等。
- 说明0与1在序列中每一位置上出现的概率相同
- 异相自相关函数时一个常数
- 意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息
伪随机序列的定义
设$\mathop{a}\limits_{\rightarrow} = (a_1, a_2,..., a_{p(q)},...)$是$GF(2)$上一个周期等于$p(\mathop{a}\limits_{\rightarrow})$的周期序列。
如果对于一切$t \not\equiv 0(mod\ p(\mathop{a}\limits_{\rightarrow}))$，有
$$R(t) = -1$$
则称序列$\mathop{a}\limits_{\rightarrow} = (a_1, a_2,..., a_{p(q)},...)$为伪随机序列。
- 意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息
- 上述定义满足Golomb三个伪随机公设。
伪随机序列示例
周期为15的二元序列100010011010111 - 0的个数为7，1的个数为8
- 0的游程个数为4，1的游程个数为4
- 异相自相关函数等于-1
伪随机序列应满足的条件
- 周期$p$要足够大，如大于$10^{50}$
- 序列$\{a_i\}_{i \ge 1}$产生易于高速生成
- 当序列$\{a_i\}_{i \ge 1}$的任何部分暴露时，要分析整个序列，提取产生它的电路结构信息，在计算上是不可行的，称此为不可预测性
条件3绝对了密码的强度，是流密码理论的核心。它包含了流密码要研究的许多主要问题，如线性复杂度，相关免疫性，不可预测性等。
线性反馈移位寄存器
反馈移位寄存器
移位寄存器是流密码产生密钥流的一个主要组成部分。
$GF(2)$上一个$n$级反馈移位寄存器由$n$个二元存储器与一个反馈函数$f(a_1, a_2,..., a_n)$组成，如下图所示：
反馈移位寄存器的状态
在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于$GF(2)$上的一个$n$维向量，共有$2^n$种可能的状态。
每一时刻的状态可用$n$维向量：
$$(a_1, a_2,...,a_n)$$
表示，其中$a_i$是第$i$级存储器的内容。
反馈函数
初始状态由用户确定。
反馈函数$f(a_1, a_2,..., a_n)$是$n$元布尔函数，即函数的自变量和因变量只取0和1这两个可能的值。
函数中的运算有逻辑与、逻辑或、逻辑补等运算
反馈移位寄存器示例
如图是一个3级反馈移位寄存器，其初始状态为$(a_1, a_2, a_3) = (1, 0, 1)$，输出可由下表给出。
一个三级反馈移位寄存器的状态和输出：
| $a_3$ | $a_2$ | $a_1$ | 输出 |
| --- | --- | --- | --- |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
即输出序列为101110111011...，周期为4。
线性反馈移位寄存器LFSR(Linear feedback shift register)
$GF(2)$上的$n$级线性反馈移位寄存器：
$$f(a_1, a_2,...,a_n) = c_1a_n \oplus c_2a_{n - 1} \oplus ··· \oplus c_na_1$$
LFSR的反馈函数
输出序列$\{ a_t \}$满足：
$$ f(a_1, a_2,...,a_n) = c_1a_n \oplus c_2a_{n - 1} \oplus ··· \oplus c_na_1 \\ a_{n + 1} = c_1a_n \oplus c_2a_{n - 1} \oplus ··· \oplus c_na_1 \\ a_{n + 2} = c_1a_{n + 1} \oplus c_2a_n \oplus ··· \oplus c_na_2 \\ ...... \\ a_{n + t} = c_1a_{n + t - 1} \oplus c_2a_{n + t - 2} \oplus ··· \oplus c_na_t, t = 1, 2,... $$
线性反馈移位寄存器：实现简单、速度快、有较为成熟的理论，成为构造密钥流生成器的最重要的部件之一。
LFSR的示例
下图是一个5级线性反馈移位寄存器，其初始状态为$(a_1, a_2, a_3, a_4, a_5) = (1, 0, 0, 1, 1)$
反馈函数：$a_{5 + t} = a_{t + 3} \oplus a_t, t = 1, 2,...$
输出序列为：1001101001000010101110110001111100110...，周期为31。
密钥流的周期
给定密钥流$\{ a_i \} = a_1, a_2, a_3,..., a_n, ...$，如果存在整数$r$，使得对于任意$a_i$，都有$a_{i + r} = a_i$，则称$r$为该密钥流的一个周期，称满足$a_{i + r} = a_i$的最小正整数为该密钥流的最小周期或简称周期。
LFSR的性质
总是假定$c_1, c_2,..., c_n$ 中至少有一个不为0，否则$f(a_1, a_2,..., a_n) \equiv 0$。
总是假定$c_n = 1$。
- LFSR输出序列的性质：完全由其反馈函数决定。
- $n$级LFSR状态数：最多有$2^n$个
- $n$级LFSR的状态周期：$\le 2^n - 1$
输出序列的周期 = 状态周期，$\le 2^n - 1$
选择合适的反馈函数可使序列的周期达到最大值$2^n - 1$，周期达到最大值的序列称为m序列。
m序列
线性反馈移位寄存器的多项式表示
线性移位寄存器的一元多项式表示
定义：设n级线性移位寄存器的输出序列满足递推关系：
$$ a_{n + k} = c_1a_{n + k - 1} \oplus c_2a_{n + k - 2} \oplus ··· \oplus c_na_k $$
用延迟算子$D(Da_k = a_{k - 1})$作为未定元，给出的反馈多项式为：
$$p(D) = 1 + c_1D +...+c_{n - 1}D^{n-1} + c_nD^n$$
这种递推关系可用一个一元高次多项式：
$$p(x) = 1 + c_1x +...+c_{n - 1}x^{n-1} + c_nx^n$$
表示，称这个多项式为LFSR的特征多项式。
根据初始状态的不同，由递推关系生成的非恒零的序列有$2^n - 1$个，记$2^n - 1$个非零序列的全体为$G(p(x))$。生成函数
定义：给定序列$\{ a_i \}$，幂级数：
$$A(x) = \sum^{x}_{i = 1}a_ix^{i - 1}$$
称为该序列的生成函数生成函数的性质
定理：设$p(x) = 1 + c_1x +...+c_{n - 1}x^{n-1} + c_nx^n$是$GF(2)$上的多项式，$F(p(x))$中任一序列$\{ a_i \}$的生成函数$A(x)$满足：
$$A(x) = \frac{\phi(x)}{p(x)}$$
其中：
$$\phi(x) = \sum^n_{i = 1}(c_{n - i}x^{n - i}\sum^i_{j = 1}a_jx^{j - 1})$$一些定理和定义
根据初始状态的不同，由递推关系生成的非恒零的序列有$2^n - 1$个，记$2^n - 1$个非零序列的全体为$G(p(x))$。
定理1：$p(x)|q(x)$的充要条件是$G(p(x)) \subset G(q(x))$。
——该定理说明：可用n级LFSR产生的序列，也可用级数更多的LFSR来产生。
定义：设$p(x)$是$GF(2)$上的多项式，使$p(x)|(x^p - 1)$成立的最小正整数$p$称为$p(x)$的周期或阶。
定理2：若序列$\{ a_i \}$的特征多项式$p(x)$定义在$GF(2)$上，$p$是$p(x)$的周期，则$\{ a_i \}$的周期$r|p$
——该定理说明：n级LFSR输出序列的周期$r$，不依赖于初始条件，而依赖于特征多项式$p(x)$。m序列产生的条件
不可约多项式
定理：设$p(x)$是n次不可约多项式，周期为m，序列$\{ a_i \} \in G(p(x))$，则$\{ a_i \}$的周期为m。
m序列产生的必要条件
定理：n级LFSR产生的序列有最大周期$2^{n - 1}$的必要条件是其特征多项式为不可约的。
该定理的逆不成立：即LFSR的特征多项式为不可约多项式时，其输出序列不一定是m序列。反例
$f(x) = x^4 + x^3 + x^2 + x + 1$为$GF(2)$上的不可约多项式，这可由$x, x + 1, x^2 + x + 1$都不能整除$f(x)$得到。以$f(x)$为特征多项式的LFSR的输出序列可由：
$$a_k = a_{k - 1} \oplus a_{k - 2} \oplus a_{k - 3} \oplus a_{k - 4}(k \ge 4)$$
和给定的初始状态求出，设初始状态为0001，则输出序列为000110001100011...，周期为5，不是m序列。m序列产生的充要条件
定义：若n次不可约多项式p(x)的阶为$2^n - 1$，则称$p(x)$是n次本原多项式。
定理：设$\{ a_i \} \in G(p(x)), \{ a_i \}$为m序列的充要条件是$p(x$)为本原多项式。
对于任意的正整数n，至少存在一个n次本原多项式。所以对于任意的n级LFSR，至少存在一种连接方式使其输出序列为m序列。m序列示例
设$p(x) = x^4 + x + 1$，若LFSR以$p(x)$为特征多项式，则输出序列的递推关系为：
$$a_k = a_{k-1} \oplus a_{k - 4}(k \ge 4)$$
若初始状态为1001，则输出为：100100011110101100100011110101...
周期为$2^4 - 1 = 15$。
任意初始状态为1000，则输出为：- 1000011110101100010000111101011000...
- 100100011110101100100011110101...
m序列的伪随机性
m序列满足Golomb的3个随机性公设。
定理：$GF(2)$上的n长m序列$\{ a_i \}$具有如下性质：
- 在一个周期内，0、1出现的次数分别为$2^{n - 1} - 1$和$2^{n - 1}$。
- 在一个周期内，总游程数为$2^{n - 1}$；对$1 \le i \le n - 2$，长为i的游程有$2^{n - i - 1} - 1$个，且0、1游程各半；长为n-1的0游程一个，长为n的1游程一个。
- $\{ a_i \}$的自相关函数为：
$$ R(t) = \left \{ \begin{array}{c} 2^n - 1, & t=0 \\ -1, & 0 \le t \le 2^n -2 \end{array} \right . $$m序列的安全性
- 寻找m序列的递推关系式。
- 已知一段序列，如果知道其反馈多项式，就可以将其后的序列依次求出
- 已知序列如何获得相应的反馈多项式（线性递推式）：
- 解方程方法——已知序列$\{ a_i \}$是由n级线性移位寄存器产生的，并且知道$\{ a_i \}$的连续2n位，可用解线性方程组的方法得到反馈多项式
- 线性反馈移位寄存器综合解——Berlekamp-Massey算法
解方程方法
设序列$a = (01111000…)$是由4级线性移位寄存器所产生序列的连续8个信号，求该移位寄存器的线性递推式。
解：设该4级移位寄存器的线性递推式为：
$$a_n = c_1a_{n - 1} \oplus c_2a_{n - 2} \oplus c_3a_{n - 3} \oplus c_4a_{n - 4} (n \ge 4)$$
由于知道周期序列的连续8各信号，不妨设为开头的8个信号，即：
$$a_0a_1a_2a_3a_4a_5a_6a_7 = 01111000$$
当$n = 4$时，由递推式可得：$a_4 = c_1a_3 \oplus c_2a_2 \oplus c_3a_1 \oplus c_4a_0$
即：
$$ \begin{array}{c} c_1 \oplus c_2 \oplus c_3 = 1 \end{array} $$
同理可得：
$$ \begin{array}{c} c_1 \oplus c_2 \oplus c_3 \oplus c_4 = 0 \\ c_2 \oplus c_3 \oplus c_4 = 0 \\ c_3 \oplus c_4 = 0 \\ \end{array} $$
解方程组得：
$$c_1 = 0, c_2 = 0, c_3 = 1, c_4 = 1$$
故所求移位寄存器递推式为：$a_n = a_{n - 3} \oplus a_{n - 4}(n \ge 4)$
线性反馈移位寄存器综合解
根据密码学的需要，对线性反馈移位寄存器(LFSR)，主要考虑下面两个问题：
- 如何利用级数尽可能短的LFSR产生周期大、随机性能良好的序列。
- 这是从密钥生成角度考虑，用最小的代价产生尽可能好的、参与密码变换的序列。
- 当已知一个长为N序列$\underline{a}$时，如何构造一个级数尽可能小的LFSR来产生它。
- 这是从密码分析角度来考虑，要想用线性方法重构密钥序列所必须付出的最小代价。
线性综合解
设$\underline{a} = (a_0, a_1,..., a_{N - 1})$是$F_2$上的长度为N的序列，而$f(x) = c_0 + c_1x + c_2x^2 + ··· + c_lx^l$是$F_2$上的多项式，$c_0 = 1$。
如果序列中的元素满足递推关系：
$$a_k = c_1a_{k - 1} \oplus c_2a_{k - 2} \oplus ··· \oplus c_la_{k - l}, k = l, l + 1,..., N - 1$$
则称$$产生二元序列$\underline{a}$。其中$$表示以$f(x)$为特征多项式的$l$级线性移位寄存器。
如果$f(x)$是一个能产生$\underline{a}$并且级数最小的线性移位寄存器的特征多项式，$l$是该移位寄存器的级数，则称$$为序列$\underline{a}$的线性综合解。线性移位寄存器的综合问题
线性移位寄存器的综合问题可表述为：给定一个N长二元序列$\underline{a}$，如何求出产生这一序列的最小级数的线性移位寄存器，即最短的线性移存器。
- 这是从密码分析角度来考虑，要想用线性方法重构密钥序列所必须付出的最小代价。
- 特征多项式$f(x)$的次数$\le l$。因为产生$\underline{a}$且级数最小的线性移位寄存器可能是退化的，在这种情况下$f(x)$的次数$\le l$；并且此时$f(x)$中的$c_l = 0$，因此在特征多项式$f(x)$中仅要求$c_0 = 1$，但不要求$c_1 = 1$。
- 规定：0级线性移位寄存器是以$f(x) = 1$为特征多项式的线性移位寄存器，且$n$长$(n = 1, 2,…, N)$全零序列，仅由0级线性移位寄存器产生。事实上，以$f(x)=1$为反馈特征多项式的递归关系式是：$a_k = 0, k = 0, 1,..., n-1$。因此，这一规定是合理的。
- 给定一个N长二元序列$\underline{a}$，求能产生$\underline{a}$并且级数最小的线性移位寄存器，就是求$\underline{a}$的线性综合解。利用B-M算法可以有效的求出。
Berlekamp-Massey算法（B-M算法）
用归纳法求出一系列线性移位寄存器：
$$ \delta ^ 0 f_n(x) \le l_n, n = 1, 2,..., N$$
每一个$$都是产生序列$\underline{a}$的前n项的最短线性移位寄存器，在$$的基础上构造相应的$$，使得$$是产生给定序列前n+1项的最短移存器，则最后得到的$$就是产生给定N长二元序列a的最短的线性移位寄存器。B-M算法的具体步骤
任意给定一个N长序列$\underline{a} = (a_0, a_1,..., a_{N - 1}$，按n归纳定义：
$$ n=0, 1, 2,..., N - 1$$ - 取初始值：$f_0(x) = 1, l_0 = 0$
- 设$, ,..., (0 \le n \le N)$均已求得，且$l_0 \le l_1 \le ... \le l_n$，记$f_n(x) = c_0^{(n)} + c_1^{(n)}x +···+c_{l_n}^{(n)}x^{l_n}, c_0^{(n)} = 1,$再计算：$d_n = c_0^{(n)}a_n + c_1^{(n)}a_{n - 1} +···+c_{l_n}^{(n)}a_{n - l_n}$，称$d_n$为第n步差值。然后分两种情形讨论：
- 若$d_n = 0$，则令：$f_{n + 1}(x) = f_n(x), l_{n + 1} = l_n$
- 若$d_n = 1$，则需区分以下两种情形：
- 当：$l_0 = l_1 = ··· = l_n = 0$时，取：$f_{n + 1}(x) = 1 + x^{n + 1}, l_{n + 1} = n + 1$。
- 当有$m(0 \le m < n)，$使：$l_m < l_{m + 1} = l_{m + 2} = ··· = l_n$ ，便置：$f_{n + 1}(x) = f_n(x) + x^{n - m}f_m(x), l_{n + 1} = max\{ l_n, n + 1 - l_n \}$
最后得到的$$便是产生序列$\underline{a}$的最短线性移位寄存器。
