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

5.1 DES 的描述

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

密鑰的長(zhǎng)度為 56 位。(密鑰通常表示為 64 位的數(shù)，但每個(gè)第 8 位都用作奇偶校驗(yàn)，可以忽略。) 密鑰可以是任意的 56 位的數(shù)，且可在任意的時(shí)候改變。其中極少量的數(shù)被認(rèn)為是弱密鑰，但能容易地避開它們。所有的保密都依賴于密鑰。

簡(jiǎn)單地說(shuō)，算法只不過(guò)是加密的兩個(gè)基本技術(shù)——混亂和擴(kuò)散的組合。DES 基本組件分組是這些技術(shù)的一個(gè)組合 (先代替后置換)，它基于密鑰作用于明文，這是眾所周知的輪 (round)。DES 有 16 輪，這意味著要在明文分組上 16 次實(shí)施相同的組合技術(shù) (見(jiàn)圖 12-1)。

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

圖12-1 DES.jpg

5.1.1 算法概要

DES 對(duì) 64 位的明文分組進(jìn)行操作。通過(guò)一個(gè)初始置換，將明文分組分成左半部分和右半部分，各 32 位長(zhǎng)。然后進(jìn)行 16 輪完全相同的運(yùn)算，這些運(yùn)算稱為函數(shù) f，在運(yùn)算過(guò)程中數(shù)據(jù)與密鑰結(jié)合。經(jīng)過(guò) 16 輪后，左、右半部分合在一起經(jīng)過(guò)一個(gè)末置換 (初始置換的逆置換)，這樣該算法就完成了。

在每一輪中 (見(jiàn)圖 12-2)，密鑰位移位，然后再?gòu)拿荑€的 56 位中選出 48 位。通過(guò)一個(gè)擴(kuò)展置換將數(shù)據(jù)的右半部分?jǐn)U展成 48 位，并通過(guò)一個(gè)異或運(yùn)算與 48 位密鑰結(jié)合，通過(guò) 8 個(gè) S 盒將這 48 位替代成新的 32 位數(shù)據(jù)，再將其轉(zhuǎn)換一次。這四步運(yùn)算構(gòu)成了函數(shù) f。然后，通過(guò)另一個(gè)異或運(yùn)算，函數(shù) f 的輸出與左半部分結(jié)合，其結(jié)果即成為新的右半部分，原來(lái)的右半部分成為新的左半部分。將該運(yùn)算重復(fù) 16 次，便實(shí)現(xiàn)了 DES 的 16 輪運(yùn)算。

圖12-2 一輪 DES.jpg

假設(shè) 是第 i 次迭代的結(jié)果， 和 是 的左半部分和右半部分， 是第 i 輪的 48 位密鑰，且 f 是實(shí)現(xiàn)代替、置換及密鑰異或等運(yùn)算的函數(shù)，那么每一輪就是：

5.1.2 初始置換

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

表12-1 初始置換.jpg

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

5.1.3 密鑰置換

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

表12-2 密鑰置換.jpg

首先，56 位密鑰被分成兩部分，每部分 28 位。然后，根據(jù)輪數(shù)，這兩部分分別循環(huán)左移 1 位或 2 位。表 12-3 給出了每輪移動(dòng)的位數(shù)。

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

移動(dòng)后，就從 56 位中選出 48 位。因?yàn)檫@個(gè)運(yùn)算不僅置換了每位的順序，同時(shí)也選擇了子密鑰，因而稱為壓縮置換 (compression permutation)。這個(gè)運(yùn)算提供了一組 48 位的集。表 12-4 定義了壓縮置換 (也稱為置換選擇)。例如，處在第 33 位的那一位在輸出時(shí)移到了第 35 位的位置，而處在第 18 位的那一位被略去了。

表12-4 壓縮置換.jpg

因?yàn)橛幸苿?dòng)運(yùn)算，所以在每一個(gè)子密鑰中使用了不同的密鑰子集的位。雖然不是所有的位在子密鑰中使用的次數(shù)均相同，但在 16 個(gè)子密鑰中，每一位大約使用了其中 14 個(gè)子密鑰。

5.1.4 擴(kuò)展置換

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

圖 12-3 顯示了擴(kuò)展置換，有時(shí)它也叫做 E 盒 (E-box)。對(duì)每個(gè) 4 位輸入分組，第 1 位和第 4 位分別表示輸出分組中的兩位，而第 2 位和第 3 位分別表示輸出分組中的一位。表 12-5 給出了哪位輸出位對(duì)應(yīng)于哪個(gè)輸入位。例如，處于輸入分組中第 3 位的位置位移到了輸出分組中第 4 位的位置，而輸入分組中第 21 位的位置位移到了輸出分組中第 30 位和第 32 位的位置。

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

表12-5 擴(kuò)展置換.jpg

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

5.1.5 S 盒代替

壓縮后的密鑰與擴(kuò)展分組異或以后，將 48 位的結(jié)果送入進(jìn)行代替運(yùn)算。代替由 8 個(gè)代替盒 (substitution box)，或 S 盒 (S-box) 完成。每一個(gè) S 盒都有 6 位輸入、4 位輸出。且這 8 個(gè) S 盒是不同的。(DES 的這 8 個(gè) S 盒占的存儲(chǔ)空間為 256 字節(jié)。) 48 位的輸入被分為 8 個(gè) 6 位的分組，每個(gè)分組對(duì)應(yīng)一個(gè) S 盒代替操作：分組 1 由 S 盒 1 操作，分組 2 由 S 盒 2 操作等。見(jiàn)圖 12-4。

圖12-4 S盒代替.jpg

每個(gè) S 盒是一個(gè) 4 行、16 列的表。盒中的每一項(xiàng)都是一個(gè) 4 位的數(shù)。S 盒的 6 個(gè)位輸入確定了其對(duì)應(yīng)的輸出在哪一行哪一列。表 12-6 列出了所有 8 個(gè) S 盒。

表12-6 S盒.jpg

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

輸入位以一種非常特殊的方式確定了 S 盒中的項(xiàng)。假定將 S 盒的 6 位輸入標(biāo)記為 。 和 組合構(gòu)成了一個(gè) 2 位的數(shù)，從 0 ~ 3，它對(duì)應(yīng)于表中的一行。從 構(gòu)成了一個(gè) 4 位的數(shù)，從 0 ~ 15，對(duì)應(yīng)于表中的一列。

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

當(dāng)然，用軟件實(shí)現(xiàn) 64 項(xiàng)的 S 盒更容易。僅需要花費(fèi)一些精力重新組織 S 盒的每一項(xiàng)，這并不困難。(S 盒的設(shè)計(jì)必須非常仔細(xì)，不要僅僅改變查找的索引，而不重新編排 S 盒中的每一項(xiàng)。) 然而，S 盒的這種描述，使它的工作過(guò)程可視化了。每個(gè) S 盒可看做一個(gè) 4 位輸入的代替函數(shù)： 直接輸入，輸出結(jié)果為 4 位。 和 位來(lái)自臨近的分組，它們從特定 S 盒的四個(gè)代替函數(shù)中選擇一個(gè)。

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

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

5.1.6 P 盒置換

S 盒代替運(yùn)算后的 32 位輸出依照 P 盒 (P-box) 進(jìn)行置換。該置換把每輸入位映射到輸出位，任一位不能映射兩次，也不能被略去，這個(gè)置換叫做直接置換 (straight permutation)，或就叫做置換。表 12-7 給出了每位移至的位置。例如，第 21 位移到了第 4 位，同時(shí)第 4 位移到了第 31 位。

表12-7 P盒置換.jpg

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

5.1.7 末置換

末置換是初始置換的逆過(guò)程，表 12-8 列出了該置換。注意 DES 在最后一輪后，左半部分和右半部分并未交換，而是將 和 并在一起形成一個(gè)分組作為末置換的輸入。到此，不再做其他的事。其實(shí)交換左、右兩部分并循環(huán)移動(dòng)，仍將獲得完全相同的結(jié)果。但這樣做，就使該算法既能用作加密，又能用作解密。

表12-8 末置換.jpg

5.1.8 DES 解密

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

DES 使得用相同的函數(shù)來(lái)加密或解密每個(gè)分組成為可能。兩者的唯一不同是密鑰的次序相反。這就是說(shuō)，如果各輪的加密密鑰分別是 ，那么解密密鑰就是 。為各輪產(chǎn)生密鑰的算法也是循環(huán)的。密鑰向右移動(dòng)，每次移動(dòng)的個(gè)數(shù)為 。

5.1.9 DES 的工作模式

FIPS PUB 81 定義了四種工作方式：電子密本 (ECB)、密碼分組鏈接 (CBC)、輸出反饋 (OFB) 和密文反饋 (CFB)。ANSI 銀行標(biāo)準(zhǔn)中規(guī)定加密用 ECB 和 CBC 方式，鑒別用 CBC 和 n 位的 CFB 方式。

在軟件界，認(rèn)證問(wèn)題沒(méi)有引起爭(zhēng)論。因?yàn)?ECB 方式簡(jiǎn)單，所以盡管它最易于攻擊，但在流行的商業(yè)軟件產(chǎn)品中，它仍是最常采用的方式。CBC 方式只是偶爾采用，盡管它比 ECB 方式僅僅復(fù)雜一點(diǎn)兒，但它提供了更好的安全性。

項(xiàng)目源代碼

項(xiàng)目源代碼會(huì)逐步上傳到 Github，地址為 https://github.com/windstamp。

Contributor

1. Windstamp, https://github.com/windstamp