嘘~这是我们的秘密！——一起来学《密码学》，第二弹

发表于2016-05-07

不知不觉，一个多月过去了。经过了五一小长假和青年节的半天假的假期时光后，是时候收心到工作和学习上了。

本期探讨的重点是流密码。比较常用的两种流密码是：RC4和A5。

流密码的基本思想是利用密钥产生一个密钥流，并使用如下规则对明文串加密：。密钥流由密钥流发生器产生：，这里是加密中的记忆元件（存储器）在时刻的状态，是由密钥和产生的函数。通俗地讲，将密钥经过密钥流发生器产生一个密钥流，然后将密钥流与明文串逐位地经过变换生成密文串。相应地，密钥流和密文串逐位地经过运算的逆变换生成明文串。

流密码的滚动密钥由函数、密钥和指定的初态完全确定。此后，由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态，因而（）可能依赖于，，，，，等参数。

根据加密器中记忆元件的存储状态是否依赖于输入的明文字符，流密码可进一步分成同步和自同步两种。独立于明文字符的称为同步流密码，否则称为自同步流密码。疏于自同步流密码的密钥流的产生与明文有关，因而较难从理论上进行分析。目前大多数研究成果都是关于同步流密码的。

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

同步流密码的模型如下：

同步流密码的加密变换可以有多种选择，只要保证变换是可逆的即可。实际使用的数字保密通信系统一般都是二元系统，因而在有限域（关于有限域，后续会详细介绍，有兴趣的同学可先行了解）上讨论的二元加法流密码是目前最为常用的流密码体制，其加密变换可表示为，其模型如下：

因此可见，对于这种同步流密钥而言，用于生成密钥流的密钥流发生器成为该加密算法的核心。

下面将着重讲解RC4和A5的密钥流生成算法。RC4首先说明下RC4算法中所使用符号所代表的意义

-- RC4使用的一个字节的长度（实际中一般取）

-- 长度为的一个字节能够显示的值的总量，即

-- RC4的内部状态，每一个中有个比特长度的值

-- 一个参数，

-- 参数时的内部状态

-- 参数时对应的两个指针，指向内部状态中的两个值

-- 中指针指向的值

-- 密钥

-- 密钥包含的字节数，即

-- 每一个对应的密钥生成器的输出值

RC4算法是参数决定的一系列算法，在每一个中包含个比特字节，，包含2个比特字节的指针和。这样，占用内存大小为。

RC4算法包含两个部分，伪随机数生成算法PRGA和密钥方案算法KSA。

PRGA首先将两个指针和初始化为0，和作为两个随机变化的指针，然后变换状态中和指向的值，该过程的输出值为位置的值。具体过程如下：

初始化：

生成过程：

KSA包含步操作，每一步操作与PRGA非常相似，该过程将内部状态初始化，并将指针和位置设为0。具体过程如下：

初始化：

操作过程：

A5算法是用于GSM系统的流密码算法。其初始化向量是64比特的会话密钥和22比特的帧序列号，生成228比特的密钥流，加密与解密各114比特。会话密钥在通话期间被使用，但是帧序列号在通话期间会改变。

A5算法可分成三个阶段：

第一阶段，3个移位寄存器、、初始全部设置为0，然后在64个周期内，将每个线性反馈移位寄存器都移位64次，每次移位后将密钥与每个线性反馈移位寄存器的最低位比特异或，之后在22个时钟周期内，将每个线性反馈移位寄存器都移位22次，每次移位后将22比特帧序列与每个线性反馈移位寄存器的最低位比特异或。记此时的内部状态为。

第二阶段，由状态出发，按照钟控规则移位100个周期，与第一阶段不同的是，不进行异或操作，舍弃密钥流。记此时的内部状态为。

第三阶段，由状态出发，按照钟控规则对、、进行移位操作，、、的最高位异或生成228比特的密钥流。

上面提到一个名词：线性反馈移位寄存器（Linear Feedback Shift Register, LFSR）。它是反馈移位寄存器（Feedback Shift Register, FSR）中的一种。FSR是由移位寄存器和反馈函数组成，其中移位寄存器是一个序列，位是移位寄存器长度的单位。如果是位长，则为-位移位寄存器。每次运算时得到一位，此时移位寄存器中全部向左移动一位。这样最左端的位被舍去，最右端的位需要更新，根据寄存器中其他位经过反馈函数计算得到最右端的位。最后，移位寄存器输出一位，一般为的值。如图：

而LFSR的反馈函数为异或运算，如图：

下面，我们用一个4位LFSR来举例说明其工作原理：

如上图所示，反馈函数的输入为第4位和第1位，假设初始值为1111，在输出序列重复之前（输出序列从开始到重复前的长度称为周期），能够产生的状态序列是：

1111，1110，1101，1010，0101，1011，0110，1100，1001，0010，0100，1000，0001，0011，0111

则输出序列（状态序列的最高位）为：111101011001000。

对于一个-位LFSR有种内部状态（全部是0的状态除外，因为运算结果不能产生别的内部状态），即-位LFSR在重复之前，能够产生位长的伪随机序列。而-位LFSR能够产生种内部状态是需要某种抽头序列（选择寄存器某些位参与计算）。为了能够有最大周期的LFSR，则要求抽头序列加1后的多项式（多项式的阶是移位寄存器的长度）是本原多项式模2（一个阶本原多项式是不可约多项式，它能够整除，不能整除，是能够整除）。