位切片如何更快？
我已閱讀有關位切片和輕量級加密的論文，但無法理解位切片如何使加密方案更快。
請有人可以用一個例子確切地解釋位切片如何使程式碼更快（即使是一個 xor 範例就足夠了）？位切片可以應用於任何加密方案嗎？
Bitslicing 是一種計算技術：
- 簡化為具有單個位輸出（通常為 NOR、XOR 和類似 OR AND NAND NXOR，通常進一步限制為兩個輸入）的基本操作（稱為門），而不是對跨越多個位的字或整數的操作。
- 並行執行，具有與某種寄存器類型中的位一樣多的同時實例（在單個 CPU 上），同時在此類寄存器的所有位上執行 NOR、XOR ..。
做1會產生大量的門：兩個的異或 $ n $ -bit 字需要 $ n $ 大門；為了 $ n>1 $ 他們的加法模 $ 2^n $ 需要 $ 5n-6 $ 大門；AES SubBytes 中的每個 8 位 S-box 查找需要大約 128 個門；另一方面，旋轉、任意位混洗、選擇或擴展不需要門。
做2個工具 $ w $ 每個指令操作的門 $ w $ 位寄存器，並且大部分加速（如果有的話）來自並行化的一個因子 $ w $ （警告：有效的 $ w $ 不能大於同時執行的計算數量）。越來越多的嵌入式 CPU 支持 $ w=32=2^5 $ ,帶有 AVX 指令的 CPU甚至支持 $ w=256=2^8 $ . 最重要的是，位片程式碼不受記憶體相關側通道（包括時序）的影響。作為獎勵，它是非常線性的，這使得數據訪問的有效調度更容易，並且沒有分支延遲。
位切片的缺點：最重要的是， $ w $ 同時操作不匹配所有工作負載！對於單個大文件和分組密碼的常見操作模式，只有 CTR（或有缺陷的 ECB）是完全可用的（CBC 和 CFB 僅可用於解密，OFB 不可用）。此外，程式碼量大且相對複雜；從普通形式到位片形式的參數的轉換（並返回結果）需要位轉置，這會增加一些顯著的成本；許多中間結果或狀態數據在正常實現中適合寄存器或 L1 高速記憶體，但不這樣做。
一個與速度無關的好處：對加密操作進行位切片消除了持續時間對所操作數據的任何依賴性（因為按位運算符具有固定的持續時間）。這可以防止通過時序分析（對操作位切片的）進行側通道攻擊，包括在 S-Table 的表查找期間難以避免的與記憶體相關的時序攻擊。
原則上，對多個實例執行的任何加密計算都可以進行位切片。然而，許多在沒有位切片的情況下本機處理的操作不太可能獲得任何速度優勢；這包括任何太簡單的事情（比如提議的 XOR），或者對門的轉換效率非常低（比如模乘，或者查找大型任意固定表，或相當大的動態表），或者執行流程有太多路徑。有關更詳細的分類，請參閱Ilmari Karonen 的回答。同樣，我們需要能夠並行進行多個計算！
位切片可以帶來速度優勢的真實密碼的典型範例是 (3)DES，這是由 Eli Biham 的A fast new DES implementation in software (in Proceedings of FSE 1997 ) 開創的。
任何比 DES 簡單得多的東西，我可以建構來展示位切片的好處，這與現實生活相去甚遠。因此，我以（單個） DES的純軟體實現為例，它帶有預先計算的子密鑰，在具有十幾個通用 128 位寄存器、128 位（記憶體）記憶體訪問的 CPU 上，用於加密 128 個塊（1024 個任意字節；我忽略了 CTR 模式下可能的優化）。
傳統的（非位片）實現是：
對於每個 $ w $ 塊
根據初始排列（IP，位轉置）將輸入塊轉換為兩個 32 位半 L 和 R
圓形 $ r $ 從 1 到 16
載入回合的 48 位子密鑰 $ r $ 進入寄存器 K
用於 S 盒 $ s $ 從 8 到 1
- 製作適當旋轉的副本或 R
- 與 K 異或
- 保持低6位
- 使用它作為索引來載入 $ s $ th S 表，包括 $ 64=2^6 $ 每個 32 位的值（實現 S-box 和置換 P 的一部分，因此是寬輸出）；該步驟通常占主導地位，並且可能是目標記憶體相關的側通道
- 異或到 L
- 將 K 向右移動 6 位以用於下一個 S-box
交換 R 和 L
將兩個 32 位的一半 R 和 L 轉換為每個 IP -1的輸出塊
S-box 循環通常是展開的（以及循環循環的至少兩次連續執行，這使得交換基本上是免費的），因此成本主要由編號的步驟決定。我們可以抑制 8 個步驟 1 和 6 中的 1 個。因此，成本的一個很好的近似值（暫時忽略 IP 和 IP -1）是 $ w $ 16 次：9 次記憶體載入（其中 8 次被索引）和大約 38 次其他簡單操作。
Bitsliced DES 抑制外部塊循環，將其替換為對 $ w=128 $ - 在每一步操作塊相關數據的位：
將 128 個輸入塊（每個 64 位）轉換為 64 個記憶體字（每個 128 位），每個記憶體字包含一個塊中相同等級的所有位（位轉置）
圓形 $ r $ 從 1 到 16
載入回合的 48 位子密鑰 $ r $ 進入寄存器 K
用於 S 盒 $ s $ 從 8 到 1
- 對於S-box的 6 個輸入位j中的每一個 $ s $
a) 將 K 的最右邊位複製到一個 128 位寬的寄存器 T j
b) 載入 128 位儲存器字，保存狀態的適當位
c) 將其異或到 T j
d) 將 K 右移一位 2. 對於 S-box 的 4 個輸出位中的每一個 $ s $
a) 計算輸出位（同時用於所有 128 個塊）作為 T 1 ..T 6的布爾函式，到 128 位寄存器 X
b) 載入 128 位記憶體字，保存狀態的適當位
c) XOR 與 X
d) 將其儲存為 128 位記憶體字，保存相應的狀態位
將 64 個記憶體字（每個 128 位）轉換為 128 個輸出塊（每個 64 位）以形成結果（位轉置反轉第一個）
我們將展開循環（如果我們想要載入/儲存的固定地址而不是子鍵，我們需要兩個版本，具體取決於 $ r $ 是奇數還是偶數）。獨立地：我們可以使用在步驟 1a 載入的 6 個值中的 2 個將可重複用於下一個（或/和最後一個）S-box，從而減少步驟 1b 的有效載入數量，但代價是很少的額外寄存器。
在步驟 2a 中，S-box 被布爾運算替換。使用 Matthew Kwan 在Reducing the Gate Count of Bitslice DES ( ePrint 2000/051 ) 中推導出的表達式，平均成本下降到每個 S-box 51 個布爾運算，代價是需要一些臨時寄存器，以及一些不受歡迎的突發在步驟 2d 儲存。
因此，成本的一個很好的近似值（忽略初始和最終轉置）是 16 倍：65 次記憶體載入和 32 次記憶體寫入（無索引），以及大約 440 次其他操作。
因此，如果我們忽略初始和最終轉置的成本，Bitslice DES 在速度上是贏家，即使寬操作比窄操作成本更高：每輪的記憶體訪問減少了 $ 9w=1152 $ 至 $ 97 $ ; 其他操作來自 $ 38w=4864 $ 至 $ 440 $ . 那十倍的改進（對於 $ w=128=2^7 $ ) 超過了換位的額外成本（無論如何，這比換位的成本略高） $ w $ 乘以 IP 和 IP -1：最終，相同數量的數據被轉置）。通過仔細編碼，bitslice DES 可能會更快，包括 $ w=32=2^5 $ .