密码学学习笔记第二章：流密码

流密码的基本思想是利用密钥 $k$ 产生一个密钥流 $z=z_0z_1...$ ，并使用如下规则对明文串 $x=x_0x_1x_2...$ 加密： $y=y_0y_1y_2...=E_{z0}E_{z1}E_{z2}...$ 。密钥流由密钥流发生器产生： $z_i=f(k,\sigma_i )$ ，这里的 $\sigma_i$ 是加密器中的记忆元件（存储器）在时刻 $i$ 的状态， $f$ 是由密钥 $k$ 和 $\sigma_i$ 产生的函数。

分组密码与流密码的区别就在于有无记忆性，如下图：

2.1.1 同步流密码

在同步流密码中，由于与明文字符无关，因而此时密文字符也不依赖于此前的明文字符。因此，可将同步流密码的加密器分成密钥流产生器和加密变换器两部分。如下图所示

同步流密码的加密变换 $E_{z_1}$ 可以有多种选择，只要保证变换时可逆的即可。实际使用的数字保密通信系统一般都是二元系统，因而在有限域 $GF(2)$ 上讨论的二元加法流密码，是目前最为常用的流密码体制，加密变换可表示为 $y_i=z_i \oplus x_i$ 。

2.1.2 有限状态自动机

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

有限状态集 $S=\left \{ s_i|i=1,2,...,l \right \}$
有限输入字符集 $A_1=\left \{ A_{j}^{\left ( 1 \right )} j=1,2,...,m\right \}$ 和有限输出字符集 $A_2=\left \{ A_{k}^{\left (2 \right )}| k=1,2,...,m\right \}$
转移、输出函数 $A_{k}^{2}=f_1(s_i,A_{j}^{1}),s_h=f_2(s_i,A_{j}^{1})$

输出函数 $f1$ （可以使用非线性函数增加输出复杂度）：根据当前状态和当前输入，产生一个输出。

状态转移函数 $f_2$ （一般是线性的函数）：根据当前状态和当前输入，更新到下一个状态。

同步密码流的关键是密钥流产生器。一般可将其看成一个参数为 $k$ 的有限状态自动机，由一个输出符号集 $Z$ ，一个状态集 $\sum$ ，两个函数 $\varphi$ 和 $\psi$ 以及一个初始状态 $\sigma _0$ 组成（如下图所示）。 $\varphi$ 为状态转移函数， $\psi$ 为输出函数。这种密钥流生成器设计的关键在于找出适当的状态转移函数 $\varphi$ 和输出函数 $\psi$ ，使得输出序列 $Z$ 满足密钥流序列应满足的几个条件，并且要求在设备上是节省的和容易实现的。

目前最流行和实用的密钥流产生器如下图所示，其驱动部分是一个或多个线性反馈移位寄存器（LFSR）

2.2 线性反馈移位寄存器

移位寄存器是流密码产生密钥流的一个主要组成部分。如下图所示为一个n级反馈移位寄存器，由n个二元存储器与一个反馈函数 $f(a_1,a_2,...,a_n)$ 组成

如果移位寄存器的反馈函数 $f(a_1,a_2,...,a_n)$ 是 $a_1,a_2,...,a_n$ 的线性函数，则称之为线性反馈移位寄存器LFSR。例如下述反馈函数：

$f(a_1,a_2,...,a_n)=c_na_1\oplus c_{n-1}a_2\oplus ...\oplus c_1a_n$

其中常数 $c_i=0$ 或 $1$ ， $c_i$ 至少有一个不为 $0$ ， $\oplus$ 是异或运算， $c_i=0$ 或 $1$ 可以用开关的断开和闭合来实现，如下图所示：

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

GF(2)全称是Galois Field (2)，即阶为 2 的伽罗瓦域（也叫有限域）。简单来说，它是一个只包含两个元素{0, 1}的数学系统，其运算规则完美契合了计算机的二进制逻辑。

设n级线性移位寄存器的输出序列 $\left \{ a_i \right \}$ 满足递推关系

$a_{n+k}=c_1a_{n+k-1} \oplus c_2a_{n+k-2} \oplus ... \oplus c_na_k$ (*)

对于任何 $k\geq 1$ 成立。这种递推关系可以用一个高次多项式

$p(x)=1+c_1x+...+c_{n-1}x^{n-1}+c_nx^n$

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

设n级线性移位寄存器对应于递推关系(*)，由于 $a_i\in GF(2)(i=1,2,...,n)$ ,所以共有 $2^n$ 组初始状态，即有 $2^n$ 个递推序列，其中非恒零的有 $2^n-1$ 个，记 $2^n-1$ 个非零序列的全体为 $G(p(x))$ 。

定义2-1 给定序列 $\left \{ a_i \right \}$ ,幂级数

$A(x)=\sum_{i=1}^{\infty }a_ix^{i-1}$

称为该序列的生成函数。

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

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

其中

$\phi (x)=\sum_{i=1}^{n}(c_{n-i}x^{n-i}\sum_{j=1}^{i}a_jx^{j-1})$

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

定义2-2 设 $p(x)$ 是 $GF(2)$ 上的多项式，使 $p(x)|(x^p-1)$ （即 $p(x)$ 能够整除 $(x^p-1)$ ）的最小 $p$ 称为 $p(x)$ 的周期或阶。

定理2-3 若序列 $\left \{ a_i \right \}$ 的特征多项式 $p(x)$ 定义在 $GF(2)$ 上， $p$ 是 $p(x)$ 的周期，则 $\left \{ a_i \right \}$ 的周期 $r|p$ 。

定义2-3 仅能被非0的常数或自身的常数倍除尽，但不能被其它多项式除尽的多项式称为即约多项式或不可约多项式。

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

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

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

定理2-6 设 $\left \{ a_i \right \}\in G(p(x))$ ， $\left \{ a_i \right \}$ 为 $m$ 序列的充要条件是 $p(x)$ 为本原多项式

2.4 m序列的伪随机性

流密码的安全性取决于密钥流的安全性，要求密钥流序列有好的随机性，使得密码分析者无法预测。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段时不会泄露更多信息，这样的序列称为伪随机序列。

首先介绍一下游程，设 $\left \{ a_i \right \} = \left \{ a_1a_2a_3... \right \}$ 为01组成的序列，例如00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再接下来是0的1游程和1的3游程。

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

$R(\tau ) = \frac{1}{T} \sum_{k=1}^{T} (-1)^{a_k} (-1)^{a_{k+\tau }} , 0\leq \tau \leq T-1$

当 $\tau = 0$ 时， $R(\tau ) = 1$ ；当 $\tau \neq 0$ 时，称 $R(\tau )$ 为异相自相关函数。

Golomb提出伪随机周期序列应满足如下三个随机性公设：

在序列的一个周期内，0与1的个数相差至多为1。
在序列的一个周期内，长为1的游程占游程总数的 $\frac{1}{2}$ ，长为2的游程占游程总数的 $\frac{1}{2^2}$ ，......，长为 $i$ 的游程占游程总数的 $\frac{1}{2^i}$ ，......，且在等长的游程中0的游程个数和1的游程个数相等。
异自相关函数是一个常数。

下面这条定理说明， $m$ 序列满足上述三个随机性公设

定理2-7 $GF(2)$ 上的 $n$ 长 $m$ 序列 $\left \{ a_i \right \}$ 具有如下性质：

在一个周期内，0、1出现的次数分别是 $2^{n-1}-1$ 和 $2^{n-1}$ 。
在一个周期内，总游程数为 $2^{n-1}$ ；对 $1\leq i\leq n-2$ ，长为 $i$ 的游程有 $2^{n-i-1}$ 个，且0、1游程各半；长为 $n-1$ 的0游程一个，长为 $n$ 的1游程一个；
$\left \{ a_i \right \}$ 的自相关函数为 $R(\tau ) = \begin{cases} 1 & \text{ } \tau = 0\\ -\frac{1}{2^n-1}& \text{ } 0 < \tau \leq 2^n-2 \end{cases}$

2.5 m序列密码的破译

这一节主要证明了只要敌手知道一段长为 $2n$ 的明密文对，便可求出一段长为 $2n$ 的密钥序列，并且可以由此破译整段m序列密码。

2.6 非线性序列

这一节介绍4种由多个LFSR驱动的非线性序列生成器。

2.6.1 Geffe序列生成器

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

当LFSR2输出1时，LFSR2与LFSR1连接；当LFSR2输出0时，LFSR2与LFSR3相连接。设LFSRi的输出序列为 $\left \{ a_i \right \}(i=1,2,3)$ ，则输出序列 $\left \{ b_k \right \}$ 可以表示为

Geffe序列生成器也可以表示为上右图的形式，其中LFSR1和LFSR3作为多路复合器的输入，LFSR2控制多路复合器的输出。设LFSRi的特征多项式分别为 $n_i$ 次本原多项式，且 $n_i$ 两两互素，则Geffe序列的周期为

$\prod_{3}^{i=1}(2^{n_i}-1)$

线性复杂度为

$(n_1+n_3)n_2+n_3$

2.6.2 J-K触发器

j-k触发器如下图所示，两个输入端分别用J和K表示，其输出 $c_k$ 不仅依赖输入，还依赖于前一个输出位 $c_{k-1}$ ，即

其中 $x_1$ 和 $x_2$ 分别是J和K端的输入。

由此可得J-K触发器的真值表如下表所示

J	K	$c_k$
0	0	$c_{k-1}$
0	1	0
1	0	1
1	1	$\overline{c_{k-1}}$

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

令驱动序列 $\left \{ a_i \right \}$ 和 $\left \{ b_i \right \}$ 分别为m级和n级m序列，则有

当m与n互素且 $a_0+b_0=1$ 时，序列 $\left \{ c_k \right \}$ 的周期为 $(2^m-1)(2^n-1)$

2.6.3 Pless生成器

Pless生成器由8个LFSR、4个J-K触发器和1个循环计数器构成，由循环计数器进行选通控制，如下图所示。时刻 $t$ 输出第 $t(mod4)$ 个单元。

2.6.4 钟控序列生成器

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

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

一多操作系统性能篇

面对传统操作系统“老糊涂”般的困境，一多操作系统（Yiduo OS）并未选择修补，而是以“一即是多”的东方哲学为指引，从零构建了一套面向 AIoT 时代的组合式架构。我们彻底抛弃了“进程独占”与“线程锁竞争”的旧规则，通过 Wasm 组件化、零拷贝共享内存与 AI 全局调度三大技术支柱，实现了从“资源抢占”到“万物共生”的范式转移。旧时代的直觉，往往是新时代的枷锁。为了兼容几十年来累积的数以亿计的

AtomGit开源社区

告别答辩PPT焦虑：百考通AI智能生成，高效搞定毕业答辩全流程

毕业答辩的核心，是清晰展示你的研究内容与成果，而不是比拼PPT的美观程度。借助百考通AI这样的工具，你可以将繁琐的排版、格式调整工作交给系统处理，自己则聚焦于：深入理解论文内容与逻辑；准备清晰流畅的答辩陈述；预判评委问题，准备应对思路；进行模拟演练，提升表达自信。如果你正在为答辩PPT感到焦虑或耗时太多，不妨尝试用百考通AI智能生成功能高效完成基础搭建，再基于个人需求做适当调整。这样既能保证PPT

AtomGit开源社区

告别答辩PPT焦虑：百考通AI一键生成，从容应对毕业答辩

归根结底，毕业答辩是你向师长和同行系统展示自己数年学习与研究成果的庄严时刻。评委们关注的核心是你工作的价值、逻辑的严谨以及你个人的思考与成长。一个制作精良、逻辑清晰的PPT是得力的助手，它能有效提升信息传递的效率，增强你陈述的说服力。我们不必，也不应该让工具的使用成为前行路上的羁绊。百考通AI所做的，就是希望通过技术手段，帮你自动化处理那些重复、繁琐且与核心研究关联度不高的“体力活”和“格式活”，