3.7 流密码
对称密码体制根据对明文的加密方式的不同而分为分组密码和流密码。分组密码的连续明文数字组使用相同的密钥来进行加密。密文组y = y1 y2…ym通过如下方式对明文组x = x1x2…xm加密得到：y = ek（x1）ek（x2）…ek（xm）。
流密码的基本思想是利用密钥k产生一个密钥流z = z0 z1…zm，并使用如下规则加密明文串x = x0 x1 x2…，得到密文串y = y0 y1 y2 … = ez0（x0）ez1（x1）ez2（x2）。
尽管分组密码也可以工作在流密码的模式，与分组密码相比，流密码的主要优点是速度更快而且需要编写的代码更少。流密码目前主要还是应用在军事、外交、无线通信等领域，虽然也有一些公开的设计和研究成果发表，但大多数还是保密的。目前可以见到的流密码算法有RC4，A5，SEAL和PIKE等。
3.7.1 流密码的定义
与分组密码类似，可以给出如下定义：
同步流密码是一个六元组（P，C，K，L，E，D）和函数f，并且满足条件：
（1）P是可能明文的有限集（明文空间）。
（2）C是可能密文的有限集（密文空间）。
（3）K是一切可能密钥构成的有限集（密钥空间）。
（4）L是一个称为密钥流字母表的有限集。
（5）f是一个密钥流生成器。f使用密钥k作为输入，产生无限的密钥流z = z0 z1…，zi ∈L，i≥1。
（6）对任意zi∈L，有一个加密算法ezi∈ E和相应的解密算法dzi∈D，并且对每一明文x ∈P，ezi：P→C和dzi：C→P分别为加密解密函数，满足dzi（ezi（x））= x。
3.7.2 同步流密码
根据加密器中的记忆元件的存储状态 σi是否依赖于输入的明文字符，流密码可进一步分成同步和自同步两种。σi独立于明文字符的叫做同步流密码，否则叫做自同步流密码。
同步流密码中，密钥流由密钥流发生器f产生：zi = f（k，σi），σi = fs（k，σi-1），这里σi是加密器中的记忆元件（存储器）在时刻i的状态，f是输出函数，fs是状态转移函数。
同步流密码中，由于zi = f（k,σi）与明文字符无关，因而密文字符yi =ezi（xi）也不依赖于此前的明文字符。因而，可将同步流密码的加密器分成密钥流生成器和加密变换器两个部分。如果与上述变换对应的解密变换为xi =dzi（yi），则可给出同步流密码的模型，如图3.20所示。
图3.20 同步流密码体制模型
同步流密码各位之间是真正独立的，因此，它的一个重要优点就是无错误传播，即一位传播错误只影响一位，不影响后面的位。
同步流密码的加密变换ezi可以有多种选择，只要保证变换是可逆的即可。实际使用的数字保密通信系统一般都是二元系统，因而在有限域GF（2）上的二元加法流密码是目前应用最多的流密码体制，其加密变换可表示为yi = zi ⊕ xi，⊕表示模2加（即异或）。
自同步流密码中，密钥流的产生过程可用函数描述为：
zi = f（k，σi），σi = fs（k， σi-1，ci-1，ci，ci+1，ci-n）
若每一个密钥字符是由前面 n 个密文字符参与运算推导出来的，如果在传输过程中发生错误，则这一错误就要向前传播 n 个字符。因此，自同步流密码有错误传播现象。在自同步流密码中，密文流和明文流都参与了密钥流的生成，密钥流的分析将复杂化，导致较难从理论上进行详尽的分析。因此，目前用的较多的是同步流密码。
3.7.3 密钥流生成器
流密码的安全强度取决于密钥流生成器所产生的密钥流的性质，当密钥流z = z0z1…zi是一个完全随机的非周期序列时，它实际上就实现了一次一密，而实际应用中的密钥流是一个伪随机序列。所以，流密码设计当中最核心的问题是密钥流生成器的设计。设计流密码从两方面进行考虑：一是从系统自身的复杂性度量出发，如输出密钥序列的周期、线性复杂度和随机性等；另一方面从抗已知攻击出发，如线性逼近和统计分析等。目前设计密钥流生成器主要的准则如下：
● 密钥量足够大：因为密钥流的输出取决于输入密钥的值，为防止强力攻击，密钥应该足够长，在目前的软/硬件技术条件下，应不小于128位。
● 加密序列的周期足够长：重复的周期越长，密码分析的难度就越大，一般为2128或2256。
● 密钥流应该尽可能地接近于一个真正的随机数流的特征，密钥流的随机特性越好，密文越随机，密码分析就越困难。
为了设计安全的密钥流生成器，必须在生成器中使用非线性变换，Rueppel将这类生成器分成两部分，即驱动部分和非线性组合部分。驱动部分控制生成器的状态序列，并为非线性组合部分提供统计性能良好的序列。驱动部分可由一个线性反馈移位寄存器组成，而非线性组合部分将驱动部分提供的序列组合成密码学特性良好的序列。
3.7.3.1 一种产生密钥流的方法
下面给出一种产生密钥流的方法。
从密钥（k1，k2，…，km）开始，假定zi = ki，1≤ i≤ m，利用次数为m的线性递归关系来产生密钥流：
这里c0，c1，…，cm-1∈Z2是确定的常数。密钥K由2m个值组成k1，k2，…，km，c0，c1，…，cm-1。当（k1，k2，…，km）=（0，0，…，0），则生成的密钥流全为零，这种情况是要避免的。如果常数c0，c1，…，cm-1选择适当的话，则任意非零初始向量（k1，k2，…，km）都将产生周期为2m-1的密钥流。
设m = 4，按下述线性递归关系产生密钥流：
zi+4 =（zi+zi+1）mod 2，i≥ 1
若初始向量为（1，0，0，0），则可以产生周期为24-1=15的密钥流如下：
100010011010111…
这种密钥流产生器可以使用线性反馈移位寄存器以硬件方式有效实现。
3.7.3.2 反馈移位寄存器
一个反馈移位寄存器（feedback shift register）由两部分组成：移位寄存器和反馈函数。如图3.21所示。
图3.21 反馈移位寄存器
序列的线性复杂度定义为生成这个序列的最短线性移位寄存器的长度。移位寄存器的周期是指输出序列从开始到重复时的长度。最简单的反馈移位寄存器是线性反馈移位寄存器（Linear Feedback Shift Register，LFSR），如图3.22所示，因为容易通过数字硬件实现。
图3.22 线性反馈移位寄存器
一个n位LFSR能够处于2n-1个内部状态中的一个，理论上，n位LFSR在重复之前能产生2n -1位长的伪随机序列。只有具有特定选择序列的LFSR才会遍历所有的2n -1个内部状态，这是最大周期的LFSR，这样的LFSR产生的输出序列称为m序列。
LFSR用软件实现时运行速度很慢，基于LFSR的密码通常都用硬件实现。
3.7.3.3 基于LFSR流密码的密码分析
密文以方式yi =（xi+zi）mod 2产生，利用下述的线性递归关系从初态（z1，z2，…，zm）=（k1，k2，…，km）产生密钥流：
这里c0，c1，…，cm-1∈Z2。
它容易受到已知明文攻击。假定攻击者Oscar有了明文串x1 x2 …xn和相应的密文串y1 y2 … yn，那么他能计算密钥流zi =（xi+yi）mod 2，1≤i≤n，若Oscar知道m的值，他仅需计算c0，c1，…，cm-1。
如果n≥ 2m，就有m个未知数的m个线性方程
这样一来，如果知道2m比特的输出串，很显然能够完全分析出m级线性移位寄存器。例如m = 20，非重复串的最大长度为220-1，超过100万，而2m的值仅为40。因为线性反馈移位寄存器很容易被分析出来，所以实际应用的流密码必须使用非线性反馈移位寄存器来产生所需的伪随机密钥比特。因为线性反馈移位寄存器容易理解和构造，通常将许多LFSR组合成一个非线性反馈移位寄存器。组合的方法主要有：
（1）非线性组合若干个LFSR的输出。
（2）非线性过滤一个LFSR的输出。
（3）一个或若干个LFSR的输出被用于控制主LFSR的时钟。
3.7.4 RC4
RC4是一个密钥长度从1字节到256字节（或8比特到2048比特）可变的流密码，于1987年由Ron Rivest设计，它保密了7年，于1994年匿名公开于Internet上。RC4是一个面向字节的流密码，它的密钥流序列独立于明文，RSA声称RC4对线性和差分分析具有免疫力。由于RC4是流密码，必须避免重复使用密钥。它是目前应用和影响力都最为广泛的一种流密码算法，被应用于SSL/TLS，WEP（IEEE802.11）等协议中。
我们可以用下述摸球模型来解释RC4算法。假设一个口袋中放有256个完全一样的球，分别标有编号0，1，2，…，255。把所有的球充分混合，随机取出一个球并记下该球的编号，再把取出的球放回袋中。重复这样做，如果重复的次数足够多，每个球出现的概率应该是相等的，这样将得到一个取出的球的编号序列，它是由整数0，1，2，…，255构成的随机序列。当序列足够长时，各个数出现的概率大致相等。RC4算法正是这一摸球模型的具体实现。
RC4算法可分为两个阶段，第一个阶段是对一个256个字节的状态矢量S的初始化阶段，相当于把编号后的球充分混合。第二个阶段是密钥流的生成阶段，相当于从袋中重复随机取球。
初始化阶段首先对S [0]到S [255]进行线性填充，即S [0] = 0，S[1] = 1，…，S [255] = 255，同时建立临时状态矢量T，将密钥K赋给T，如果K的长度为256字节，则直接赋值，如果密钥长度小于256字节为keylen字节，则循环重复把K赋给T。这一操作的伪代码如下：
for i=0 to 255 do
S[i]=i;
T[i]=K[i mod keylen]
然后用T对S进行初始置换，这一操作的伪代码如下：
j=0;
for i = 0 to 255 do
j = (j + S[i] + T[i]) mod 256;
Swap S[i] and S[j];
初始化阶段结束后，状态矢量S的元素S [0]，S [1]，…，S [255]变成了整数0到255之间的随机值。
在密钥流生成阶段中，S[t]存放的是取出的球的编号，t =（S[i]+S[ j]）mod 256的功能是希望第t个球是随机取出的；交换S[i]和S[ j]（Swap S[i] and S[ j]）的目的是每取一次球，就对袋子中的球重新“混和一把”。这一阶段的伪代码如下：
i,j=0
While(true)
i = (i + 1) mod 256;
j = (j + S[i]) mod 256;
Swap S[i] and S[j];
t = (S[i] + S[j]) mod 256;
k = S[t];
根据需要可产生足够长度的密钥流k，加密时k与明文异或产生密文，与密文异或产生明文。
3.7.5 A5算法
A5序列密码是欧洲GSM（Group Special Mobile）标准中规定的加密算法，用于数字蜂窝移动电话的加密，加密从用户设备到基站之间的链路。A5由三个LFSR组成，移位寄存器的长度分别是19，22和23，三个LFSR在时钟控制下运行。A5算法有两个版本：强安全性的A5/1和弱安全性的A5/2。