唐琳

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

數(shù)據(jù)加密標(biāo)準(zhǔn)研究之DES加密原理剖析

唐琳

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

DES的原始設(shè)計(jì)思想類似于恩尼格瑪密碼機(jī)，都是用了擴(kuò)散的循環(huán)移位思想，本文在闡述了恩尼格瑪機(jī)構(gòu)造原理的基礎(chǔ)上，針對(duì)DES的歸屬關(guān)系從迭代分組密碼的Feistel結(jié)構(gòu)出發(fā)對(duì)DES的分組位數(shù)、密鑰及基本原理進(jìn)行論述.

DES；加密；原理

1 引言

筆者在《數(shù)據(jù)加密標(biāo)準(zhǔn)研究之DES設(shè)計(jì)思想及體制分析》一文中，論述了傳統(tǒng)密碼加密的核心思想大多來源于古代的循環(huán)移位思想，在此思想基礎(chǔ)上再進(jìn)行模糊擴(kuò)散，便構(gòu)成了由德國(guó)發(fā)明家亞瑟·謝爾比烏斯（ArthurScherbius）和理查德·李特（RichardRitter）發(fā)明的恩尼格瑪密碼機(jī)的基本原理.DES的原始思想與恩尼格瑪機(jī)的基本思想大致相同，都是在代換過程中進(jìn)行模糊運(yùn)算以增加密碼（算法）分析的難度.這里所說的模糊擴(kuò)散，就是在模糊信息處理中加上一種有效的過濾信息的方法——信息擴(kuò)散法，這是一個(gè)蘸方法，是從原始數(shù)據(jù)信息中直接抽象構(gòu)建出模型，這樣做的好處是減少了數(shù)學(xué)上的外加約束，避免了原始數(shù)據(jù)結(jié)構(gòu)的破壞.在這一理論指導(dǎo)下，形成了模糊擴(kuò)散下的循環(huán)移位，這才為恩尼格瑪機(jī)的誕生奠定了理論基礎(chǔ).

2 恩尼格瑪機(jī)的構(gòu)造原理

圖1 恩尼格瑪密碼機(jī)

圖2 恩尼格瑪機(jī)基本構(gòu)造

如圖1所示，恩尼格瑪機(jī)由鍵盤、顯示器和轉(zhuǎn)子三個(gè)部件構(gòu)成，鍵盤共有26個(gè)英文字母鍵，顯示器則是簡(jiǎn)單的對(duì)應(yīng)26個(gè)按鍵的小燈泡，實(shí)現(xiàn)的只是最原始的“指示燈”作用，當(dāng)在鍵盤上按下某一字母鍵時(shí)，與這個(gè)字母加密后得到的密文字母所對(duì)應(yīng)的指示燈就會(huì)點(diǎn)亮.其實(shí)最能體現(xiàn)恩尼格瑪機(jī)關(guān)鍵加密技術(shù)的核心部件是轉(zhuǎn)子（如圖3所示），轉(zhuǎn)子的作用是在輸入一個(gè)明文字母后，其相應(yīng)密文字母的指示燈會(huì)閃爍，轉(zhuǎn)子則自動(dòng)轉(zhuǎn)動(dòng)到下一個(gè)字母.也就是說位于明文不同位置的同一個(gè)字母，依靠轉(zhuǎn)子的轉(zhuǎn)動(dòng)可以被不同的字母替換，相反的，位于密文中不同位置的同一個(gè)字母可以用來表示（對(duì)應(yīng)）明文中的不同字母，這種方法在密碼學(xué)中又被稱為“復(fù)式替換密碼”.應(yīng)用復(fù)式替換加密的密碼并不是簡(jiǎn)單的字母代換，傳統(tǒng)的字母頻率分析法對(duì)此密碼的破解沒有任何作用.

圖3 恩尼格瑪機(jī)中的轉(zhuǎn)子

在恩尼格瑪機(jī)中，轉(zhuǎn)子的數(shù)目越多，編碼的重復(fù)性就越小，常使用三個(gè)轉(zhuǎn)子的情況較多，此時(shí)編碼重復(fù)的概率為1/(26×26×26)，即在編碼輸入17576個(gè)字母之后才會(huì)出現(xiàn)重復(fù).轉(zhuǎn)子的初始方向則是整個(gè)恩尼格瑪機(jī)加密技術(shù)的關(guān)鍵，也是通信雙方約定的密鑰，在通信前，發(fā)信人首先要初始化設(shè)定好三個(gè)轉(zhuǎn)子的旋轉(zhuǎn)方向，然后輸入明文，并依次記錄指示燈閃亮字母的順序，最后把這些字母順序（即密文）發(fā)送給收信方.收信方收到密文通信數(shù)據(jù)后，按照密鑰約定調(diào)整轉(zhuǎn)子初始化方向，依次鍵入密文字母，此時(shí)閃亮的指示燈標(biāo)示的就是明文.由此可見，在恩尼格瑪機(jī)中，加密和解密過程都是用相同的步驟來完成，關(guān)鍵之處就在于密鑰——轉(zhuǎn)子的初始化方向上.為了進(jìn)一步增加破解難度，恩尼格瑪機(jī)除了約定轉(zhuǎn)子的初始化方向外，還要選擇三個(gè)轉(zhuǎn)子的六種排列方式，同時(shí)又用連接板將鍵盤和第一個(gè)轉(zhuǎn)子連接起來，讓明文字母在進(jìn)入轉(zhuǎn)子之前就會(huì)轉(zhuǎn)變?yōu)榱硪粋€(gè)字母.這樣一來，由轉(zhuǎn)子方向、排列順序及連接板簡(jiǎn)單替換密碼系統(tǒng)共同構(gòu)筑的三道防線組成了一套完整的恩尼格瑪機(jī)，通信雙方只要事先約定好這三項(xiàng)內(nèi)容，就可以很容易地實(shí)現(xiàn)通信，這也被稱為恩尼格瑪機(jī)的三重密鑰，也是恩尼格瑪機(jī)的保密原理.

3 基于Feistel技術(shù)的DES分組及密鑰

DES加密過程雖然在原理上和恩尼格瑪機(jī)的工作原理有很大差別，但是它們二者的核心思想都是模糊擴(kuò)散后的循環(huán)移位思想，這也就讓DES在算法設(shè)計(jì)時(shí)從明文到密文的轉(zhuǎn)變過程中首先要對(duì)明文字母進(jìn)行循環(huán)移位，并盡可能將模糊擴(kuò)散做到最優(yōu)，擴(kuò)散的優(yōu)劣是直接影響密碼安全的主要因素.通過擴(kuò)散使得明文中的單個(gè)字符可以影響密文中的多個(gè)字符，從而在密文中消除明文的統(tǒng)計(jì)特征，相當(dāng)于擴(kuò)散掉明文的統(tǒng)計(jì)結(jié)構(gòu).我們可以通過下面這個(gè)例子來直觀看到這種擴(kuò)散效果：

例 構(gòu)造一個(gè)數(shù)學(xué)模型，使得明文中的1個(gè)數(shù)字可以影響密文中的k個(gè)數(shù)字.

在上面的例子中我們可以感受到擴(kuò)散后的循環(huán)效果，實(shí)際分組中，DES密碼又是基于Feistel結(jié)構(gòu)的迭代分組密碼，這里所謂的迭代，就是在加密過程中增加循環(huán)的次數(shù).之所以DES要選擇Feistel密碼結(jié)構(gòu)，可以使得DES密碼中當(dāng)明文變化一位時(shí)會(huì)有至少一半以上的密文發(fā)生變化，盡可能實(shí)現(xiàn)雪崩效應(yīng)這種加密算法中的理想屬性，極大的增加了加密安全性.

3.1 Feistel結(jié)構(gòu)

Feistel結(jié)構(gòu)是分組密碼加密方案的一種通用規(guī)則，在這一方案中，明文由若干個(gè)長(zhǎng)度為2l的分組構(gòu)成，密鑰設(shè)定為K=(k1,k2,…,kn)，其中ki為每一輪加密的子密鑰，i=1,2,…,n，表示第i輪加密過程.

此結(jié)構(gòu)在加密前首先將輸入的明文分組分成長(zhǎng)度都為l的左右兩部分，記為L(zhǎng)和R，實(shí)現(xiàn)加密過程的第一步是對(duì)L和R進(jìn)行n輪迭代，在迭代完成后再將新得到的L和R合并到一起以產(chǎn)生密文分組.

新的左半部分和右半部分產(chǎn)生規(guī)則為：

其中，ki是派生自密鑰K并遵循特定密鑰調(diào)度算法的第i輪加密的子密鑰，F(xiàn)是以舊的右半部分Ri－1和子密鑰ki作為輸入?yún)?shù)的輪函數(shù).一般來說，各輪加密中的子密鑰ki之間各不相同，即k1≠k2≠k3≠…≠kn，這樣就能保證輪函數(shù)F的值也各不相同.

經(jīng)過n輪加密后，得到的密文C則是最后一輪加密結(jié)果的輸出：C=(Ln，Rn)

由公式1可知，每一輪迭代后得到的新的左半部分Li就是舊的右半部分Ri-1；

由公式2可知，每一輪迭代后得到的新的右半部分Ri是舊的左半部分Li-1與輪函數(shù)F的輸出值進(jìn)行異或運(yùn)算的結(jié)果.

這里需要說明的是，在每輪代換過程完成后，還要經(jīng)過一個(gè)置換過程，即將代換后得到的新的左右兩個(gè)部分Li和Ri進(jìn)行交換，如圖4所示.

總結(jié)前文，可以得出基于Feistel結(jié)構(gòu)的通信網(wǎng)絡(luò)其安全性能與明文分組大小、密鑰大小、密鑰調(diào)度（子密鑰產(chǎn)生算法）、輪數(shù)及輪函數(shù)等幾個(gè)參數(shù)有關(guān)，但是這些參數(shù)最后都會(huì)歸結(jié)為密鑰調(diào)度和輪函數(shù)這兩個(gè)問題，而密鑰調(diào)度中產(chǎn)生子密鑰的算法越復(fù)雜，密碼分析就越困難，而這種調(diào)度中本身就包含了Feistel結(jié)構(gòu)的加密算法，無需保密，所以密碼調(diào)度問題不會(huì)成為影響安全性的主要問題，因此從Feistel結(jié)構(gòu)上來說，絕大多數(shù)密碼分析往往都會(huì)集中于輪函數(shù)F的問題上，而輪函數(shù)的數(shù)學(xué)描述越復(fù)雜，分析起來就越困難，這樣就要求輪函數(shù)的結(jié)構(gòu)復(fù)雜性要高，并隨著子密鑰ki的取值變化其函數(shù)值也各不相同.

圖4 Feistel加密結(jié)構(gòu)圖

3.2 DES分組位數(shù)

在引文[1]中，我們知道DES既是一種對(duì)稱密碼標(biāo)準(zhǔn)，同時(shí)又是一種分組密碼，之所以將DES劃歸到分組密碼體系中是因?yàn)镈ES在進(jìn)行循環(huán)移位時(shí)需要事先將明文分成若干等數(shù)位的序列組，如同當(dāng)前許多分組密碼通用規(guī)則一樣，DES對(duì)數(shù)據(jù)加密時(shí)的分組也是以64位作為標(biāo)準(zhǔn)分組長(zhǎng)度.通信時(shí)將輸入端輸入的明文分成64位一組的明文塊，逐塊加密后在輸出端以64位一組的密文塊輸出.

3.3 DES密鑰及其長(zhǎng)度

作為一種對(duì)稱算法，DES加密和解密使用的是同一個(gè)算法（私有密鑰），其密鑰長(zhǎng)度為56位，再加上8位奇偶校驗(yàn)位，所以經(jīng)常能看到DES密鑰是一個(gè)64位的分組數(shù)列，其中56位密鑰數(shù)字是實(shí)際上的密鑰長(zhǎng)度，可以隨時(shí)任意改變，同時(shí)DES所擁有的子密鑰長(zhǎng)度為48位.

4 DES的基本原理

4.1 DES加密原理

眾所周知，DES的前身Lucifer密碼是一種基于Feistel結(jié)構(gòu)的密碼，DES在Lucifer的基礎(chǔ)上將密鑰長(zhǎng)度從128位壓縮到64位，并修改了替換盒S-box（substitutionboxes，又稱S盒），雖然密鑰縮短了，但經(jīng)過多次密碼分析后，對(duì)DES攻擊的成本比用窮舉式密鑰檢索方法遍試255個(gè)密鑰的成本只略微小了一點(diǎn)，對(duì)S-box的修改進(jìn)一步增強(qiáng)了DES算法的復(fù)雜性，所以實(shí)際僅擁有56位密鑰長(zhǎng)度的DES算法與擁有更長(zhǎng)密鑰的Lucifer密碼的安全性相差并不大，DES完全能夠?qū)苟嗄暌院蟪霈F(xiàn)的若干新的密碼分析技術(shù)，也造就了DES算法多年來在加密領(lǐng)域中一直處于牢不可破的領(lǐng)軍地位的輝煌.

由于這種血統(tǒng)上的遺傳特性，DES亦是基于Feistel結(jié)構(gòu)的迭代分組密碼，這樣DES的加密計(jì)算也勢(shì)必要遵循前文中的公式1和公式2.

以一輪DES加密為例，其數(shù)學(xué)模型的構(gòu)建與Feistel結(jié)構(gòu)相同，也是由下面的公式構(gòu)成DES加密的數(shù)學(xué)表達(dá).

公式3說明，DES明文分組在一輪加密后新得到的左半部分就是原來的右半部分Ri－1；

公式4說明，DES明文分組在一輪加密后新得到的右半部分Ri就是原來的左半部分Li－1與輪函數(shù)F的異或.

DES的一輪加密運(yùn)算結(jié)構(gòu)如圖5所示.

5DES加密算法結(jié)構(gòu)圖

在這一方案中，構(gòu)成DES結(jié)構(gòu)的輪函數(shù)F由排列擴(kuò)展、子密鑰、S-box和P-box等幾個(gè)部分組成，其中關(guān)于擴(kuò)展、子密鑰產(chǎn)生算法、S-box和P-box的詳細(xì)內(nèi)容將在關(guān)于DES算法解析一文中詳細(xì)論述.DES輪函數(shù)結(jié)構(gòu)如圖6所示，它的數(shù)學(xué)表達(dá)式為：

F(Ri-1,ki)=P-box{S-box[Expand(Ri-1)⊕ki]} 公式5

在公式5中，Expand函數(shù)的作用是對(duì)32位的右半部分排列擴(kuò)展至48位，擴(kuò)展后的結(jié)果再與子密鑰ki進(jìn)行異或運(yùn)算.運(yùn)算后的值仍為48位，通過S-box壓縮為32位后作為輸入?yún)?shù)賦給P-box.P-box運(yùn)算后得出的結(jié)果就是DES輪函數(shù)F的值.

在DES加密過程中，加密輪數(shù)并不是無窮盡的，共計(jì)有16輪加密過程，即i的最大值n=16，每一輪都重復(fù)著如圖5所示的加密過程.

4.2 DES解密原理

圖6 DES輪函數(shù)F結(jié)構(gòu)圖

而在DES解密過程中，其本質(zhì)原理與加密過程一樣，密文作為輸入端數(shù)據(jù)，子密鑰產(chǎn)生規(guī)則發(fā)生變化，以相反次序使用子密鑰.解密與加密過程都使用同一個(gè)算法，將加密結(jié)構(gòu)圖中的輸入改為密文分組，解密過程仍然遵循公式3、4、5的數(shù)學(xué)規(guī)則，例如用C來代表密文，密文仍然分為左右各32位的分組，則解密規(guī)則數(shù)學(xué)表達(dá)式為：

其中Li是密文分組的左半部分，Ri是密文分組的右半部分，其余公式的說明可以參照加密規(guī)則，公式及算法完全一致.

5 總述

隨著數(shù)據(jù)加密技術(shù)的不斷發(fā)展，密碼分析手段也在不斷推陳出新，各種破解技術(shù)及工具層出不窮，為了進(jìn)一步增加DES的加密安全性，目前使用的DES較數(shù)年前進(jìn)化了許多，最常用的就是DES的變體——三重DES（3DES或稱TripleDES）.這一變體對(duì)資料數(shù)據(jù)（明文）重復(fù)三次DES加密過程，解密時(shí)也需要重復(fù)三次DES解密過程，這種重復(fù)并不只是對(duì)過程的三次累計(jì)，而是使用三組每組56位有效數(shù)字的密鑰產(chǎn)生一個(gè)168位的復(fù)雜密鑰來對(duì)數(shù)據(jù)進(jìn)行三次DES加密，這種加密機(jī)制通常可為我們提供極為強(qiáng)大的安全保障.在三重DES加密時(shí)，存在著一種極端情況，即算法選擇的三組56位密鑰的子密鑰都相同時(shí)，三重DES在實(shí)施時(shí)對(duì)數(shù)據(jù)安全性的增值幅度并不大，這就需要向后繼續(xù)兼容新的DES加密過程來調(diào)度出三組不同的密鑰完成3DES過程.

其實(shí)對(duì)傳統(tǒng)的DES來說，截止目前也只有一種方法能對(duì)其進(jìn)行破解，那就是窮舉法，既使密鑰僅有56位有效數(shù)再加上8位校驗(yàn)數(shù)，用它來加密一段256位空間的明文，如果使用一臺(tái)百萬次/秒計(jì)算級(jí)的PC機(jī)對(duì)其密文進(jìn)行窮舉，大概需要花費(fèi)2285年的時(shí)間，所以相對(duì)來說DES目前還是具有一定安全性的.

然而DES隨著時(shí)間的推移也并非絕對(duì)安全，其本身還存在著致命的缺陷，56位密鑰強(qiáng)度會(huì)隨時(shí)間的流逝而日益減弱，這種缺陷盡管被三重DES在一定程度上有所解決，但面臨著層出不窮的新的密碼分析手段最終在安全性上會(huì)馬失前蹄，所以風(fēng)靡一時(shí)的DES也將被新的加密標(biāo)準(zhǔn)所取代.這也正如日月盈仄一般向我們揭示著事物發(fā)展演化的客觀規(guī)律，在密碼安全領(lǐng)域也存在著新生與消亡.

TP309

A

1673-260X（2014）12-0021-03