基于双伪随机变换的轻量级分组密码VH和VHF

1、基于双伪随机变换的轻量级分组密码VH和VHF代学俊黄玉划（南京杭空杭天大学计算机科学与技术学院，南京210016）摘要：本文提出了基于双伪随机变换的轻量级分组密码VH和VHF算法，分别采用SP结构与Feistel结构.通过产生由256个字节随机排列组成的加密变换表5256）和解密变换表5T256,简化S盒的设计，并用于算法的密钥扩展和数据加解密。加密时，先对64bit分组数据的每个字节进行伪通机变换，从而实现混乱；再对数据的每个科对向线进行伪随机变换，同时实现扩散和混乱.对VH和VHF关用差分和我收分析.不可能差分分析的分析方法进行安全分析.在安全基础上测试软、硬件实现效率，与现有的轻量级分组

2、密码进行对比，VH和YHF的软硬件效率都高于同为面向8位平台的国际标准CLEFIA算法。关词：轻量级分组密码；优应机变换：差分分析；线性分析；不可能差分分析中图分类号：*文献标志码：A文章编号：1介当近年来，大量安全和高性能的分组密码设计推动了密码学的发展。例如，AES、Camellia和SHACAL等。然而，随着无线网络技术的发展，普通的分组密码算法难以满足资源受限的移动终端,需要轻量级密码算法,以满足软硬件、计算能力和能耗等资源受限终端的需求.CIEFIA和PRESENT】作为轻局级分组密码的杰出代表，为我们基于当前最先进的技术设计适用于资源受限的移动终端提供了良好的时机分组密码闺是这样一

3、个数学变换:它苜先将明文消息用二进制数字序列必编码表示并划分成长为m的分组x=Q“2，Tm），然后在密钥1=（比,%，-，&）的作用下，将各分组信息分别变换成等长的数字序列y=（%小2，.“，%）后输出，这个过程可以用如图1所示为数学模型表示.本文提出了一种新的轻试级分组率:码VH和VHF,即VerticalHorizontal（纵横）和VerticalHorizontalFeistel.分别采用SP和Feistel结构。VH是指将64bits明文排列成8字节8bits的矩阵，对其每一行每一列分别进行伪随机变换，支持长度为64、80、96、112and128bits的密钥VHF是将128bit

4、s明文分为长度为64bits的左右两个分支，轮函数采用VH兜法.VH和VHF新颖的设计方法之一是采用伪随机变换构造256个字节的加密变换表和解密变换表，简化了S盒的设计，充分体现轻量级分组密码实现占用空间小的特点。此外，VH和VHF经过P置换后,对已置换过的对角线数据进行伪随机变换,提高了它的安全性。VH和VHF对当前已知的攻击方法达到足够的免疫力并旦在硬件实现和软件消耗上呈现高效性。VH的硬件实现需要3182个GE（等效门电路）数.软件效率为44.47Mb/s。而CLEFIA的硬件实现达到5979个GE数,软件效率为33.90Mb/s=我们认为VH和VHF算法的软硬件效率部高于同为面向8位平

5、台的国际标准CLEFIA算法，VH和VHF化安全和性能上取得了优越的平衡性，在满足安全性的基础上，提高了软件效率并兼顾了硬件效率，从而更加实用.图1分组密码的数学模型2VH和VHF算法2.1符号及术语说明本文采用的符号及说明如表1所示VH算法采用的符号说明符号说明P明文Key扩展密钥/于密包C密文Co初始密文S256加密变换表必解密变换表Ek加密区法%解密算法1连接运算异或运算&与运尊DS差分活动S盒LS线性活动S盒22VH算法描述本文所述的轻量级分组密码算法VH采用SR.结构,分组长度为64bit,支持长度为6k80、96、112.128bit的密钥，相应的迭代轮数分别为r=10、11、12

6、、13、14轮。VH尊法有3个参数：64bit明文尸，密钥其6,lbit密文C加密算法用C=耳伊)表示，解密算法用=Dk(C)表示.VH算法的加解密过程包括以下步骤.221加密变换表S256和解密变换表ST256加解密S盒采用伪随机变换的方法产生。先计算E)=256s，n”/,其中表示FJ向下取整运算：为了产生不重复的256个字节,1的取值由1到30000,遇到重复的排除，直到产生全部不重复的256个字节为止加密变换表S256和解密变换表S-256是256个字节的一个伪随机排列.由T中字节轮换得到：ST0)=T(/+1),ST(255)=T(0);5叩(/+1)=顶,S-,T(O)=7(255

7、):其中0WjW2540伪随机变换的256个字节对应的散点图如图2所示，通过点的分布可以看出S盒的分散性和随机性。图2伪随机变换的散点图2.2.2密钥扩展通过递推进行密钥扩展,将L字节的密钥K扩展成8(r+l)字节：扩展密钥K”=KJKJ闾|K,=kjkj每个长为8字节,OW/Wrs每个号为单元字节，0/48r+70对于8、10、12、14、16字节的密钥相应的迭代轮数分别为1=10、11、12、13、14轮.扩展密钥Key的前L字节就是击钊K：1=同“k”2SW8r+7时,扩展密钥Key中的k川因一和用_两个字节递推得到，即冗=5因79卜一2.2.3数据加密过程VH加密过程如图3所示，明文与

8、初始密钥片先进行异或运算，得到的结果再进行r轮迭代加密，每一轮加密包括S盒变换、尸置换和轮密钥异或运算，输出的结果作为下一轮的输入，最终得到密文C。先进行初始加密，再进行r轮迭代加密，得到密文C,如图3所示：图3VH算法加密描述a) 初始加密初始密文C。=P3K。其中尸为64bit初始明文，Ko为密钥K的前8字节。b) 2轮迭代加密i从1到r,保轮迭代包括以下三步：首先对数据进行“行伪随机变换”，即对数据的每个字节用加密S盒进行伪随机变换：M,S=SCiS)：其中I从1到r,X。)表示X的第J个字节，0WjW7再把64bM数捌此排成8-8的方阵，对M1的每个斜对角线用加密S盒进行伪随机变换:H

9、(0)=SM(0)&128|M(l)&64|M|&32|此(3)&16|M,(4)&8|M(5)&4|Ml(6)a2|M,(7)&l)P,(1)=S(1Ml(1)&128HM&|附(3)&3即必(4)&16|固&8|M(6)&4|M(7)&2|M(8)&1)P,(2)=SM2)&128|M,(3)aXl|M(4)&3列四(5)&16|Ml(6)a8|H(7)&4|M1(0)&2|M1(l)&l)凡(3)=5M1(3)&128|M,(4)&64|M1(5)&32|MI(6)&16|M(7)a8|Mi(0)a4|Ml(l)a2|M1(2)aiR(4)=SM.(4)&128|此&64|必(6)&32

10、此(7)&16P,(5)=SM(5)&128|血(6)&64M(7)&3*M(0)&16|Mz(l)a8|M,(2)a4|M1(3)aZ|MI(4)ai)H(6)=SMl(6)ai28|M(7)a64|Ml(0)a3q|Ml(l)ai6I阳(2)&8M(3)&4|M,(4)&2|M&1-=5Ml(7)&128|MI(0)&64|Ml(l)&32|M1(2)&16最后再将上述输出B与该轮的子密钥片进行异或得到该轮的密文：C,=P.9K,：其中I从1到fo最后一轮的输出结果Cr即为鼓终的密文C.2.2.4数据解密过福a) 初始解密p,=cr，其中。为61bit密文，尤为扩展密钥的后8字节.b) 2

11、轮迭代解密，从r-1到0,每轮迭代包括以下三步：首先对数据进行“行伪随机变换”,即对数据的每个字节用解密S盒进行仍随机变换：“=7用.|0)：其中1从7-1到0.XQ)表示用的第J个字节，0WJW7：再把64bit数据风排成8*8的方阵,对M的每个斜对角线用解密S盒进行伪随机变换：C(0)=S1Mi(0)&128|M1(7)a64|MI(6)&32|M&1句|阳&8|阳(3)&4|阳,q(l)=SlM|(l)&128|MI(0)&64|M1(7)432|句网&8|阳(4)&4|M(3)&2|M&1DG(2)=5-1M1(2)&i28|M1(l)&64|MI(0)&32|四旬|阳(6)&8|阳&

12、4|风(4)&列明(3)&卬C,(3)=尸M(3)h281M&6孙此(1)&32雨(0)&1创阳&叫阳&4|此C(4)=5,Mi(4)&i28|MI(3)&64|MI(2)&32|明阳&2mM&卬C,=5Tm&1281M&64|此(3)&32M(2)aiq|Ml(i)a8|M1(o)a4|Ml(7)a2|M1(6)aiDG(6)=5-l(MJ(6)ai28|Ml(5)a64|M1(4)*32lM&1创阳&8|MM)&4M(0)&C(7)=5*,xWi(7)&128|xWi(6)&64|xWi(5)&32|印阳&8mM(2)&4|M(1)&2|M(O)&1D最后再将上述输出G与该轮的子密钥周进行

13、异或得到该轮的明文：p.=c,9K,其中1从L1到0。最后一轮的输出结果P。即为明文产。23VHF算法描述木文所述的轻显级分组密码算法VHF.采用Feistel结构，轮函数采用VH克法。VHF的分组长度为128比特,分为64比特长的左右两个分支乙和凡，支持长度为64、80、96、112、128比特的密钥,相应的迭代轮数分别为r=10、11、12、13、14轮。加密过程为:L=RiRr=Lr-1F(RLt)其中轮函数歹采用VH的加密流程，轮函数尸为：sBoxLayer(Rr-i)pLayerU?1)RoundKey(Z?r-P除一。sBoxLayer：是一个关了字节的非线性变换，它将加含过程中的

14、每个字节非线性地变换为另外一个字节。VHF算法的字节变换中的S愈:采用VH加密中的5盒。player：行位移变换是对一个状态的你一行循环左移不同的位移量.第0行不移位，第一行循环左移一个字节，第二行循环左移两个字节，第三行循环左移三个字节。即：RoixidKey：VH克法TT3个参数:128bit明文”|总密钥K.128bit密文C加密比法用C=E(P)表示，解密算法用P=%(C)表示.VH算法的加解密过程包括以下步骤。3VH和VHF算法的软硬件实现3-1软件效率在Intel(R)、Core(TM).CPU为i7-3610QM、主频2.3GHz、内存8GB、C语言编程环境下测试，密钥长度为80

15、bit的VH尊法的效率。依次从100万比特数据选取到600万比特数据,VH-80尊法的时间消耗如图3所示，可以计算出VH-80和法的软件效率为44.47Mb/so与现仃的轻量级分组密码算法NIBS算法、CLEFIA算法和PRESENT笠法的效率进行比较可以看出，VH比法软件实现所消耗的时间明显少于其它轻量级分组密码党法.VH-80算法、MIBS尊法、CLEFIA-128算法、PRESENT尊法的软件效率分别为44.47Mb/s、33.26Mb/s、33.90b/s和0.98Mb/s,如表2所示。由此可见,VH-80软件效率优F其他轻量级分组密码算法。图3VH-80算法与其他分组密码算法的时间消

16、耗比较32硬件实现硬件实现效率一般用等效GE数来衡量。文献对CLEFIA-128尊法硬件实现的GE数作估算，作者认为忽略不同的ASIC库的影响，实现CLEFIA-128算法需要5979个GE数。文献日指出存储1个比特需要6个GE数,实现1次异或运算需要约2.67个GE数。VH-80算法密钥扩展中字节的异或运克需要8个异或门，共21.36个GE数：每轮需存储长度为64bit的子密钥,共38-1个GE数。加密过程中，存储6-lbit明文需耍381个GE数：S盒需要200个GE数：存储每轮生成的61bit长的密文需要381个GE数：加密过程中采用704个与门,共936.32个GE数：采用616个或门

17、,共819.28个GE数：每轮加密明文需要和子密钥进行异或运身.需要12个异或门，总共53.4个GE数VH克法与其他轻量级分组密码算法的硬件实现所需要的门电路数如表2所示,VH算法大约为3182个GE数，与CLEFIA算法的硬件实现所需要的门电路数5979GE比较可知，VH算法的硬件效率高于同为面向8位平台的国际标准CLEFIA算法。表2VH兜法与其他算法的软硬件效率轻量级分组软件效率硬件效率密码算法（Mb/s）（GE教）VH-8044.473182CLEFIA-12833.905979PRESE1TT0981570VHF-8033261100NIBS4VH和VH算法的安全性分析4.1差分分析

18、和线性分析片分分析间和线性分析向一口以来都是针对分组密码最有效的攻击手段，所以确定一个分组密码的最大差分和线性分析的概率对分组密码的安全性评估是非常有必要的。U前，新提出任何一个分组密码兑法时，都要具备抵抗这两种攻击的能力。自从差分和线性分析被提出以来.学术界针对它们作了大量研究.文献【I】详细论述了评估密码抗差分和线性分析能力的实际方法，即通过计算活动S盒个数来计算最大差分和线性概率，文献中作者在对CLEFIA算法进行评估时运用了这种方法，其它的诸如AES、Camellia等分组密码算法的评估也采用了该方法.该方法的主要TT以下一代理论.定义1：任意给定Arqz,rx,rzGF（2m）,S盒

19、的差分和线性概率定义为：3=-）|scx）=gcz、n（xeGF（2r）xrx=s4（x）rz）今LPrz-rx）=（2x-2m定义2：S盒的最大整分概率和最大线性概率分别定义为：ps=maxnraxDPs（Ax-Ac）q,=raaxmax叱（1；-1）定义3：如果一个S盒的输入差非零的话，就说该S盒为年分活动S盒：同理，如果一个S盒的输出掩码非零的话，就说该S盒是线性活动S食。定义4：匿=（必,xn）eGF（2）,则丫的汉明重量定义为：%=*0）定义5：设S盒是双射的，即既是单射乂是满射，则混治层（即尸函数）的差分分支数定义为：Pd=TT（H3G）+/L（Ay）其中是指混淆层的输入差分,而非

20、是指混淆层的输出差分.定义6：假设儿f?是第1轮的基分活动S盒数，则2轮Feistel密码的基分特征概率P?满足以下关系：p）=mtnV定义7：混清层(即尸函数)的线性分支数定义为：P尸向斯3(%(/)+/()其中是混淆层的输出掩码,而Z是混谓层的输入掩码。定义即1：假设儿(rz)是第i轮的线性活动S盒数，则r轮Feistel密码的线性特征概率为pf)满足以下关系：其中，rzo=p.(r).P*是混淆函数，且它的掩码是与扩散函数相关的。根据这个定义，计克最大线性特征概率可以等价转化为计算最小线性活动S盒的个数，它的定义如下：坟)=minVH“(rZ(”通过计算可得VH算法的S盒的最大至分概率是

21、2一4加5,通过程序计算密钥长度为80bit的VH算法前10轮的活动S盒的个数DS,如表4所示.由此可得VH算法的4轮最大片分概率为DCkZW*=2-679242*。当迭代轮数大于4轮时，找不到一个有效的片分特征进行分析,所以完整轮数的VH算法可以抵抗星分分析。通过计克可得VH算法的S盒的最大线性概率是2-2相，通过程序计算密钥长度为80bit的VH算法前10轮的活动S盒的个数LS,如表4所示.由此可得VH算法的4轮最大线性概率为LCg12“(-)=2-22-匕当迭代轮数大于4轮时，找不到一个有效的线性特征进行分析，所以完整轮数的VH算法可以抵抗线性分析。衣3VM和VHF鳏法前10轮的差分和戌

22、性活MS盒个收轮数DSLS轮数DSLS100635402一i871218311168195642124956615283210637233不可能差分分析不可能差分分析对VH和VHF党法来说是一种非常有效的攻击手段。J.Kim等.发明/一种矩算法method用来对分组密码的结构进行不可能七分分析，该方法能够找到不同的不可能星分路径。采用此方法对VH和VHF算法进行不可能星分分析，得到最大轮数为6轮,找到了8条不可七分路径.(0,0Aat0,a,a,a)(0,0,0,0,a,a,a,a)p=1(0,0a0,a,Q,a,0)(0Q0Qa,Q,%Q)p=1(0a0,aMa,0,0)?(0Q0aQ,aa

23、0)p=1(0aaa0,0,0,a)g(0aa,a,%0,0,0)p=1(a.0,0,0,%0,Q,a)T(a，Q，QMQ)p=1(Q,O,Q,Q,a,O,OQ)，(O,O,Q,Q,OQ,0.O)p=13，Q,O,O,OaO,Q)*QMa,O,O,O,0,Q)p=1(QaQ,oaOaO)(a,a,a,Q,OAO,0)p=1式中：awGF(28),表示非零片分。由此可知,不可能看分分析对VH和VHF算法攻击无效。4结束语文中提出了一种基双伪随机变换的轻量级分组密码算法VH和VHF.应用无线通信中低成本嵌入式移动终端.通过产生加密变换表C256进行行伪随机变换和对角线伪随机变换，实现混淆和扩散。通

24、过软件效率测试与NIBS、CLEFIA.PRESENT等初鼠级分组密码算法进行比较得出，VH和VHF算法软件实现性能优异：通过硬件实现与其他轻量级分组密码算法进行比较，得到3182个GE数高丁国际标准算法CLEFIA的5979个GE数：总体来说，VH克法的软硬件效率都高于同为面向8位平台的国际标准CLEFIA克法.对VH和VHF獴法采用差分、线性分析和不可能度分分析方法进行安全分析，验证了VH和VHF算法的安全性。叁考文献1吴文玲.冯整国,张文涛.分如密码的议,计与分析（第2版）M.北京：才华大学出版社.2009.2 JuelsAWeisSA.Authenticatingpervasivede

25、viceswithhumanprotocolsC/AdvancesinCryptology-CRYPTO2005.SpringerBerlinHeidelberg.2005：293-308.3 ShiraiT.ShibutaniK.AkishitaT.etal.The128-bitBlockcipherCLEFIAC/Fastsoftwareencryption.SpringerBerlinHeidelberg.2007:181-195.4 BoxdanovA,KnudsenLR.LeanderG.etal.PRESENT：Anultra-lightweightblockcipherM/CryptographicHardwareandEmbeddedSystems-CHES2007.SpringerBerIinHeidelberg.2007：450-466.5 IzadiM.SadeghiyanB.SadeghianSS.etal.MI