轻量级分组密码算法设计研究

陈怀凤

(中国电子信息产业集团有限公司第六研究所，北京 100083)

0 引言

分组密码算法是对称密码算法中一种，主要用于对信息进行机密性保护，例如当前最为世人所熟知的高级加密标准AES[1]。最近几年，随着物联网的快速发展，无线射频技术(RFID)和传感器网络(WSNs)等应用场景大幅增加，适于在此类资源受限环境中进行信息加密保护的轻量级密码算法吸引了广大密码学者的注意力，许多轻量级的分组密码算法也被设计出来，例如PRESENT、LED、LBlock、Piccolo、Simon、Speck等。目前，关于“轻量”没有严格明确的定义，一般情况下是指算法的实现很“小”，也就是占有很小的面积。除了面积外，设计人员也会考虑一些其他的准则，例如算法的吞吐量、各种平台的普适性、功率、能耗、延时等等。

本文从最近几年提出的轻量级分组密码算法出发，分析当前阶段轻量级分组密码算法的设计准则与方法，为新的轻量级分组密码算法的设计提供参考。

1 轻量级分组密码算法

替换-置换结构(SPN)和Feistel结构是设计分组密码算法的两种主要结构，轻量级分组密码算法方面同样如此，在具体设计时，算法的某些组件也可能是利用SPN或者Feistel结构进行设计，形成嵌套结构。

1.1 SPN结构的轻量级分组密码算法

(1)PRESENT

PRESENT算法[2]在CHES’07上被提出，是与AES差异较大的SPN结构算法，其线性变换是面向比特进行操作的，而非以往常用的面向字节的变换，非线性层采用4比特S盒。该算法已被国际标准化组织(ISO)标准化[3]。

(2)LED

LED算法[4]在CHES’11上被提出，是基于AES的框架设计的64比特分组长度的轻量级分组密码算法，每一轮包括常数加、S盒替换、行移位、列混合，每四轮组成一步，进行一次密钥加。可认为其不存在密钥扩展算法，128比特密钥分为两个64比特长度的子密钥轮流与每一步的状态进行异或。

(3)PRINCE

PRINCE算法[5]在ASIACRYPT’12上被提出，前5轮与后5轮的轮常数具有简单的代数关系，除此之外是互逆的操作。该算法无密钥扩展算法，一部分用作白化密钥，另一部分作为子密钥直接与轮常数和轮状态进行异或，具有α-反射性，即以密钥k的加密运算等价于以k⊕α的解密运算。

(4)ZORRO

ZORRO算法[6]在CHES’13上被提出，是借鉴了AES和LED的设计思路，每一轮包括S盒替换(只对其中4个nibble进行)、常数加、行移位、列混合、密钥加，该算法像LED一样没有密钥扩展算法，主密钥分为64比特长的子密钥按轮进行异或。

(5)Fantomas/Robin

Fantomas/Robin算法[7]在FSE’14上被提出，这两个算法是属于“LS设计”，状态表示为s×l的矩阵，非线性层对每一列进行s比特的S盒替换，线性层则对每一行进行l比特的线性变换，利用bit-slice技术进行S盒快速实现。

(6)PRIDE

PRIDE算法[8]在CRYPTO’14上被提出，主要针对SPN结构的线性层进行优化，在8比特微处理器上用尽可能少的指令实现算法，采用对合的S盒来降低加密和解密的差异性，也可利用bit-slice技术快速实现。密钥分成白化密钥和子密钥，子密钥只在部分字节上异或常数，然后与每一轮状态进行异或。

(7)Midori

Midori算法[9]在ASIACRYPT’15上被提出，包括64比特和128比特两种分组长度版本，其基本结构与AES类似，也是包括S盒替换、行移位、列混合，密钥扩展算法极为简单，以128比特版本为例，密钥与轮常数异或形成各轮的子密钥，与每一轮状态进行异或。

(8)Rectangle

Rectangle[10]也是基于bit-slice技术设计的SPN结构的轻量级分组密码算法，状态表示成4×16的矩阵。非线性操作为对每一列进行4比特S盒替换，线性层则是对每一行进行行循环移位，各行移位常数不同，其密钥扩展算法采用广义Feistel结构。

(9)SKINNY/MANTIS

SKINNY算法族[11]在CRYPTO’16上被提出，是一族可调的轻量级分组密码算法，每一轮包括S盒替换、常数加、密钥加、行移位、列混合，该算法使用TWEAKEY结构，输入包括明文分组、tweak和密钥，该算法利用MILP(混合整数线性编程)技术给出了差分路径下活性S盒个数的界。MANTIS是SKINNY的低延时变种算法。

(10)SPARX

SPARX算法[12]在ASIACRYPT’16上被提出，整体采用SPN结构，但是其非线性层是采用模加、循环移位和异或操作构造的ARX结构算法，具体为三轮或四轮SPECK轮函数。其密钥引入时覆盖整个状态，而不是一半。该算法第一次对基于ARX结构的分组密码算法给出了针对差分特征和线性特征的可证明安全界。

1.2 Feistel结构的轻量级分组密码算法

(1)HIGHT

HIGHT算法[13]在CHES’06上被提出，是采用广义Feistel结构的ARX类算法，具有8个分支，非线性操作通过模加运算引入，线性变换有两个，都是将一个输入的3个循环移位进行异或求和。通过密钥扩展算法生成白化密钥和轮密钥，各种密钥通过模加运算和异或运算引入。

(2)LBlock

LBlock算法[14]在ACNS’16上被提出，分组长度为64比特，采用平衡Feistel结构，在其中一个分支上进行循环移位操作，F函数则采用SPN结构。F函数中采用4比特S盒，按nibble进行位置变换完成线性操作。其密钥扩展算法引入了两个新的4比特S盒。

(3)Piccolo

Piccolo算法[15]在CHES’11上被提出，分组长度为64比特，采用广义Feistel结构，具有4个分支。与其他广义Feistel结构算法不同，该算法的几个分支之间具有较复杂的线性变换。其F函数采用SPN结构，其4比特S盒在具有合适的非线性度盒差分分布的密码学特性的基础上，硬件占用特别低。

(4)TWINE

TWINE算法[16]在2011年被提出，分组长度为64比特，采用广义Feistel结构，具有16个分支。其F函数是4比特状态异或密钥后过一个4比特S盒替换，线性变换主要是16个分支较为复杂的位置置换。

(5)LEA

LEA算法[17]在WISA’13上被提出，分组长度为128比特，是采用广义Feistel结构的ARX类算法，具有4个分支。所有的模加、循环移位和异或都是面向32比特字进行的，密钥扩展算法也同样采用ARX结构。

(6)SIMON/SPECK

SIMON/SPECK算法[18]在2013年由美国国家安全局(NSA)提出，SIMON算法是面向硬件实现的轻量级分组密码算法族，具有10个版本，采用平衡Feistel结构。其轮函数特特别简单，只使用与、循环移位和异或操作。SPECK算法是面向软件实现的轻量级分组密码算法族，采用ARX结构，其轮函数只采用模加、循环移位和异或操作。设计人员并未对这两个算法进行安全性说明，而是留给广大密码学者进行分析。

(7)RoadRunneR

RoadRunneR算法[19]在LightSec’15上被提出，分组长度为64比特，采用平衡Feistel结构。与LBlock类似，其F函数采用SPN结构，类似于Fantomas/Robin算法的LS设计，使用bit-slice技术实现S盒，其线性层则类似于HIGHT算法，也是几个循环移位的异或和。

(8)SIMECK

SIMECK算法[20]在CHES’15上被提出，是受SIMON算法族启发而设计的算法族，其轮函数与SIMON相比，只在循环移位的位数上有所不同，以获得更小的硬件面积。

2 分组密码算法设计中的“重量”与“轻量化”

轻量级分组密码算法在设计时主要考虑的是“轻量化”，但除此之外，不同的密码学者还有不同的考虑，在本节将根据上一节简单介绍的密码算法，总结轻量级分组密码算法的设计考虑的关键点。

2.1 对“重量”的理解

本小节主要介绍密码学界对密码算法设计中“重量”的理解，在文献[21]中对此有所介绍。

算法的“重量”一般是指运行算法所需要的时间和空间的资源占用量，可以在两种不同的环境中进行测量：硬件环境和软件环境。但是要注意，硬件环境中的轻量级算法并不意味着软件环境中的轻量级，反之亦然。

2.1.1硬件环境中的重量

存储方面主要考虑实现算法需要的逻辑门数量，该量一般使用GE(Gate Equivalence，1GE等价于一个与非门)作为单位。时间效率方面使用吞吐量(Throughput)来表示，也就是在给定时钟频率下，算法每秒钟处理的数据比特数；包括密钥扩展操作在内的延时也是考虑点之一。对上述量的评估比较复杂，由于各种硬件环境较多且不同密码研究人员不同的评估环境和方式，很难对不同密码研究人员的实现结果进行合适的比较。

2.1.2软件环境中的重量

软件环境中的重量包括算法运行的时间复杂度和存储复杂度。时间复杂度的一种评估方式是加密算法(或解密算法)处理1字节数据需要的时钟周期数，但是某些特定的应用场景中，密钥扩展等间接开销也较大，这种计算方式不太准确；另外一种就是考虑算法整体的延时，也就是将所有间接开销都计算在内考虑需要的时钟周期数。存储复杂度主要是考虑算法正常运行时占用的RAM空间量，另外，也要考虑算法存储(例如Flash)占用的空间量。

2.1.3耗电功率

耗电量是软硬件实现都要考虑的一个指标。RFID中存在功率限制，或者说某些嵌入式设备是采用电池供电的，在设计算法时应当要考虑算法运行时的平均耗电量以及相应的功率峰值。

2.2 对“轻量级密码算法”的理解

在2012年，SAARINEN M J O和ENGELS D W从RFID或轻量化传感器网络的工业使用方面提出了轻量级密码算法应该符合的限制和目标[22]，主要包括以下几点：

(1)算法可在不经过明显改动的条件下，实现单向可调的认证加密算法、解密算法以及安全的哈希函数。

(2)各种输入(包括初始化向量IV、认证关联数据等)的填充以及操作规则需明确定义，输入数据比率应当尽可能小以避免消息的扩展操作。

(3)初始化向量IV可以不是nonce(nonce在重用选择IV攻击中也是安全的)，在各种可能的攻击模型中，安全强度与密钥以及状态的长度一致。

(4)硬件实现应当低于2 000门(GE)，该实现包含加密、解密算法以及相应的状态存储；在MCU或CPU平台上的软件实现速度以及大小也应在设计时作为指标进行考虑。

(5)算法应当有不低于50个周期的延时，且加密或解密的吞吐量满足每周期至少输出1比特。

(6)功率应当低于1～10 μW/MHz，相应的峰值应分别低于3 μW和30 μW，也就是说在2 MHz频率下，峰值应当低于1.5～15 μW/MHz。

3 轻量级分组密码算法的设计方法

根据设计准则，将第1节中的轻量级分组密码算法进行简单的分类，主要包括面向软件轻量化、面向硬件轻量化这两个方向进行设计的算法，部分算法在设计者精心选择密码组件的前提下，能够适应多种平台或者满足多种目标，例如低延时或低功耗。

3.1 面向硬件轻量化的分组算法

面向硬件轻量化设计的分组密码算法如下：

(1)PRESENT：非线性层采用4比特S盒，线性层使用简单的比特拉线。

(2)LED：采用4比特S盒(PRESENT的S盒)，线性变换是特别简单的矩阵乘重复四次。

(3)PRINCE：采用4比特S盒，采用4个简单的小矩阵构造大的线性层矩阵。

(4)Midori：Midori64采用4比特S盒，线性层采用的矩阵只有1和0元素，比较简单。

(5)Rectangle：采用4比特S盒，使用bit-slice技术快速实现，线性层由循环移位和异或组成，利于软硬件实现。

(6)SKINNY/MANTIS：SKINNY64采用4比特S盒，线性变换只有循环移位操作以及简单的异或构成，该算法的软件实现也很有优势。

(7)HIGHT：面向硬件实现设计的ARX类算法，所有运算都是以8比特为单位进行的，所以也适合8比特软件平台实现。

(8)LBlock：采用4比特S盒，线性操作包括32比特字的循环左移8位以及按4比特nibble的置换。

(9)Piccolo：采用广义Feistel结构，4比特S盒，F函数中的线性操作只有按nibble的拉线，分支间使用简单的矩阵乘。

(10)TWINE：采用具有16个分支的广义Feistel结构，4比特S盒，线性变换就是按nibble的拉线操作。

(11)SIMON、SIMECK：只有循环移位、与和异或操作，硬件占用极低。

3.2 面向软件轻量化的分组算法

面向软件轻量化设计的分组密码算法如下：

(1)ZORRO：采用的8比特S盒是利用更小的S盒组合构造而成的。

(2)Fantomas/Robin：采用8比特S盒(利用小S盒构造)，利用bit-slice技术快速实现，设计者认为该算法硬件实现也较有优势。

(3)PRIDE：面向8比特位宽单片机的软件实现设计，bit-slice技术实现16个并行的4比特S盒，并选择使用极少指令数的线性变换操作。

(4)SPARX：面向软件轻量化实现设计，采用ARX结构。

(5)LEA：面向软件快速实现设计，采用ARX结构，以32比特为单位进行各种运算。

(6)SPECK：面向软件快速实现设计，采用ARX结构。

(7)RoadRunneR：面向8比特处理器的软件轻量化实现设计，具有较低的代码量，同时吞吐量较高。采用可bit-slice快速实现的4比特S盒以及具有较少代码量的线性操作。

3.3 轻量级分组密码算法的特点与设计思路

3.3.1硬件轻量化的分组算法特点与设计思路

通过总结以上可以发现，面向硬件的轻量级分组密码算法具有以下特点：

(1)非线性运算多使用4比特S盒或者不使用S盒。这主要是4比特S盒的代数表示形式比较简单，占用的门数较少，例如LBlock选取的S盒全都可以只使用22个GE实现。

(2)存在多个S盒时，使用相同的S盒，利于算法的多种实现方式，比如并行以提高加密速率，或着串行重用S盒以降低资源占用。

(3)线性层比较简单，多使用按nibble的位置置换或是由简单矩阵构成的复杂矩阵进行矩阵乘运算。位置置换在硬件中几乎不占用资源，复杂矩阵在硬件中可以通过简单矩阵的重用来实现，资源占用低。

(4)使用SPN结构的轻量级分组密码算法其加密与解密的操作一般是不同的，这会在实现解密运算时，增加许多额外的资源，但考虑到各种工作模式的存在以及实际使用中加密和解密在设备中使用的不对称性(只进行加密或解密)，这一问题可以通过相应的协议来解决。不然的话，就需要非常细心地选择各种密码组件，例如对合的S盒或像PRINCE的α-反射结构。

(5)Feistel结构的加密和解密运算结构相同，在实现时不会增加太多额外资源。

(6)密钥扩展算法要简单，可以重用密码算法轮函数中的组件，有些算法甚至无密钥扩展的过程，直接与轮常数异或后再作用到中间状态上，例如LED、PRINCE等。

3.3.2软件轻量化的分组算法特点与设计思路

通过总结以上可以发现，面向软件的轻量级分组密码算法具有以下特点：

(1)使用4比特S盒的密码算法多利用bit-slice技术提升加密效率，这需要在选择S盒时注意S盒代数实现时的指令个数。

(2)ARX类的算法适合软件快速实现，加法、异或、循环移位操作适合在CPU或MCU中通过一条(或很少的)指令实现。

(3)循环移位常数选择8或者8的倍数，适合在8比特及其以8倍数为位宽的处理器上快速执行。

(4)SPN结构或者Feistel结构在硬件实现中的优缺点在软件方面也有类似的问题，主要体现在代码量以及执行效率方面。

(5)密钥扩展算法要简单，可以重用密码算法轮函数中的组件以降低代码量。

4 结论

本文简单介绍了当前阶段轻量级分组密码算法的设计特点，在给出密码算法“重量”理解的基础上，分析了轻量级密码算法非线性组件与线性组件的特点，并从结构以及组件等方面给出了设计面向硬件轻量化或软件轻量化分组密码算法的设计思路，为新轻量级分组密码算法的设计提供参考。