DES中S盒差分概率表的实现

陈海红

（赤峰学院 计算机与信息工程学院，内蒙古 赤峰 024000）

DES中S盒差分概率表的实现

陈海红

（赤峰学院 计算机与信息工程学院，内蒙古 赤峰 024000）

差分分析是分组密码最常用的密码分析技术，DES就是其中的一种.采用C++语言实现了计算差分概率表的过程，并对DES的S8盒进行了差分分析，得出最大概率为1/4，共有5种情况.

DES；S盒；差分分析；概率分布

1 DES算法的差分分析

DES是现代对称密钥分组密码的典型代表，算法分组长度为64位，密钥长度56位，生成的密文也是64位.加密过程由初始置换、16个Feistel轮和最终置换组成.每一轮由混合器和交换器构成.DES的核心是轮函数，轮函数的输入是每一轮的右半部分的32位，以及48位的轮密钥.轮函数由扩展换位盒、轮密钥加、换字盒和直接换位盒构成.DES采用8个6*4的S盒.

差分分析是现代分组密码最常用一种密码分析技术，经常用其检验一种密码算法的抗攻击能力，DES也不例外.DES的差分分析用到如下的性质：

性质1[1]在有限域GF(2n)中，每一个字符都是其自身的加法逆.即x茌x=0.

性质2[1]对一个带有恒等元素的字符异或不能改变该字符.即x茌0=x.

由此可知，轮密钥的作用被取消了.

而C1茌C2=X1茌X2(存在概率关系).

因此，差分分析的首要任务就落在了计算S盒的差分概率表上，而DES的S盒是6*4结构，即输入6位，输出4位，如果输入差分是001001，从左到右分别标记为p0p1p2p3p4p5，则表示p2位和p5位不同，其余相同，p2和p5可组合出2对，分别为00和11,01和10，其余4位相同位可组合出24种情况，分别为 0000、0001、0010……1111，组合在一起共有32种情况，由此计算输出差分的概率.

2 差分概率表的实现

计算差分概率表的程序使用C++语言实现，输入差分应该是二进制形式，但是使用二进制不容易操作，因此程序使用数组来代替.有如下定义：

Din，b：表示输入差分的数组

1p：输入差分中所有是1的位置

0p：输入差分中所有是0的位置

index0：记录输入差分中0的具体位置及个数

index1：记录输入差分中1的具体位置及个数

（1）首先计算出输入差分中1的个数和0的个数，以及1和0的具体位置，个数分别记入index1和index0数组的第零个位置，以便确定循环的次数.如输入差分是001001，则：

index0的数据为：44310

index1的数据为：252

（2）将Din数组全部清零，从零开始循环，并将Din数值记入b中.

（3）计算第一个数P1的下标，行下标等于Din的第一个数和最后一个数合起来的结果，列下标等于中间的四位数的结果，即如果Din等于000011，则：

行下标等于：2*Din[0]+1*Din[5]=1

列下标等于：8*Din[1]+4*Din[2]+2*Din[3]+1*Din[4]=1

根据下标查S盒表得到第一个数值记入first

（4）修改Din的数值，计算第二个数，第二个数应该为：index1所指示的位置处的数字如果是0变为 1，如果是 1变为 0；即如（3）中 Din为 000011，则修改后Din的值为001010.

（5）计算第二个数的下标，方法同（3），根据下标查S盒表得到第二个数字记入second.

（6）求first和second异或的值，得到一个差分结果.

（7）对b中的1p执行类似二进制的加1操作，将b记入Din中，转（3）循环2index1[0]-1次.

（8）对b中的0p执行类似二进制的加1操作，将 b记入 Din 中，转（3）循环 2index0[0]次.

（9）转（1）循环63次.

S盒输入差分为6位，因此有26=64种不同的输入，记为 L(0<=L<=63)；L要进行（1）～（8）的计算，必须先转换为数组，并记入Din中，具体实现步骤：

（1）零取反，再左移一位，以6位表示即111110.

（2）将（1）的结果取反，即 000001.

（3）将（2）的结果与L进行按位与&操作，即L&000001，取得最后一位的数值.

（4）L右移一位，转（1）循环 5次，得到 Din的数值.

部分实现代码如下：

二进制加1操作的具体过程：

（1）置1p或0p的位置为最右位.

（2）判断当前1p或0p的位置是否为0，是，变为1，结束.

（3）否，变为0.

（4）转下一个1p或0p的位置，继续（1）.

部分实现代码如下：

DES中的换字盒8如表1所示：

根据上述执行过程，计算得到的部分差分概率表为表2所示：

分析表2可以得出：

表1 S8盒

（1）空白的地方概率为0，绝不可能出现.

（2）最大的概率为16/64，即1/4，共有5个，分别如表3所示.

（3）输入为3(000011)输出也为3(0011)的概率为12/64.

（4）输入为3输出为9的概率为6/64，输入9输出3的概率也为6/64.

（5）输入为4输出为6的概率为6/64，输入6输出4的概率也为6/64.

表2 S8的差分概率表

表3 概率为1/4的情

3 总结

从差分概率表中可查找到差分最大的概率分布情况，上述实现过程也适用于其他具有S盒的密码算法的差分分析过程，如DESL（轻量级 DES）、mCrypton、MIBS等，从差分概率表，进一步可推出轮特征，为差分密码分析奠定了基础.

〔1〕Behrouz A.Forouzan，马振晗，贾军保.密码学与网络安全[M].北京：清华大学出版社，2009.

〔2〕黄维通.Visual C++面向对象与可视化程序设计[M].北京：清华大学出版社，2003.

〔3〕谭浩强.C++程序设计[M].北京：清华大学出版社，2004.

〔4〕李贞，等.差分分析中的特征概率计算问题研究[J].电子与信息学报，2003.

〔5〕张焕国，等.演化密码与 DES的演化研究[J].计算机学报，2003.

〔6〕杨林，等.约减轮的 MIBS算法的差分分析[J].山东大学学报（理学版），2010.

〔7〕张基温.C++程序设计基础[M].北京：高等教育出版社，1996.

TP311

A

1673-260X（2012）02-0043-03