分组密码算法作为对称密码的一个重要分支，在计算机通信和信息系统安全领域有着广泛应用，同时也是构造认证加密算法、Hash函数和密码协议的底层算法.分组密码的典型结构主要包括Feistel结构、SPN(substitution permutation network)结构和Lai-Massey结构.Feistel结构代表有数据加密标准(data encryption standard, DES)算法[1]和NSA(National Security Agency)设计的SIMON算法[2]等；SPN结构的算法有高级加密标准(advanced encryption standard, AES)[3]、轻量级分组密码算法Midori[4]和SKINNY[5]等；Lai-Massey结构的算法有国际数据加密算法IDEA[6].Feistel结构加解密采用相同的结构，加解密算法同时实现可以节省资源，但是由于其混淆扩散速度慢，一般轮数比较多，加解密效率相对低一些.而Lai-Massey结构的混淆扩散速度较快，加解密一致，且软件实现速度快.但是轮函数较为复杂，每轮的硬件实现面积较大.SPN结构混淆扩散速度快，算法轮数一般较少，算法实现时吞吐量较大.一般情况下加密和解密的部件是不同的，解密是加密运算的逆.一些SPN结构加密算法实现解密的开销通过使用对合运算作为组成部分来进行优化.在SPN结构中，有一类是基于S盒和乘矩阵的AES类结构，该类结构算法有利于对抗差分和线性分析，并进行安全性证明.

轻量级分组密码是一种特殊的分组密码体制，对轻量级分组密码进行研究的动机是某些特定应用需要比AES面积低、功耗低且安全强度相当的加密算法.轻量级密码算法硬件实现和运行时所占用的系统资源的开销较少，例如硬件实现面积、运行时所占内存空间大小和能耗等.这类分组密码算法主要被用于资源受限的计算环境中，例如电子标签射频识别(radio frequency identification, RFID)以及一些电池驱动的设备.随着物联网的快速发展，物联网终端传感器部件广泛部署,对轻量级密码体制的需求也越来越大[7].由于轻量级分组密码具有较低的实现成本和较低的能耗，在物联网终端和卫星通信网络中大量部署轻量级密码算法可以带来显著的社会经济效益.第1代轻量级密码，例如PRESENT[8]和KATAN[9]仅关注芯片面积，并使用非常简单的轮函数作为算法的主要组成部分.近年来，具有各类特色的新轻量分组密码如雨后春笋般涌现.例如短代码型PRIDE[10]和SPECK[2]，低延迟型PRINCE[11]，MANTIS[5]，QARMA[12]，能抵抗侧信道攻击型LS-Designs[13]和PICARO[14]，以及低能耗型Midori和GIFT[15].

小型加密设备适用于物联网中，轻量级加密算法的侧信道保护实现是一个非常重要的方面，防止侧信道攻击的一种额外保护措施是使用防泄漏设计，尤其是通过对密码进行额外的调柄(Tweak)输入.轻量级可调分组密码通过附加的公开输入Tweak进行扩展.这样的算法允许更好的加密模式和认证加密方案的有效构造[16].这类算法包括SKINNY[5]，CRAFT[17]，Deoxys-BC[18]，QARMA[12]，Joltik[19]，以及作为一般设计原则的TWEAKEY框架[20].

安全是密码算法得以应用的前提.近年来，分组密码的安全性评估己取得长足的进步.特别是，基于混合整数线性规划(mixed integer linear programming， MILP)方法的提出和应用[21-23]，使得分组密码算法安全分析朝着自动化、精细化、标准化、可证明方向发展.

1 RAIN分组密码

RAIN是一族可调分组密码算法，分组长度支持64 b和128 b，根据分组长度的不同记为RAIN-64和RAIN-128.两个版本调柄的长度等于密钥长度分别为64 b和128 b，它们的迭代轮数分别为30轮和36轮.

1.1 符号说明

符号说明如表1所示：

1.2 RAIN算法描述

算法的轮函数由4种运算组成：列混合、字替换、行移位和轮可调密钥加.图1和图2分别展示了RAIN算法的轮函数结构和算法的整体结构.令n比特向量(w0,w1,…,wn-2,wn-1)表示一个密码内部状态ST，最左比特w0代表最高有效位，若将内部状态从左至右每n/16比特划分为一个单元，则密码内部状态ST可表示为(st0,st1,…,st15)，其矩阵形式为

其中，st0表示内部状态的最左单元，st15表示内部状态最右单元，每个单元st中最左比特代表最高有效位.

RAIN算法的具体加密流程：

1) 初始白化(Whitening).将明文P与密钥K按单元进行异或运算.

2) 列混合(MixColumns, MC).密码内部状态矩阵的每一列乘以下二元矩阵：

3) 字节替换(SubCells, SC).将s×s的S盒并行应用于密码内部状态的每个单元，当分组长度为64 b时s=4，当分组长度为128 b时s=8.表2给出了RAIN算法所用S盒S4的十六进制表示形式：

当s=8时所用8 b的S盒S8是经过与SKINNY所用8 b的S盒相似的变换而来，即通过并行放置2个4 b的S盒S4来构造如图3所示8 b的S盒S8.

4) 行移位(ShiftRow, SR).采用与AES相同的行移位变换，密码状态的第2～4行分别向左循环移动1，2，3个单元.

5) 轮可调密钥加(AddTweakey, ATK).将轮可调密钥RTKi与步骤4)的输出进行异或运算.

轮可调密钥编排流程：

① 密钥加(AddKey, AK).令轮可调密钥经过密钥加之后的状态为TAK，则首轮可调密钥更新中密钥加计算记为TAK=T⨁K.随后的第i轮中TAK=RTKi-1⨁K，2≤i≤30或36.

② 行移位(SR).对密钥加(AK)运算的输出状态使用与轮函数相同的位置变换.

③ 轮常数加(AddConstant, AC).对于RAIN-64版本，每轮使用4个4 b的轮常数与轮可调密钥编排过程中行移位(SR)运算的输出状态的第1列按半字节进行异或.对于RAIN-128版本，每轮使用4个8 b的轮常数，与轮可调密钥编排中的行移位运算输出状态的第1列按字节进行异或运算.常数由的小数部分的十六进制编码得到，算法的2个版本所使用的轮常数分别如表3和表4所示：

④ 比特加(AddBit, AB).令轮可调密钥编排过程中轮常数加运算的输出状态为TAC，则比特加运算可描述为：提取状态TAC中每个单元的第1比特，将提取的16个比特进行异或运算得到1 b的输出，即：

TAC[0][0]+TAC[1][0]+…+TAC[15][0],

运算结果用于替代状态TAC中每个单元的第1位即为比特加运算的输出RTK.

加密过程和解密过程伪代码见算法1和算法2所示.实现RAIN算法的代码可通过https://github.com/CaoMeichun/RAIN.git获取.RAIN算法的测试向量见附录A.

算法1. 加密算法.

输入:P,K,T;

输出:C.

① stateWhitening=P⨁K;

② for 1≤i≤Nrdo

③ stateMC=M·stateWhitening;

④ for 0≤j≤15 do

⑤ stateSC[j]=Ss(stateMC[j]),s=4,8;

⑥ end for

⑦ for 1≤j≤15 do

⑧ stateSR[j]=SR(stateSC[j]);

⑨ end for

⑩ stateATK=stateSR⨁RTKi;

end for

C←stateATK.

算法2. 解密算法.

输入:C,K,T;

输出:P.

① stateMC_inv←C;

② for Nr≥i≥1 do

③ stateRTK_inv=stateMC_inv⨁RTKi;

④ for 0≤j≤15 do

⑤ stateSR_inv[j]=SR-1(stateMC_inv[j]);

⑥ end for

⑦ for 1≤j≤15 do

⑧ stateSC_inv[j]=Ss-1(stateSR_inv[j]),s=4或8;

⑨ end for

⑩ stateMC_inv=M·stateSC_inv;

end for

stateWhitening_inv=stateMC_inv⨁K;

C←stateWhitening_inv.

2 算法轮函数的设计

我们的设计遵循强安全性、高效的软硬件实现、简单的结构以及强灵活性等宗旨.RAIN的整体结构为SPN结构，S盒的选择是密码设计中的关键，对于4 b的S盒，我们将S盒的差分均匀度设为4，并将线性度设为8.当2个条件都满足时，我们筛选出具有安全性的S盒.扩散层的设计既要为算法获取良好的安全边界也要考虑到软硬件实现的性能，另一个重要标准是使得加密过程中密钥尽可能快地影响密码内部状态.轮常数的选取需遵循3个原则：1)区分不同的轮并避免对称性;2)使子空间密码分析复杂化;3)避免利用S盒中的固定点进行攻击.

2.1 RAIN算法的S盒设计

本算法采用4×4安全轻量S盒以及基于此S盒构造的8 b输入输出S盒.S盒的选择不仅考虑了如差分密码分析和线性密码分析等常规的安全性，还考虑了S盒的门限实现方案以达到抵御侧信道攻击的目的.

RAIN算法2个版本均采用4 b的S盒，一个原因是4 b的S盒可以用单指令多数据流扩展(streaming SIMD extensions, SSE)等指令集快速实现，另一个原因是硬件实现代价的考虑.和8 b的S盒相比，4 b的S盒具有明显的硬件优势，不仅硬件实现代价小，而且延迟能耗等方面都有明显优势.采用由2个并行处理的4 b的S盒组成8 b的S盒，以最小化基于轮的实现中的路径延时.该结构采用4 b的S盒构造非线性变换层，相较于AES等算法采用的8 b的S盒，更易于硬件实现，延迟、面积、能耗等指标更优.其次，4 b的S盒在各种平台的软件实现灵活，可以采用查表方式，也可以采用比特切片的实现方式.

定义1[24]. 令S表示一个4 b的S盒，表示该S盒的输入差分和输出差分，对于任意的ΔI,ΔO，定义S盒的差分均匀度Diff(S)为

S(x+ΔI)=ΔO}|.

(1)

定义2[25]. 令S表示一个4 b的S盒，表示该S盒的输入掩码和输出掩码，对于任意的ΓI,ΓO，定义S盒的线性度Lin(S)为

ΓI,x}|-2s,

(2)

其中s的值为4.

对于任意双射4 b的S盒，均有Diff(S)≥4且Lin(S)≥8，当这2个值都达到最小时,可以称该S盒为最优S盒.

RAIN算法使用的S盒的差分均匀度、非线性度以及线性度为别为4，4，8，该S盒的密码学性质达到了最优.且此S盒代数次数为3，同时兼顾了S盒高代数次数的要求.

2.2 S盒的门限实现

S盒门限实现[26-28]为加密算法的实现提供了可证明的安全性，用来抵抗侧信道攻击.本文S盒S4的布尔表达式为

(3)

其中，(x0,x1,x2,x3)表示S4的4 b输入变量，(y0,y1,y2,y3)表示S4的4 b输出变量.S4的1个分量函数y0由1个立方项、2个二次项和2个一次项组成.为了降低硬件实现中的电路复杂性以及缩减电路开销，将代数次数为3的分量函数转换为代数次数为2的子函数的复合，然后对这些子函数进行门限实现.共享份额[29]为3的门限实现方案[30]见附录B.

此门限方案中，秘密信息被随机地分成了多个份额，即使其中某个份额的信息被泄露，也不会对此S盒造成威胁.

由于S4其余的3个分量函数可通过该分量函数y0中变量的循环移位获得，其余的3个分量函数的门限实现方案与y0相同.在进行硬件实现时，它们的面积开销与功耗也相似.

2.3 RAIN算法的扩散层设计

扩散层的设计是为了提供扩散，因此输出的每一列依赖于输入的某些列.在算法的扩散层结构上，我们希望扩散层便于解密过程的求逆，并且解密逆运算和加密正运算的性能是等价的.同时还考虑了扩散层和S盒产生强扩散的计算资源和实现效率，要求每个比特使用的异或数量不能超过3个.考虑到可逆性，我们利用对合矩阵M构造扩散层，使线性层的加密和解密可以使用相同的代码块来减少算法实现所需指令的数量.

分支数反映了线性扩散层的安全性能，扩散层的分支数越大，在进行差分密码分析或者线性密码分析时需要选择(己知)明文数越多，密码的安全性就越好.分组密码的扩散层都可以表示为有限域上的线性变换操作，所以设计一种高扩散性的密码算法就相当于设计一个具有最大分支数的线性变换.

任意的线性变换一般都能够用有限域上的矩阵M进行刻画，若将线性变换表示成矩阵形式θ(X)=M·X，那么矩阵M的差分分支数和线性分支数可表示为

(4)

(5)

其中，MT是矩阵M的转置，W(X)表示向量X的汉明重量.

定义3. 若一个m阶矩阵的差分分支数和线性分支数均等于此矩阵的阶数m，即BD(M)=BL(M)=m，则该矩阵M是几乎最优极大距离可分码(maximum distance separable, MDS)矩阵.

虽然许多加密算法使用MDS矩阵作为扩散层，但不可否认的是，MDS矩阵在提供了最优的扩散性能的同时，使算法效率下降，这将消耗更多的软硬件资源，算法的实现需要更长的运行时间.我们使用线性分支数和差分分支数均等于4的几乎最优MDS矩阵，从而在安全性和效率之间取得最佳平衡.几乎最优MDS矩阵都具有次优的分支数，但是与MDS矩阵相比，它们的实现代价小，具有更高的硬件和软件实现效率.几乎最优MDS矩阵只需要简单的异或运算，从而大大减少了硬件和软件资源的消耗.

3 安全性分析

3.1 差分分析

差分分析是最初由Biham和Shamir[31]于1991年针对DES算法提出的一种密码分析方法.该方法几乎适用于所有的分组密码体制，是对分组密码算法威胁最大的分析方法之一[32-33].对于采用S盒作为核心部件的分组密码算法，评估单条差分传播路径最大概率上界的最有效方法就是估算差分传播路径中活跃S盒的个数.2011年Mouha等人[21]利用混合整数线性规划给出差分分析和线性分析中活跃S盒个数下界的评估方法.首先将差分分析和线性分析中活跃S盒传播规律用线性不等式刻画，目标函数为最小的活跃S盒个数，然后利用求解MILP问题的软件进行求解，如Cplex，Gurobi等.该方法得到的下界精度较高，许多时候达到最优值，因此被广泛用来作为评估分组密码抵抗差分分析和线性分析能力的参考指标.

针对差分分析采用搜索差分活跃S盒个数的方法评估算法抵抗攻击的能力.该方法也被其他大量算法的安全性评估所采用.我们通过对算法建立差分传播MILP模型搜索了RAIN算法的差分活跃S盒个数，结果如表5所示.6轮RAIN-64算法至少有34个差分活跃S盒，由于算法采用S盒的最大差分概率为2-2，因此6轮RAIN-64算法的最大差分路径概率(differential characteristic probability, DCP)，满足说明6轮RAIN-64已不存在差分分析可利用的有效差分路径.同理11轮RAIN-128已不存在差分分析可利用的有效差分路径.考虑到RAIN的迭代轮数和全扩散轮数，可以相信全轮RAIN算法针对差分分析是安全的.

我们将RAIN-64的最小活跃S盒与其他轻量级分组密码在相同安全级别64 b分组128 b密钥上进行比较，结果如表6所示(表6中所有加密都使用4 b的S盒，最大差分概率为2-2)：

3.2 不可能差分分析

不可能差分分析是利用概率为0的差分路径进行密码分析的分析方法[34].根据不可能差分密码分析的研究现状，一个分组密码的最长不可能差分区分器的轮数接近于全扩散轮数的2倍.对于RAIN算法而言，当输入差分汉明重量为1时，4轮可达到差分全扩散.

我们利用基于MILP的自动化搜索方法对RAIN的不可能差分路径进行搜索.由己知的不可能差分分析结果来看，几乎所有的不可能差分路径的输入和输出差分模式分别只有一个活跃S盒，因此选定输入输出差分时，应满足输入、输出只能使单个S盒活跃.搜索到RAIN算法的6轮不可能差分形式为

*000 0000 0000 0000|→*000 0000 0000 0000.

利用不可能差分区分器，可以给出缩减轮RAIN的不可能差分分析.考虑到RAIN算法的扩散性和迭代轮数，可以相信全轮RAIN针对不可能差分分析提供了足够的安全冗余.

3.3 积分分析

积分分析可以看成是一种代数攻击,主要构造关于若干输入明文比特的零和区分器.可分性(division property)是目前分析对称密码算法积分性质最有力的工具[35-38]，同样可以借助MILP方法方便准确的搜索算法的积分区分器.我们利用Xiang等人[36]以及Zhang等人[38]提出的生成S盒及线性层可分性不等式的方法构造了RAIN算法可分性传播的MILP模型.文献[36]中对S盒可分性传播的不等式描述近乎完美.文献[38]中利用线性层矩阵所描述的异或运算，通过构造线性不等式来建模可分性在线性扩散层中的传播，使不等式的可行解精确地表示线性层的所有可分性传播轨迹.因此，利用该方法描述是紧致的，得到的解是最优的，轮数是用可分性方法所得最多的.借助可分性可以搜索得到RAIN-64算法的7轮积分区分器，其中输入63个活跃比特，输出4个平衡比特.

7轮RAIN-64积分区分器的输入为

0111 1111 1111 1111…1111 1111 1111 111，

其中“1”表示活跃比特位；

7轮RAIN-64积分区分器的输出为

????BBBB????????…????????????????，

其中，“B”表示平衡比特，“?”表示未知状态.

受限于计算能力，目前还无法断定RAIN-64是否存在8轮积分区分器，但是我们构造出的积分区分器的轮数7和RAIN-64的总轮数30相差很大.因此我们相信RAIN-64具有足够的抵抗积分密码分析的安全性.

3.4 不变子空间分析

我们采用Guo等人[39]提出的不变子空间分析方法对算法S盒的不动点导致的弱密钥存在性进行了分析.观察算法的S盒发现有可能存在的弱密钥空间为:{0,5,a,f}，{1,9}，{2,3}，{4,6}.

由此我们考察了算法各个部件的输入输出可能性.当明文、调柄和主密钥都从以上某一个空间中取值时，密钥编排中的密钥加，行移位都不会改变输出值的空间.例如明文、调柄和主密钥都从{0,5,a,f}中取值，那么密钥编排中密钥加和行移位的输出值仍在{0,5,a,f}这个空间中.比特加操作会使{0,5,a,f}，{2,3}，{4,6}这3个空间不成立，因为该操作会改变半字节的最高位.而算法所使用的轮常数使得密钥编排经过轮常数加之后不能保持上述4个空间中的任何一个.虽然轮函数的每一步操作都使得输入输出空间一致，但是每一轮的密钥都无法与明文保持在同一个空间中，所以以上4个可能的弱密钥空间是不存在的.

4 软硬件性能评估

4.1 软件性能评估

RAIN算法便于软件实现，算法可以采用基于字的基本逻辑运算实现.

RAIN算法使用的矩阵M每行有3个1，在计算输出状态矩阵列向量时，可以通过增加辅助变量t达到减少使用模加运算的目的.

令乘矩阵的输入为(x0,x1,x2,x3)，输出为(y0,y1,y2,y3)，输出向量可由输入向量计算得到：

(6)

若引入辅助变量t=x0⨁x1⨁x2⨁x3，则输出向量可计算为

(7)

通过式(6)计算输出列向量所需模加数量为7个，而式(7)计算输出列向量所需模加数量为8个.

我们采用标准C实现RAIN算法,在64 b Windows(i7-7700 CPU@3.6 GHz；Win7操作系统；16 GB内存；x86_64环境；编译器为visual studio2017 x64 release)和64 b ARM(TaiShan 200 MHz CPU@2.6 GHz；Cortex A73架构；编译器gcc 9.1.0)环境下，对RAIN算法的加解密速率进行测试，测试结果如表7所示:

表7中对RAIN算法的软件实现性能与其他提供相同安全级别的轻量级可调分组密码SKINNY和CRAFT进行了对比，RAIN-64算法的加解密速率是较高的.

4.2 硬件性能评估

为了评估RAIN的硬件实现性能，我们针对可编程逻辑阵列(FPGA)实现平台进行评估.使用Xilinx公司的Xilinx Kintex xc7k325tffg900-2平台来评估RAIN在FPGA上的实现结果和性能.算法实现的加/解密运算用时包含密钥编排运算用时.算法电路面积规模为包含加密、解密、密钥编排运算的算法整体实现的含互连线面积.表8给出了RAIN在FPGA上的实现结果，并将RAIN算法的实现与SKINNY进行了比较，RAIN算法的加解密速率更优且面积较小.

5 结 论

本文设计了一个面向软硬件和门限实现的轻量分组密码算法，算法兼顾了安全性和软硬件实现性能.RAIN算法对64 b的分组和128 b的分组，采用统一的结构都可以转化为基于字的基本逻辑运算，这种实现方式在现代英特尔中央处理器架构下可以很方便地结合扩展指令SSE实现分组密码的并行处理，同时对S盒的门限实现方案在抗侧信道攻击上具有优势.

参考文献

[1]International Business Machines Corporation. Data Encryption Standard (DES)[S/OL]. 1977 [2021-02-04]. https://csrc.nist.gov/csrc/media/publications/fips/46/3/archive/1999-10-25/documents/fips46-3.pdf

[2]Beaulieu R, Shors D, Smith J, et al. The SIMON and SPECK lightweight block ciphers[C] //Proc of the 52nd Annual Design Automation Conf. Piscataway, NJ: IEEE, 2015: 1-6

[3]Daemen J, Rijmen V.The Design of Rijndael： AES—The Advanced Encryption Standard[M/OL]. 2002[2021-02-04]. https://www.springer.com/cn/book/9783540425809

[4]Banik S, Bogdanov A, Isobe T, et al. Midori: A block cipher for low energy[C] //Proc of the 21st Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2015: 411-436

[5]Beierle C, Jean J, Kölbl S, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS[C] //Proc of the 36th Annual Int Cryptology Conf. Berlin: Springer, 2016: 123-153

[6]Lai Xuejia, Massey J L. A proposal for a new block encryption standard[C] //Proc of Workshop on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1990: 389-404

[7]Feng Cheng. Research on key issues in the application of 256-bit cipher algorithm in 5G mobile communication system[J]. Journal of Information Security Research, 2020, 6(8): 716-721 (in Chinese)(冯程. 256比特密码算法在5G移动通信系统应用中关键问题研究[J]. 信息安全研究, 2020, 6(8): 716-721)

[8]Bogdanov A, Knudsen L R, Leander G, et al. PRESENT: An ultra-lightweight block cipher[C] //Proc of the 9th Int Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2007: 450-466

[9]Cannière C, Dunkelman O, Kneževi M. KATAN and KTANTAN—A family of small and efficient hardware-oriented block ciphers[C] //Proc of the 11th Int Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2009: 272-288

[10]Albrecht M R, Driessen B, Kavun E B, et al. Block ciphers-focus on the linear layer (feat. PRIDE)[C] //Proc of the 34th Annual Cryptology Conf. Berlin: Springer, 2014: 57-76

[11]Borghoff J, Canteaut A, Güneysu T, et al.PRINCE—A low-latency block cipher for pervasive computing applications-extended abstract[C] //Proc of 18th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2012: 208-225

[12]Avanzi R. The QARMA block cipher family[J]. IACR Transactions on Symmetric Cryptology, 2017, 2017(1): 4-44

[13]Grosso V, Leurent G, Standaert F X, et al. LS-Designs: Bitslice encryption for efficient masked software implementa-tions[C] //Proc of the 21st Int Workshop on Fast Software Encryption. Berlin: Springer, 2014: 18-37

[14]Piret G, Roche T, Carlet C. PICARO—A block cipher allowing efficient higher-order side-channel resistance[C] //Proc of the 10th Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2012: 311-328

[15]Banik S, Pandey S K, Peyrin T, et al. GIFT: A small present towards reaching the limit of lightweight encryption[R/OL]. 2017 [2021-02-04]. https://infoscience.epfl.ch/record/232021/files/622.pdf

[16]Liskov M, Rivest R, Wagner D. Tweakable block ciphers[C] //Proc of the 22nd Annual Int Cryptology Conf. Berlin: Springer, 2002: 31-46

[17]Beierle C, Leander G, Moradi A, et al. CRAFT: Lightweight tweakable block cipher with efficient protection against DFA attacks[J]. IACR Transactions on Symmetric Cryptology, 2019, 2019(1): 5-45

[18]Jean J, Nikoli I, Peyrin T, et al. Submission to caesar: Deoxys v1.41[OL]. 2016[2021-02-04]. http://competitions.cr.yp.to/round3/deoxysv141.pdf.

[19]Jean J, Nikoli I, Peyrin T. Joltik v1.3[OL]. 2015[2021-02-04]. http://competitions.cr.yp.to/round2/joltikv13.pdf

[20]Jean J, Nikoli I, Peyrin T. Tweaks and keys for block ciphers: The TWEAKEY framework[C] //Proc of the 20th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2014: 274-288

[21]Mouha N, Wang Qingju, Gu Dawu, et al. Differential and linear cryptanalysis using mixed-integer linear programming[C] //Proc of the 7th Int Conf on Information Security and Cryptology. Berlin: Springer, 2011: 57-76

[22]Sun Siwei, Hu Lei, Wang Peng, et al. Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES (L) and other bit-oriented block ciphers[C] //Proc of the 20th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2014: 158-178

[23]Fu Kai, Wang Meiqin, Guo Yinghua, et al. MILP-based automatic search algorithms for differential and linear trails for speck[C] //Proc of the 23rd Int Conf on Fast Software Encryption. Berlin: Springer, 2016: 268-288

[24]Canteaut A, Duval S, Leurent G. Construction of lightweight S-boxes using Feistel and MISTY structures[C] //Proc of the 22nd Int Conf on Selected Areas in Cryptography. Berlin: Springer, 2015: 373-393

[25]Mariot L, Picek S, Leporati A, et al. Cellular automata based S-boxes[J]. Cryptography and Communications, 2019, 11(1): 41-62

[26]Bilgin B, Nikova S, Nikov V, et al. Threshold implementations of small S-boxes[J]. Cryptography and Communications, 2015, 7(1): 3-33

[27]Tu Binbin, Chen Yu. A survey of threshold cryptosystems[J]. Journal of Cryptologic Research, 2019, 7(1): 1-14 (in Chinese)(涂彬彬, 陈宇. 门限密码系统综述[J]. 密码学报, 2019, 7(1): 1-14)

[28]De Meyer L, Bilgin B, Reparaz O. Consolidating security notions in hardware masking[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019, 2019(3): 119-147

[29]Kutzner S, Nguyen P H, Poschmann A. Enabling 3-share threshold implementations for all 4-bit s-boxes[C] //Proc of the 16th Int Conf on Information Security and Cryptology. Berlin: Springer, 2013: 91-108

[30]Li Fan, ZhangWenying, Xing Zhaohui. Design of secure lightweight S-box for software and hardware implementation[J]. Journal of Application Research of Computer, 2020, 37(12): 1-6 (in Chinese)(李凡, 张文英, 邢朝辉. 适于软硬件实现的安全轻量S盒的设计[J]. 计算机应用研究, 2020, 37(12): 1-6)

[31]Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology, 1991, 4(1): 3-72

[32]Biham E, Shamir A. Differential cryptanalysis of snefru, khafre, redoc-ii, loki and lucifer[C] //Proc of the 12th Annual Int Cryptology Conf. Berlin: Springer, 1991: 156-171

[33]Biham E, Shamir. A differential cryptanalysis of the full 16-round DES[C] //Proc of Annual Int Cryptology Conf. Berlin: Springer, 1992: 487-496

[34]Cui Jingyi, Guo Jiansheng, Liu Yipeng. Impossible differential attack on Crypton[J]. Journal of Computer Research and Development, 2017, 54(7): 1525-1536 (in Chinese)(崔竞一, 郭建胜, 刘翼鹏. Crypton算法的不可能差分分析[J]. 计算机研究与发展, 2017, 54(7): 1525-1536)

[35]Todo Y, Morii M. Bit-based division property and application to Simon family[C] //Proc of the 23rd Int Conf on Fast Software Encryption. Berlin: Springer, 2016: 357-377

[36]Xiang Zejun, Zhang Wentao, Bao Zhenzhen, et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C] //Proc of the 22nd Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2016: 648-678

[37]Yu Xiaoli, Wu Wenling, Li Yanjun. Integral attack of reduced-round MIBS block cipher[J]. Journal of Computer Research and Development, 2013, 50(10): 2117-2125 (in Chinese)(于晓丽, 吴文玲, 李艳俊. 低轮MIBS分组密码的积分分析[J]. 计算机研究与发展, 2013, 50(10): 2117-2125)

[38]Zhang Wenying, Rijmen V. Division cryptanalysis of block ciphers with a binary diffusion layer[J]. IET Information Security, 2018, 13(2): 87-95

[39]Guo Jian, Jean J, Nikolic L, et al. Invariant subspace attack against full Midori64[C/OL] //Proc of from IACR Conf and Workshops. Berlin: Springer, 2015 [2021-04-01]. https://eprint.iacr.org/2015/1189.pdf

RAIN: A Lightweight Block Cipher Towards Software, Hardware and Threshold Implementations

Cao Meichun1, Zhang Wenying1, Chen Yanqin2, Xing Zhaohui1,3, and Wu Lei1

1(School of Information Science and Engineering, Shandong Normal University, Jinan 250358) 2(Sansec Technology Co., Ltd, Jinan 250014) 3(School of Sciences, Shandong Jiaotong University, Jinan 250357)

Abstract The lightweight block cipher RAIN proposed in this paper is based on the SPN(substitution permutation network) structure widely used in international block cipher design. It provides strong avalanche utility through iterative confusion layer S -box and diffusion layer, which not only guarantees strong security, but also takes into account the implementation of software and hardware. The algorithm supports 64 b block and 128 b block. Two different block lengths are implemented using the same round function structure, and the scheme is simple and beautiful. The confusion layer is implemented using a 4 b S -box. When the S -box is implemented, not only its security is considered, but also the software and hardware implementation of the S -box is considered. The hybrid operation of the diffusion layer provides high implementation performance. We evaluated the algorithm and give differential analysis, impossible differential analysis, integral attack and invariant subspace analysis. In the process of analysis, we combined some of the latest analysis methods and automated search based on MILP. Our algorithm can resist the existing analysis methods, and has greater safety redundancy. RAIN algorithm is efficient on software and hardware implementation, and it has excellent performance on PC, ARM platform and hardware FPGA platform. The algorithm S -box can be converted into basic logic operations, and the cost of resisting side channel attacks is low.

Key words lightweight tweakable block cipher; SPN(substitution permutation network) structure; block cipher design; RAIN algorithm; mixed integer linear programming

收稿日期：2020-11-09；修回日期：2021-02-22

基金项目：国家自然科学基金项目(61672330)；山东省自然科学基金项目(ZR2020KF011,ZR2020MF056)

This work was supported by the National Natural Science Foundation of China (61672330) and the Natural Science Foundation of Shandong Province of China (ZR2020KF011, ZR2020MF056).

通信作者：张文英(zhangwenying@sdnu.edu.cn)

(caomeichun@stu.sdnu.edu.cn)

中图法分类号 TP309.7

作者简介

Cao Meichun, born in 1993. PhD candidate. Student member of CCF. Her main research interests include information security and analysis and design of block ciphers.

曹梅春，1993年生.博士研究生,CCF学生会员.主要研究方向为信息安全和分组密码的分析与设计.

Zhang Wenying, born in 1970. PhD, professor, PhD supervisor. Member of CCF. Her main research interests include cryptography, Boolean function and Hash function analysis. (zhangwenying@stu.sdnu.edu.cn)

张文英，1970年生.博士，教授，博士生导师，CCF会员.主要研究方向为密码学、布尔函数和散列函数的分析.

Chen Yanqin, born in 1989. Master. Her main research interests include information security and analysis and design of block ciphers.

陈彦琴，1989年生.硕士.主要研究方向为信息安全和分组密码的分析与设计.

Xing Zhaohui, born in 1978. PhD candidate, associate professor, member of CCF. Her main research interests include cryptography, block cipher and Hash function analysis.

邢朝辉，1978年生.博士研究生，副教授，CCF会员.主要研究方向为密码学、分组密码和散列函数分析.

Lei Wu, born in 1980. PhD, associate professor, master supervisor. Member of CCF. His main research interest includes cryptology and cloud computing security and privacy protection.

吴 磊，1980年生.博士，副教授，硕士生导师，CCF会员.主要研究方向为密码学、云计算安全、隐私保护.

附录A. RAIN算法测试向量.

附录B. S盒S4的门限实现方案.

将代数次数为3的y0分解为代数次数为2的子函数g1，g2，g3的复合：

y0=x0x1x2+x1x3+x2x3+x0+x3, g1(x1,x2,x3)=x2+x3+x1x2+x1x3, g2(x0,x2,x3)=x0+x0x2+x2x3, g3(x0,x1,x2)=x1+x2+x0x1+x0x2.

(B1)

将式(B1)子函数与输入变量的共享份额设置为3，有：

g1=g11+g12+g13, g2=g21+g22+g23, g3=g31+g32+g13, x0=x01+x02+x03, x1=x11+x12+x13, x2=x21+x22+x23, x3=x31+x32+x33.

(B2)

共享份额为3的门限实现方案设计为

g11=x22+x33+x12x22+x12x23+x13x22+ x12x32+x12x33+x13x32,g12=x23+x31+x13x23+x13x21+x11x23+ x13x33+x13x31+x11x33, g13=x21+x32+x11x21+x11x22+x12x21+ x11x31+x11x32+x12x31, g21=x02+x02x22+x02x23+x03x22+ x22x32+x22x33+x23x32, g22=x03+x03x23+x03x21+x01x23+ x23x33+x23x31+x21x33, g23=x01+x01x21+x01x22+x02x21+ x21x31+x21x32+x22x31, g31=x12+x23+x02x12+x02x13+x03x12+ x02x22+x02x23+x03x22, g32=x13+x21+x03x13+x03x11+x01x13+ x03x23+x03x21+x01x23, g33=x11+x21+x01x11+x01x12+x02x11+ x01x21+x21x22+x02x21, y0(x0,x1,x2,x3)=g1+g2+g1g3+g2g3= g1(g1,g2,g3).

(B3)