【密码学】（五）流密码概述、伪随机序列、密钥流生成器

本文转载自：《现代密码学》课程笔记知乎专栏
仅作个人学习记录。

一、流密码的起源和伪随机序列

1、流密码的概念和起源：

流密码是一种对称密码体制。它一次只对明文的一个位进行加密，然后得出密文。

典型的流密码起源于Vernam密码体制（第一篇古典密码学讲过），它通过明文序列和密钥流（通常和明文序列等长）的按位异或来得出密文。这种按位异或是典型的流密码的特征。

其加解密体制如下图所示。其中明文长度=密钥长度=密文长度。加解密变换中的模2加等价于异或。

图8-1 流密码的加解密方式

2、流密码的核心问题：

在第一篇中，我们曾提到：如果Vernam密码体制中的密钥流是完全随机的，那么这种加密体制就是绝对安全的（理论上不可破译）。然而，完全随机的无限长的密钥流的生成、分发和存储是非常困难的。因此，我们需要采用另外一种思路来生成接近随机的密钥流。

我们需要使用有限长的种子密钥（易生成、分发、存储），来生成无限长的随机密钥序列——我们称拥有这种功能的算法为伪随机序列发生器。如何设计高效而又安全的伪随机数发生器，是流密码的核心研究内容。

3、伪随机序列：

之所以要给“伪随机序列”加一个“伪”字，是因为伪随机序列发生器生成的随机序列并不是完全随机的。它往往拥有一定的周期性，只能做到在窃取较短的一段序列时，不会泄露太多信息而已。

4、伪随机序列应该满足的条件：

作为一个合格的伪随机序列，应该需要看起来足够随机，不然会不太安全。

为了衡量一个伪随机序列是否足够随机，我们可以采用一定的方法对其进行测评。

[!note] 补充：
（1）游程的概念：
游程就是一个序列中，相同符号连续出现的次数。比如，对于序列00110111，其前两个数字为0的2游程；接下来是1的2游程；然后是0的1游程和1的3游程。
（2）自相关函数：
对于一个周期为 的序列 $a=(a0,a_1,\ldots,a{T-1})Tta^{(t)}=(at,a{t+1},\ldots,a{t-1})Ta_i=a{i+t}indR(t)=n-dt\ne0100110T=6t=2011010n=2d=4R(2)=n-d=-2$。

Golomb提出了二元0-1随机序列应该满足的三条原则：

• （1）如果序列的周期为奇数，则要求序列中0和1的个数只能相差1个；如果序列的周期为偶数，则要求序列中0和1的个数相等。
• （2）在一个周期的序列中，要求1游程（包含0的1游程和1的1游程）的个数为总游程数的 ；2游程（包含0的2游程和1的2游程）的个数为总游程数的 ；以此类推， 游程（包含0的 游程和1的 游程）的个数为总游程数的 。此外，还要求在等长的游程中，0的游程个数与1的游程个数相等，即要求0的1游程个数=1的1游程个数；0的2游程个数=1的2游程个数；以此类推，0的 游程个数=1的 游程个数。
• （3）要求序列的异相自相关函数是一个常数。即满足：在一个周期内，不管平移多少位，序列均不会反映出任何信息。

除了需要满足Colomb伪随机性测试的条件，伪随机序列还需要满足

• 伪随机序列的周期足够大。
• 伪随机序列的产生在计算上是容易的。
• 已知密文和明文的部分信息，不能确定整个伪随机序列。

二、流密码的分类

依据流密码密钥序列产生的方式，可以将流密码分为同步流密码和自同步流密码**两类。

1、同步流密码：

在流密码产生密钥序列时，如果密钥序列的产生与之前明文字符、密文字符均无关，也即密钥序列的产生可以完全独立于明文加密，则将这种流密码称为同步流密码。

由于同步流密码的密钥流生成和加密过程是独立的，因此同步流密码可以分为密钥流产生器、加密变换器两部分。

在同步流密码中，前面出现的加解密错误不会影响到后面的加解密，这是因为相邻两位明文的加密是相互独立，没有关系的。

同步流密码在加密或解密时，需要使两者密钥流生成器的状态一致（这里的状态可以决定密钥流生成器产生的密钥），否则会导致加解密密钥不一致，使解密失败。当两者密钥流生成器的状态不一致时，必须借助外接手段来同步，同步流密码本身不具有自同步功能。

在上一讲《分组密码的工作模式》中，OFB、CTR模式就属于同步流密码（可以回去复习一下）。

2、自同步流密码：

在流密码产生密钥序列时，如果密钥序列的产生与以往的密文序列有关，即密钥产生算法是密钥和以往密文序列的函数，则称这种流密码为自同步流密码。

自同步流密码中，密钥序列的产生与明文的加密是不独立的，也是不能分割的。很多情况下，明文或者密文都需要给密钥序列的产生提供反馈。

自同步流密码具有自同步功能。因为密钥序列的产生与明密文序列有关，所以加密和解密密钥生成器的状态不一致时，是可以自己进行同步的，无需认为同步。

自同步流密码可能会对错误进行传播。因为密钥序列的产生与明文序列有关，所以前边明文的加密错误，会导致后边密钥序列生成出错，导致后边明文序列也加密错误。

在上一讲《分组密码的工作模式》中，CFB模式就属于同步流密码（可以回去复习一下）。

三、密钥流产生器

1、密钥流产生器概述：

前面提到，同步流密码可以分为密钥流产生器和加密变换器两部分。而如何构建一个好的密钥流产生器是同步流密码需要解决的核心问题。

密钥流产生器的功能是：在一个输入子密钥 的作用下，产生一个符合伪随机序列条件的密钥序列。数学模型——有限状态自动机可以很好地实现这个功能。

[!note] 补充：
输入子密钥：是指输入流密码算法的密钥。用来产生密钥序列。
密钥流产生器产生的密钥序列：指在输入子密钥的作用下，密钥流产生器产生的符合伪随机序列条件的密钥序列。用来跟明文进行运算，对明文加密。

2、有限状态自动机：

有限状态自动机由一系列不同的状态组成，一个状态在一定条件下可以转换为另一个状态，每一个状态都有一个输出。

一个有限状态自动机由两个集合、两个函数、一个初始状态组成。

分别为：

一个输出符号集 ，其中包含所有输出符号 。对于0-1二元符号集， 。

一个状态集 ，其中包含自动机的所有状态 。

一个输出函数 ，表示在当前状态 中，在子密钥 的作用下，输出一个符号 的映射过程，即 。

一个状态转移函数 ，表示在子密钥 $kis_is{i+1}s_{i+1}=g(s_i,k_i)$。

一个初始状态 ，为输出函数和状态转移函数提供一个初始输入。

通过有限状态自动机中状态的转换、密钥序列的输出，就可以得到符合条件我的伪随机序列。

符号集和状态集较容易构建，但是输出函数和状态转移函数是相对较难构建的。如何寻找合适的输出函数和状态转移函数？这是我们接下来应该解决的问题。

3、合适的输出函数和状态转移函数：

为了使得输出序列和状态转移尽可能随机，我们可以直观知道，输出函数和状态转移函数最好都是非线性的函数（线性函数一般会有线性相关的性质，这会使得输出序列、状态转移与输入子密钥相关，而不够随机，因此采用非线性函数）。

但是，采用非线性状态转移函数的有限自动机理论还不太完善，这会使得整个密钥流生成器的分析受到限制。

所以，我们只能使用==线性的状态转移函数和非线性的输出函数==，来构建密钥流产生器。

这样的密钥流生成器由线性驱动部分和非线性组合部分组成。

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

非线性组合部分==用这些序列生成满足要求的密钥流序列。==

线性驱动和非线性组合的具体构造会在下一节中详细讲解。