快速便攜的 DES 加密與解密

注意

以下是來自 descore.shar 軟體包的原始 README 檔案，已轉換為 ReST 格式。

des - 快速便攜的 DES 加密與解密。

版權所有 © 1992 Dana L. How

本程式是自由軟體；您可以在自由軟體基金會發布的 GNU 寬通用公共許可證（GNU Library General Public License）的條款下重新分發和/或修改它；您可以選擇許可證的第 2 版，或（根據您的選擇）任何更高版本。

本程式是抱著將會有用的希望而釋出的，但 不附帶任何擔保；不附帶任何適銷性或特定用途適用性的默示擔保。更多詳情請參閱 GNU 寬通用公共許可證。

您應該已經隨本程式收到一份 GNU 寬通用公共許可證的副本；如果未收到，請致函自由軟體基金會，地址：Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA。

作者地址：how@isl.stanford.edu

==>> 在解壓/解包後進行編譯，只需 make <<==

本軟體包旨在實現以下目標

  1. 實現儘可能高的加密/解密效能。

  2. 可移植到任何具有 32 位無符號 C 型別且支援位元組定址的主機。

  3. 可即插即用地替代 KERBEROS 的底層例程。

此第二個版本包含了針對暫存器稀缺機器的多項效能增強。我與 Richard Outerbridge（71755.204@compuserve.com）的討論促成了其中的一些增強。

為了更快地理解本軟體包中的程式碼，請在著手研究 desCode.h 之前，先檢查 desSmallFips.i（透過輸入 make 生成）。後者以引數化方式設定，以便追求極致速度的駭客可以輕鬆修改它，以榨取最後一微秒的效能。您會發現檢查一個具體的實現會更有啟發性，然後在此基礎上再轉到通用的抽象骨架。

與我在 SPARCStation 1 上能編譯的其他可用 DES 程式碼的效能比較 (cc -O4, gcc -O2)

此程式碼 (位元組序無關)

  • 每次加密 30 微秒 (選項：64k 表，無 IP/FP)

  • 每次加密 33 微秒 (選項：64k 表，FIPS 標準位序)

  • 每次加密 45 微秒 (選項：2k 表，無 IP/FP)

  • 每次加密 48 微秒 (選項：2k 表，FIPS 標準位序)

  • 設定新金鑰 275 微秒 (使用 1k 金鑰表)

    這是我見過最快的加密/解密例程。由於我更關注快速的 DES 過濾器，而非 crypt(3) 和密碼破解，因此我尚未真正著手加速金鑰設定例程。此外，我對重新實現 MIT Kerberos DES 庫中的所有其他無用功能不感興趣，所以我只為我的例程提供了少量樁介面，以便它們可以作為 MIT 程式碼或下方任何相容 MIT 的軟體包的直接替代品使用。(請注意，上述前兩個計時資料由於快取效應而具有高度可變性)。

來自澳大利亞的 Kerberos DES 替代方案 (版本 1.95)

  • 每次加密 53 微秒 (使用 2k 表)

  • 設定新金鑰 96 微秒 (使用 2.25k 金鑰表)

    因此，儘管作者採納了我向他提出的一些效能改進建議，但該軟體包在 SPARC 和 68000 上的加密/解密速度仍然較慢。具體來說，根據編譯器的不同，在 68020 上慢 19-40%，在 SPARC 上慢 11-35%。詳細資料如下 (ALT_ECB 是 libdes 的一個變體)：

    編譯器

    機器

    desCore libdes

    ALT_ECB 慢

    gcc 2.1 -O2

    Sun 3/110

    304 uS 369.5uS

    461.8uS 22%

    cc -O1

    Sun 3/110

    336 uS 436.6uS

    399.3uS 19%

    cc -O2

    Sun 3/110

    360 uS 532.4uS

    505.1uS 40%

    cc -O4

    Sun 3/110

    365 uS 532.3uS

    505.3uS 38%

    gcc 2.1 -O2

    Sun 4/50

    48 uS 53.4uS

    57.5uS 11%

    cc -O2

    Sun 4/50

    48 uS 64.6uS

    64.7uS 35%

    cc -O4

    Sun 4/50

    48 uS 64.7uS

    64.9uS 35%

    (我的時間測量不如他準確)。

我對 desCore 1.92 版本首次釋出時的評論

  • 每次加密 68 微秒 (使用 2k 表)

  • 設定新金鑰 96 微秒 (使用 2.25k 金鑰表)

    這是一個非常不錯的軟體包，它實現了我在加密例程中所做的最重要的最佳化。它在常見的底層最佳化方面稍顯不足，這就是為什麼它慢 39%-106% 的原因。由於他關注快速的 crypt(3) 和密碼破解應用，他也利用相同的想法來加速金鑰設定例程，並取得了令人印象深刻的結果。(在某個時候我可能會在我的軟體包中也這樣做)。他還實現了 MIT DES 庫的其餘部分。

    (程式碼來源：eay@psych.psy.uq.oz.au，透過 comp.sources.misc)

來自丹麥的快速 crypt(3) 軟體包

這裡的 DES 例程巢狀在一個迴圈中以執行 crypt 函式，我不想將其剝離出來測量效能。他的程式碼需要 26 條 SPARC 指令來計算一次 DES 迭代；上面，Quick (64k) 需要 21 條，Small (2k) 需要 37 條。他聲稱使用了 280k 的表，但迭代計算似乎只使用了 128k。他的表和程式碼是機器無關的。

(程式碼來源：glad@daimi.aau.dk，透過 alt.sources 或 comp.sources.misc)

Kerberos DES 庫的瑞典重新實現

  • 每次加密 108 微秒 (使用 34k 表)

  • 設定新金鑰 134 微秒 (使用 32k 金鑰表才能達到此速度！)

    所使用的表似乎與機器無關；他似乎包含了許多特殊情況程式碼，例如，當機器架構允許時，可以使用 long 載入代替 4 個 char 載入。

    (程式碼獲取自 chalmers.se:pub/des)

來自英國的 crack 3.3c 軟體包

如上文 crypt 所述，DES 例程巢狀在一個迴圈中。它也針對 crypt 進行了大量修改。他的迭代程式碼使用 16k 的表，並且看起來很慢。

(程式碼獲取自 aem@aber.ac.uk，透過 alt.sources 或 comp.sources.misc)

高度最佳化 和調整過的 Kerberos/Athena 程式碼 (位元組序相關)

  • 每次加密 165 微秒 (使用 6k 表)

  • 設定新金鑰 478 微秒 (使用 <1k 金鑰表)

    因此，儘管該程式碼中有這些註釋，但仍然可以獲得更快且更小的表，並使表與機器無關。(程式碼獲取自 prep.ai.mit.edu)

加州大學伯克利分校程式碼 (取決於機器位元組序)

  • 每次加密 226 微秒

  • 設定新金鑰 10848 微秒

    表大小不清楚，但看起來不大 (程式碼獲取自 wuarchive.wustl.edu)

動機與歷史

一段時間前，我想要一些 DES 例程，但 Sun 手冊頁中記載的例程要麼不存在，要麼會產生核心轉儲。我聽說過 Kerberos，並且知道它使用 DES，所以我想我會使用它的例程。但當我拿到它並檢視程式碼時，它著實引發了我很多不滿——它過於複雜，程式碼在編寫時沒有利用 IP、E 和 FP 等操作的常規結構（即作者在編碼前沒有坐下來思考），它慢得離譜，作者試圖透過新增更多語句來使資料移動更 一致，而不是簡化其實現並減少所有資料移動（特別是他對 L1、R1、L2、R2 的使用），並且充滿了愚蠢的 調整，針對特定機器進行了調整，這些調整未能帶來顯著的速度提升，反而混淆了一切。因此，我從他的驗證程式中獲取了測試資料，並重寫了其他所有內容。

不久之後，我偶然發現了上面提到的那個出色的 crypt(3) 軟體包。他透過每次表查詢計算 2 個 S 盒而不是 1 個（並且在此過程中使用了大得多的表）這一事實，鼓勵我效仿——這只是一個微不足道的改變，但我曾因更大的表大小而望而卻步。在他的例子中，他沒有意識到你不需要將工作資料保持兩種形式：一種用於索引一半 S 盒以便於使用，另一種用於另一半以便於使用；相反，你可以將其保持為前半部分的形式，然後使用簡單的旋轉來獲取另一半。這意味著我的資料操作量和表大小（幾乎）減半。不過公平地說，他可能在他的表中編碼了與 crypt(3) 相關的一些特定內容——我沒有檢查。

我很高興我以這種方式實現了它，因為這個 C 語言版本是可移植的（ifdef 是效能增強），而且它比為 SPARC 手寫彙編的版本更快！

移植說明

我不想做的一件事就是編寫一個龐大的混亂程式碼，它依賴於位元組序和其他機器特性，並且必然為不同的機器生成不同的程式碼和不同的查詢表。請參閱 Kerberos 程式碼，瞭解我不想做的事情的例子；他們所有針對位元組序的 最佳化 混淆了程式碼，並且最終比更簡單的機器無關方法更慢。然而，總會有一些可移植性方面的考慮，我提供了一些選項，用於不同數量的暫存器變數。也許有些人仍然會認為結果是一團糟！

  1. 我假設所有內容都是位元組可定址的，儘管我實際上不依賴於位元組序，並且位元組是 8 位。我假設字指標可以自由地轉換為字元指標，反之亦然。請注意，99% 的 C 程式都做出了這些假設。如果最高位可能被設定，我總是使用無符號字元 (unsigned char)。

  2. 型別定義 word 表示一個 32 位無符號整型。如果 unsigned long 不是 32 位，請修改 desCore.h 中的型別定義。我假設在所有地方 sizeof(word) == 4。

我在圍繞金鑰迭代的資料載入和儲存程式碼中沒有進行位元組序特定最佳化的（最壞情況）成本低於 12%。此外，還有一個額外的好處是輸入和輸出工作區域無需進行字對齊。

可選效能最佳化

  1. 您應該定義 i386, vax, mc68000, 或 sparc, 中的一個，選擇最接近您機器能力的那個。請參閱 desCode.h 的開頭，瞭解此選擇的具體含義。請注意，如果您選擇了錯誤的選項，DES 程式碼仍然可以工作；這些只是效能調整。

  2. 對於具有功能性 asm 關鍵字的使用者：如果您的機器支援旋轉指令，您應該更改 ROR 和 ROL 宏以使用機器旋轉指令。這將為每次使用節省 2 條指令和一個臨時變數，或者每次加密/解密節省大約 32 到 40 條指令。

    請注意，GCC 足夠智慧，可以將 ROL/R 宏轉換為機器旋轉指令！

這些最佳化都相當細緻，但有了它們，您應該能夠獲得與彙編編碼相當的效能，除非

  1. 由於 C 語言中缺少位旋轉運算子，旋轉必須從移位操作中合成。因此，如果您的機器有旋轉指令，訪問 asm 將加快速度，如上文 (3) 所述（如果您使用 GCC 則不需要）。

  2. 如果您的機器的 32 位暫存器少於 12 個，我懷疑您的編譯器會生成好的程式碼。

    i386 嘗試為 386 配置程式碼，只宣告 3 個暫存器（似乎 GCC 可以使用 ebx、esi 和 edi 來儲存暫存器變數）。然而，如果您喜歡彙編程式設計，386 確實有 7 個 32 位暫存器，如果您使用所有這些暫存器，並使用 scaled by 8 定址模式以及位移和其他技巧，您可以為 DesQuickCore... 獲得合理的例程，每個例程大約 250 條指令。對於 DesSmall...，重新排列 des_keymap 會有所幫助，即現在 S 盒編號是索引的高位部分，而 6 位資料是低位部分；交換這些會有幫助。

    由於我無法方便地測試它，因此我沒有提供我的強制 386 版本。請注意，在 desCore 的這個版本中，GCC 能夠將所有內容放入暫存器中（！），併為 DesQuickCore... 例程生成大約 370 條指令！

編碼說明

加密/解密例程每個使用 6 個必要的暫存器變數，其中 4 個在內部迭代期間同時活躍使用。如果您沒有 4 個暫存器變數，請換一臺新機器。在某些配置中，最多還會使用 8 個暫存器來儲存常量。

我假設使用常量比使用暫存器開銷更大

  1. 此外，我嘗試將較大的常量放入暫存器中。暫存器分配優先順序如下：

    • 超過 12 位的任何值 (對 RISC 和 CISC 都不利)

    • 值大於 127 (無法在 CISC 上使用 movq 或位元組立即數)

    • 9-127 (可能無法使用 CISC 移位立即數或快速加/減),

    • 1-8 從未被註冊，因為它們是開銷最低的常量。

  2. 編譯器可能過於愚蠢，無法意識到 table 和 table+256 應該分配給不同的常量暫存器，而是重複進行算術運算，因此我儘可能且有益地將這些分配給顯式的 m 暫存器變數。

我假設索引操作比自動增/減操作更便宜或等效，其中索引為 7 位無符號數或更小。對於 68k 和 VAX，這個假設是相反的。

我假設地址可以廉價地由兩個暫存器，或由一個暫存器和一個小常量構成。對於 68000，兩個暫存器和小偏移 形式很少使用。所有索引縮放都明確完成——沒有透過 log2(sizeof) 進行隱藏移位。

程式碼的編寫方式使得即使是愚蠢的編譯器也絕不需要多於一個隱藏臨時變數，從而增加了所有內容都能放入暫存器中的機會。如果您重寫任何程式碼，請牢記這一更微妙的要點。

(實際上，現在有一些程式碼片段確實需要兩個臨時變數，但修復它要麼會破壞宏的結構，要麼需要宣告另一個臨時變數)。

特殊高效資料格式

大多數情況下，位按此排列進行操作 (S7 S5 S3 S1)

003130292827xxxx242322212019xxxx161514131211xxxx080706050403xxxx

(x 位仍然存在，我只是在強調 S 盒的位置)。在計算 S6 S4 S2 S0 時，位向左旋轉 4 位。

282726252423xxxx201918171615xxxx121110090807xxxx040302010031xxxx

最右邊的兩位通常被清零，以便較低的位元組可以用作 S 盒對映表的索引。接下來的兩個 x 位被設定為各種值，以訪問表的各個部分。

如何使用這些例程

資料型別

指向 DesData 型別 8 位元組區域的指標，用於儲存金鑰和 DES 的輸入/輸出塊。

指向 DesKeys 型別 128 位元組區域的指標，用於儲存完整的 768 位金鑰。必須進行長字對齊。

DesQuickInit()

在使用任何名稱中包含 Quick 的例程之前呼叫此函式。它會生成這些例程所需的特殊 64k 表。

DesQuickDone()

釋放此表

DesMethod(m, k)

m 指向一個 128 位元組塊，k 指向一個 8 位元組的 DES 金鑰，該金鑰必須具有奇校驗（否則返回 -1）並且不能是（半）弱金鑰（否則返回 -2）。通常 DesMethod() 返回 0。

m 從 k 填充，因此當使用 m 呼叫以下例程之一時，該例程將像使用金鑰 k 的標準 DES 加密/解密一樣執行。如果您使用 DesMethod，您將提供一個標準的 56 位金鑰；但是，如果您自己填充 m，您將得到一個 768 位金鑰——但它將不是標準的。它是 768 位而不是 1024 位，因為每個位元組的最低兩位未被使用。請注意，這兩個位將被設定為魔術常量，這在某些機器上可以加快加密/解密速度。是的，每個位元組在特定迭代期間控制一個特定的 S 盒。

您真的不應該直接使用 768 位格式；我應該提供一個例程，將 128 個 6 位位元組（以 S 盒對映順序或其他方式指定）轉換為適合您的正確格式。這需要進行一些位元組連線和旋轉操作。

Des{Small|Quick}{Fips|Core}{Encrypt|Decrypt}(d, m, s)

將 s 處的 8 個位元組進行 DES 運算，結果存入 d 處的 8 個位元組中。 (d,s: char *)。

如上所述，使用 m 作為 768 位金鑰。

Encrypt|Decrypt 的選擇很明顯。

Fips|Core 決定是否執行完全標準的 FIPS 初始置換和最終置換；如果不是，則資料以非標準位序載入和儲存（不帶 IP/FP 的 FIPS）。

Fips 會使 Quick 慢 10%，Small 慢 9%。

Small|Quick 決定您是使用常規例程還是佔用額外 64k 記憶體的超快速例程。Small 比 Quick 慢 50%，但 Quick 需要 32 倍的記憶體。Quick 適用於只進行 DES 操作的程式，例如加密過濾器等。

在您的機器上編譯

程式碼中沒有機器依賴性（參見移植說明），除了 desTest.c 中的 now() 宏。所有生成的表都是機器無關的。您應該使用適合您的編譯器的最佳化標誌（最大最佳化）編輯 Makefile。

加速 Kerberos（和/或其 DES 庫）

請注意，我已經在 desUtil.c 中透過 des_key_sched() 和 des_ecb_encrypt() 函式包含了 Kerberos 相容介面。要將這些與 Kerberos 或 Kerberos 相容程式碼一起使用，請在連結器命令列中將 desCore.a 放在 Kerberos 相容庫之前。您不需要 #include desCore.h；只需包含 Kerberos 庫提供的標頭檔案即可。

其他用途

desCode.h 中的宏對於在更復雜的加密例程中嵌入 DES 行內函數非常有用。