密碼學(xué)專題 - 對稱加密算法 - DES 算法

5.1 DES 的描述

DES 是一個分組加密算法，它以 64 位為分組對數(shù)據(jù)加密蓬蝶。64 位一組的明文從算法的一端輸入，64 位的密文從另一端輸出。DES 是一個對稱算法：加密和解密用的是同一算法 (除密鑰編排不同以外)。

密鑰的長度為 56 位表锻。(密鑰通常表示為 64 位的數(shù)，但每個第 8 位都用作奇偶校驗乞娄，可以忽略瞬逊。) 密鑰可以是任意的 56 位的數(shù)，且可在任意的時候改變仪或。其中極少量的數(shù)被認為是弱密鑰确镊，但能容易地避開它們。所有的保密都依賴于密鑰范删。

簡單地說蕾域，算法只不過是加密的兩個基本技術(shù)——混亂和擴散的組合。DES 基本組件分組是這些技術(shù)的一個組合 (先代替后置換)，它基于密鑰作用于明文旨巷，這是眾所周知的輪 (round)巨缘。DES 有 16 輪，這意味著要在明文分組上 16 次實施相同的組合技術(shù) (見圖 12-1)采呐。

此算法只使用了標準算術(shù)和邏輯運算若锁，而其作用的數(shù)也最多只有 64 位，因此用 20 世紀 70 年代末期的硬件技術(shù)很容易實現(xiàn)懈万。算法的重復(fù)特性使得它可以非常理想地用在一個專用芯片中拴清。最初的軟件實現(xiàn)很粗陋，但現(xiàn)在已好多了会通。

圖12-1 DES.jpg

5.1.1 算法概要

DES 對 64 位的明文分組進行操作口予。通過一個初始置換，將明文分組分成左半部分和右半部分涕侈，各 32 位長沪停。然后進行 16 輪完全相同的運算，這些運算稱為函數(shù) f裳涛，在運算過程中數(shù)據(jù)與密鑰結(jié)合木张。經(jīng)過 16 輪后，左端三、右半部分合在一起經(jīng)過一個末置換 (初始置換的逆置換)舷礼，這樣該算法就完成了。

在每一輪中 (見圖 12-2)郊闯，密鑰位移位妻献，然后再從密鑰的 56 位中選出 48 位。通過一個擴展置換將數(shù)據(jù)的右半部分擴展成 48 位团赁，并通過一個異或運算與 48 位密鑰結(jié)合育拨，通過 8 個 S 盒將這 48 位替代成新的 32 位數(shù)據(jù)，再將其轉(zhuǎn)換一次欢摄。這四步運算構(gòu)成了函數(shù) f熬丧。然后，通過另一個異或運算怀挠，函數(shù) f 的輸出與左半部分結(jié)合析蝴，其結(jié)果即成為新的右半部分，原來的右半部分成為新的左半部分绿淋。將該運算重復(fù) 16 次嫌变，便實現(xiàn)了 DES 的 16 輪運算。

圖12-2 一輪 DES.jpg

假設(shè) $B_i$ 是第 i 次迭代的結(jié)果躬它， $L_i$ 和 $R_i$ 是 $B_i$ 的左半部分和右半部分， $K_i$ 是第 i 輪的 48 位密鑰东涡，且 f 是實現(xiàn)代替冯吓、置換及密鑰異或等運算的函數(shù)倘待，那么每一輪就是：
$L_i = R_{i-1}$

$R_i = L_{i-1} \bigoplus f(R_{i-1}, K_i)$

5.1.2 初始置換

初始置換在第一輪運算之前執(zhí)行，對輸入分組實施如表 12-1 所示的變換组贺。此表應(yīng)從左向右凸舵、從上向下讀。例如失尖，初始置換把明文的第 58 位換到第 1 位的位置啊奄，把第 50 位換到第 2 位的位置，把第 42 位換到第 3 位的位置等掀潮。

表12-1 初始置換.jpg

初始置換和對應(yīng)的末置換并不影響 DES 的安全性菇夸。(正如人們所說，它的主要目的是為了更容易地將明文和密文數(shù)據(jù)以字節(jié)大小放入 DES 芯片中仪吧。記住庄新，DES 早于 16 位和 32 位微處理總線。) 因為這種位方式的置換用軟件實現(xiàn)很困難 (雖然用硬件實現(xiàn)較容易)薯鼠，所以 DES 的許多軟件實現(xiàn)方式刪去了初始置換和末置換择诈。盡管這種新算法的安全性不比 DES 差，但它并未遵循 DES 標準出皇，所以不應(yīng)該叫做 DES羞芍。

5.1.3 密鑰置換

開始，由于不考慮每個字節(jié)的第 8 位郊艘，所以 DES 的密鑰由 64 位減至 56 位荷科，如表 12-2 所示。每個字節(jié)的第 8 位可作為奇偶校驗以確保密鑰不發(fā)生錯誤暇仲。在 DES 的每一輪中步做，從 56 位密鑰產(chǎn)生出不同的 48 位子密鑰 (subkey)，這些子密鑰 $K_i$ 由下面的方式確定奈附。

表12-2 密鑰置換.jpg

首先全度，56 位密鑰被分成兩部分，每部分 28 位斥滤。然后将鸵，根據(jù)輪數(shù)，這兩部分分別循環(huán)左移 1 位或 2 位佑颇。表 12-3 給出了每輪移動的位數(shù)顶掉。

表12-3 每輪移動的位數(shù).jpg

移動后，就從 56 位中選出 48 位挑胸。因為這個運算不僅置換了每位的順序痒筒，同時也選擇了子密鑰，因而稱為壓縮置換 (compression permutation)。這個運算提供了一組 48 位的集簿透。表 12-4 定義了壓縮置換 (也稱為置換選擇)移袍。例如，處在第 33 位的那一位在輸出時移到了第 35 位的位置老充，而處在第 18 位的那一位被略去了葡盗。

表12-4 壓縮置換.jpg

因為有移動運算，所以在每一個子密鑰中使用了不同的密鑰子集的位啡浊。雖然不是所有的位在子密鑰中使用的次數(shù)均相同觅够，但在 16 個子密鑰中，每一位大約使用了其中 14 個子密鑰巷嚣。

5.1.4 擴展置換

這個運算將數(shù)據(jù)的右半部分 $R_i$ 從 32 位擴展到了 48 位喘先。由于這個運算改變了位的次序，重復(fù)了某些位涂籽，所以稱為擴展置換 (expansion permutation)苹祟。這個運算有兩個方面的目的：它產(chǎn)生了與密鑰同長度的數(shù)據(jù)以進行異或運算；它提供了更長的結(jié)果评雌，使得在替代運算時能進行壓縮树枫。但是，以上的兩個目的都不是它在密碼學(xué)上的主要目的景东。由于輸入的一位將影響兩個替換砂轻，所以輸出對輸入的依賴性將傳播得更快，這叫做雪崩效應(yīng) (avalanche effect)斤吐。故 DES 的設(shè)計著重于盡可能快地使得密文的每一位依賴明文和密鑰的每一位搔涝。

圖 12-3 顯示了擴展置換，有時它也叫做 E 盒 (E-box)和措。對每個 4 位輸入分組庄呈，第 1 位和第 4 位分別表示輸出分組中的兩位，而第 2 位和第 3 位分別表示輸出分組中的一位派阱。表 12-5 給出了哪位輸出位對應(yīng)于哪個輸入位诬留。例如，處于輸入分組中第 3 位的位置位移到了輸出分組中第 4 位的位置贫母，而輸入分組中第 21 位的位置位移到了輸出分組中第 30 位和第 32 位的位置文兑。

圖12-3 擴展轉(zhuǎn)換.jpg

表12-5 擴展置換.jpg

盡管輸出分組大于輸入分組，但每一個輸入分組產(chǎn)生唯一的位輸出分組腺劣。

5.1.5 S 盒代替

壓縮后的密鑰與擴展分組異或以后绿贞，將 48 位的結(jié)果送入進行代替運算。代替由 8 個代替盒 (substitution box)橘原，或 S 盒 (S-box) 完成籍铁。每一個 S 盒都有 6 位輸入涡上、4 位輸出。且這 8 個 S 盒是不同的拒名。(DES 的這 8 個 S 盒占的存儲空間為 256 字節(jié)吓懈。) 48 位的輸入被分為 8 個 6 位的分組，每個分組對應(yīng)一個 S 盒代替操作：分組 1 由 S 盒 1 操作靡狞，分組 2 由 S 盒 2 操作等。見圖 12-4隔嫡。

圖12-4 S盒代替.jpg

每個 S 盒是一個 4 行甸怕、16 列的表。盒中的每一項都是一個 4 位的數(shù)腮恩。S 盒的 6 個位輸入確定了其對應(yīng)的輸出在哪一行哪一列梢杭。表 12-6 列出了所有 8 個 S 盒。

表12-6 S盒.jpg

表12-6續(xù) S盒.jpg

輸入位以一種非常特殊的方式確定了 S 盒中的項秸滴。假定將 S 盒的 6 位輸入標記為 $b_1武契、b_2、b_3荡含、b_4咒唆、b_5、b_6释液、b_7全释、b_8$ 。 $b_1$ 和 $b_6$ 組合構(gòu)成了一個 2 位的數(shù)误债，從 0 ~ 3浸船，它對應(yīng)于表中的一行。從 $b_2 \sim b_5$ 構(gòu)成了一個 4 位的數(shù)寝蹈，從 0 ~ 15李命，對應(yīng)于表中的一列。

例如箫老，假設(shè)第 6 個 S 盒的輸入 (即異或函數(shù)的第 31 ~ 36 位) 為 110011封字。第 1 位和最后一位組合形成了 11，它對應(yīng)著第 6 個 S 盒的第三行槽惫。中間的 4 位組合在一起形成了 1001周叮，它對應(yīng)著同一個 S 盒的第 9 列。S 盒 6 的第三行第 9 列的數(shù)是 14 (記住界斜，行仿耽、列的記數(shù)均從 0 開始，而不是從 1 開始)各薇，則值 1110 就代替了 110011项贺。

當(dāng)然君躺，用軟件實現(xiàn) 64 項的 S 盒更容易。僅需要花費一些精力重新組織 S 盒的每一項开缎，這并不困難棕叫。(S 盒的設(shè)計必須非常仔細，不要僅僅改變查找的索引奕删，而不重新編排 S 盒中的每一項俺泣。) 然而，S 盒的這種描述完残，使它的工作過程可視化了伏钠。每個 S 盒可看做一個 4 位輸入的代替函數(shù)： $b_2 \sim b_5$ 直接輸入，輸出結(jié)果為 4 位谨设。 $b_1$ 和 $b_6$ 位來自臨近的分組熟掂，它們從特定 S 盒的四個代替函數(shù)中選擇一個。

這是該算法的關(guān)鍵步驟扎拣。所有其他的運算都是線性的赴肚，易于分析。而 S 盒是非線性的二蓝，它比 DES 的其他任何一步都提供了更好的安全性誉券。

這個代替過程的結(jié)果是 8 個 4 位的分組，它們重新合在一起形成了一個 32 位的分組侣夷。這個分組將進行下一步：P 盒轉(zhuǎn)換横朋。

5.1.6 P 盒置換

S 盒代替運算后的 32 位輸出依照 P 盒 (P-box) 進行置換。該置換把每輸入位映射到輸出位百拓，任一位不能映射兩次琴锭，也不能被略去，這個置換叫做直接置換 (straight permutation)衙传，或就叫做置換决帖。表 12-7 給出了每位移至的位置。例如蓖捶，第 21 位移到了第 4 位地回，同時第 4 位移到了第 31 位。

表12-7 P盒置換.jpg

最后俊鱼，將 P 盒置換的結(jié)果與最初的 64 位分組的左半部分異或刻像，然后左、右半部分交換并闲，接著開始另一輪细睡。

5.1.7 末置換

末置換是初始置換的逆過程，表 12-8 列出了該置換帝火。注意 DES 在最后一輪后溜徙，左半部分和右半部分并未交換湃缎，而是將 $R_16$ 和 $L_16$ 并在一起形成一個分組作為末置換的輸入。到此蠢壹，不再做其他的事嗓违。其實交換左、右兩部分并循環(huán)移動图贸，仍將獲得完全相同的結(jié)果蹂季。但這樣做，就使該算法既能用作加密疏日，又能用作解密乏盐。

表12-8 末置換.jpg

5.1.8 DES 解密

在經(jīng)過所有的代替、置換制恍、異或和循環(huán)移動之后，你或許認為解密算法與加密算法完全不同神凑，并且也像加密算法一樣有很強的混亂效果净神。恰恰相反，經(jīng)過精心選擇各種運算溉委，獲得了這樣一個非常有用的性質(zhì)：加密和解密可使用相同的算法鹃唯。

DES 使得用相同的函數(shù)來加密或解密每個分組成為可能。兩者的唯一不同是密鑰的次序相反瓣喊。這就是說坡慌，如果各輪的加密密鑰分別是 $K_1、K_2藻三、K_3洪橘、...、K_{16}$ 棵帽，那么解密密鑰就是 $K_{16}熄求、K_{15}、K_{14}逗概、...弟晚、K_1$ 。為各輪產(chǎn)生密鑰的算法也是循環(huán)的逾苫。密鑰向右移動卿城，每次移動的個數(shù)為 $0,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1$ 。