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

基于双伪随机变换的轻量级分组密码VH和VHF (南京航空航天大学 计算机科学与技术学院，南京 210016) 摘 要：本文提出了基于双伪随机变换的轻量级分组密码VH和VHF算法，分别采用SP结构与Feistel结构。通过产生由256个字节随机排列组成的加密变换表S256和解密变换表S-1256，简化S盒的设计，并用于算法的密钥扩展和数据加解密。加密时，先对64bit分组数据的每个字节进行伪随机变换，从而实现混乱；再对数据的每个斜对角线进行伪随机变换，同时实现扩散和混乱。对VH和VHF采用差分和线性分析、不可能差分分析的分析方法进行安全分析。在安全基础上测试软、硬件实现效率，与现有的轻量级分组密码进行对比，VH和VHF的软硬件效率都高于同为面向8位平台的国际标准CLEFIA算法。关键词：轻量级分组密码；伪随机变换；差分分析；线性分析；不可能差分分析中图分类号:* 文献标志码: A 文章编号：1 介绍近年来，大量安全和高性能的分组密码设计推动了密码学的发展。例如，AES、Camellia和SHACAL等。然而，随着无线网络技术的发展，普通的分组密码算法难以满足资源受限的移动终端，需要轻量级密码算法，以满足软硬件、计算能力和能耗等资源受限终端的需求。CLEFIA3和PRESENT4作为轻量级分组密码的杰出代表，为我们基于当前最先进的技术设计适用于资源受限的移动终端提供了良好的时机。分组密码1是这样一个数学变换：它首先将明文消息用二进制数字序列x1,x2,编码表示并划分成长为m的分组x=(x1,x2,xm)，然后在密钥k=(k1,k2,kt)的作用下，将各分组信息分别变换成等长的数字序列y=(y1,y2,yn)后输出，这个过程可以用如图1所示为数学模型表示。本文提出了一种新的轻量级分组密码VH和VHF，即Vertical Horizontal (纵横)和Vertical Horizontal Feistel，分别采用SP和Feistel结构。VH是指将64 bits明文排列成8字节*8 bits 的矩阵，对其每一行每一列分别进行伪随机变换，支持长度为64、80、96、112 and 128 bits的密钥。VHF是将128 bits 明文分为长度为64 bits的左右两个分支，轮函数采用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位平台的国际标准CLEFIA算法，VH和VHF在安全和性能上取得了优越的平衡性，在满足安全性的基础上，提高了软件效率并兼顾了硬件效率，从而更加实用。图1 分组密码的数学模型2 VH和VHF算法2.1符号及术语说明本文采用的符号及说明如表1所示表1 VH算法采用的符号说明符号说明P明文Key扩展密钥K0子密钥C密文C0初始密文S256加密变换表S-1 256解密变换表EK加密算法DK解密算法|连接运算异或运算&与运算DSLS差分活动S盒线性活动S盒2.2 VH算法描述本文所述的轻量级分组密码算法VH采用SP1结构，分组长度为64bit，支持长度为64、80、96、112、128bit的密钥，相应的迭代轮数分别为r = 10、11、12、13、14轮。VH算法有3个参数：64bit明文P，密钥K，64bit密文C。加密算法用C=EK(P)表示，解密算法用P=DK(C)表示。VH算法的加解密过程包括以下步骤。2.2.1加密变换表S256和解密变换表S-1 256加解密S盒采用伪随机变换的方法产生。先计算 Ti=|256sini| ，其中表示向下取整运算；为了产生不重复的256个字节，i的取值由1到30000，遇到重复的排除，直到产生全部不重复的256个字节为止。加密变换表S256和解密变换表S-1 256是256个字节的一个伪随机排列，由T中字节轮换得到：STj=T(j+1)，ST255=T(0)；S-1Tj+1=T(j)，S-1T0=T(255)；其中0j254。伪随机变换的256个字节对应的散点图如图2所示，通过点的分布可以看出S盒的分散性和随机性。图2 伪随机变换的散点图2.2.2密钥扩展通过递推进行密钥扩展，将L字节的密钥K 扩展成8(r+1)字节：扩展密钥Key=K0K1Ki|Kr=k0k1|ki|k8r+7，每个Ki 为8字节，0ir；每个ki为单元字节，0i8r+7。对于8、10、12、14、16字节的密钥K，相应的迭代轮数分别为r =10、11、12、13、14轮。扩展密钥Key的前L字节就是密钥K：K=k0|k1|kL-1, Li8r+7时，扩展密钥Key中的ki由ki-L和ki-1两个字节递推得到，即ki=Ski -1ki-L。 2.2.3数据加密过程VH加密过程如图3所示，明文与初始密钥K0先进行异或运算，得到的结果再进行r轮迭代加密，每一轮加密包括S盒变换、P置换和轮密钥异或运算，输出的结果作为下一轮的输入，最终得到密文C。先进行初始加密，再进行r轮迭代加密，得到密文C，如图3所示：图3 VH算法加密描述a) 初始加密初始密文C0 =PK0。其中P为64bit初始明文，K0为密钥K的前8字节。b) r轮迭代加密i从1到r，每轮迭代包括以下三步：首先对数据进行“行伪随机变换”，即对数据的每个字节用加密S盒进行伪随机变换：Mi(j)=SCi-1(j)；其中i从1到r，Xi(j)表示Xi的第j个字节，0j7。再把64bit数据Mi排成8*8的方阵，对Mi的每个斜对角线用加密S盒进行伪随机变换：Pi0=SMi0&128|Mi1&64|Mi2&32|Mi3&16 |Mi4&8|Mi5&4|Mi6&2|Mi7&1Pi1=SMi1&128|Mi2&64|Mi3&32|Mi4&16 |Mi5&8|Mi6&4|Mi7&2|Mi8&1Pi2=SMi2&128|Mi3&64|Mi4&32|Mi5&16 |Mi6&8|Mi7&4|Mi0&2|Mi1&1Pi3=SMi3&128|Mi4&64|Mi5&32|Mi6&16 |Mi7&8|Mi0&4|Mi1&2|Mi(2)&1Pi4=SMi4&128|Mi5&64|Mi6&32|Mi7&16 |Mi0&8|Mi1&4|Mi2&2|Mi3&1Pi5=SMi5&128|Mi6&64|Mi7&32|Mi0&16 |Mi1&8|Mi2&4|Mi3&2|Mi4&1Pi6=SMi6&128|Mi7&64|Mi0&32|Mi1&16 |Mi2&8|Mi3&4|Mi4&2|Mi5&1Pi7=SMi7&128|Mi0&64|Mi1&32|Mi2&16 |Mi3&8|Mi4&4|Mi5&2|Mi6&1最后再将上述输出Pi与该轮的子密钥Ki进行异或得到该轮的密文：Ci=PiKi；其中i从1到r。最后一轮的输出结果Cr即为最终的密文C。2.2.4 数据解密过程a) 初始解密Pr=CKr ,其中C为64bit密文，Kr为扩展密钥的后8字节。b) r轮迭代解密i从r -1到0，每轮迭代包括以下三步：首先对数据进行“行伪随机变换”，即对数据的每个字节用解密S盒进行伪随机变换：Mij=S-1Pi+1(j)；其中i从r -1到0，Xi(j)表示Xi的第j个字节，0j7；再把64bit数据Mi排成8*8的方阵，对Mi的每个斜对角线用解密S盒进行伪随机变换：Ci0=S-1Mi0&128|Mi7&64|Mi6&32| Mi5&16|Mi4&8|Mi3&4|Mi2&2|Mi1&1Ci1=S-1Mi1&128|Mi0&64|Mi7&32| Mi6&16|Mi5&8|Mi4&4|Mi3&2|Mi2&1Ci2=S-1Mi2&128|Mi1&64|Mi0&32| Mi7&16|Mi6&8|Mi5&4|Mi4&2|Mi3&1Ci3=S-1Mi3&128|Mi2&64|Mi1&32| Mi0&16|Mi7&8|Mi6&4|Mi5&2|Mi4&1Ci4=S-1Mi4&128|Mi3&64|Mi2&32| Mi1&16|Mi0&8|Mi7&4|Mi6&2|Mi5&1Ci5=S-1Mi5&128|Mi4&64|Mi3&32| Mi2&16|Mi1&8|Mi0&4|Mi7&2|Mi6&1Ci6=S-1Mi6&128|Mi5&64|Mi4&32| Mi3&16|Mi2&8|Mi1&4|Mi0&2|Mi7&1Ci7=S-1Mi7&128|Mi6&64|Mi5&32| Mi4&16|Mi3&8|Mi2&4|Mi1&2|Mi0&1最后再将上述输出Ci与该轮的子密钥Ki进行异或得到该轮的明文：Pi=CiKi，其中i从r-1到0。最后一轮的输出结果P0即为明文P。2.3 VHF算法描述本文所述的轻量级分组密码算法VHF，采用Feistel结构，轮函数采用VH算法。VHF的分组长度为128比特，分为64比特长的左右两个分支Li和Ri，支持长度为64、80、96、112、128比特的密钥，相应的迭代轮数分别为r = 10、11、12、13、14轮。加密过程为:Lr=Rr-1Rr=Lr-1F(Rr-1,Kr-1)其中轮函数F 采用VH的加密流程，轮函数F为:sBoxLayer(Rr-1)pLayer(Rr-1)RoundKey(Rr-1，Kr-1)sBoxLayer：是一个关于字节的非线性变换，它将加密过程中的每个字节非线性地变换为另外一个字节。VHF 算法的字节变换中的S盒采用VH加密中的S盒。pLayer：行位移变换是对一个状态的每一行循环左移不同的位移量。第0 行不移位，第一行循环左移一个字节，第二行循环左移两个字节，第三行循环左移三个字节。即:RoundKey：VH算法有3个参数：128bit明文L|R，密钥K，128bit密文C。加密算法用C=EK(P)表示，解密算法用P=DK(C)表示。VH算法的加解密过程包括以下步骤。3 VH和VHF算法的软硬件实现3.1 软件效率在Intel(R)、Core(TM)、CPU为i7-3610QM、主频2.3GHz、内存8GB、C语言编程环境下测试，密钥长度为80bit的VH算法的效率。依次从100万比特数据选取到600万比特数据，VH-80算法的时间消耗如图3所示，可以计算出VH-80算法的软件效率为44.47Mb/s。与现有的轻量级分组密码算法MIBS5算法、CLEFIA算法和PRESENT算法的效率进行比较可以看出，VH算法软件实现所消耗的时间明显少于其它轻量级分组密码算法。VH-80算法、MIBS算法、CLEFIA-128算法、PRESENT算法的软件效率分别为44.47Mb/s、33.26 Mb/s、33.90Mb/s和0.98Mb/s，如表2所示。由此可见，VH-80软件效率优于其他轻量级分组密码算法。图3 VH-80算法与其他分组密码算法的时间消耗比较 3.2 硬件实现硬件实现效率一般用等效GE数来衡量。文献3对CLEFIA-128算法硬件实现的GE数作了估算，作者认为忽略不同的ASIC库的影响，实现CLEFIA-128算法需要5979个GE数。文献2指出存储1个比特需要6个GE数，实现1次异或运算需要约2.67个GE数。VH-80算法密钥扩展中字节的异或运算需要8个异或门，共21.36个GE数；每轮需存储长度为64bit的子密钥，共384个GE数。加密过程中，存储64bit明文需要384个GE数；S盒需要200个GE数；存储每轮生成的64bit长的密文需要384个GE数；加密过程中采用704个与门，共936.32个GE数；采用616个或门，共819.28个GE数；每轮加密明文需要和子密钥进行异或运算，需要12个异或门，总共53.4个GE数。VH算法与其他轻量级分组密码算法的硬件实现所需要的门电路数如表2所示，VH算法大约为3182个GE数，与CLEFIA算法的硬件实现所需要的门电路数5979GE比较可知，VH算法的硬件效率高于同为面向8位平台的国际标准CLEFIA算法。表2 VH算法与其他算法的软硬件效率轻量级分组密码算法软件效率(Mb/s)硬件效率(GE数)VH-8044.473182VHF-80MIBS33.261400CLEFIA-12833.905979PRESENT0.9815704 VH和VH算法的安全性分析4.1 差分分析和线性分析差分分析6和线性分析7一直以来都是针对分组密码最有效的攻击手段，所以确定一个分组密码的最大差分和线性分析的概率对分组密码的安全性评估是非常有必要的。目前，新提出任何一个分组密码算法时，都要具备抵抗这两种攻击的能力。自从差分和线性分析被提出以来，学术界针对它们作了大量研究，文献6-8详细论述了评估密码抗差分和线性分析能力的实际方法，即通过计算活动S盒个数来计算最大差分和线性概率，文献3中作者在对CLEFIA算法进行评估时运用了这种方法，其它的诸如AES、Camellia等分组密码算法的评估也采用了该方法。该方法的主要有以下一些理论。定义1：任意给定x,z,x,zGF(2m)，S盒的差分和线性概率定义为：DPSixz=#xGF(2m)|SixSixx=z2mLPSizx=(2#xGF(2m)|xx=Si(x)z2m-1)2定义2：S盒的最大差分概率和最大线性概率分别定义为：ps=maximaxx0,zDPsi(xz)qs=maximaxx,z0LPsi(zx)定义3：如果一个S盒的输入差非零的话，就说该S盒为差分活动S盒；同理，如果一个S盒的输出掩码非零的话，就说该S盒是线性活动S盒。定义4：设X=(x1,xn)GF(2m)n，则X的汉明重量定义为：HX=#i|xi0定义5：设S盒是双射的，即既是单射又是满射，则混淆层（即P-函数）的差分分支数定义为：pd=minx0(HX+H(Y)其中X是指混淆层的输入差分，而Y是指混淆层的输出差分。定义6：假设H(X(i)是第i轮的差分活动S盒数，则r轮Feistel密码的差分特征概率pd(r)满足以下关系：pd(r)psmin(X0,X1,Xr+1(0,0,0)i=1rH(X(i)根据这个定义，计算最大差分特征概率可以等价转化为计算最小差分活动S盒的个数，它的定义如下：D(r)=min(X0,X1,Xr+1(0,0,0)i=1rH(X(i)定义769：混淆层（即P-函数）的线性分支数定义为：pl=minY0(HZ+HY)其中Y是混淆层的输出掩码，而Z是混淆层的输入掩码。定义869：假设HZ(i)是第i轮的线性活动S盒数，则r轮Feistel密码的线性特征概率为pl(r)满足以下关系：pl(r)plmin(Y0,Y1,Yr+1(0,0,0)i=1rHZ(i)其中，Z(i)=P*(Y(i)，P*是混淆函数，且它的掩码是与扩散函数相关的。根据这个定义，计算最大线性特征概率可以等价转化为计算最小线性活动S盒的个数，它的定义如下：L(r)=min(Y0,Y1,Yr+1(0,0,0)i=1rHZ(i)通过计算可得VH算法的S盒的最大差分概率是2-4.415，通过程序计算密钥长度为80bit的VH算法前10轮的活动S盒的个数DS，如表4所示。由此可得VH算法的4轮最大差分概率为DCPmax4r221*(-4.415)=2-67.922-64。当迭代轮数大于4轮时，找不到一个有效的差分特征进行分析，所以完整轮数的VH算法可以抵抗差分分析。通过计算可得VH算法的S盒的最大线性概率是2-2.83，通过程序计算密钥长度为80bit的VH算法前10轮的活动S盒的个数LS，如表4所示。由此可得VH算法的4轮最大线性概率为LCPmax4r224*(-2.83)=2-67.622-64。当迭代轮数大于4轮时，找不到一个有效的线性特征进行分析，所以完整轮数的VH算法可以抵抗线性分析。表3 VH和VHF算法前10轮的差分和线性活动S盒个数轮数DSLS轮数DSLS100635402787424831416849564212495664528321063723.3 不可能差分分析不可能差分分析9对VH和VHF算法来说是一种非常有效的攻击手段。J. Kim等10发明了一种矩算法-method用来对分组密码的结构进行不可能差分分析，该方法能够找到不同的不可能差分路径。采用此方法对VH和VHF算法进行不可能差分分析，得到最大轮数为6轮，找到了8条不可差分路径。0,0,0,0,6r0,0,0,0, p=10,0,0,06r0,0,0,0, p=10,0,0,06r0,0,0,0 p=10,0,0,0,6r0,0,0,0 p=1,0,0,0,0,6r,0,0,0,0, p=1,0,0,0,06r0,0,0,0,0,0 p=1,0,0,0,0,6r,0,0,0,0, p=1,0,0,0,06r,0,0,0,0 p=1式中： GF(28),表示非零差分。由此可知，不可能差分分析对VH和VHF算法攻击无效。4 结束语文中提出了一种基于双伪随机变换的轻量级分组密码算法VH和VHF，应用于无线通信中低成本嵌入式移动终端。通过产生加密变换表S256进行行伪随机变换和对角线伪随机变换，实现混淆和扩散。通过软件效率测试与MIBS、CLEFIA、PRESENT等轻量级分组密码算法进行比较得出，VH和VHF算法软件实现性能优异；通过硬件实现与其他轻量级分组密码算法进行比较，得到3182个GE数高于国际标准算法CLEFIA的5979个GE数；总体来说，VH算法的软硬件效率都高于同为面向8位平台的国际标准CLEFIA算法。对VH和VHF算法采用差分、线性分析和不可能差分分析方法进行安全分析，验证了VH和VHF算法的安全性。 参考文献1 吴文玲，冯登国，张文涛. 分组密码的设计与分析(第2版)M. 北京：清华大学出版社，2009.2 Juels A, Weis S A. Authenticating pervasive devices with human protocols C/Advances in Cryptology-CRYPTO 2005. Springer Berlin Heidelberg, 2005: 293-308.3 Shirai T, Shibutani K, Akishita T, et al. The 128-bit Blockcipher CLEFIAC/Fast software encryption. Springer Berlin Heidelberg, 2007: 181-195.4 Bogdanov A, Knudsen L R, Leander G, et al. PRESENT:An ultra-lightweight block cipherM/Cryptographic Hardware and Embedded Systems-CHES 2007. Springer Berlin Heidelberg, 2007: 450-466.5 Izadi M, Sadeghiyan B, Sadeghian S S, et al. MIBS: a new lightweight block cipherM/Cryptology and Network Securi