【密码学】从有限状态自动机到密钥流生成器

本文是对流密码内容的拓展，在流密码中种子密钥通过一个伪随机数生成器产生一个与明文等长的伪随机密钥流。而本文的内容就是在回答这样两个问题：

伪随机密钥流是如何生成的？
流密码、流密钥生成器和有限状态自动机之间是什么关系？

一、什么是有限状态自动机？

（1）定义

有限状态自动机（Finite State Machine，FSM）是具有离散输入和输出（输入集合与输出集合均有限）的一种数学模型。用于描述和分析系统的行为，特别是那些可以根据输入信号在不同状态之间切换的系统。由以下三个部分组成：

① 有限状态集

状态集：一组有限的状态，表示系统可能处于的条件或模式。每个状态代表系统的一个特定配置。

$S=\{ s_i | i=1,2,3,...,l\}$

② 有限输入字符集和有限输出字符集

输入集：一组有限的输入符号，这些符号可以触发状态的转换。

$A_1 = \{ A^{(1)}_j | j=1,2,3,...,m\}$

输出集：一组可能的输出符号，这些符号由自动机根据当前状态和输入产生。

$A_2 = \{ A^{(2)}_k | k=1,2,3,...,n\}$

③ 转移函数

状态转移函数：定义了在给定当前状态和输入的情况下，自动机会转移到哪个新状态。这个函数是自动机行为的核心。

$s_h = f_2(s_i,A_j^{(1)})$

输出函数：在某些FSM模型中，还定义了一个输出函数，它根据当前状态（和可能的输入）决定自动机的输出。

$A_k^{(2)} = f_1(s_i,A_j^{(1)})$

公式代表的含义是在状态为 $s_i$ ，输入为 $A_j^{(1)}$ 时，输出为 $A_k^{(2)}$ ，而状态转移为 $s_h$

（2）表现形式一：转移图

有限状态自动机（FSM）经常用有向图来表示，这种图形化的表示方法被称为转移图或状态图。转移图提供了一种直观的方式来展示FSM的结构和行为，便于理解和分析。

节点：转移图中的每个节点代表FSM中的一个状态。通常，节点会被标记以表示其状态名称或编号。
有向边：边表示从一个状态到另一个状态的转移。每条有向边都关联有一个或多个输入符号，这些输入符号触发从源状态到目标状态的转移。边上的标签通常包含触发转移的输入符号。
初始状态：转移图中通常会明确标出一个初始状态，表示FSM启动时的默认状态。初始状态通常用一个箭头指向或特殊形状的节点来表示。
终止状态：在某些FSM中，特定的状态被标记为终止状态或接受状态，表示自动机完成了一个特定任务或识别了一个特定输入序列。这些状态通常用双圆圈或类似标记来表示。
循环：转移图中可能存在从一个状态回到自身的边，这表示在特定输入下状态不会改变，形成一个循环。
分支：对于非确定性有限状态自动机（NFA），一个状态可能有多条边指向同一个或不同的状态，表示对于同一输入可能有多种响应。

（2）表现形式二：矩阵

除了使用转移图直观地表示有限状态自动机（FSM）的状态和转移外，我们还可以使用矩阵来数学化地描述FSM的行为。

有限状态自动机的矩阵表示主要有两种类型的矩阵：

状态转移矩阵：这是最常见的一种矩阵表示法，它描述了当前状态和输入组合下的下一个状态。如果FSM有n个状态，并且输入符号集合大小为m，则状态转移矩阵将是一个n×(m×n)的矩阵。每一行对应于一个当前状态，每一列对应于一个特定的输入，而矩阵中的元素则表示该输入下从当前状态转移到的下一个状态。如果FSM是非确定性的，那么矩阵中的元素可以是一个状态集，表示从当前状态出发，给定输入后可能达到的多个状态。
输出矩阵（对于带有输出的FSM）：在带有输出功能的FSM中，每个状态转移不仅涉及状态的变化，还可能伴随有输出。输出矩阵描述了在给定状态和输入的情况下，FSM产生的输出。如果FSM有n个状态，m个输入符号，k个可能的输出，则输出矩阵将是n×(m×k)的矩阵，其中矩阵中的每个元素表示在特定状态和输入下产生的输出。

二、密钥流生成器

（1）有限状态自动机怎么转换成密钥流生成器？

将有限状态自动机（FSM）转换成密钥流生成器通常是在设计密码系统时的一个步骤，尤其是对称加密中流密码的设计。流密码使用密钥流与明文进行逐位异或操作，以产生密文。密钥流生成器可以认为就是一个参数为 $k$ 的有限状态自动机。如下图：

由一个输出符号集 $Z$ 、一个状态集 $\sum$ 、两个函数 $\varphi$ 和 $\psi$ 以及一个初始状态 $\sigma _0$ 组成。

状态转移函数 $\varphi$ ：将当前状态 $\sigma _i$ 变为一个新状态 $\sigma _{i+1}$

输出函数 $\psi$ ：将当前状态 $\sigma _i$ 变为输出符号集中的一个元素 $z_i$

（2）密钥流生成器设计的关键

密钥流的生成需要满足两个关键要求：随机性和不可预测性，确保攻击者无法轻易推断出密钥流的后续部分。

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

一般采样线性的状态转移函数和非线性的输出函数，这样能够进行深入的分析并可以得到好的生成器。所以密钥流生成器可以分成两个部分：驱动部分（包含线性组件）和非线性组合部分

驱动部分：负责控制生成器的状态转移过程。这通常涉及到一种或多种线性反馈移位寄存器（LFSRs），它们通过线性反馈规则更新状态。驱动部分的主要目标是生成一系列统计特性良好的伪随机比特序列，这些序列随后会被馈送到非线性组合部分。

非线性组合部分：任务是接收来自驱动部分的序列，并通过非线性变换将其转化为最终的密钥流输出。增加了输出序列的不可预测性，提高了生成器的整体安全性。

三、总结

流密码作为密码学领域中的一个重要分支，它采用了一种动态的、逐位加密的技术，通过将明文与一个同长度的密钥流进行异或运算，实现了数据的安全传输和存储。这里的“逐位”加密，意味着每一个明文字符或比特位都会与相应的密钥流位进行一对一的加密操作。

然而，直接使用与明文相同长度的密钥流在实际应用中面临着严峻的挑战，尤其是密钥分发和存储方面的问题。为了解决这一难题，密码学家们设计出了密钥流生成器——一种能够从一个较短的种子密钥出发，生成足够长、看似随机的密钥流的算法。这种生成的密钥流，虽然源自于简短的种子，但经过精心设计后，其长度可轻松匹配任何规模的明文，从而解决了密钥长度受限的问题。

密钥流生成器的设计灵感来源于有限状态自动机，这是一种数学模型，用于描述系统如何基于当前状态和输入信号，在一组预定义状态之间进行转换的过程。在流密码的背景下，有限状态自动机被巧妙地运用，通过一系列复杂的内部状态变化，将种子密钥作为初始状态，逐步演进生成所需的密钥流。这一过程不仅保证了密钥流的不可预测性和随机性，同时也确保了生成器的高效性和实用性。