陳海紅

（赤峰學(xué)院 計算機與信息工程學(xué)院，內(nèi)蒙古 赤峰 024000）

DES中S盒差分概率表的實現(xiàn)

陳海紅

（赤峰學(xué)院 計算機與信息工程學(xué)院，內(nèi)蒙古 赤峰 024000）

差分分析是分組密碼最常用的密碼分析技術(shù)，DES就是其中的一種.采用C++語言實現(xiàn)了計算差分概率表的過程，并對DES的S8盒進行了差分分析，得出最大概率為1/4，共有5種情況.

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

1 DES算法的差分分析

DES是現(xiàn)代對稱密鑰分組密碼的典型代表，算法分組長度為64位，密鑰長度56位，生成的密文也是64位.加密過程由初始置換、16個Feistel輪和最終置換組成.每一輪由混合器和交換器構(gòu)成.DES的核心是輪函數(shù)，輪函數(shù)的輸入是每一輪的右半部分的32位，以及48位的輪密鑰.輪函數(shù)由擴展換位盒、輪密鑰加、換字盒和直接換位盒構(gòu)成.DES采用8個6*4的S盒.

差分分析是現(xiàn)代分組密碼最常用一種密碼分析技術(shù)，經(jīng)常用其檢驗一種密碼算法的抗攻擊能力，DES也不例外.DES的差分分析用到如下的性質(zhì)：

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

性質(zhì)2[1]對一個帶有恒等元素的字符異或不能改變該字符.即x茌0=x.

由此可知，輪密鑰的作用被取消了.

而C1茌C2=X1茌X2(存在概率關(guān)系).

因此，差分分析的首要任務(wù)就落在了計算S盒的差分概率表上，而DES的S盒是6*4結(jié)構(gòu)，即輸入6位，輸出4位，如果輸入差分是001001，從左到右分別標(biāo)記為p0p1p2p3p4p5，則表示p2位和p5位不同，其余相同，p2和p5可組合出2對，分別為00和11,01和10，其余4位相同位可組合出24種情況，分別為 0000、0001、0010……1111，組合在一起共有32種情況，由此計算輸出差分的概率.

2 差分概率表的實現(xiàn)

計算差分概率表的程序使用C++語言實現(xiàn)，輸入差分應(yīng)該是二進制形式，但是使用二進制不容易操作，因此程序使用數(shù)組來代替.有如下定義：

Din，b：表示輸入差分的數(shù)組

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

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

index0：記錄輸入差分中0的具體位置及個數(shù)

index1：記錄輸入差分中1的具體位置及個數(shù)

（1）首先計算出輸入差分中1的個數(shù)和0的個數(shù)，以及1和0的具體位置，個數(shù)分別記入index1和index0數(shù)組的第零個位置，以便確定循環(huán)的次數(shù).如輸入差分是001001，則：

index0的數(shù)據(jù)為：44310

index1的數(shù)據(jù)為：252

（2）將Din數(shù)組全部清零，從零開始循環(huán)，并將Din數(shù)值記入b中.

（3）計算第一個數(shù)P1的下標(biāo)，行下標(biāo)等于Din的第一個數(shù)和最后一個數(shù)合起來的結(jié)果，列下標(biāo)等于中間的四位數(shù)的結(jié)果，即如果Din等于000011，則：

行下標(biāo)等于：2*Din[0]+1*Din[5]=1

列下標(biāo)等于：8*Din[1]+4*Din[2]+2*Din[3]+1*Din[4]=1

根據(jù)下標(biāo)查S盒表得到第一個數(shù)值記入first

（4）修改Din的數(shù)值，計算第二個數(shù)，第二個數(shù)應(yīng)該為：index1所指示的位置處的數(shù)字如果是0變?yōu)?1，如果是 1變?yōu)?0；即如（3）中 Din為 000011，則修改后Din的值為001010.

（5）計算第二個數(shù)的下標(biāo)，方法同（3），根據(jù)下標(biāo)查S盒表得到第二個數(shù)字記入second.

（6）求first和second異或的值，得到一個差分結(jié)果.

（7）對b中的1p執(zhí)行類似二進制的加1操作，將b記入Din中，轉(zhuǎn)（3）循環(huán)2index1[0]-1次.

（8）對b中的0p執(zhí)行類似二進制的加1操作，將 b記入 Din 中，轉(zhuǎn)（3）循環(huán) 2index0[0]次.

（9）轉(zhuǎn)（1）循環(huán)63次.

S盒輸入差分為6位，因此有26=64種不同的輸入，記為 L(0<=L<=63)；L要進行（1）～（8）的計算，必須先轉(zhuǎn)換為數(shù)組，并記入Din中，具體實現(xiàn)步驟：

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

（2）將（1）的結(jié)果取反，即 000001.

（3）將（2）的結(jié)果與L進行按位與&操作，即L&000001，取得最后一位的數(shù)值.

（4）L右移一位，轉(zhuǎn)（1）循環(huán) 5次，得到 Din的數(shù)值.

部分實現(xiàn)代碼如下：

二進制加1操作的具體過程：

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

（2）判斷當(dāng)前1p或0p的位置是否為0，是，變?yōu)?，結(jié)束.

（3）否，變?yōu)?.

（4）轉(zhuǎn)下一個1p或0p的位置，繼續(xù)（1）.

部分實現(xiàn)代碼如下：

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

根據(jù)上述執(zhí)行過程，計算得到的部分差分概率表為表2所示：

分析表2可以得出：

表1 S8盒

（1）空白的地方概率為0，絕不可能出現(xiàn).

（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 總結(jié)

從差分概率表中可查找到差分最大的概率分布情況，上述實現(xiàn)過程也適用于其他具有S盒的密碼算法的差分分析過程，如DESL（輕量級 DES）、mCrypton、MIBS等，從差分概率表，進一步可推出輪特征，為差分密碼分析奠定了基礎(chǔ).

〔1〕Behrouz A.Forouzan，馬振晗，賈軍保.密碼學(xué)與網(wǎng)絡(luò)安全[M].北京：清華大學(xué)出版社，2009.

〔2〕黃維通.Visual C++面向?qū)ο笈c可視化程序設(shè)計[M].北京：清華大學(xué)出版社，2003.

〔3〕譚浩強.C++程序設(shè)計[M].北京：清華大學(xué)出版社，2004.

〔4〕李貞，等.差分分析中的特征概率計算問題研究[J].電子與信息學(xué)報，2003.

〔5〕張煥國，等.演化密碼與 DES的演化研究[J].計算機學(xué)報，2003.

〔6〕楊林，等.約減輪的 MIBS算法的差分分析[J].山東大學(xué)學(xué)報（理學(xué)版），2010.

〔7〕張基溫.C++程序設(shè)計基礎(chǔ)[M].北京：高等教育出版社，1996.

TP311

A

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