第3章
流　密　
码


3.1
伪随机序列的生成

从上一章的讨论可以发现,完善保密的局限性在于需使用足够长的随机比特串作为
密钥,而用自然的方法产生的随机比特流难以保证效率和安全性。因此人们更倾向于寻
找一种短密钥扩展方法,使加密时能够生成近似随机比特流。这就是现代密码学的基础。

3.1 
一般方式
1.
大多数的计算机均支持生成随机数,如标准C语言库函数中的rand()函数可产生介
于0~65535之间的任意一个伪随机(即看似均匀)数,这个伪随机函数需要一个“种子” 
(sed)作为输入,之后就可产生一个比特流的输出。这类伪随机序列发生器一般都建立
在线性同余生成器(r)的基础之上,它可以根据以下关系式产
生一系列数。
linearcongruentialgenerato

xn 
≡axn-1+b(modm)

设x0 是初始值,、
b 
和
m 
是关系式中的参数。但是这类伪随机序列发生器所产生

a 

的伪随机序列无法满足密码学的要求,较适合以实验为目的的情况,因为它们依然是可被
预知的比特流。对于已经知道的任何多项式同余生成器都存在潜在的不安全性。
为产生不可预知的比特流作为输入源,常用两种比特流创建方法,分别是利用单向函
数和数论中的难解问题(em )。

intractableprobl
单向函数是指那些在已知
y 
和
y 
=f(x)的情况下依然不能求解
x 
的函数。假设存
在一个单向函数
f 
和一个随机的输入参数s,f(1,3,…, 是yj 

b1,
yj 
=s+j),j=2,若令bj 
的最低有效比特,那么序列b0,…将是一个伪随机的比特序列。运用这种方法的最具
代表性的加密算法就是DES安全散列算法。

而解决数论中的难解问题的方法中人们最常用的密码安全伪随机序列生成器之一是
平方剩余伪随机序列生成器(Blum-Blum-Shub,BBS),即人们所说的二次剩余方程生成
器。BBS是一种流行的产生安全的伪随机数的方法,是由它的研制者的名字(BlumL, 
BlumM和ShubM)命名的。该算法首先产生两个大的素数
p 
和q,它们都同余于3模
4,设n=pq,且存在一个随机的整数
x 
与
n 
互素,则为了初始化BBS生成器,设初始输入
是x0≡x2(dn),BBS通过如下过程产生一个随机的序列b0,…满足

mob1,
①xj 
≡x21(modn)
;


j


现代密码学概论(第2版) 
②bj 
是xj 
的最低有效比特。

BBS生成器的安全性是基于分解
n 
的难度,很可能是不可预测的,但是它的计算速

度慢,在有些情况下人们可能更在意加密的效率而非安全性。因此在保证应有的安全性

时可以减少
k 
个xj 
中的最低有效比特,只要k≤log2log2n,这样应该也能保证加密的安

全性。

1.线性反馈移位寄存序列
3.2 

在很多加密情景中,人们需要考虑到存储开销、计算效率与安全性的平衡。线性反馈
移位寄存器(ierfakshfegses,具有满足该场景的多项优点:高计算

lnaedbcitritrLFSR) 
性能、低实现开销以及统计性良好的生成序列。例如,可用如下一个线性递归关系表示
LFSR 。
xn+5≡xn 
+xn+2(mod2) (3-1) 

并设置式中变量的初始值为

x0=0,x1=1,x2=0,x3=0,x4=0 (3-2) 
则将式(3-2)代入式(3-1)并重复31次后即可得到如下序列。
010000100101100111110001101110101000 
一般一个长度为
m 
的线性递归关系(系数c0,…是整数)

c1,1(
可表示为

xn+
m 
≡c0xn 
+c1xn+1+ 
…+cm-1xn+m-mod2)
若给出了初始值(intaauIV)


iilvle,为

x0,x1,…,xm-1 

则序列{xn 
}的所有值都可以由递归计算出来,这个由0和1组成的结果序列可被用作加

密的密钥。

这种方法可以用短的种子密钥生成一个周期非常长的加密密钥,这个长周期是相较

于维吉内尔密码的改进。上例中,1,0,0,

IV 
和线性递归关系式系数分别为|0,0,0|和|1,

1,0,0| 。这表示可以存储10比特产生31比特的伪随机数序列。对于精心选取的长为

31的线性递归关系,任何非零IV 
均可产生一个周期为231-1=2147483647的序列,这

是相当可观的。

人们可用被称为线性反馈移位寄存器的硬件以实现上述过程,自动而快速地产生随

机序列。图3-1描述了一个简单的线性反馈移位寄存器的工作原理,它由三个寄存器和

两个异或运算器组成。

在图3-1所示的线性反馈移位寄存器中,每增加一次计算,每个盒子中的比特被移到

另一个盒子中作为输入,用异或运算表明其引入的比特的模2加法。比特xm 
即输出和明

文的下一个比特异或产生的密文。图3-1中,当x0,x1,x2 的初始值被确定后,这个运算

器就可以高效率地产生随机比特流。

但是,这种加密方法容易受到已知明文的攻击。一旦得知一段连续的明文比特及其

相对应的密文比特就能异或得到相应的密钥,再通过求解线性方程组就可以确定递推关

系,因此由递推关系和部分密钥就可以计算出密钥的所有比特。

42 


第3章 流密码 
图3-1 一个满足xm +2=xm +1+xm 的线性反馈移位寄存器 
3.2 流密码 
流密码一般由初始化和密钥生成两个阶段组成,其主要包含密钥加载算法与迭代算
法。初始化阶段首先调用密钥加载算法将短密钥k(有时也被称为种子)以及可选的初始
化向量IV 加载到密码的内部状态中。然后多次调用迭代算法来更新内部状态,形成生
成密钥流的初始状态st。初始化阶段的目的是混淆,使攻击者无法确定k、IV 与st 的关
系。然后在密钥生成阶段重复调用迭代算法并输出近似随机的无限比特流。无IV 的流
密码应该像伪随机生成器一样,即当密钥k 是均匀的时,生成的比特序列应该与一串独立均
匀的比特无法区分。当流密码使用IV 时,它应该像伪随机函数一样工作,也就是说,只需改
变初始化向量IV 的值而输入k 保持不变,就能够生成一串序列与独立均匀的比特序列。
LFSR输出比特之间的线性关系导致了采用该部件设计的流密码无法抵抗相关攻击、
代数攻击等方法。为了阻止这些攻击,必须引入一些非线性,即使用秘密值的与操作而不仅
是异或操作。以下是常用的几种增加非线性度的方法,在一些流密码方案中这些方法也会
组合出现。
非线性反馈:使用高于一次的反馈函数作为反馈移位寄存器(feedbackshift 
registers,FSR)。换句话说,如果t 时刻状态为x(t) m -1,…,x(0t),那么下一时钟的状态为
x(t+1) i =x(t) i+1, i=0,…,m -2 
x(t+1) m-1 =f(x(t) m-1,…,x0(t)) 
其中,f 为精心选取的非线性函数,其目的是使攻击者难以通过某时刻的部分状态计算出
其他时刻的状态。使用此设计的流密码有Grain系列、Trivium 等。
非线性滤波:在输出序列中产生非线性。也就是寄存器状态仍然可以用LFSR 更
新,只是每个时钟的输出值是当前状态的一个非线性函数g,而不仅是最右侧的寄存器
值。采用此设计的流密码有SNOW、ZUC等。
非线性组合:以多个独立的LFSR输出作为一个非线性布尔函数g 的输入,以各个LFSR 
的输出作为密钥流的输出。这个方式被称为非线性组合器。采用此设计的流密码有E0。
当然,使用以上方法得到的密钥流还需要满足平衡性(0与1的个数几乎相同)、长周
期、高非线性度(与线性函数的输出序列相似性低)等性质。下面将介绍三种不同结构的流密
码:基于非线性反馈移位寄存器的Trivium、基于置换的ChaCha20和基于非线性滤波的ZUC。
43

现代密码学概论(第2版) 
3.2.1 
Trivium 
2008年欧洲完成的eSTREAM新型流密码项目的最终方案有3个适用于受限硬件
环境,即Grainv0和Trivium 。其中,Trivium流密码不仅结构简单而且硬

1、MICKEY2.
件实现紧凑[10],其结构如图3-2所示。首先,方案的主要器件只有三个级数分别为93 、84 、
111的NFSR,记为A,B,C。其次,Trivium的输出序列仅为6个寄存器的异或,即在每个

t)t)t)t)t)t)t)

FSR中选取最右侧寄存器和另一个寄存器:Z(=66 ..A(69 ..B(66 ..C(。

A(93 ..B(84 ..C(111 


图3-
2 
Trivium 
内部结构图

Trivium的内部是互相耦合的:每个时钟周期,每个FSR最左侧寄存器的更新值是
由同一个FSR中的某一个寄存器和另一个FSR部分寄存器共同计算得到[11]。三个非线
性反馈函数具体如下所示。

t+1) t)t)t)t)t)

A(C(

1 =109 ∧C(111 ..A(

66 ..C(110 ..C(
t+1) t)t)t)t)((69) 

B(=A(91 ∧A(93 ..Bt)

1 66 ..A(92 ..A(78 

t+1) t)t)t)t)t)

=69 ..B(83 ..B(

C(B(82 ∧B(84 ..C(

Trivium的初始化算法(1) 接受80比特密钥和80比特IV。首先,(87) 密钥和IV 
分别加载
到A和B的左80个寄存器中,对于
C 
的3个最右寄存器被赋值为1,其余寄存器设置为
0。然后运行Next4×288次时钟周期(丢弃输出),并将结果状态作为初始状态。

流密码的侧信道攻击

侧信道攻击(side-channelatack,SCA)指攻击者利用密码算法与其所运行的物理
设备交互过程中泄露的信息来展开攻击。近几十年来,该攻击相关研究主要集中在针
对分组密码方案来提高攻击效果或提出新颖的抗攻击方法。2022年,S.Kumar等组
合机器学习、混合整数线性规划、可满足性模理论开发了一个自动化框架[12],可在任何
流密码或类似结构上执行SCA 。这种攻击不但可以恢复例如Trivium方案的内部状
态,还能逆向得到其初始密钥。

44 


第3章 流密码 
3.2.2 ChaCha20 
ChaCha是D.J.伯恩斯坦(D.J.Bernstein)于2008年设计的流密码方案,本节介绍
的ChaCha20为Chacha类中一个有20轮运算、96比特随机数、256比特密钥的特例方
案[13]。ChaCha20结合了Poly1305消息验证码以构造TLS协议中面向软件的高性能认
证加密方案,旨在替代已经不安全的RC4 算法。ChaCha20-Poly1305 是OpenSSH、
WireGuard、OTRv4和比特币闪电网络中默认的关联数据认证加密(authenticated 
encryptionwithassociateddata,AEAD)方案[14]。ChaCha20主要思想如下。
此算法的核心是一个精心选取的固定置换P ,其具有既高效又密码学高强度的特点。
为了提高效率,它被设计为主要依赖在32比特字上运行的三个汇编级指令:模232加
(addition),循环逐比特旋转(rotation)以及异或(Xor);P 也因此被称为基于ARX 的设
计。从密码学的角度来看,P 可以是一个“随机置换”的实例,并且基于P 的构造方法可
以用随机置换模型分析。与随机预言机模型相比,随机置换模型假设所有参与方都可以
调用关于一个均匀置换P 及其逆P -1的预言机。就像在随机预言机模型中一样,计算P 
或P -1的唯一方法就是直接询问这些预言机。
在ChaCha20中,512比特的置换P 用于构造一个伪随机函数F,该函数根据256比
特密钥值将128比特输入映射到512比特输出,如下所示。
Fk(x)=P(const||k||x)(const||k||x 
其中,const为4个32比特字0x61707865,0x3320646e,0x79622d32,0x6b206574组成的
常数,(为逐字模加操作。如果P 是随机置换,可以证明F 就是一个伪随机函数。
给定一个256比特种子s 和一个初始向量IV∈{0,1}64,ChaCha20流密码输出是Fs 
(IV||<0>),Fs(IV||<1>),…,其中计数器<0>,<1>,…,均代表64比特整数。明
文长度如果不是512的倍数时将填充0,之后逐比特异或密钥流就能得到密文。
3.2.3 ZUC 
ZUC(祖冲之密码)是由冯登国院士团队研制的一种基于字的商用流密码算法,是
LTE (longtermevolution)国际移动通信标准的核心部分。该算法包括祖冲之算法
(ZUC)、加密算法(128-EEA3)和完整性算法(128-EIA3)三个部分[15]。
它以128-bit的初始密钥KEY 和128-bit的初始向量IV 作为输入,算法的输出为位
宽32-bit的字序列。整个ZUC 加密算法的运行按照工作性质可分为两个阶段:初始化
阶段和工作阶段。在初始化阶段,算法运行32轮但不输出密钥流,目的是让内部状态和
初始密钥的关系尽可能地无法预测,从而得到近似随机的内部状态。在工作阶段,算法每
完成一次运算后输出一个32-bit的密钥字,其具体的执行过程会在后文中算法执行部分
详细描述。ZUC 加密算法从逻辑上可以分为三层,从上到下依次为线性反馈移位寄存器
(LFSR)层,比特重组(BR)层和非线性函数(F)层,其基本结构如图3-3所示。方案生成
的密钥流可以用来加密解密或实现消息完整性认证。
与大多数流密码的LFSR设计不同,ZUC的LFSR基于有限域GF(231-1),其目的
是在不牺牲效率的条件下提供一定的安全性。LFSR 为16个字的寄存器S=(s0,…,
45

现代密码学概论(第2版) 
图3-
3 
ZUC 
内部结构图

s15), 每个寄存器si 
(
有31 比特,

t+1 时刻反馈函数输出字

t+1) 15t17t21t20tt

s15 =2s15+213+210+24+ 
(28+1)s0 

因其线性反馈函数为本原多项式,所(s) 以LFS(s) R的周期(s) 为(231-1)16-1≈2496 。换句话
说,ZUC 像其他流密码方案中的LFSR 一样有序列周期长、统计特性好的优点。而且由
于任意a∈GF(231-1)都可以表示为a=a31231+a30230+a020,其中ai∈GF(2)。换句话

46 


第3章 流密码 
说,a 可以用向量表示,GF(231-1)上的乘法可以用左移位和加法快速实现,因此,LFSR 
层避开了GF(2)上已经成熟的序列分析方法还能保证较高的实现效率。
BR层有四个32比特寄存器X0,X1,X2,X3,其中存储的每个值都是由LFSR 中两
个状态的各16比特信息级联而成,如下所示。
X0 =s15H‖s14L 
X1 =s11L‖s9H 
X2 =s7L‖s5H 
X3 =s2L‖s0H 
例如,两个31 比特寄存器s15 =0x12345678,s14 =0x1abcdef2,那么X0 = 
0x2468def2。虽然重组操作仍然是一种线性变换,但经过重组后的输出序列能够更快地
做出变化。
F 层旨在为保密算法提供混淆与扩散性的同时降低对移动通信设备的硬件资源占
用。其F 函数包含三个主要部件:两个32比特寄存器R1、R2,两个32比特到32比特
的线性变换L1、L2以及两个8进8出S 盒S0和S1。F 函数将BR层3个寄存器X0、
X1、X2 压缩为一个32比特字W ,与此同时使用线性变换和S 盒置换更新寄存器R1、
R2。两个线性变换在S 盒变换操作前,实现信息跨S 盒间的扩散,表达式如下。
L1(X )=X ..(X <<<322)..(X <<<3210)..(X <<<3218)..(X <<<3224) 
L2(X )=X ..(X <<<328)..(X <<<3214)..(X <<<3222)..(X <<<3230) 
其中,X <<<32k 表示对32比特字X 循环左移k 位,..为逐比特异或。线性变换后的32 
比特输出再通过4个小的S 盒进行局部混淆,这4个S 盒由两个非线性S 盒S0和S1 
(见表3-1、表3-2)组合而成,即
S(X )=S0X ( .24) S1(X .16∧0xff) S0(X .8∧0xff)||S1(X ∧0xff) 
表3-1 S 盒S0 
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 
00 3e 72 5b 47 ca e0 00 33 04 d1 54 98 09 b9 6d cb 
01 7b 1b f9 32 af 9d 6a a5 b8 2d fc 1d 08 53 03 90 
02 4d 4e 84 99 e4 ce d9 91 dd b6 85 48 8b 29 6e ac 
03 cd c1 f8 1e 73 43 69 c6 b5 bd fd 39 63 20 d4 38 
04 76 7d b2 a7 cf ed 57 c5 f3 2c bb 14 21 06 55 9b 
05 e3 ef 5e 31 4f 7f 5a a4 0d 82 51 49 5f ba 58 1c 
06 4a 16 d5 17 a8 92 24 1f 8c ff d8 ae 2e 01 d3 ad 
07 3b 4b da 46 eb c9 de 9a 8f 87 d7 3a 80 6f 2f c8 
08 b1 b4 37 f7 0a 22 13 28 7c cc 3c 89 c7 c3 96 56 
09 07 bf 7e f0 0b 2b 97 52 35 41 79 61 a6 4c 10 fe 
0a bc 26 95 88 8a b0 a3 fb c0 18 94 f2 e1 e5 e9 5d 
0b d0 dc 11 66 64 sc ec 59 42 75 12 f5 74 9c aa 23 
0c 0e 86 ab be 2a 02 e7 67 e6 44 a2 6c c2 93 9f f1 
47

续表 
现代密码学概论(第2版) 
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 
0d f6 fa 36 d2 50 68 9e 62 71 15 3d d6 40 c4 e2 0f 
0e 8e 83 77 6b 25 05 3f 0c 30 ea 70 b7 a1 e8 a9 65 
0f 8d 27 1a db 81 b3 a0 f4 45 7a 19 df ee 78 34 60 
表3-2 S 盒S1 
0 1 2 3 4 5 6 7 8 9 0a 0b 0c 0d 0e 0f 
0 55 c2 63 71 3b c8 47 86 9f 3x da 5b 29 aa fd 77 
1 8c c5 94 0c a6 1a 13 00 e3 a8 16 72 40 f9 f8 42 
2 44 26 68 96 81 d9 45 3e 10 76 c6 a7 8b 39 43 e1 
3 3a b5 56 2a c0 6d b3 05 22 66 bf dc 0b fa 62 48 
4 dd 20 11 06 36 c9 c1 cf f6 27 52 bb 69 f5 d4 87 
5 7f 84 4c d2 9c 57 a4 bc 4f 9a df fe d6 8d 7a eb 
6 2b 53 d8 5c a1 14 17 fb 23 d5 7d 30 67 73 08 09 
7 ee b7 70 3f 61 b2 19 8e 4e e5 4b 93 8f 5d db a9 
8 ad f1 ae 2e cb 0d fc f4 2d 46 6e 1d 97 e8 d1 e9 
9 4d 37 a5 75 5e 83 9e ab 82 9d b9 1c e0 cd 49 89 
0a 01 b6 bd 58 24 a2 5f 38 78 99 15 90 50 b8 95 e4 
0b d0 91 c7 ce ed 0f b4 6f a0 cc f0 02 4a 79 c3 de 
0c a3 ef ea 51 e6 6b 18 ec 1b 2c 80 f7 74 e7 ff 21 
0d 5a 6a 54 1e 41 31 92 35 c4 33 07 0a ba 7e 0e 34 
0e 88 b1 98 7c f3 3d 60 6c 7b ca d3 1f 32 65 04 28 
0f 64 be 85 9b 2f 59 8a d7 b0 25 ac af 12 03 e2 f21 
其中,X .k 表示对32比特字X 右移k 位。非线性函数F 的伪代码如下。
F(X0,X1,X2) 
{ 
W =(X0..R1)(R2 
W1=R1(X1 
W2=R2..X2 
R1=S(L1(W1L||W2H)) 
R2=S(L2(W2L||W1H)) 
returnW 
} 
其中,(为模232加法。
加密算法(128-EEA3)和完整性算法(128-EIA3)均基于ZUC算法,前者使用对称密
钥初始化,再用生成的密钥流逐比特异或明文进行加密。后者使用另一个密钥(即完整性
48

第3章流密码
密钥)来初始化,生成密钥流后,将密钥流根据明文的值以累加到一个32 比特的累加器中
以生成最终的MAC 。

ZUC 
密码研究新进展

冯登国教授(如图3-4所示)团队于2016 年起草发布了国家
标准《信息安全技术祖冲之序列密码算法》的第一部分[16],此部
分保证祖冲之序列密码算法使用的正确性,为国内企业正确研
发祖冲之算法的相关设备提供指导。2021 年,冯教授团队继续
完善ZUC 算法标准的剩余部分,包括保密性算法[17]和完整性
算法[18]。这两部分主要适用于基于祖冲之序列密码算法的保
密性算法和完整性算法的相关产品的研制、检测和使用。图3-
4 
冯登国教授


3.3
小结

本章首先引入了多个伪随机序列生成器以替代保存足够长的完全随机密钥,介绍了
伪随机序列生成的一般方式,接着讲解了伪随机序列生成的例子,也是研究最为广泛的
LFSR 及其序列,并阐述其优缺点。之后分析了流密码方案的工作流程,介绍了几种主要
密码学器件。最后介绍了三种不同结构的流密码方案:Trivium 、ChaCha20 以及国产
ZUC 密码。在实际应用中,往往精心设计的流密码方案可以用于存储及计算资源受限且
需要高性能的设备中。

思考题

1. 下图是一个4级LFSR,它的输出序列最小周期是多少? 请给出一个初试状态并
计算相应的一个周期的输出序列。
2. 下图是一个4级LFSR,它的输出序列最大周期是多少? 请给出一个初试状态并
计算相应的一个周期的输出序列。
49 


现代密码学概论(第2版) 
3. 对于一个仅用LFSR 的流密码方案,已知用户从
t 
时刻起发送的明文为01001101 
100110,并截获其密文为01100011110001 。
(1)请确定该LFSR 的级数和
t 
时刻的内部状态。
(2)求LFSR 的反馈系数并画出该LFSR 的电路图。
4. 两个LFSR 的线性移位寄存器A、B,其级数分别为2、3,它们由如下方法互相耦
合而成: 
t+1) t) t)

A(B(

2 =..B(
B(=A((1) ..A((3) 

t+1) t) t) 

t+1)t) t) t) t)

求Z(=1..A(1..B(生(3) 成序列的(1) 最大周(2) 期。

A(2..B(

已知一个GF(上的5级(3) s0,…,每个s1,…,7}, 如果反
馈函数为本原多项式f(x)≡x5+x3+x2+x+1(mod7), 那么该寄存器输出序列最大
周期是多少? 

5. 
7) LFSRS=(s4), 
i 
取值为{
50