密码学02-流密码

2025-11-07 14:44:32

流密码

流密码的基本概念

一次一密

一次一密密码

一种理想的加密方案，叫做一次一密密码（one-time pad），由 Major Joseph Mauborgne和 AT&T 公司的 Gilbert Vernam 1917年发明的

明文：$x=x_0 x_1 x_2\dots$

密钥：$k=k_0 k_1 k_2 \dots$

密文：$y=y_0 y_1 y_2 \dots$

加密函数：$y_i=x_i+k_i(mod26)$

解密函数：$x_i=y_i-k_i(mod26)$

注：密钥为随机产生的，而且只使用一次

优点：

密钥随机产生，仅使用一次

无条件安全

加密和解密为加法运算，效率较高

缺点：

密钥长度至少与明文长度一样长，密钥共享困难，不太实用

流密码的定义

概况

流密码(stream cipher)是一种重要的密码体制

明文消息按字符或比特逐位加密

流密码也称为序列密码(Sequence Cipher)

流密码在20世纪50年代得到飞跃式发展

密钥流可以用移位寄存器电路来产生，也促进了线性和非线性移位寄存器发展

流密码主要是基于硬件实现

基本思想

流密码的基本思想：

利用密钥k产生一个密钥流$z=z_0z_1z_2…$，并使用如下规则对明文串$x=x_0x_{1}x_{2}…$加密：

\[y=y_0 y_1 y_2 \dots＝E_{z_0}(x0) E{z_1}(x1) E{z_2}(x2)\dots

密钥流

由密钥流发生器$f$ 产生：$z_i＝f(k,σ_i)$

$σ_i$ 是加密器中的记忆元件在时刻 $i$ 的状态

$f$ 是由 $k, σ_i$ 产生的函数

\[流密码：y_i = E_{z_i}(x_i)

\[分组密码：y = E_k(x)

内部记忆元件由一组移位寄存器构成

\[\sigma_i = (a_0,a_1,\dots,a_n)

同步流密码

内部记忆元件的状态 $σ_i$ 独立于明文字符的叫做同步流密码，否则叫做自同步流密码。

在同步流密码中，由于 $z_i=f(k,σ_i)$ 与明文字符无关，因而此时密文字符 $y_i=E_{z_i}(x_i)$ 也不依赖于此前的明文字符。因此，可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。

体制模型

二元加法流密码是目前最为常用的流密码体制，其加密变换可表示为yi=zi ㊉ xi。

需求

一次一密密码是加法流密码的原型

如果密钥用作滚动密钥流，则加法流密码就退化成一次一密密码。

密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：

极大的周期

良好的统计特性

抗线性分析

有限状态自动机

模型

有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成：

① 有限状态集$S=\{ s_i | i=1,2,\dots,l \}$

②有限输入字符集$A_1=\{ A^{(1)}_j| j=1,2,\dots,m\}$和有限输出字符集$A_2=\{A^{(2)}_k |k=1,2,\dots,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=\{s_1,s_2,s_3\}$， $A_1=\{A_1^{(1)},A_2^{(1)},A_3^{(1)}\}$， $A_2=\{A_1^{(2)},A_2^{(2)},A_3^{(2)}\}$，则该有限状态自动机的矩阵表示如下:

A1(1)

A2(1)

A3(1)

s 1

A1(2)

A3(2)

A2(2)

s 2

A2(2)

A1(2)

A3(2)

s 3

A3(2)

A2(2)

A1(2)

A1(1)

A2(1)

A3(1)

s 1

s 2

s 3

实例

若输入序列为：

$A^{(1)}_1,A^{(1)}_2,A^{(1)}_1,A^{(1)}_3,A^{(1)}_3,A^{(1)}_1$

初始状态为$s_1$，则得到状态序列：

$s_1,s_2,s_2,s_3,s_2,s_1,s_2$

输出字符序列：

$A^{(2)}_1,A^{(2)}_1,A^{(2)}_2,A^{(2)}_1,A^{(2)}_3,A^{(2)}_1$

密钥流生成器

产生器

密钥流产生器: 参数为$k$的有限状态自动机，

一个输出符号集 $Z$、一个状态集 $∑$、两个函数 $φ$ 和 $ψ$ 以及一个初始状态 $σ_0$ 组成。

状态转移函数 $φ:σ_i→σ_i+1$，将当前状态σi变为一个新状态$σ_i+1$，

输出函数$ψ:σ_i→z_i$，当前状态σi变为输出符号集中的一个元素 $z_i$。

作为有限状态自动机的密钥流生成器

设计的关键

关键在于：找出适当的状态转移函数 $φ$ 和输出函数 $ψ$ ，使得输出序列 $z$ 满足密钥流序列 $z$ 应满足的随机性条件，并且要求在设备上是节省的和容易实现的。

一般采用线性的 $φ$ 和非线性的 $ψ$，这样将能够进行深入的分析并可以得到好的生成器

分解

密钥流生成器可分成驱动部分和非线性组合部分

驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列

非线性组合部分要利用这些序列组合出满足要求的密钥流序列

常见的两种密钥流产生器

目前最为流行和实用的密钥流产生器，其驱动部分是一个或多个LFSR（Linear Feedback Shift Register，线性反馈移位寄存器）。

前者称为滤波生成器，或前馈生成器

后者称为非线性组合生成器

还有钟控生成器，缩减生成器，停走生成器等

二元序列的伪随机性

二元序列的相关概念

定义

GF（2）上的一个无限序列

\[\underset{\rightarrow}{a} = ( a_1,a_2,\dots,a_n,\dots)

称为二元序列，其中 $a_i \in GF(2)$。

• 周期：对于二元序列 $\underset{\rightarrow}{a}$，如果存在正整数$l$，使得对于一切正整数k都有

\[a_k = a_{k+l}

则称 $\underset{\rightarrow}{a}$ 是周期的。

满足上述条件的最小正整数称为 $\underset{\rightarrow}{a}$ 的周期,记为 $p(\underset{\rightarrow}{a})$

二元序列（Binary Sequence）是一种只包含两种可能值的序列，这两种值通常是0和1。二元序列在计算机科学、信息理论、密码学等领域有着广泛的应用。以下是有关二元序列的详细介绍：

特点

值的范围：二元序列中的每个元素都是0或1。这种二元性质使其在计算机中非常容易处理，因为计算机的基本数据单元就是二进制位（bit）。

长度：二元序列的长度可以是任意的有限正整数。例如，一个长度为5的二元序列可能是10101。

示例

基本示例：

0101101：一个长度为7的二元序列。

111000：一个长度为6的二元序列。

周期的性质

设 $GF(2)$ 上的一个无限序列 $\underset{\rightarrow}{a} = ( a_1,a_2,\dots,a_n,\dots)$ 是周期为 $p(\underset{\rightarrow}{a})$ 的二元序列，并设正整数 $l$ 对任何非负整数 $k$ 都有 $a_k=a_{k+1}$，则一定有

\[p(\underset{\rightarrow}{a})|l

• 证明：设 $l=qp(\underset{\rightarrow}{a})+r$ ，其中 $q,r$ 为正整数，且 \(0\le r

\[a_k = a_{k+l} \\

\Rightarrow a_k = a_{qp(a)+r+k}\\

a_k = a_{r+k}

又由于 \(0\le r

游程的定义

设 $a$ 是 $GF(2)$ 上周期为 $p(\underset{\rightarrow}{a})$ 的周期序列。将 $a$ 的一个周期

\[( a_1,a_2,\dots,a_{p(\underset{\rightarrow}{a})})

依次排列在一个圆周上使 $a_{p(\underset{\rightarrow}{a})}$ 与 $a_1$相连，把这个圆周上形如

\[\underset{都是1}{0\underbrace{11\dots1}0}\,或\, \underset{都是0}{1\underbrace{00\dots1}1}

的一连串两两相邻的项分别称为 $\underset{\rightarrow}{a}$ 的一个周期中一个 1 游程或一个 0 游程。而 1 游程中 1 的个数或 0 游程中 0 的个数称为游程的长度。

游程的例子

周期为15的二元序列

1100010011010111

011110为1的4游程10001为0的3游程

自相关函数

$GF(2)$上周期为T的序列$\{a_i\}$的自相关函数定义为

\[R(t)=\sum\limits_k^T(-1)^{a_k}(-1)^{a_{k+1}},0\le t

当$t=0$时， $R(t)=T$；当$t≠0$时，称$R(t)$为异相自相关函数。

二元序列的自相关函数（Autocorrelation Function）用于衡量序列与其自身的相似度。自相关函数是信号处理中一个重要的工具，它可以帮助分析序列的周期性和重复性。

定义

对于一个长度为 $N$ 的二元序列$\{x_n\}$，其自相关函数 $R_k$ 定义为：

\[R_k = \frac{1}{N} \sum_{n=0}^{N-1} x_n \cdot x_{(n+k) \mod > N}

这里：

$R_k$ 是自相关函数在滞后 $k$ 下的值。

$x_n$ 是序列的第 $n$ 个元素。

$x_{(n+k)\mod N}$ 是在滞后 $k$ 下的序列元素，取模操作确保序列在末尾后循环回到开始。

示例：

假设有一个长度为 $N = 4$ 的二元序列 $\{x_n\} = \{1, 0, 1, 0\}$。我们可以计算其自相关函数 $R_k$ 如下：

滞后 $k = 0$:

\[R_0=\frac{1}{4}(x0⋅x0+x1⋅x1+x2⋅x2+x3⋅x3)\\

=\frac{1}{4}(1⋅1+0⋅0+1⋅1+0⋅0)\\

=\frac{2}{4}=0.5

滞后 $k=1$

\[R_1=\frac{1}{4}(x0⋅x1+x1⋅x2+x2⋅x3+x3⋅x0)\\

=\frac{1}{4}(1⋅0+0⋅1+1⋅0+0⋅1)\\

=\frac{0}{4}=0

滞后 $k=2$

\[R_2=\frac{1}{4}(x0⋅x2+x1⋅x3+x2⋅x0+x3⋅x1)\\

=\frac{1}{4}(1⋅1+0⋅0+1⋅1+0⋅0)\\

=\frac{2}{4}=0.5

滞后$k=3$

\[R_3=\frac{1}{4}(x0⋅x3+x1⋅x0+x2⋅x1+x3⋅x2)\\

=\frac{1}{4}(1⋅0+0⋅1+1⋅0+0⋅1)\\

=\frac{0}{4}=0

因此，该序列的自相关函数为：

\[R=[0.5,0,0.5,0]

两种自相关函数的区别

1. 第一种自相关函数

公式：\(R(t)=\sum\limits_k^T(-1)^{a_k}(-1)^{a_{k+1}},0\le t

解释：

这是一个特定形式的自相关函数计算公式，其中 $a_k$ 是二元序列中的元素。

公式中，$(-1)^{a_k}$ 将二元序列中的0和1转换为-1和1，因此公式可以看作是计算了二元序列经过这种转换后的自相关。

$(-1)^{a_k}$ 和$(-1)^{a_{k+1}}$ 之间的乘积用于表示序列在不同位置上的相关性。这种形式的自相关函数常用于检测序列的周期性和模式。

2. 经典自相关函数

公式：$R_k = \frac{1}{N} \sum_{n=0}^{N-1} x_n \cdot x_{(n+k) \mod > N}$

解释：

这是经典的自相关函数公式，适用于任何二元序列或一般的序列。

$x_n$ 是序列在位置 $n$ 上的值，$x_{(n+k) \mod N}$ 是在滞后 $k$ 后的值。

这个公式计算了序列在滞后 $k$ 下的自相关程度，结果为滞后 $k$ 时的相关性，通常用于分析信号的周期性和相似度。

主要区别

形式和转换：

第一种公式通过 $(-1)^{a_k}$ 的转换将二元序列中的0和1映射为-1和1，这使得它更适用于特定的分析，例如检测周期性和相位关系。

经典自相关函数公式直接使用二元序列中的0和1进行计算，不进行转换。

计算方式：

第一种公式是通过对序列的转换后进行计算，结果通常用于更具体的信号处理或序列分析。

经典自相关函数公式更通用，用于计算序列的自相关值，结果通常用于了解序列的整体相关性和周期性。

适用范围：

第一种公式通常用于特殊的二元序列分析，特别是在信号处理中或特定的数学模型中。

经典自相关函数公式适用于一般的自相关分析，包括二元序列和其他类型的序列。

伪随机序列

Golomb伪随机公设

3个随机性公设：

在序列的一个周期内， 0与1的个数相差至多为1。

说明{ai}中0与1出现的概率基本上相同

在序列的一个周期内，长为i的游程占游程总数的1/2i (i=1,2,…)，且在等长的游程中0的游程个数和1的游程个数相等。

说明0与1在序列中每一位置上出现的概率相同

异相自相关函数是一个常数。

意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息

伪随机序列的定义

设 $\underset{\rightarrow}{a} = ( a_1,a_2,\dots,a_n,\dots)$ 是 GF（2）上一个周期等于 $p(\underset{\rightarrow}{a})$ 的周期序列。

如果对于一切 $t\not\equiv{0(mod{p(\underset{\rightarrow}{a})})}$，有

\[R(t)=-1

则称序列 $\underset{\rightarrow}{a} = ( a_1,a_2,\dots,a_n,\dots)$ 为伪随机序列。

可以证明上述定义满足Golomb三个伪随机公设，详情参考万哲先著。代数和编码（第三版）。高等教育出版社， 2007.

伪随机序列的例子

周期为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(a1,a2,…,an)$组成，如下图所示。

反馈移位寄存器的状态

在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于$GF(2)$上的一个n维向量，共有 $2^n$种可能的状态。每一时刻的状态可用 $n$ 维向量

\[(a_1,a_2,\dots,a_n)

反馈函数

初始状态由用户确定。

反馈函数$f(a_1,a_2,\dots,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, \dots, a_n) = c_1a_n\oplus c_2a_{n-1}\oplus\dots \oplus c_na_1

LFSR的反馈函数

输出序列$\{a_t\}$满足：

\[f(a_1,a_2,\dots,a_n) = c_1a_n\oplus c_2a_{n-1}\oplus\dots \oplus c_na_1 \\

a_{n+1}=c_1a_n\oplus c_2a_{n-1}\oplus\dots\oplus c_na_1\\

a_{n+2}=c_1a_{n+1}\oplus c_2a_{n}\oplus\dots\oplus c_na_2\\

\ldots\ldots\\

a_{n+t}=c_1a_{n+t-1}\oplus c_2a_{n+t-2}\oplus\dots\oplus c_na_t,t=1,2,\dots

线性反馈移位寄存器：实现简单、速度快、有较为成熟的理论，成为构造密钥流生成器的最重要的部件之一。

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,\dots$

求解如：

$a_6 = a_{5+1} = a_{1+3}\oplus a_1 = a_4\oplus a_1 = 1 \oplus 1 = 0$

可求出输出序列为：

$\underbrace{10011}_{初始序列}\,01001000010101110110001111100110…$

周期31。

密钥流的周期

给定密钥流$\{a_i\}=a_1,a_2,a_3,\dots a_n,\dots$，如果存在整数 $r$，使得对于任意 $a_i$ ，都有 $a_{i+r}=a_i$，则称 $r$ 为该密钥流的一个周期，称满足 $a_{i+r} = a_i$ 的最小正整数为该密钥流的最小周期或简称周期。

LFSR的性质

总是假定$c_1,c_2,…,c_n$中至少有一个不为0，否则$f(a1,a2,\dots,an)\equiv 0$。总是假定$c_n=1$。

LFSR输出序列的性质：完全由其反馈函数决定。

n级LFSR状态数：最多有$2^n$个

n级LFSR的状态周期： $\le2^{n-1}$

输出序列的周期=状态周期, $\leq2^{n-1}$

选择合适的反馈函数可使序列的周期达到最大值 $2^{n-1}$ ，周期达到最大值的序列称为$m$。

m-序列

线性反馈移位寄存器的多项式表示

定义2.1 设$n$级线性移位寄存器的输出序列满足递推关系：

\[a_{n+k}=c_1a_{n+k-1}\oplus c_2a_{n+k-2}\oplus\dots\oplus c_na_{k}

用延迟算子 $D(Da_k=a_{k-1})$ 作为未定元，给出的反馈多项式为：

\[p(D)=1+c_1D+\dots +c_{n-1}D^{n-1}+c_nD^{n}

这种递推关系可用一个一元高次多项式：

\[p(x)=1+c_1x+\dots +c_{n-1}x^{n-1}+c_nx^{n}

表示，称这个多项式为LFSR的特征多项式。

关于特征多项式的解释

\[a_{n+k}=c_1a_{n+k-1}\oplus c_2a_{n+k-2}\oplus\dots\oplus c_na_{k} \\

由\,a_{n+k}\oplus a_{n+k}=0 有 \\

\Leftrightarrow a_{n+k}\oplus c_1a_{n+k-1}\oplus c_2a_{n+k-2}\oplus\dots\oplus c_na_{k} = 0

$D(a_k)=a_{k-1}$，用 $p(D)=1+c_1D+\dots+c_bD^n$ 作用于 $a_{n+k}$ 后恰好就是上式左侧，即：

\[p(D)(a_{n+k})=(1+c_1D+\dots+c_nD^n)\\

= a_{n+k}+c_1D(a_{n+k})+\dots +c_nD^n(a_{n+k})\\

= a_{n+k}+c_1a_{n+k-1}+c_2a_{n+k-2}+\dots +c_na_k

生成函数

定义2.2 给定序列{ai}，幂级数 :

\[A(x)=\sum^{\infty}_{i=1}a_ix^{i-1}

称为该序列的生成函数。

生成函数的性质

定理2.1 设 $p(x)=1+c_1x+ \dots +c_{n-1}x^{n-1}+c_n x_n$ 是$GF(2)$上的多项式， $G(p(x))$中任一序列${a_i}$的生成函数$A(x)$满足：

\[A(x)=\frac{\phi(x)}{p(x)}\\

其中\,\phi(x)=\sum^n_{i=1}(c_{n-i}x^{n-1}\sum^i_{j=1}a_jx^{j-1})

一些定理和定义

根据初始状态的不同，由递推关系$(*)$生成的非恒零的序列有$2^n-1$个，记这$2^n-1$个非零序列的全体为$G(p(x))$。

定理2.2 $p(x)|q(x)$的充要条件是$G(p(x))\subset G(q(x))$。

——该定理说明：可用$n$级LFSR产生的序列，也可用级数更多的LFSR来产生。

定义2.3 设$p(x)$是$GF(2)$上的多项式，使$p(x)|(x^p-1)$成立的最小正整数$p$称为$p(x)$的周期或阶。

定理2.3 若序列${ai}$的特征多项式$p(x)$定义在$GF(2)$上， $p$是$p(x)$的周期，则${ai}$的周期$r|p$。

—— 该定理说明： $n$级LFSR输出序列的周期 $r$，不依赖于初始条件，而依赖于特征多项式 $p(x)$。

m-序列产生的条件

不可约多项式

定理2.4 设 $p(x)$ 是 $n$ 次不可约多项式，周期为$m$，序列${a_i}\in G(p(x))$，则 ${a_i}$ 的周期为 $m$。

m-序列产生的必要条件

定理2.5 $n$ 级LFSR产生的序列有最大周期$2^n-1$的必要条件是其特征多项式为不可约的。

该定理的逆不成立，即LFSR的特征多项式为不可约多项式时，其输出序列不一定是m序列。

定理2.5 的反例

例2.4 $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≥4)

和给定的初始状态求出，设初始状态为0001，则输出序列为000110001100011…，周期为5，不是$m$序列。

m-序列产生的充要条件

定义2.4 若$n$次不可约多项式$p(x)$的阶为$2^n-1$，则称$p(x)$是$n$次本原多项式。

定理2.6 设${ai}\in G(p(x))$， ${ai}$为$m$序列的充要条件是$p(x)$为本原多项式。

m-序列举例

例2.5 设$p(x)=x^4+x+1$，若LFSR以$p(x)$为特征多项式，则输出序列的递推关系为

\[a_k=a_{k-1}\oplus a_{k-4}(k\ge 4)

若初始状态为1001，则输出为

\[\underline{100100011110101}100100011110101\dots

周期为$2^4-1=15$。

若初始状态为1000，则输出为

\[\underline{100011110101100}100011110101\dots\\

100\underline{100011110101100}100011110101\dots

m-序列的伪随机性

回顾：

游程: 设${a_i}=(a_1a_2a_3…)$为二元序列，例如 00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程。

自相关函数： $GF(2)$上周期为 $T$ 的序列 ${a_i}$ 的自相关函数定义为

\[ R(t)=\sum^T_{k=1}(-1)^a_k(-1)^{a_{k+t}},0\leq t\leq T-1

当$t=0$时， $R(t)=T$；当$t≠0$时，称$R(t)$为异相自相关函数。

Golomb伪随机公设

3个随机性公设：

在序列的一个周期内， 0与1的个数相差至多为1。

说明{ai}中0与1出现的概率基本上相同

在序列的一个周期内，长为$i$的游程占游程总数的$\frac{1}{2^i}(i=1,2\dots)$，且在等长的游程中0的游程个数和1的游程个数相等。

说明0与1在序列中每一位置上出现的概率相同

异相自相关函数是一个常数

意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息

伪随机序列的定义

设 $\underrightarrow{a}=(a_1,a_2,\dots,a_{p(\underrightarrow{a})},\dots)$ 是 GF（2）上一个周期等于 $p(\underrightarrow{a})$的周期序列。如果对于一切$t\not\equiv0(mod\,p(\underrightarrow{a}))$，有

\[R(t)=-1

则称序列 $\underrightarrow{a}=(a_1,a_2,\dots,a_{p(\underrightarrow{a})},\dots)$ 为伪随机序列。

m-序列的伪随机性

m序列满足Golomb的3个随机性公设。

定理2.7 $GF2)$上的$n$长$m$序列${a_i}$具有如下性质：

在一个周期内， 0、 1出现的次数分别为$2^{n-1}-1$和$2^{n-1}$。

在一个周期内，总游程数为$2^{n-1}$；对$1≤i≤n-2$，长为$i$的游程有$2^{n-i}-1$个，且0、1游程各半；长为$n-1$的0游程一个，长为n的1游程一个。

{ai}的自相关函数为 :

\[R(t)=

\begin{cases}

2^n-1,&t =0\\

-1,&0

\end{cases}

证明1：

在$n$长$m$序列的一个周期内，除了全0状态外，每个$n$长状态（共$2^n- 1$个）都恰好出现一次。

LFSR的输出为每个状态的$a_1$ ，因此输出为1的状态必然是$（**…*1）$的形式，而$m$序列这类状态共有$2^{n-1}$个，所以输出中1的个数为$2^{n-1}$个。

输出为0的状态必然是$（**…*0）$的形式，而$m$序列这类状态共有$2^{n-1}-1$个（因为不能有全零状态），所以输出中0的个数为$2^{n-1}-1$个。

证明2：

对n=1,2，易证结论成立。

对$n>2$，当$1≤i≤n-2$时， $n$长$m$序列的一个周期内，长为i的0游程数目等于序列中如下形式的状态数目： $100…01… …$，其中$n-i-2$个可任取0或1。这种状态共有$2^{n-i-2}$个。同理可得长为i的1游程数目也等于$2^{n-i-2}$，所以长为$i$的游程总数为$2^{n-i-1}$。

由于寄存器中不会出现全0状态，所以不会出现0的$n$游程，但必有一个1的$n$游程，而且1的游程不会更大，因为若出现1的$n+1$游程，就必然有两个相邻的全1状态，但这是不可能的。这就证明了1的$n$游程必然出现在如下的串中：

\[0\underbrace{11\dots1}_{n个1}0

当这n+2位通过移位寄存器时，便依次产生以下状态：

\[0\,\underbrace{11\dots1}_{n-1个1}\quad \underbrace{11\dots1}_{n个1}\quad \underbrace{11\dots1}_{n-1个1}\,0

由于 $0\,\underbrace{11\dots1}_{n-1个1}\quad \underbrace{11\dots1}_{n-1个1}\,0$ 两个状态只能各出现一次，所以不会再有1的n-1游程。

0的n-1游程只有一个

\[1\,\underbrace{00\dots0}_{n-1个0}\,1

于是在一个周期内，总游程数为 :

\[1+1+\sum^{n-1}_{i=1}2^{n-i-1}=2^{n-1}

证明3：

${ai}$是周期为$2^n-1$的$m$序列，对于任一正整数\(t(0

\[a_{h+n}=c_1a_{h+n-1}\oplus c_2a_{h+n-2}\oplus\dots\oplus c_na_h\\

\[故：a_{h+n+t}=c_1a_{h+n+t-1}\oplus c_2a_{h+n+t-2}\oplus\dots\oplus c_na_{h+t}

\[有：a_{h+n}\oplus a_{h+n+t}=c_1(a_{h+n-1}\oplus a_{h+n+t-1})\oplus c_2(a_{h+n-2}\oplus a_{h+n+t-2})\oplus c_n(a_n\oplus a_{h+t})\\

令$b_j=a_j\oplus a_{j+t}$，序列${b_j}$满足：$b_{h+n}=c_1b_{h+n-1}\oplus c_2b_{h+n-2}\oplus \dots \oplus c_nb_n$

因为对应同样的特征多项式，所以也是序列。

所以

\[R(t)=\sum^T_{k=1}(-1)^{a_k}(-1)^{a_{k+t}}=\sum^T_{k=1}(-1)^{b_k}=2^{n-1}-1-2^{n-1}=-1

m-序列的安全性

寻找m序列的递推关系式。

已知一段序列，如果知道其反馈多项式，就可以将其后的序列依次求出

已知序列能否获得相应的反馈多项式(或线性递推式)呢？

解方程方法——已知序列 ${ai}$ 是由 $n$ 级线性移存器产生的，并且知道 ${ai}$ 的连续 $2n$ 位，可用解线性方程组的方法得到反馈多项式。

线性反馈移位寄存器综合解——Berlekamp-Massey算法

解方程方法

例1 设序列 $a = (01111000…)$ 是由4级线性移存器所产生序列的连续8个信号，求该移存器的线性递推式。

解：设该4级移存器的线性递推式为：

\[a_{n}=c_{1}a_{n-1}\oplus c_{2}a_{n-2}\oplus c_{3}a_{n-3}\oplus c_{4}a_{n-4}(n\geq_{4})

由于知道周期序列的连续8个信号，不妨设为开头的8个信号，即

\[a_{0}a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}a_{7}=01111000

当 $n=4$ 时，由递归式可得：$a_{4}=c_{1}a_{3}\oplus c_{2}a_{2}\oplus c_{3}a_{1}\oplus c_{4}a_{0}$

\[\begin{aligned}

即：c_{1}\oplus c_{2}\oplus c_{3}&=1\\

同理可得：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\\

解方程可得：c_{1}=0,c_{2}=0,c_{3}=1,c_{4}=1

\end{aligned}

故所求移存器递推式为：$a_{n}=a_{n-3}\oplus a_{n-4}(n\geq_{4})$

例2

\[\begin{aligned}

设敌手得到密文串&: 101101011110010\\

和相应的明文串&: 011001111111001\\

因此，可得相应的密钥流&: 110100100001011\\

\end{aligned}

进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密钥流中的前10个比特建立如下方程

\[\begin{pmatrix}

a_{6} & a_{7} & a_{8} & a_{9} & a_{10}

\end{pmatrix}

\begin{pmatrix}

c_{5} & c_{4} & c_{3} & c_{2} & c_{1}

\end{pmatrix}

\begin{pmatrix}

a_{1} & a_{2} & a_{3} & a_{4} & a_{5}\\

a_{2} & a_{3} & a_{4} & a_{5} & a_{6} \\

a_{3} & a_{4} & a_{5} & a_{6} & a_{7} \\

a_{4} & aa_{5} & a_{6} & a_{7} & a_{8} \\

a_{5} & a_{6} & a_{7} & a_{8} & a_{9}

\end{pmatrix}

即

\[\begin{pmatrix}

0 & 1 & 0 & 0 & 0

\end{pmatrix}=

\begin{pmatrix}

c_{5} & c_{4} & c_{3} & c_{2} & c_{1}

\end{pmatrix}

\begin{pmatrix}

1 & 1 & 0 & 1 & 0 \\

1 & 0 & 1 & 0 & 0 \\

0 & 1 & 0 & 0 & 1 \\

1 & 0 & 0 & 1 & 0 \\

0 & 0 & 1 & 0 & 0

\end{pmatrix}

\[\begin{pmatrix}

1 & 1 & 0 & 1 & 0 \\

1 & 0 & 1 & 0 & 0 \\

0 & 1 & 0 & 0 & 1 \\

1 & 0 & 0 & 1 & 0 \\

0 & 0 & 1 & 0 & 0

\end{pmatrix}^{-1}=

\begin{pmatrix}

0 & 1 & 0 & 0 & 1 \\

1 & 0 & 0 & 1 & 0 \\

0 & 0 & 0 & 0 & 1 \\

0 & 1 & 0 & 1 & 1 \\

1 & 0 & 1 & 1 & 0

\end{pmatrix}

从而得到

\[\begin{pmatrix}

c_{5} & c_{4} & c_{3} & c_{2} & c_{1}

\end{pmatrix}=

\begin{pmatrix}

0 & 1 & 0 & 0 & 0

\end{pmatrix}

\begin{pmatrix}

0 & 1 & 0 & 0 & 1 \\

1 & 0 & 0 & 1 & 0 \\

0 & 0 & 0 & 0 & 1 \\

0 & 1 & 0 & 1 & 1 \\

1 & 0 & 1 & 1 & 0

\end{pmatrix}

所以

\[\begin{pmatrix}

c_{5} & c_{4} & c_{3} & c_{2} & c_{1}

\end{pmatrix}=

\begin{pmatrix}

1 & 0 & 0 & 1 & 0

\end{pmatrix}

密钥流的递推关系为

\[a_{i+5}=c_{5}a_{i}\oplus c_{2}a_{i+3}=a_{i}\oplus a_{i+3}

密钥流的递推关系为

\[a_{i+5}=c_{5}a_{i}\oplus c_{2}a_{i+3}=a_{i}\oplus a_{i+3}

线性反馈移位寄存器综合

根据密码学的需要，对线性反馈移位寄存器(LFSR)主要考虑下面两个问题：

如何利用级数尽可能短的LFSR产生周期大、随机性能良好的序列。

这是从密钥生成角度考虑，用最小的代价产生尽可能好的、参与密码变换的序列。

当已知一个长为N序列 $\underline{a}$ 时，如何构造一个级数尽可能小的LFSR来产生它。

这是从密码分析角度来考虑，要想用线性方法重构密钥序列所必须付出的最小代价。

线性综合解

设 $\underline{ a }=(a_{0},a_{1},\dots a_{N-1})$ 是 $F_{2}$ 上的长度为N的序列，而 $f(x)=c_{0}+c_{1}x+c_{2}x^{2}+\dots c_{l}x^l$ 是 $F_{2}$ 上的多项式，$c_{0}=1$

如果序列中的元素满足递推关系：

\[ak=c_{1}a_{k-1}\oplus c_{2}a_{k-2}\oplus\dots \oplus c_{l}a_{k-l},k=1,l+1,\dots,N-1

则称 $\langle{f(x),l}\rangle$ 产生二元序列 $\underline{a}$ 。其中 $\langle{f(x),l}\rangle$ 表示以 $f(x)$ 为特征多项式的 $l$ 级线性移位寄存器。

如果 $f(x)$ 是一个能产生a并且级数最小的线性移位寄存器的特征多项式， $l$ 是该移存器的级数，则称 $\langle{f(x),l}\rangle$ 为序列 $\underline{a}$ 的线性综合解。

线性移位寄存器的综合问题

线性移位寄存器的综合问题可表述为：给定一个N长二元序列 $\underline{a}$，如何求出产生这一序列的最小级数的线性移位寄存器，即最短的线性移存器。

特征多项式 $f(x)$ 的次数小于 $l$。因为产生 $\underline{a}$ 且级数最小的线性移位寄存器可能是退化的，在这种情况下 $f(x)$ 的次数小于 $l$；并且此时 $f(x)$ 中的$c_{l}=0$，因此在特征多项式 $f(x)$ 中仅要求$c_{0}=1$，但不要求$c_{l}=1$。

规定：0级线性移位寄存器是以 $f(x)=1$ 为特征多项式的线性移位寄存器，且 $n$ 长 $(n=1, 2, …, N)$ 全零序列，仅由0级线性移位寄存器产生。事实上，以f(x)=1为反馈特征多项式的递归关系式是： $a_k=0， k=0, 1, \dots, n-1$. 因此，这一规定是合理的。

给定一个N长二元序列 $\underline{a}$，求能产生 $\underline{a}$ 并且级数最小的线性移位寄存器，就是求 $\underline{a}$ 的线性综合解。利用 $B-M$ 算法可以有效的求出。

Berlekamp-Massey算法（B-M算法）

用归纳法求出一系列线性移位寄存器：

\[\langle{f(x),l}\rangle\quad\delta^0f_{n}(x)\leq l_{n},\quad n=1,2,\dots ,N

每一个 $\langle{f_{n}(x),l_{n}}\rangle$ 都是产生序列 $\underline{a}$ 的前n项的最短线性一位寄存器，在 $\langle{f_{n}(x),l_{n}}\rangle$ 的基础上构造相应的 $\langle{f_{n+1}(x),l_{n+1}}\rangle$ ，使得是 $\langle{f_{n+1}(x),l_{n+1}}\rangle$

产生给定序列前n+1项的最短移存器，则最后普得到的 $\langle{f_{N}(x),l_{N}}\rangle$ 就是产生给定N长二院序列 $\underline{a}$ 的最短的线性移位寄存器。

任意给定一个N长序列 $\underline{a}=(a_{0},a_{1},\dots,a_{N-1})$ ，按 $n$ 归纳定义

\[\langle{f_{n}(x),l_{n}}\rangle\qquad n=0,1,2,\dots,N-1

取初始值： $f_0(x)=1, l_{0} = 0$

设 $\langle{f_{0}(x),l_{0}}\rangle,\langle{f_{1}(x),l_{1}}\rangle,\dots,\langle{f_{n}(x),l_{n}}\rangle(0\geq{N})$ 均以求得，且 $l_{0}\geq,l_{1}\geq\dots\geq l_{n}$

记：$f_{n}(x)=c_{0}^{(n)}+c_{1}^{(n)}x+\dots+c_{l}^{(n)}x^{l_{n}}=1,$再计算：

\[d_{n}=c_{0}

非线性序列1

非线性序列

密钥流生成器可分解为驱动子系统和非线性组合子系统，如图所示

![[非线性序列1.png]]

驱动子系统常用一个或多个线性反馈移位寄存器来实现

非线性组合子系统用非线性组合函数F来实现

为了使密钥流生成器输出的二元序列尽可能复杂，也应保证其周期尽可能大、线性复杂度和不可预测性尽可能高

Geffe序列生成器

Geffe序列生成器由3个LFSR组成，其中LFSR2作为控制生成器使用，如图所示

![[Geffe序列生成器.png]]

当LFSR2输出1时， LFSR2与LFSR1相连接

当LFSR2输出0时， LFSR2与LFSR3相连接

![[Geffe序列生成器（续）.png]]

Geffe序列的周期实现了极大化，且0与1之间的分布大体上是平衡的。

若设 $LFSRi$ 的输出序列为 $a_{k}^{(i)} (i=1,2,3)$，则输出序列 $\{b_k\}$ 可以表示为

\[b_{k}=a_{k}^{(1)}a_{k}^{(2)}+a_{k}^{(3)}\overline{a_{k}^{(2)}}

=a_{k}^{(1)}a_{k}^{(2)}+a_{k}^{(3)}{a_{k}^{(2)}}+a_{k}^{(3)}

设LFSRi的特征多项式分别为ni次本原多项式，且ni 两两互素

则Geffe序列的周期$=\prod^3_{{i=1}}(i^{n_{i}}-1)$

线性复杂度 = $(n_{1}+n_{3})n_{2}+n_{3}$

J-K触发器

J-K触发器如图所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即

\[c_{k}=\overline{ (x_{1}+x_{2}) }c_{k-1}+x_{1}

![[J-K触发器.png]]

其中x1和x2分别是J和K端的输入。由此可得J-K触发器的真值表，如下表所示

$J$

$K$

$c_{k}$

$0$

$c_{k-1}$

$0$

$1$

$0$

$1$

$0$

$1$

$\overline{c_{k-1}}$

J-K触发器真值表

利用J-K触发器的非线性序列生成器

![[利用J-K触发器的非线性序列生成器.png]]

\[{\large c_{k}=\overline{(a_{k}+b_{k})}c_{k-1}+a_{k}=(a_{k}+b_{k}+1)c_{k-1}+a_{k}}

当$m$与$n$互素且$a_{0}+b_{0}=1$时，序列$\{c_k\}$的周期为$(2^m-1)(2^n-1)$。

利用J-K触发器的非线性序列生成器的实例

例令$m=2,n=3$，两个驱动 $m$ 序列分别为

\[\{a_{k}\}=0,1,1

和

\[\{b_{k}\}=1,0,0,1,0,1,1,\dots

于是，输出序列$\{ck\}$是$0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,…,$

其周期为$(2^2-1)(2^3-1)=21$。

弱点

由$c_{k}=(a_{k}+b_{k}+1)c_{k-1}+a_{k}$可得

\[c_{k}=

\begin{cases}

a_{k}, & k-1=0 \\

\overline{b_{k}}, & c_{k-1}=1

\end{cases}

如果知道 $\{c_k\}$ 中相邻位的值$c_{k-1}$和 ${c_k}$，就可以推断出 $a_k$ 和 $b_k$ 中的一个。而一旦知道足够多的这类信息，就可通过密码分析的方法得到序列$\{a_k\}$和$\{b_k\}$。

为了克服上述缺点， Pless提出了由多个J-K触发器序列驱动的多路复合序列方案，称为Pless生成器。

Pless生成器

Pless生成器由8个LFSR、 4个J-K触发器和1个循环计数器构成，由循环计数器进行选通控制，如图所示。

![[Pless生成器.png]]

非线性序列2

钟控序列生成器

钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图所示，一个最简单钟控序列生成器

![[钟控序列生成器模型.png]]

假设LFSR1和LFSR2分别输出序列 $\{a_k\}$ 和 $\{bk\}$ ，其周期分别为p1和p2。

当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位。

当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR2。因此LFSR2重复输出前一位。

钟控序列的周期

假设LFSR1和LFSR2分别输出序列 $\{a_k\}$ 和 ${b_k}$ ，其周期分别为 $p_{1}$ 和 $p_{2}$ 。假设钟控序列 ${c_{k}}$ 的周期为p，可得如下关系：

\[p=\frac{p_{1}p_{2}}{gcd(w_{1},p_{2})},其中w_{1}=\sum^{p_{1}-1}_{i=0}a_{i}

$c_{k}$ 的一个周期至少是LFSR1和LFSR2同时回到初始状态的时刻

显然当运行$p_{1}× p_{2}$个节拍后两个LFSR必然回到初态，因此周期至多是 $p_{1}× p_{2}$

LFSR1运行一个周期， LFSR2运行$w_{1}＝d{t}$ 拍，$d＝gcd(w1,p2)$

则LFSR1运行 $\frac{p_{2}}{d}$ 个周期后， LFSR2刚好运行 $dt\times \frac{p_{2}}{d}=tp_{2}$ 拍，即$t$个周期，于是两个LFSR都回到初态，这时运行了 $\frac{p_{2}}{d}\times p_{1}$个节拍

若 $a_{k}$和 $b_{k}$ 的极小特征多项式分别为GF(2)上的m和n次本原多项式 $f_1(x)$ 和 $f_2(x)$，且$m|n$。

则 $p_{1}=2^m-1,p_{2}=2^n-1$

而 $w_{1}$ 为 ${a_{k}}$一个周期内1的个数，因此 $w_{1}=2^{m-1}$

故 $gcd(w_{1},p_{2})$，所以 $p=p_{1}p_{2}=(2^m-1)(2^n-1)$。

钟控序列的线性复杂度

可推导出{ck}的线性复杂度为 $n(2^m-1)$，极小特征多项式为 $f_{2}(x^{2^m-1})$

其对应的LFSR2的抽头每隔周期$p1＝2^m－1$一个，这样，参与运算的每个抽头对应的状态的节奏相同，从而相当于对LFSR2序列进行每 $2^m－1$ 拍的抽样序列(不计由于LFSR1的0游程而产生的重复)，这个序列只是LFSR2的平移和按照LFSR1中的0游程进行迟延，而抽头应该与LFSR2的节奏一致，所以其极小多项式和线性复杂度如上

在这个设置中，LFSR2 的抽头每隔 $2^m-1$ 个周期被选中。这意味着：

LFSR2的抽头位置每隔 $2^m-1$ 个时钟周期参与运算。这种机制相当于通过 LFSR1 来对 LFSR2 的输出序列进行采样。因为每个抽头位按照这个周期来工作，LFSR2 序列的抽样就遵循了 LFSR1 的周期。

钟控序列的例子

设LFSR1为3级m序列生成器，其特征多项式为$f_1(x)=1+x+x3$。设初态为 $a_{0}=a_{1}=a_{2}=1$ ，于是输出序列为$\{a_k\}=1,1,1,0,1,0,0,\dots$

又设LFSR2为3级m序列生成器，且记其状态向量为${\sigma_{k}}$，则在上图的构造下 $\sigma_{k}$ 的变化情况如下：

\[\begin{array}{l}

\sigma_{0}, & \sigma_{1}, & \sigma_{2}, & \sigma_{3}, & \sigma_{3}, & \sigma_{4}, & \sigma_{4}, & \sigma_{4}, \\

\sigma_{5}, & \sigma_{6}, & \sigma_{0}, & \sigma_{0}, & \sigma_{1}, & \sigma_{1}, & \sigma_{1}, \\

\sigma_{2}, & \sigma_{3}, & \sigma_{4}, & \sigma_{4}, & \sigma_{5}, & \sigma_{5}, & \sigma_{5}, \\

\sigma_{6}, & \sigma_{0}, & \sigma_{1}, & \sigma_{1}, & \sigma_{2}, & \sigma_{2}, & \sigma_{2}, \\\dots

\end{array}

$\{c_{k}\}$ 的周期为(23-1)2=49，在它的一个周期内，每个 $\sigma_{k}$ 恰好出现7次

设 $f_2(x)=1+x2+x3$ 为LFSR2的特征多项式，且初态为 $b_{0}=b_{1}=b_{2}=1$，则$\{b_k\}=1,1,1,0,0,1,0,1,1,1…$

![[钟控序列的例子.png]]

$\{ck\}$的极小特征多项式为 $1+x^{14}+x^{21}$，其线性复杂度为 $3·(2^3-1)=21$，下图是其线性等价生成器。

![[钟控序列的例子线性等价生成器。.png]]

A5流密码算法

A5流密码算法的基本用法

A5流密码算法用于蜂窝式移动电话系统语音和数字加密。

A5/1算法用于用户的手机到基站之间的通信加密，通信内容到基站后先解密变成明文，然后再进行基站到基站之间、以及基站到用户手机之间的信息加密，完成通信内容在通信过程的加密保护

![[A5_1流密码算法通信模式.png]]

应用环节

只需考察用户A到基站1之间通信内容的加解密，中间消息的传送由基站到基站之间的加密完成，而接收方用户B对消息的加解密与用户A到基站1之间的通信完全类似，只不过是用户B先解密消息。

基本密钥$K_{A1}$

基本密钥KA1：预置在SIM卡中，与基站1共享。

生存期：一旦植入SIM卡将不再改变。

用途：用来分配用户和基站之间的会话密钥。

会话密钥 $k$

产生方式：在每次会话时，基站产生一个64比特的随机数k。

分配方式：利用基本密钥$K_{A1}$，使用其它密码算法将k加密传给用户手机。

生存期：仅用于一次通话时间。

明文处理

按每帧228比特分为若干帧后逐帧加密，每帧处理方式相同。

\[M=M_{1}||M_{2}||\dots||M_{i}||\dots\quad |M_{i}|=228

![[A5_1流密码算法加解密.png]]

加密方式:

加密：$E_{k}=E_{k_{1}}(M_{1})E_{k_{2}}(M_{2})E_{k_{3}}(M_{3})\dots$

一次通话使用一个会话密钥，对每帧使用不同的帧密钥

帧会话密钥：帧序号，长度为22比特

帧会话密钥共产生228比特密钥流，实现对本帧228比特通信数据的加解密

明密结合方式：逐位异或

一次通话量：至多$2^{22}$帧数据，约$0.89× 2^{30}$比特

A5/1序列密码算法中的线性反馈移位寄存器

![[A5_1序列密码算法中的线性反馈移位寄存器.png]]

注： A5/1算法中， LFSR的移位方式是左移方式。各寄存器的编号从第0级编号到第n$-1$级。

A5流密码算法的基本原理

算法初始化

初始化是利用一次通话的会话密钥k和帧序号设定三个移存器的起点，即初始状态。

Step 1：将三个LFSR的初态都设置为全零向量；

Step 2： (密钥参与) 三个LFSR都规则动作64次，每次动作1步。在第 $i$ 步动作时，三个LFSR的反馈内容都首先与密钥的第 $i$ 比特异或，并

将异或结果作为LFSR反馈的内容。

密钥参与过程举例

以移存器1为例的密钥参与过程：

\[\begin{aligned}

k=k_{64}k_{63}\dots k_{1}\qquad f_{1}(x)&=x^{19}\oplus x^{18}\oplus x^{17}\oplus x^{14}\oplus 1\\

初始状态：S_{0}&=(x_{18},x_{17},\dots x_{0})=(0,0,\dots,0)\\

动作1步后状态：S_{0}&=(x_{18},x_{17},\dots x_{0})=(0,0,\dots,k_{1})\\

动作2步后状态：S_{0}&=(x_{18},x_{17},\dots x_{0})=(0,0,\dots,k_{1},k_{2})\\

动作14步后状态：S_{0}&=(x_{18},x_{17},\dots x_{0})=(0,0,\dots,k_{1},k_{2},\dots k_{13},k_{14})\\

动作15步后状态：S_{0}&=(x_{18},x_{17},\dots x_{0})=(0,0,\dots,k_{1},k_{2},\dots,k_{14},k_{1}\oplus k_{15}) \\

动作64步完成密钥参与过程。

\end{aligned}

帧序号参与

Step 3： (帧序号参与) 三个LFSR都规则动作22次，每次动作1步。在第 $i$ 步动作时，三个LFSR的反馈内容都首先与帧序号的第 $i$ 比特异或，并将异或的结果作为LFSR反馈的内容；帧序号比特的序号是从最低位编到最高位。

帧序号参与方式：与密钥参与方式相同，不同的明文数据帧按顺序编号，每个编号为22比特。

记帧序号为:$T_{0}=t_{22}t_{21}\dots t_{1}=00\dots00\quad T_{1}=t_{22}t_{21}\dots t_{1}=00\dots 01$

帧密钥参与的目的：对不同的帧设置不同的帧会话密钥，保证对每帧以不同的起点生成密钥流，尽可能避免密钥重用。

密钥流生成与加解密

A5算法中，采用钟控方式控制3个LFSR来产生密钥流。

钟控信号$x_{1}x_{2}x_{3}$的采取： $x_{1}$取自LFSR-1第9级； $x_{2}$取自LFSR-2第11级；$x_{3}$取自LFSR-3第11级。

控制方式：采用多项式 $g(x)=x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{1}$ 来确定，取钟控信号和多项式值相同的进行移位，不同的就不动。

$(X1,X2,X2)$

000

001

010

011

100

101

110

111

LFSR-1

动

不动

动

LFSR-2

动

不动

动

不动

动

LFSR-3

动

不动

动

不动

动

钟控方式

略，详见ppt

关于加密

Step 4：三个LFSR以钟控方式连续动作100次，但不输出密钥流；

Step 5：三个LFSR以钟控方式连续动作114次，在每次动作后，三个LFSR都将最高位寄存器中的值输出，这三个比特的异或就是当前时刻输出的1比特密钥。

连续动作114步，共输出114比特密钥流，用于对用户手机到基站传送的114比特数据的加密；

加密方式: $c_{i}=m_{i}\oplus d_{i};i=1,2,\dots,114$

Step 6：三个LFSR以钟控方式连续动作100次，但不输出密钥流；

Step 7：三个LFSR以钟控方式连续动作114次，在每次动作后，三个LFSR都将最高级寄存器中的值输出，这三个比特的模2和就是当前时刻输出的1比特密钥流。

连续动作114步，共输出114比特密钥流，这114比特用于对基站到用户手机传送的114比特数据的解密。

解密方式：$m'_{i}=c'_{i}\oplus d_{i;i=115,116,\dots,228}$

A5/1算法的弱点

移位寄存器太短容易遭受穷举攻击

A5/1算法把主密钥作为算法中三个寄存器的初始值，长度为64比特。如果利用已知明文攻击，只需要知道其中两个寄存器的初始值，就可以计算出另一个寄存器的初始值，这只需要$2^{40}$步就可以得出寄存器LFSR-1和LFSR-2的结构。

事实上， A5/1加密算法中存在严重的安全问题

利用了GSM通信加密中的两个安全漏洞，可以通过离线迭代计算生成一个彩虹表，它包含有密钥和其相对应的输出密码。这个彩虹表的大小为984GB。得到了彩虹表之后，安全专家就可以在短短的九秒内确定用于加密通信数据的密钥。

密钥流生成器的基本原则

设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性” ，它可分解为下述基本原则：

长周期。

高线性复杂度(用最少的移位寄存器来实现)。

统计性能良好。

足够的“混乱” 。

足够的“扩散” 。

抵抗不同形式的攻击。

祖冲之密码

ZUC 算法最初是面向4G LTE 空口加密设计的序列密码算法

2011年9月被3GPP LTE 采纳为国际加密标准（3GPP TS 33.401）

2012年3月，发布为国家密码行业标准GM/T0001-2012

2016年10月，发布为国家标准GB/T 33133-2016

ZUC 算法目前主要用于通信领域

ZUC算法是一个基于字设计的同步序列密码算法

种子密钥SK和初始向量IV的长度均为128比特

在SK和IV的控制下，每拍输出一个32比特字

标准起草人：冯登国、林东岱、冯秀涛、周春芳

算法中的符号及含义

数制表示

文中整数如果不加特殊说明都为十进制，如果有前缀“0x” 则表示十六进制，如果有下标“2” 则表示二进制。

例整数 $a$ 可以有以下不同数制表示形式。

\[\begin{aligned}

a&=1234567890\\

&=0x499602D2\\

&={1001001100101100000001011010010}_{2}

\end{aligned}

数据位序

文中所有数据的最高位（或字节）在左边，最低位（或字节）在右边。如=10010011001011000000010110100100，的最高位为其最左边一位1，的最低位为其最右边一位0。

运算符号

$+$

两个整数相加

$ab$

两个整数 $a$ 和 $b$ 相乘

$=$

赋值运算

$mod$

整数取模

$\oplus$

整数间逐比特异或（模2加）

$\boxed{+}$

模 $2^{32}$ 加

$a||b$

串 $a$ 和 $b$ 的级联

$a_{H}$

整数 $a$ 的高（最左） 16位

$a_{L}$

整数 $b$ 的低（最右）16位

$a\lll{k}$

$a$循环左移$k$位

$a\gg{1}$

$a$右移一位

$a_{1},a_{2},\dots ,a_{n}$

$a_{i}$ 到 $b_{i}$ 的并行赋值

算法中的符号及含义

例 $a=0x1234,b=0x5678,c=a||b=0x12345678$

例 $a=\overline{ 100100110010110}\overline{ \underline{0}}\underline{000001011010010}_{2}$，则

\[a_{H}=1001001100101100_{2},a_{L}=0000001011010010_{2}

例 $a=11001001100101100000001011010010_{2}$，则

\[a\gg{1}=1100100110010110000000101101001_{2}

例设 $a_{1},a_{2},\dots,a_{15},b_{1},b_{2},\dots,b_{15}$ 都是整数，$(a_{1},a_{2},\dots,a_{15})\to(b_{1},b_{2},\dots,b_{15})$

意味着 $b_{i}=a_{i}(1\leq i \leq {15})$

祖冲之密码的算法结构

![[祖冲之密码的算法结构.png]]

线性反馈移位寄存器

线性反馈移位寄存器（LFSR）由16个31比特寄存器单元$s_{1},s_{2},\dots s_{15}$组成，每个单元在集合 $\left\lbrace 1,2,3,\dots,2^{31}-1 \right\rbrace$ 中取值。

线性反馈移位寄存器的特征多项式是有限域 $GF(2^{31}-1)$ 上的16次本原多项式

\[p\left( x \right)=x^{16}-2^{15}x^{15}-2^{17}x^{13}-2^{21}x^{10}-2^{20}x^4-\left( 2^8+1 \right)

其输出为有限域 $GF(2^{31}-1)$ 上的 $m$ 序列，具有良好的随机性。

\[s_{16+t}=2^{15}s_{15+t}+2^{17}s_{13+t}+2^{21}s_{10+t}+2^{20}s_{4+t}+\left( 2^8+1 \right) s_{t}(mod 2^{31}-1)

线性反馈移位寄存器的运行模式有两种：初始化模式和工作模式。

（1）初始化模式

在初始化模式中， LFSR接收一个31比特字, 是由非线性函数 $F$ 的32比特输出 $W$ 通过舍弃最低位比特得到，即 $u=W\gg{1}$ 。计算过程如下：

\[\begin{align}

&LFSRWithInitialisationMode(u) \\

&\quad1.v=2^{15}s_{15}+2^{17}s_{13}+2^{21}s_{10}+2^{20}s_{4}+(1+2^{8})mod(2^{31}-1) \\

&\quad2.s_{16}=(v+r)mod(2^{31}-1) \\

&\quad 如果 s_{16}=0，则 s_{16}=2^{31}-1 \\

&\quad{4}. \left( s_{1},s_{2},s_{3},\dots,s_{15},s_{16} \right) \to \left( s_{0},s_{1},\dots,s_{14},s_{15} \right)

\end{align}

（2）工作模式

在工作模式下， LFSR没有输入。其计算过程如下：

\[\begin{align}

&LFSRWithWorkMode( ) \\

&\quad{1}. s_{16}=2^{15}s_{15}+2^{17}s_{13}+2^{21}s_{10}+2^{20}s_{4}+(1+2^{8})s_{0}\mod(2^{31}-1) \\

&\quad 如果s_{16}=0 \qquad则置 s_{16}=2^{31}-1 \\

&\quad (s_{1},s_{2},\dots,s_{15},s_{16})\to (s_{0},s_{1},\dots,s_{14},s_{15})

\end{align}

比特重组

比特重组从LFSR的寄存器单元中抽取128比特组成4个32比特字，其中前3个字将用于下层的非线性函数，第4个字参与密钥流的计算。

![[祖冲之密码的算法结构比特重组.png]]

\[\begin{align}

& BitReconstruction() \\

& \quad 1. X_{0}=s_{15H}||s_{9H} \\

& \quad 2. X_{1}=s_{11L}||s_{9H} \\

& \quad 3. X_{2}=s_{7L}||s_{5H} \\

& \quad 4. X_{3}=s_{2L}||s_{0H}

\end{align}

非线性函数F

非线性函数有2个32比特长的存储单元 $R_{1}$ 和 $R_{2}$ ，其输入为来自上层比特重组的3个32比特字 $X_{0}、X_{1}、X_{2}$，输出为一个32比特字。因此，非线性函数是一个把96比特压缩为32比特的一个非线性压缩函数。

具体计算过程如下：

\[\begin{aligned}

&F(X_{0},X_{1},X_{2}): \\

&\quad W=(X_{0}R_{1})\boxed{+}R_{2} \\

&\quad W_{1}=R_{1}\boxed{+}X_{1}\\

&\quad W_{2}=R_{2}\oplus X_{2}\\

&\quad R_{1}=S\left( L_{1}(W_{1L}||W_{2H}) \right) \\

&\quad R_{1}=S\left( L_{2}(W_{2L}||W_{1H}) \right)

\end{aligned}

S盒：（即输入长和输出长都为32比特）的S盒由4个并置的的S盒构成，即

\[S=(S_{0},S_{1},S_{2},S_{3})

$$其中 $s_{2}=s_{0},s_{3}=s_{1}$ ，于是有

S=(S_{0},S_{1},S_{0},S_{1})

\[（2）经S盒替换后$\to$线性变换 $L_{1}$ 和 $L_{2}$：$L_{1}$ 和 $L_{2}$ 为32比特线性变换，定义如下：

\begin{cases}

L_{1}(X)=X\oplus(X\lll 2)\oplus(X\lll{10})\oplus(X\lll{18})\oplus(X\lll{24}) \

L_{2}(X)=X\oplus(X\lll 8)\oplus(X\lll{14})\oplus(X\lll{22})\oplus(X\lll{30})

\end{cases}

\[非线性函数$F$输出的$W$与比特重组（BR）输出的$x_{3}$异或，形成输出密钥序列Z。

##### 密钥载入

密钥载入过程将128比特的初始密钥和128比特的初始向量 $IV$ 扩展为16个31比特长的整数，作为LFSR寄存器单元 $s_{0},s_{1},\dots,s_{15}$ 的初始状态。

设 $k$ 和 $IV$ 分别为 $k=k_{0}||k_{1}||\dots||k_{15}$ 和 $IV=iv_{0}||iv_{1}||\dots||iv_{15}$

其中：$k_{i}$ 和 $iv_{i}$ 均为 8bit 长字节，$0\leq i\leq {15}$。

##### 密钥载入步骤

1. 设D为240比特的常量，可按如下方式分成16个15比特的子串：

D=d_{0}||d_{1}||\dots||d_{1}5

\[2. 对 $0\leq i\leq 15$，取 $s_{i}=k_{i}||d_{i}||iv_{i}$

#后续暂时不想写了。。。\]