第
3 
章　轻量级流密
码


3.
1. 
1 
1.3
概述
流密码一般性设计原理

1949年,Shannon证明了一次一密体制在唯密文攻击下是理论上不可破译和绝对安全
的;然而,为了建立一次一密的密码系统,通常需要在安全信道上交换传输至少和明文一样
长的密钥,在很多情况下是不现实和不经济的,并且在密钥的产生和管理方面也面临着许多
复杂问题。流密码算法本质上是对一次一密体制的模仿,同时消除了密钥产生、分配和管理
维护中的各类问题。流密码所产生的密钥流至少要做到看起来很像随机比特序列,且要求
恢复算法的初始状态和密钥或者将算法及其密钥流与随机情况区分开来都是在一定计算能
力与许可范围内困难的。

流密码一般可分为同步流密码和自同步流密码两大类。在同步流密码中,生成的密钥
流和发送的明文消息之间相互独立,其内部状态仅仅依赖于上一时刻的内部状态,与输入明
文无关。同步流密码的优点在于其有限的错误传播,当一个符号在传输过程中发生错误后
不会影响后续的符号。而自同步流密码的密钥流则依赖之前的明/密文信息,常见的自同步
流密码是类似于分组密码密文反馈模式的自同步流密码,即密文参与密钥流的生成过程,这
使得这类流密码的安全性从理论上分析起来非常困难,也造成这类算法的设计非常稀少。
目前常见的大多数流密码算法都是同步流密码,因其设计上的可分析性,使得设计者能够更
好地理解自己设计的流密码对于已知甚至某些未知攻击的抵抗力。从总体上说,一个流密
码的安全性在很大程度上取决于其采用的密钥流生成器,由于以线性反馈移位寄存器
(LFSR)为研究对象的伪随机序列代数理论的成熟,20世纪五六十年代以来的大量流密码
多是基于LFSR设计,例如美国未公开的Fibonaci生成器、E0 、A5/1等。由于LFSR的线
性性质对于密码分析没有任何免疫力(如Berlekamp-Masey算法等),需要采用各种非线
性部件来显式或隐式地掩盖线性性质并增强其非线性,常见的方法有非线性组合、非线性滤
波、不规则钟控、带记忆及其各种组合方式。Rueppel给出了此类流密码设计的一些方法和
准则,比如著名的线性驱动部件加非线性组合部件的设计范式[285]。这些方法和准则代表
了传统的流密码设计思路及其衍生准则,其中一些已经很少见,另一些的影响则仍然存在。
21世纪伊始,由于代数攻击的提出,传统的基于LFSR的流密码设计方案进一步丧失了其
吸引力。

2000年,欧洲提出了NESSIE(NewEuropeanSchemesforSignatures,Integrity,and 
Encryption,欧洲新签名、完整性和加密方案)计划。这个计划一直持续到2003年,其目标
之一就是征集新的流密码算法,但很遗憾的是,研究者提交的所有流密码算法,包括较为著
名的SNOW1.LILI128等,在安全性方面都存在一些问题,最终没有一个流密码能够入

0、
选。为了进一步推动流密码的发展,2004年欧洲启动了ECRYPT计划,其中就包含了专门
面向流密码的eSTREAM计划,其主要目标是征集一些新的流密码算法,以便于日后广泛


轻量级密码学

应用。eSTREAM计划共征集到34个算法,总体来看,算法设计思路多样化,且大多数不再
局限于传统的基于LFSR的结构,而是采用了一些新的设计思路,比如采用非线性反馈移
位寄存器、采用类似分组密码的结构等。具体来讲,eSTREAM计划将流密码算法分为两
大类:面向受限硬件环境的算法,比如Grainv1、Trivium和Mickeyv2等,这些算法一般采
用比特级的操作;面向高速软件应用的算法,比如Salsa20/12 、SOSEMANUK 、Rabbit和
HC等[286,287],这些算法大都采用面向字的操作。eSTREAM计划明显地影响了流密码的发
展进程,其后流密码的研究很快陷入沉寂,这主要是由于学术界对于大量采用极大内部状态
和极高初始化轮数的新型流密码算法普遍缺乏有效的分析思路和办法,这一状况一直持续
到现在。其间虽有立方攻击、扩域上快速相关攻击等新方法的提出,但对于采用极大内部状
态和极高初始化轮数的流密码,短时间内还是无法获得快于穷搜索的攻击。

在ESC2013上,一项新的对称密码算法竞赛项目被提出,称为CAESAR竞赛,其目的
是征集认证加密算法。传统的单一目的对称密码算法及其组合在某些情况下已经无法满足
实际应用的需求,新的应用趋势是在确保机密性的同时也要保证信息的完整性,这就是
CAESAR竞赛的初衷。从提交的算法来看,基于流密码的候选算法的主要思想仍然是
eSTREAM计划最终入选算法的组合与改进,变化只是在传统的加密模块之外增加的认证
模块以及采用杂凑函数结构设计的流加密算法。最近,为了满足同态加密应用环境的需求, 
在Eurocrypt2016上,一个新的流密码结构被提出,称为置换滤波生成器,这种结构可以看
作滤波生成器的一个变体,它以人为的形式模拟产生大量固定次数、固定形式的代数等式, 
以满足同态加密应用环境的需求。

3..轻量级流密码研究进展

12 

回顾历史可以发现,欧洲eSTREAM计划最终入选算法即包括了适用于硬件实现的轻
量级流密码算法,比如Grainv1、Trivium及Mickeyv2等。以Grainv1为例,它由Martin 
Hel 
等人设计,算法分为密钥流产生和初始化两个阶段,密钥长度为80比特,也有采用128 
比特密钥的Grain-128和Grain-128a,这些流密码算法均比较适合RFID等资源受限环境。
Trivium算法虽然结构简单,但目前并没有发现明显的安全性漏洞,而且具有轻量级的显著
特点。此外,还有一些专门为RFID标签设计的轻量级流密码,比如WG-7算法和A2U2 
算法。WG-7算法的密钥长度为80比特,初始向量为81比特,是专门为RFID应用而设计
的流密码算法。虽然设计者给出了一定前提下的安全性分析证明[288],力图说明WG-7算
法能够有效抵御差分分析、代数攻击、相关攻击等分析方法,但已经有一些密码分析结果表
明该算法并不能提供80比特的安全性。A2U2也是专用的轻量级流密码,它结合了流密码
的设计原则和某些分组密码的设计方法,考虑了资源受限设备的特点,其硬件实现代价较
低。但是,已有密码分析结果表明A2U2的设计并不成功。WG-7和A2U2的例子可以说
明,轻量级流密码的设计绝非易事。

纵观近年推出的轻量级流密码算法,可以观察到两条明显的技术路线:第一条路线采
用较大的内部状态与相对简单的逻辑运算;第二条路线采用较小的内部状态与相对复杂的
逻辑组合函数。第一条路线采用通常的流密码设计思路,尽可能降低算法的逻辑运算占用
的硬件资源;第二条路线却反其道而行之,采用较小的内部状态,即内部状态小于密钥长度
的两倍,但在密钥流生成阶段却采用了依赖于初始密钥的状态更新函数,这种轻量级流密码


第
3 
章　轻量级流密码

现在一般称为小状态流密码。

第一条路线的一个典型代表是CAESAR竞赛入选算法ACORN 。虽然可以看出
ACORN算法与Grain系列算法的明显关系,即Grain系列算法只是把非线性反馈加在中
间,而ACORN算法则将反馈加在了最远的反馈端,但ACORN算法采用的逻辑运算比较
简单,非线性运算只包含了数个逻辑与门,线性运算则有多个逻辑异或门,其扩散性由6个
级联的线性移位寄存器来保证。在某些特定硬件平台上,该算法的实现较为简便。
ACORN允许多拍并行运行,即同时输出多个连续的密钥流比特,这一特点既适合硬件实
现,也适合软件实现,可以说是同时面向软硬件的轻量级流密码算法。

第二条路线的轻量级流密码目前有多个典型算法,比如Sprout、Plantlet等。其核心设
计思想是:在密钥流生成阶段,采用依赖于密钥的状态更新函数重复利用密钥,以打破时
间/存储/数据折中曲线规定的复杂度限制,从而使得算法的内部状态可以小于密钥长度的
两倍。在这一大类算法之下继续细分,还可以观察到一种变形设计———FP(1)模式[289],它
在初始化阶段采用了再次异或密钥的方式,使得从初始状态求逆以恢复密钥变得代价高昂, 
这种轻量级流密码算法在密钥流生成阶段并没有采用依赖于密钥的设计方案,而是像经典
的流密码算法一样运行。从目前公开文献提出的算法来看,无论是哪种设计思路,其本质都
是基于Grain系列算法的结构设计的。

在上述第二条路线的两种设计思路中,前一种设计思路的代表性轻量级流密码算法有
Sprout、Fruit和Plantlet等。Sprout算法于2015年首次提出采用依赖于密钥的轻量级流
密码设计思想,试图在Grain-128a的基础上做一些避免后者弱点的修改,以更小的内部状
态提供同等的时间/存储/数据折衷攻击免疫力,因此可以有效降低算法的硬件实现面积。
Sprout算法在结构上与Grain算法相似,它包括一个40比特的NFSR 、一个40比特的
LFSR 、一个80比特的固定密钥寄存器和一个计数器。由于存储固定密钥要比一般的寄存
器节省硬件面积,所以Sprout算法可以获取一定的硬件实现上的收益。但是Sprout算法
公布不久,就有人找到了有效的分析方法,特别值得注意的是这些有效分析甚至包含了算法
设计时试图避免的时间/存储/数据折中攻击[290-293]。

Sprout算法的设计思想激发了其他新的轻量级流密码算法,例如Fruit(Fruit算法版本
几经变动,较新的一个版本可参考文献[294 ])。Fruit算法采用了43比特的LFSR 、37比特
的NFSR 、80比特的固定密钥寄存器以及两个长度分别为7比特和8比特的计数器。但是
该算法仍然不安全,存在Lalemand-like攻击[295]以及ESC2017上公布的相关攻击,快速
Walsh变换在攻击中起到了重要作用。Fruit的设计者随后又对算法进行了调整,但仍然不
能有效避免攻击。

Plantlet是对于Sprout算法的另一个重要的改进,它继承了Sprout算法的基本结构, 
也是Grain系列算法族中的一员。Plantlet设计的主要目的是修补Sprout算法的安全缺
陷,以达到以下的设计目的:80比特寄存器状态同时满足小面积要求和保证安全性,即使
密钥永久存储并连续读取于可重写非易失存储器(Non-VolatileMemory,NVM)中,算法仍
具有硬件友好性,不依赖于背后的NVM技术,能保持较高的吞吐率。Plantlet算法采用了
61比特LFSR 、40比特NFSR和一个计数器,但对密钥的使用方式进行了简化设计。
Plantlet算法自公布以来,还没有人公布有效的分析方法。2017年,MathiasHamann等学
者研究了对于小状态流密码的时间/存储/数据折中分析,给出了Plantlet算法的一个分析


轻量级密码学

结果[296]。

尽管算法运行过程中使用依赖于密钥的状态更新函数在理论上具有一定的意义,而且
可以减小硬件实现面积,但是在实际上不是这样。原因有两个。一是由于密钥并不是固化
到器件上的,而是存储到EEPROM中的,所以持续访问密钥会减低KSG的时钟频率。特
别当访问不是按顺序进行的时候,该问题尤其突出(例如在Fruit算法中)。同时,这种密钥
访问的能量消耗也较大,RFID标签执行一次EEPROM读操作,需要5~10μW,执行一次
写操作更是需要50μW,而RFID 标签的能量消耗预算仅为10μW。为了避免使用
EEPROM的缺点,可将密钥移到可变存储器中,但这又会使硬件实现面积增加。二是若密
钥固化到器件上,虽然可以解决持续访问密钥的代价问题,但还需要考虑密钥的生命周期, 
即每个密钥可与多少初始向量搭配使用。

鉴于持续访问密钥带来的问题,MathiasHamann等人提出了Lizard算法。Lizard算
法也是Grain系列算法族中的一员,但是与Sprout、Plantlet等的设计思想不同,Lizard算
法采用FP(1)模式,以获得对于时间/存储/数据折中攻击的可证明安全性,达到减少内部状
态规模的目的(从160比特减少到121比特),而且由于同时采用了更强的输出函数与更大
规模的密钥(从80比特增加到120比特),Lizard算法目前并没有发现有效的分析方法。设
计者认为Lizard算法可以避免频繁访问存储密钥的EEPROM带来的开销。Lizard算法的
设计安全性为80比特的状态恢复攻击安全性与60比特的区分攻击安全性,并且由于使用
了FP(1)模式,其对基于时间/存储/数据折中攻击的密钥恢复攻击的安全性可达到超越生
日界的安全性2n/3。

观察近年来轻量级流密码发展,可以看出其未来研究的一些端倪,主要有以下4点。一
是对于资源受限的定义[297,298]。二是针对特殊应用,以优化的设计来达到安全轻量的目的。
例如,Lizard算法是针对小包模式的优化设计,即每个Key/IV对至多生成218比特密钥流
(设计者称这足以满足SSL/TLS 、11等多数协议的要求)。三是可证明安全性,

IEEE802.
即一个轻量级流密码算法设计上的安全性是否是可证明的。四是关于密钥恢复或区分攻
击,经典的时间/存储/数据折中攻击安全界是否可以改进。无论如何,相关问题研究与轻量
级流密码的发展必会相互影响、相互促进[299]。

3.基于LFSR的流密码
2 

3../1

21 
A5

A5/1是GSM网络中保障通信私密性的流密码算法。它最初是保密的,直到1994年
才被逆向工程。A5系列算法有多个变种。其中A5/1安全性最强,被用于欧洲和美国;A5/2 
用于欧美以外地区;A5/3是为第三代合作伙伴计划(3rdGenerationPartnershipProject, 
3GPP)设计的加密算法。由于这3个算法在实际应用中通常使用相同的会话密钥,攻破安
全性较弱的算法会导致其余两个算法的安全问题。

A5/1的内部状态为64比特,密钥长度为64比特,已知的初始化向量长度为22比特。
完成内部状态初始化后,内部状态转移依赖一个择多(majority)钟控函数。A5/1产生的密
钥流为每帧通信的双方各提供114比特。


第3 章　轻量级流密码1 21 
1.A5/1的结构
A5/1算法由3个长度分别为19、22、23比特的线性反馈移位寄存器R1、R2、R3组成,其
结构如图3-1所示。其中,R1[8]、R2[10]和R3[10]是钟控位,R1[13,16,17,18]、R2[20,21]和
R3[7,20,21,22]是反馈位。
图3-1 A5/1的结构
2.A5/1的伪随机比特生成算法
A5/1的加密算法由内部状态初始化和伪随机比特生成两个阶段组成。内部状态初始
化可用伪代码描述如下: 
for i from 0 to 63 do 
R1,R2 and R3 are clocked 
R1[0]=R1[0].. K [i ] 
R2[0]=R2[0].. K [i ] 
R3[0]=R3[0].. K [i ] 
end for 
for i from0 to 21 do 
R1,R2 and R3 are clocked 
R1[0]=R1[0].. Fn [i ] 
R2[0]=R2[0].. Fn [i ] 
R3[0]=R3[0].. Fn [i ] 
end for 
初始化过程完成后的寄存器状态称为初始状态。
接下来要进行的是依赖择多钟控函数的停走。择多钟控函数为
Maj=a·b ..b·c ..c·a 
该函数的输入为R1[8]、R2[10]和R3[10],并且钟控位与Maj值一致的寄存器进行移位。
进行100轮择多钟控停走后,继续进行228 轮择多钟控停走,每轮停走后产生一个伪随机
比特作为加解密的密钥流。每轮停走产生的密钥比特为
zi= R1[18].. R2[21].. R3[22] 
上述过程用伪代码描述如下:

1 22 轻量级密码学 
for i from 0 to 99 do 
R1,R2 and R3 are clocked with the majority-based clock control 
end for 
for i from 0 to 227 do 
R1,R2 and R3 are clocked with the majority-based clock control 
zi =R1[18].. R2[21].. R3[22] 
end for 
3.A5/1的加解密
A5/1的加密算法是将明文比特串与A5/1生成的伪随机比特进行模2 加法。解密算
法是加密算法的逆。加解密过程如下: 
Ci=Pi..zi 
Pi=Ci..zi 
4.A5/1的安全性
A5/1自1994年被逆向工程出来后得到了广泛的关注,经受了各种攻击的考验。1997 
年,Golic对A5/1进行了已知输出密钥流的分治攻击[300]。首先重建初始状态,然后由此确
定密钥。分治攻击的平均计算复杂度是240.16;然后又提出了基于生日悖论的时间/存储折
中攻击。此攻击的目标是:对于已知输出密钥流,找出在某个已知时刻的未知内部状态。
2000年,Biham 等人提出一种猜测确定攻击[301]。假设R3连续10轮没有进行状态更
新,这样就可以得到大约31比特的寄存器信息。假设已知R3[10]和R3[22],即可知这10 
轮中R1和R2的钟控位。猜测R2[0]和R1[9,10,11,12,14,15,16,17,18]来确定R3的未
知比特。采用这种攻击方式,预计算复杂度是233.6,数据复杂度是220.8 比特,存储空间是
2GB,时间复杂度是240.97。
Biryukov等人使用一台PC对A5/1进行了实时攻击[302]。他们用了两个方法:一是有
偏差的生日攻击,二是随机子图攻击。攻击以Golic的时间/存储折中攻击为基础,利用
A5/1内部状态的收缩,存储数量较少的初始状态,通过这些初始状态得到密钥。存储时利
用易于采样的特殊状态来减少存储量。有偏差的生日攻击需要2min的通信数据、2(或4) 
个73GB的硬盘和248(或242)步预计算,可在1s内恢复出密钥。随机子图攻击只需要2s的
通信数据,需要4个73GB硬盘和248步预计算,但是恢复密钥需要几分钟。
Barkan等人首先介绍了对A5/2的唯密文攻击,利用纠错码和校验矩阵恢复密钥[303]。
对A5/1的被动唯密文攻击也利用了相似的方法,同时结合了Biryukov等人的时间/存储
折中攻击。Ekdahl提出了对A5/1的一种相关攻击[304]。2008年,Maximov等人提出了改
进的相关攻击[305]。与此同时,Gendrullis等人利用特殊的硬件COPACOBANA 实现了实
际可用的攻击[306]。
Shah等人进行了猜测确定攻击[307]。猜测R1 的全部比特和输出密钥流比特,根据输
出密钥流比特方程和钟控位之间的关系确定R2和R3,成功率可达100%。但是,在寻找过
程中需要复制存储所有可能状态,需要的存储空间达5.6GB。这种攻击的平均时间复杂度
为248.5。
Lu等人提出了使用GPGPU 的时间存储折中攻击,他们称这个分析为统一的彩虹表分

第 
3 
章　轻量级流密码

析。他们可以用55 天完成一个984GB 的彩虹表,如果使用两个这样的彩虹表,并且使用
8个已知的114 比特密钥流,就能够以81% 的成功率完成9s的在线攻击[308]。

3..0

22 
E

E0 是用于蓝牙的流密码算法,密钥长度可变,最长为128 比特,初始向量(IV)长度为
74 比特(由48 比特蓝牙地址和26 比特主计数器构成)。蓝牙协议每帧最多处理2745 比
特,每一帧均由不同的初始向量加密,但是密钥在整个会话中保持不变。E0 和一般的流密
码相同,均由内部状态初始化和密钥流比特生成两部分组成。为了增加生成的伪随机序列
的长度和随机性,E0 采用了4个线性反馈移位寄存器。

1.E0 的结构
E0 由求和生成器演化而来,由线性反馈移位寄存器(4个)、组合逻辑电路和混合器3 
部分构成,其结构如图3-2所示。线性反馈移位寄存器作为输入,并结合4比特内存单元得
到密钥流。4个线性反馈移位寄存器的长度分别为25 、31 、33 和39 。它们的反馈多项式均
为有5个非零项的本原多项式,分别为
x25+x20+x12+x8+1

P1(x)=
P2(x)x31+x24+x16+x12+1

=
P3(x)=x33+x28+x24+x4+1 

P4(x)=x39+x36+x28+x4+1 


图3-
2 
E0 
的结构

混合器中T1 和T2 是线性变换网络,Z-1为延迟网络。Ct/St 
时刻
t 
的额外内存单
元值。


124
轻量级密码学

2.E0 的内部状态初始化和密钥流生成
产生密钥流时,线性反馈移位寄存器需要赋初值。初始值进入线性反馈移位寄存器的
过程如图3-3所示,此时4比特的额外内存单元置零。该初始化过程进行200 步。在这200 
步中,后128 比特再次作为线性反馈移位寄存器的初始值,额外内存单元的值Ct 
和Ct+1 被
保留,此时产生的输出即为通信密钥流。


图3-
3 
初始值进入LFSR 
的过程

其中,K'由密钥Kc 
变换得到的,最长为128 比特,ADR 为48 比特主设备地址,CL 

c 
Kc 
为26 比特时钟,
t 
为时刻
t 
第
i 
个线性反馈移位寄存器的输出。

xi 

3.E0 的安全性
对E0 的攻击最初出现在2000 年前后,Hermelin和Nyberg对蓝牙组合器进行了相关
攻击,证明了给出
O 
(264)长度的密钥流,128 比特密钥的蓝牙流密码可在O(264)步中被破
解[309]。Fluhrer等分析了E0 加密模式[310]。
[

2004 年,Lu等人对E0 进行了区分攻击和密钥恢复攻击311]。根据最大相关性的线性
依赖进行了区分攻击,提出了基于快速Walsh变换的最大似然解码算法。同年,他们又发
表了对两级E0 的密钥恢复攻击,给出了235 帧的前24 比特,进行了240 在线攻击[312]。文

8

献[313]将密钥恢复攻击提升至进行复杂度为238 的预计算,只需给出223.帧的前24 比特。

1

2013 年,张斌等人提出了一种新的攻击,给出222.7帧的前24 比特,进行复杂度为221.的
预计算,仅需4MB 内存即可在复杂度为227 的在线计算后恢复密钥[314]。2018 年,张斌等人
又提出了一种降低数据复杂度的新方法。在已知初始向量的情景下,给出224 帧的前24 比

1

特,进行复杂度为221.的预计算,仅需4MB 内存即可在复杂度为225 的在线计算后恢复密
钥。他们将攻击变为唯密文攻击,给出226 帧的前24 比特,恢复密钥的总复杂度低于226,这
是目前对蓝牙加密模式的第一个实用的唯密文攻击[315]。

3..nw20

23So.

Sn0是NESSIE 计划的候选算法之一。该算法面向软件设计,

ow2.采用了线性反馈移
位寄存器,结构比较简单,加解密速度快,固定初始向量为128 比特,密钥长度有两种,分别
是128 比特和256 比特。


第3 章　轻量级流密码1 25 
1.Snow2.0算法
1)加密流程
加密操作如下:首先是密钥初始化,它提供了线性反馈移位寄存器初始状态和有限状
态机(FiniteStateMachine,FSM)内部寄存器R1和R2的初始值。然后是整个加密流程进
行一次循环,生成一个密钥流字;接着再循环一次,生成一个密钥流字;后面依此类推,最终
生成的密钥流字不超过250个。加密流程如图3-4所示。
图3-4 Snow2.0算法的加密流程
Snow2.0是面向32比特字的流密码算法,伪随机生成器由有限域F232 上的16级线性
反馈移位寄存器构成。反馈多项式为
π(x)=αx16 +x14 +α-1x5 +1∈F232 [x] 
其中,α 是以下多项式的根: 
x4 +β23x3 +β245x2 +β48x +β239 ∈F28 [x] 
β 是以下多项式的根: 
x8 +x7 +x5 +x3 +1∈F2[x] 
非线性变换由FSM 来实现,密钥初始化后,开始整个循环迭代。FSM 有两个寄存器, 
分别表示为R1和R2,每个寄存器有32比特。在时刻t≥0时,这两个寄存器的值分别表示
为R1t 和R2t。FSM 的输入是(st+15,st+5),输出用Ft 表示,Ft 的计算公式如下: 
Ft =(st+15 (R1t).. R2t, t ≥0 
输出的密钥流用zt表示,zt 的计算公式如下: 
zt =Ft ..st, t ≥1 
而寄存器R1和R2更新如下: 
R1t+1 =st+5 (R2t 
R2t+1 =S(R1t), t ≥0 
2)S盒
S盒记作S(w ),是一个输入和输出均为32比特的非线性变换,它由4 个并置的8 比
特S 盒加换位变换构成。用w 表示S 盒的输入:

1 26 轻量级密码学
w = 
w0 
w1 
w2 
w3 
é
.
êêêêê
ê 
ù
.
úúúúú
ú 
应用AES的S盒,w 变成
w = 
SR [w0] 
SR [w1] 
SR [w2] 
SR [w3] 
é
.
êêêêê
ê 
ù
.
úúúúú
ú 
然后,进行列混合变换并输出r: 
r0 
r1 
r2 
r3 
é
.
êêêêê
ê 
ù
.
úúúúú
ú 
= 
x x +1 1 1 
1 x x +1 1 
1 1 x x +1 
x +1 1 1 x 
é
.
êêêêê 
ù
.
úúúúú 
SR [w0] 
SR [w1] 
SR [w2] 
SR [w3] 
é
.
êêêêê
ê 
ù
.
úúúúú
ú 
即r=S(w )。
3)密钥初始化
初始向量记作IV=(IV3,IV2,IV1,IV0),128比特密钥记作K =(k3,k2,k1,k0),256 
比特密钥记作K =(k7,k6,k5,k4,k3,k2,k1,k0)。
128比特密钥初始化如下: 
s15 =k3 ..IV0,s14 =k2, s13 =k1, s12 =k0 ..IV1, 
s11 =k3 ..1, s10 =k2 ..1..IV2,s9 =k1 ..1..IV3 s8 =k0 ..1, 
s7 =k3, s6 =k2, s5 =k1, s4 =k0, 
s3 =k3 ..1, s2 =k2 ..1, s1 =k1 ..1, s0 =k0 ..1 
其中1表示32比特全1向量。
256比特密钥初始化与上面类似: 
s15 =k7 ..IV0 s14 =k6 s13 =k5 s12 =k4 ..IV1 
s11 =k3 s10 =k2 ..IV2 s9 =k1 ..IV3 s8 =k0 
s7 =k7 ..1 s6 =k6 ..1 … s0 =k0 ..1 
在初始化过程中循环32轮,但不生成输出密钥流。Snow2.0的初始化流程如图3-5 
所示。
2.Snow2.0的安全性
Snow2.0虽然针对Snow1.0的弱点做了很大的改进,但是仍存在代数攻击、线性区分
攻击、快速相关攻击等。其中区分攻击针对Snow2.0所需的时间复杂度为2174,数据复杂
度为2174[316]。最新的快速相关攻击比原来的密钥恢复攻击已经有了很大的突破[317],所需
的时间复杂度为2164.15,数据复杂度为2163.59。Snow2.0算法是欧洲eSTREAM 计划的指定
比较算法,国际密码学界普遍认为Snow2.0是一个128比特密钥下的十分安全且高效的流
密码算法。

第3 章　轻量级流密码1 27 
图3-5 Snow2.0的初始化流程
3.2.4 Snow3G 
Snow3G是Snow1.0和Snow2.0的设计者为抵抗代数攻击而推出的又一个流密码算
法。由于其结构简洁,加解密速度快,安全性高,最终被选入3GPP 的机密性和完整性机制
UEA2和UIA2,成为第四代移动通信加密标准。Snow3G 是一个面向字的流密码算法,在
128比特密钥和128 比特初始向量的控制下,生成以32 比特字为单位的密钥流序列。
Snow3G的执行分为两个阶段:初始化阶段和工作阶段。第一阶段执行密钥初始化,即在
加密循环过程中不输出密钥流;第二阶段每轮循环都会输出一个32比特密钥流。
1.Snow3G算法组成部分
1)MULx 
MULx是从16比特到8比特的映射。令V 和c 为8比特的值,则MULx定义如下: 
如果V 的最左边(最高有效)比特为1,则
MULx(V,c)= (V =81)..c 
否则, 
MULx(V,c)=V =81 
2)MULxPOW 
MULxPOW 是从16比特和一个正整数i 到8比特的映射。令V 和c 为8比特的值, 
则MULxPOW(V,i,c)递归定义如下: 
如果i 为0,则
MULxPOW(V,i,c)=V 
否则, 
MULxPOW(V,i,c)=MULx(MULxPOW(V,i -1,c),c) 
3)32比特S盒S1 
S1 是32比特输入、32比特输出的非线性映射。令w =w0‖w1‖w2‖w3 为32比特
输入,w0 和w3 分别为最高有效字节和最低有效字节。使用AES的8比特S盒SR ,如下
计算32比特输出S1(w )=r0‖r1‖r2‖r3。
r0 = MULx(SR (w0),0x1B)..SR (w1)..SR (w2).. MULx(SR (w3),0x1B)..SR (w3) 
r1 = MULx(SR (w0),0x1B)..SR (w0).. MULx(SR (w1),0x1B)..SR (w2)..SR (w3) 
r2 = SR (w0).. MULx(SR (w1),0x1B)..SR (w1).. MULx(SR (w2),0x1B)..SR (w3)

1 28 轻量级密码学
r3 = SR (w0)..SR (w1).. MULx(SR (w2),0x1B)..SR (w2).. MULx(SR (w3),0x1B) 
4)32比特S盒S2 
S2 是32比特输入、32比特输出的非线性映射。令w =w0‖w1‖w2‖w3 为32 比特
输入,使用基于Dickson多项式导出的8比特S盒SQ ,如下计算S2(w )=r0‖r1‖r2‖ 
r332比特输出: 
r0 = MULx(SQ (w0),0x69)..SQ (w1)..SQ (w2).. MULx(SQ (w3),0x69)..SQ (w3) 
r1 = MULx(SQ (w0),0x69)..SQ (w0).. MULx(SQ (w1),0x69)..SQ (w2)..SQ (w3) 
r2 = SQ (w0).. MULx(SQ (w1),0x69)..SQ (w1).. MULx(SQ (w2),0x69)..SQ (w3) 
r3 = SQ (w0)..SQ (w1).. MULx(SQ (w2),0x69)..SQ (w2).. MULx(SQ (w3),0x69) 
5)函数MULα 
函数MULα 是8比特到32比特的映射。令c 为8比特输入,则MULα 定义如下: 
MULa(c)=(MULxPOW(c,23,0xA9)‖MULxPOW(c,245,0xA9) 
‖MULxPOW(c,48,0xA9)‖ MULxPOW (c,239,0xA9)) 
6)函数DIVα 
函数DIVα 是8比特到32比特的映射。令c 为8比特输入,则DIVα 定义如下: 
DIVα(c)=(MULxPOW (c,16,0xA9)‖ MULxPOW (c,39,0xA9) 
‖MULxPOW(c,6,0xA9)‖ MULxPOW (c,64,0xA9)) 
7)初始化模式
LFSR的初始化模式接收来自FSM 的32比特输出字F。
令s0=s0,0‖s0,1‖s0,2‖s0,3,s11=s11,0‖s11,1‖s11,2‖s11,3,其中s11,0和s11,3分别为最
高有效字节和最低有效字节。如下计算中间值v: 
v= (s0,1 ‖s0,2 ‖s0,3 ‖0x00).. MULα(s0,0)..s2 .. (0x00‖s11,0 ‖s11,1 ‖s11,2).. 
DIVα(s11,3)..F 
令
s0 =s1,s1 =s2, s2 =s3, s3 =s4, s4 =s5, s5 =s6, s6 =s7, s7 =s8, 
s8 =s9,s9 =s10,s10 =s11,s11 =s12,s12 =s13,s13 =s14,s14 =s15,s15 =v 
8)FSM 循环模式
FSM 有两个来自LFSR的输入字s15和s5,输出一个32比特的字F: 
F =(s15 (R1).. R2 
其中(是模232加法。
然后寄存器更新,计算中间值r: 
r =R2((R3..s5) 
令
R3=S2(R2) 
R2=S1(R1) 
R1=r 
2.Snow3G算法操作
1)初始化
Snow3G初始化使用128比特密钥和128比特初始向量,密钥包含4个32比特字k0, 
k1,k2,k3,初始向量包含4个32比特字IV0,IV1,IV2,IV3,定义如下:

第3 章　轻量级流密码1 29 
s15 =k3 ..IV0,s14 =k2, s13 =k1, s12 =k0 ..IV1, 
s11 =k3 ..1, s10 =k2 ..1..IV2,s9 =k1 ..1..IV3,s8 =k0 ..1, 
s7 =k3, s6 =k2, s5 =k1, s4 =k0, 
s3 =k3 ..1, s2 =k2 ..1, s1 =k1 ..1, s0 =k0 ..1 
其中1表示全1的字(0xFFFFFFFF)。FSM 初始化为R1= R2= R3=0。
然后加密,以一种特殊模式运行,不产生输出密钥流,伪代码描述如下: 
for t from 1 to 32 do 
1. The FSM is clocked producing the 32-bit word F . 
2. Then the LFSR is clocked in Initialisation Mode using F . 
end for 
Snow3G的初始化流程如图3-6所示。
图3-6 Snow3G 的初始化流程
2)密钥流生成
首先FSM 循环执行一次,但是丢弃FSM 的输出字。然后LFSR在密钥流初始化模式
执行一次。最后产生加密使用的n个32比特的密钥流字,伪代码描述如下: 
for t from 1 to n do 
3. The FSM is clocked and produces a 32-bit output word F . 
4. The next keystream word is computed as zt =F .. s 0. 
5. Then the LFSR is clocked in Keystream Mode. 
end for 
Snow3G的密钥流生成的流程如图3-7所示。
3.Snow3G安全性分析
到目前为止,还没有一种行之有效的方法可以完全破译Snow3G,但针对它的改进版
本的攻击已经可以在2124.2复杂度下达到16轮(初始化共33轮)[318]。针对Snow3G 算法的
密钥流生成阶段,目前最好的状态恢复攻击是文献[319]给出的结果,复杂度为2177。

1 30 轻量级密码学
图3-7 Snow3G 的密钥流生成流程
3.2.5 ZUC 
ZUC 算法(又称祖冲之算法)是我国自主设计的流密码算法,2011年被3GPPLTE 采
纳为国际加密标准,即第四代移动通信加密标准。ZUC 算法同时也是中国第一个成为国际
标准的密码算法,其标准化的成功是中国在商用密码算法领域取得的一次重大突破。与早
期同样被纳入3GPPLTE国际加密标准的Snow3G相比,在吞吐率相同的情形下,ZUC的
资源和功耗更小。
ZUC是面向字的流密码算法。它采用128比特初始密钥和128 比特初始向量作为输
入,执行算法后,输出一个32 比特字的密钥流。通信中使用此密钥流进行加密和解密。
ZUC 的执行分为两个阶段:初始化阶段和工作阶段。第一阶段,执行密钥和初始向量的初
始化,不产生密钥流输出;第二阶段,每一轮加密循环生成一个32比特密钥流。
1.ZUC算法描述
1)算法的一般结构
ZUC有3个逻辑层,如图3-8所示。顶层是一个16级的线性反馈移位寄存器(LFSR), 
中间层是比特重组层(BR),底层是一个非线性函数F(FSM)。
2)线性反馈移位寄存器
线性反馈移位寄存器(LFSR)有16个31比特的单元(s0,s2,…,s15)。每个单元si(0≤ 
i≤15)限定只能从集合{1,2,…,231-1}中取值。LFSR有两个操作模式:初始化模式和工
作模式。
在初始化模式下,LFSR收到一个31比特字u,它是由非线性函数F 产生的32比特字
w 移除最右边1比特得到的,即u=w ?1。伪代码描述如下: 
LFSRWithInitializationMode(u ) 
{ 
v =(215 s 15+217s 13+221s 10+220 s 4+(1+28)s 0) mod (231-1) 
s 16=(v +u ) mod(231-1) 
if s 16=0 then set s 16=231-1 
(s 1,s 2,…,s 16) → (s 0,s 1,…,s 15) 
}

第3 章　轻量级流密码1 31 
在工作模式下,LFSR不会收到任何输入,伪代码描述如下: 
LFSRWithWorkMode(u) 
{ 
s16=(215s15+217s13+221s10+220s4+(1+28)s0) mod (231-1) 
if s16=0, then set s16=231-1 
(s1,s2,…,s16) → (s0,s1,…,s15) 
} 
图3-8 ZUC算法的结构
提示1:31比特串s 在GF(231-1)上乘以2i 可以通过循环左移i 比特实现,比如,在
LFSR初始化模式第一步中,可以转换成下面的式子: 
v =(s15 3115)+ (s13 3117)+ (s10 3121)+ (s4 3120)+ 
(s0 318)+s0 mod(231 -1) 
提示2:对于在GF(231-1)上的两个整数a 和b,v=(a+b)mod(231-1)可以由下面
两步实现:①计算v=a+b;②如果进位是1,则设定v=v+1。另外,为了更好地抵抗可
能的计时攻击,有下面两个补充:①计算w =a+b,其中w 是一个32 比特的值;②设定
v=w 的最左边31位比特+w 的最右边的比特。
3)比特重组
ZUC算法的中间层是比特重组。它从LFSR中抽取128比特,生成4个32比特的字, 
前3个字用于底层非线性函数F,最后1个字参与密钥流生成。

1 32 轻量级密码学
令s0,s2,s5,s7,s9,s11,s14,s15为上述LFSR的8个单元。比特重组就是使用它们形成
4个32比特的字X0,X1,X2,X3,伪代码描述如下: 
Bitreorganization() 
{ 
X 0=s 15H ‖s 14L 
X 1=s 11L ‖ s 9H 
X 2=s 7L ‖ s 5H 
X 3=s 2L ‖ s 0H 
} 
提示:si 是31比特,所以siH 意味着比特下标为30~15,而不是31~16,其中0≤i 
≤15。
4)非线性函数F 
非线性函数F 有两个32比特内存单元R1和R2。令F 的输入为X0,X1,X2,它们来
自比特重组的输出,经过F 函数后生成一个32比特字W 。伪代码描述如下: 
F (X 0,X 1,X 2) 
{ 
W =(X 0 .. R 1) (R 2 
W 1=R 1(X 1 
W 2=R 2(X 2 
R 1=S (L 1(W 1L ‖ W 2H)) 
R 2=S (L 2(W 2L ‖ W 1H)) 
} 
其中,S 是一个32比特S盒:L1 和L2 都是从32比特到32 比特的线性变换,具体
如下: 
L1(X )=X .. (X 322).. (X 3210).. (X 3218).. (X 3224) 
L2(X )=X .. (X 328).. (X 3214).. (X 3222).. (X 3230) 
32比特S盒S 由4个8比特S 盒组成,即S = (S0,S1,S2,S3),其中S0=S2,S1= 
S3。S0 和S1 见表3-1和表3-2。令x 为S0(或者S1)的一个8比特输入,把x 写成两个
16进制的形式:x =h‖l,那么在下表中第h 行第l 列的单元即为S0 (或者S1)的
输出。 
表3-1 S0 
列
行 0 1 2 3 4 5 6 7 8 9 A B C D E F 
0 3E 72 5B 47 CA E0 00 33 04 D1 54 98 09 B9 6D CB 
1 7B 1B F9 32 AF 9D 6A A5 B8 2D FC 1D 08 53 03 90

第 
3 
章　轻量级流密码

续表

133
列
行0 1 2 3 4 5 6 7 8 9 A B C D E F 
2 4D 4E 84 99 E4 CE D9 91 DD B6 85 48 8B 29 6E AC 
3 CD C1 F8 1E 73 43 69 C6 B5 BD FD 39 63 20 D4 38 
4 76 7D B2 A7 CF ED 57 C5 F3 2C BB 14 21 06 55 9B 
5 E3 EF 5E 31 4F 7F 5A A4 0D 82 51 49 5F BA 58 1C 
6 4A 16 D5 17 A8 92 24 1F 8C FF D8 AE 2E 01 D3 AD 
7 3B 4B DA 46 EB C9 DE 9A 8F 87 D7 3A 80 6F 2F C8 
8 B1 B4 37 F7 0A 22 13 28 7C CC 3C 89 C7 C3 96 56 
9 07 BF 7E F0 0B 2B 97 52 35 41 79 61 A6 4C 10 FE 
A BC 26 95 88 8A B0 A3 FB C0 18 94 F2 E1 E5 E9 5D 
B D0 DC 11 66 64 5C EC 59 42 75 12 F5 74 9C AA 23 
C 0E 86 AB BE 2A 02 E7 67 E6 44 A2 6C C2 93 9F F1 
D F6 FA 36 D2 50 68 9E 62 71 15 3D D6 40 C4 E2 0F 
E 8E 83 77 6B 25 05 3F 0C 30 EA 70 B7 A1 E8 A9 65 
F 8D 27 1A DB 81 B3 A0 F4 45 7A 19 DF EE 78 34 60 

表3-
2 
S1 

列
行0 1 2 3 4 5 6 7 8 9 A B C D E F 
0 55 C2 63 71 3B C8 47 86 9F 3C 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 
A 01 B6 BD 58 24 A2 5F 38 78 99 15 90 50 B8 95 E4 
B D0 91 C7 CE ED 0F B4 6F A0 CC F0 02 4A 79 C3 DE 


134
轻量级密码学

续表

列
行0 1 2 3 4 5 6 7 8 9 A B C D E F 
C A3 EF EA 51 E6 6B 18 EC 1B 2C 80 F7 74 E7 FF 21 
D 5A 6A 54 1E 41 31 92 35 C4 33 07 0A BA 7E 0E 34 
E 88 B1 98 7C F3 3D 60 6C 7B CA D3 1F 32 65 04 28 
F 64 BE 85 9B 2F 59 8A D7 B0 25 AC AF 12 03 E2 F2 

2. 密钥加载
密钥加载程序扩展初始密钥和初始向量为16 个31 比特的整数,作为LFSR 的初始状
态。令128 比特的初始密钥
k 
和128 比特的初始向量iv为
k=k0‖k1‖…‖k15 
iv=iv0‖iv1‖…‖iv
其中k和ivi 
都是字节(0≤
i 
≤15), 那么
k 
和iv按下面(15) 两个规则加载到LFSR 。

(1(i) )令D是一个240 比特常量字符串,由16 个15 比特长的子串构成
:
D 
=d0‖d1‖…‖d15


其中

d0=1000100110101112 
d1=0100110101111002 
d2=1100010011010112 
d3=0010011010111102 
d4=1010111100010012 
d5=0110101111000102 
d6=1110001001101012 
d7=0001001101011112 
d8=1001101011110002 
d9=0101111000100112 
d10=1101011110001002 
d11=0011010111100012 
d12=1011110001001102 
d13=0111100010011012 
d14=1111000100110102 
d15=1000111101011002 

(2)对于0≤i≤15,令si=ki‖di‖ivi。

3.ZUC 算法执行
ZUC 算法的执行有两个阶段:初始化阶段和工作阶段
1)初始化阶段
在初始化阶段,ZUC 算法调用密钥加载程序把128 比特的初始密钥和128 比特的初始


第3 章　轻量级流密码1 35 
向量加载到LFSR,再把32比特的内存单元R1 和R2 都设为0。然后ZUC算法运行下列
操作32次: 
Bitreorganization() 
W =F (X 0,X 1,X 2) 
LFSRWithInitializationMode(W?1) 
2)工作阶段
初始化阶段后,ZUC 算法转移到工作阶段。在工作阶段,ZUC 算法执行下列操作一
次,并且把F 的输出w 丢弃: 
Bitreorganization() 
W =F (X 0,X 1,X 2) 
LFSRWithWorkMode() 
然后ZUC算法进入密钥流生成阶段,即在每次迭代中执行一次下列操作,32比特的密
钥流Z 就会生成并输出: 
Bitreorganization() 
Z =F (X 0,X 1,X 2) .. X 3 
LFSRWithWorkMode() 
3.3 基于NFSR的流密码
3.3.1 A2U2 
A2U2是为印刷电子标签而设计的一种轻量级流密码算法。A2U2由一个线性反馈移
位寄存器(LFSR)、两个非线性反馈移位寄存器(NFSR)、一个密钥调度和一个过滤函数四
部分构成,它的密钥长度是56比特。
1.A2U2的结构
A2U2是由一个7级线性反馈移位寄存器、两个分别长17比特和9比特的非线性反馈
移位寄存器、一个密钥调度模块和一个过滤函数4部分构成,如图3-9所示。
A2U2的基本模块定义如下。
1)线性反馈移位寄存器
7级LFSR作为计数器,反馈函数为Fc =x7+x4+1。计数器由以下3个比特串的异
或值初始化:由标签生成的32比特伪随机数的5个LSB(最低有效位)、读取器生成的32 
比特随机数的5个LSB和密钥的5个LSB。5个比特的结果输入到LFSR的MSB(最高有
效位)。为避免全零状态,将LFSR的第二个LSB置1;为避免全1状态,要将第一个LSB置0。
初始化直到LFSR状态变为全1时为止。根据随机选择的计数器初始化值,计数器被
计时的次数(9~126次)是不规则和秘密的。在初始化完成后,计数器将只作为LFSR 
使用。

136
轻量级密码学


图3-
9 
A2U2的结构

2)非线性反馈移位寄存
器
两个NFSR互相为对方提供反馈。在时刻i,两个NFSR的反馈函数分别
为
si+9=li+li+2·li+3+li+5+li+7·ti+li+10 ·li+11 ·li+12+li+13 ·li+15


li+17=si+si+1·si+2+si+3+si+6+ski 

其中,是密钥调度模块生成的子密钥比特。

sk

3)密(i) 钥调度模块

A2U2的密钥部分有61比特,前56比特用于产生子密钥,后5比特为计数器初始化保

留。在时刻i,56比特密钥中的5个比特、计数器的3个比特和NFSR-L的1个比特组合产
生子密钥ski: 

skx(
i 
mok(i+1)motx(5d56,i+14,i+5)+

i=muk5d56,5d56,i+1)
× 
muk(i+4)molt

muk(d56,i+3)mot

x(i+2)mok(d56,i+3) 

其中,mu是复用器。对(5) 的(5) y,如果z=那么mux,z)x; 

则,
x() 
。
任意给出x,
z 
∈F2, 0,x(y,=否
mux(y,=y

x,z)
4)过滤函数
F
假设在时刻0产生密文,过滤器定义如下
:


ci=mux(i+8+tsi),i+16)

si+6,i+8+pf(l

-

pi 
和c是时刻
i 
的明密文比特,0)0,f(= Σ(1) (i) 。

if(=i≥1时,i)lj+16 

j=0 

2.A2U2的安全性
2011年,Chai等人提出了一种针对A2U2的选择性明文攻击模型下的高效密钥恢复攻
击,该攻击要求两个选择的明文使用相同的密钥和初始向量进行加密[320]。Abdelrahem