帶 Bitslice 的 DES SBOX 輸出
我不明白如何在 DES 中使用位片技術計算 6 到 4-SBOX 的輸出位。Matthew Kwan 在 Biham 原始論文的論文“Reducing the Gate Count of Bitslice DES”中做了一個簡短的回顧。他寫了：
基本上，對於每個 S-box，該技術是獲取兩個輸入位，將它們擴展為兩個變數的所有 16 個可能的函式，然後使用剩餘的四個 S-box 輸入從這 16 個函式中進行選擇。不過細節稍微複雜一些
我相信我了解如何將 2 個變數擴展為 16 個函式（從 f0 到 f15）……但是我現在如何選擇剩餘的 4 個輸入位和所有 4 個輸出？
Matthew Kwan 的論文可以在這裡找到：http: //fgrieu.free.fr/Mattew%20Kwan%20-%20Reducing%20the%20Gate%20Count%20of%20Bitslice%20DES.pdf
Eli Biham 在Matthew Kwan 的論文中描述的實現任何 6 到 4 位 S-box 的原始算法是
挑出兩個輸入位，比如說 $ i_1 $ 和 $ i_2 $
建構所有 $ 2^{(2^2)}=16 $ 的單比特函式 $ i_1 $ 和 $ i_2 $ ， 說 $ f_0 $ 至 $ f_{15} $
將 S-box 的四個輸出中的每一個描述為這些功能中的哪一個 $ f_j $ 需要為每個 $ 2^4=16 $ 其他四個輸入位的組合 $ i_3 $ $ i_4 $ $ i_5 $ $ i_6 $ S-box，並通過對每個輸出使用四層數字多路復用來實現：
- 對於每一個 $ 2^3=8 $ 的組合 $ i_4 $ $ i_5 $ $ i_6 $ ，我們根據 $ i_3 $ 哪個 $ f_j $ 是需要的。例如，如果對於某個輸出和某些組合 $ i_4 $ $ i_5 $ $ i_6 $ 我們需要選擇 $ f_4 $ 什麼時候 $ i_3=0 $ 和 $ f_7 $ 什麼時候 $ i_3=1 $ ，那麼我們可以這樣做 $ (f_4\operatorname{NAND}\bar{i_3})\operatorname{NAND}(f_7\operatorname{NAND}i_3) $ , 成本核算 $ 3 $ 門（反相的折扣成本 $ i_3 $ ）。因此這個階段將花費 $ 4\times8\times3=96 $ 門總數（但請參閱下面的優化 1）。
- 對於每一個 $ 2^2=4 $ 的組合 $ i_5 $ $ i_6 $ ，我們根據 $ i_4 $ 需要早期的兩個功能中的哪一個。
- 對於每一個 $ 2 $ 的值 $ i_6 $ ，我們根據 $ i_5 $ 需要早期的兩個功能中的哪一個。
- 我們根據選擇 $ i_6 $ 需要前一階段的兩個函式中的哪一個。
上面做了多路復用 $ 4\times(8+4+2+1)\times3=180 $ $ \operatorname{NAND} $ 門（加 $ 4 $ 逆變器 $ i_3 $ $ i_4 $ $ i_5 $ $ i_6 $ 如果需要考慮這些）。
許多優化是可能的，包括：
- 使用 $ \operatorname{XOR} $ 這允許與兩個門/指令而不是三個多路復用，例如，我們計算 $ ((f_4\operatorname{XOR}f_7)\operatorname{AND}i_3)\operatorname{XOR} f_4 $ ，注意到 $ f_4\operatorname{XOR}f_7 $ 免費提供，因為這仍然是 $ i_1 $ 和 $ i_2 $ ，因此一個 $ f_j $ , 可能 $ f_3 $ 對於一些自然編號；通過調整早期階段計算的內容，對於後面的多路復用階段也是如此。這種優化在軟體中非常有效。它在 Biham 的實施和 Kwan 的帳戶中。
- 計算 $ 8 $ 而不是 $ 16 $ 功能 $ f_j $ ，通過調整復用中的極性。
- 在某些情況下，重用一個函式（超出 $ f_j $ ) 跨多個 S-box 輸出。
- 在某些情況下，不需要所有功能 $ f_j $ ，因為一個碰巧沒有被使用。
- 在某些情況下，能夠移除多路復用級，因為多路復用輸入對所需輸出沒有影響。
- 在某些情況下，能夠簡化多路復用器，因為其中一個數據輸入是恆定的。
- 重新排序可以的東西（輸入 $ i_j $ ，多路復用器的數據輸入，多路復用位的順序 $ i_3 $ $ i_4 $ $ i_5 $ $ i_6 $ 對於每個輸出）以最大化 3/4/5/6 的出現。