基于S盒优化的轻量级加密算法设计

S盒作为DES算法的一个关键环节，它的设计好坏直接影响DES的加密性能。为此，我们首先根据DES算法，并结合分组密码特点提出了一种基于s盒优化的轻量级分组加密算法。

一、轻量级安全加密算法过程及实现

该算法的密钥k采用28bit的0、1符号串，明文m和密文c则是由0，1组成的长度为32bit的符号串。设m=m1m2...m32，c=c1c2...32，k=k1k2...k28。由于初始置换及其逆置换不影响加密，没有密码学意义，故将其取消，其加密过程可表达如下：

DES（m）=T16*T15....T2*T1（m）。算法流程图如图1所示。

加密过程可由明文初始化、迭代过程、密钥生成方案完成。

先将明文串的每一个字符转化为其ASCII码，用8位二进制0，1串来表示，依次选取32bit划为一块，共将明文分为n块，若最后一块不满32bit，可以补随机产生的0，1串，但必须让接收者清楚哪些是多余的明文。

本加密算法的迭代过程与DES中类似。先将要加密的32bit明文块分为左右两块等长L0，R0，迭代计算式为：Li=Ri1，Ri=Li-1⊕f（Ri-1，ki），再将16bit的Ri1经E作用膨胀为24bit，
再与ki作异或运算，将运算结果分为4组，通过S盒输出结果为16bit，S盒的输出又经过一个固定置换P后得f（Ri-1，ki），迭代8轮后的结果L8R8左右交换为R8L8即密文。

每一轮都使用不同的、从初始密钥k导出的24 bit密钥ki（1≤i≤16）。k是由一个长度为32的比特串，删去第8，16，24，32位的4个校验比特得到的，校验比特主要为了检错。

二、S盒设计

1、 S盒元素选取方案

S盒中输出元素是由输入的六个比特确定，一般将首末两位构成的二进制数作为行标，而中间四位二进制数作为列标，通过增加逻辑陷阱进行选取。逻辑运算不仅实现简单，而且便于编程修改，在一定周期内可通过修改逻辑门来提高算法安全性。具体过程如下:

①在迭代过程中计算Ri-1⊕E后，将结果24比特串分成4个长度为6的比特串，将它们记为B=B1B2B3B4；

②使用4个S1、S2、S3、S4，每个Si是一个固定的4×16阶矩阵，它的元素来自0到15这16个整数。给定一个长度为6的比特串，例如：B1=b1b2b3b4b5b6，我们可按下列办法计算S1盒的输出S1（B1）：用两个比特b2、b3对应的整数r （0≤r≤3）来确定S1的行（所谓两个比特b2、b3对应的整数r意指r的二进制表示为b2、b3，以下含义相同），用b1⊕b4，b4，b5，b6四位对应的整数c（0≤r≤15）来确定S1的列，S1（B1）的取值就是S1的第r行第c列的整数所对应的二进制表示。将四个S盒的输出比特记为：Dj=Sj（Bj），1≤j≤4。

③将长度为16的比特串D=D1D2D3D4通过一个固定的置换P，所得结果即为迭代过程中的f（Ri-1，ki）。

表1给出了四个S盒的行列标的选择方法，通过增加逻辑运算来改变传统DES算法中的行列标选择位，打乱了原来S盒固有的选择模式，这种方案增加了元素选择方式，不仅能使算法的安全性得到提高，而且由于逻辑运算实现起来较简单，可以使算法在开销方面节俭很多。

2、S盒元素设计

S盒作为DES算法中唯一的非线性器件，是加密的关键所在，然而，多年来，一直未有人将S盒的设计准则公开。从已有的关于S盒的推理不难看出有如下几条准则。

①S盒的每一行是整数0，1，2，…，15的一个置换；

②每个S盒均为6位输入，4位输出；

③S盒的输出都不是其输入的简单线性或仿射函数；

④改变S盒的1位输入，至少要引起2位的输出变化。

通过分析知S盒行列标的选择位已发生变化，因此必须根据以上的原则重新设计S盒中元素来满足加密所需，其中要使输入的1位改变至少导致输出的2位改变是S盒非线性的关键准则。首先假设行标的2位不变，那么对于输入的4位列标中有1位发生变化，则所对应的S盒中元素至少2位变化，以S1盒设计为例说明，则有表2所示的相关表，其他三个S盒设计类似。表中带黑框的数为排在该行列代码前面的列号，下划线标出的表示与自己相同的列号可不用考虑。

当b2b3=00时，如果b1b4b5b6=0100，那么b1⊕b4=1、b4=1、b5=0、b6=0，即表示选择的是S1盒0行12列的元素，从表2中可看出，该元素必须与它前面的0、5、6列中的元素至少有两位不同，也就是说必须从0、5、6列已选择元素的非线性相关数的交集中选取。

当b2b3=01或10时，由于与b2b3=00有1位不同，故该行元素的选取方法与第二行类似。当b2b3=11，由于与01，11均有一位不同，必须考虑与第1行和第2行的对应列的相关性。即第3行的每1位元素的选取不仅要考虑与本行的列代码1位不同的相关性，还要考虑与1行和2行对应列的相关性。例如:当b1b2b3b4b5b6=011101，则表示选择S盒第3行第13列元素，由于非线性要求，查表2知，该元素必须与1、4、7列元素至少有2位不同，还要与第1行13列元素，以及第2行13列中元素不同，故只能从这五个元素的交集中去选取，以此类推。表3仅给出了S1盒的元素的选定结果，其他S盒选择过程与其类似。

三、安全性分析

这4个S盒的输入输出对应于4个函数。每个函数的定义域都是{0，1，2，3，…，63}，而值域都是{0，1，2，3，…，15}。因为这4个S盒是相互独立的，因而可以计算出这4个S盒并出的概率分布，根据以往分析，实际DES的S盒统计特性近似满足正态分布，故也可认为本文设计的S盒近似满足正态分布特性。

由于4个S盒的输出之和取值范围是{0，1，2，3，…，60}，可计算出它的均值和方差为μ=（0+1+2+...+60）/61=30和σ=17.6068。

图2分别给出了实际设计的四个S盒的概率密度曲线、理论曲线、DES算法S盒曲线以及实际曲线与DES算法S盒输出概率的误差曲线，从图2中可看出理论概率密度曲线的输出值在60-80之间仍能取到，但是根据以上分析可知实际的四个S盒输出值不可能超过60。通过本算法设计的四个S盒的实际概率密度曲线与理论概率密度曲线以及标准DES算法S盒曲线进行比较，本算法S盒输出与理论S盒输出概率密度误差公式以及与DES算法S盒输出概率密度误差公式分别为如式（1）、式（2）所示：

本算法S盒输出与理论S盒输出概率密度曲线平均误差为1.40×10-3，最大误差1.96×10-2，与DES算法S盒输出概率密度平均误差为1.88×10-3，最大误差2.3×10-3，与它们误差基本控制在10-3数量级，因此统计特性与DES算法中S盒统计特性近似，具有较高的安全性，从图2中以可看出绝大多数明文经过S盒替换之后，本算法中4个子S盒的输出之和将集中在30周围，DES算法也有此特性，因此，若在选择密文时使得其相应于4个S盒的输出之和尽量远离30，可防止选择密文攻击。

加密技术应用的领域很广，然而标准加密算法受成本限制在低端领域很难应用。S盒作为DES算法中的唯一非线性器件，是起混乱作用的重要环节，其设计优劣直接影响整个加密系统的性能。