真實的 AES 軟體運作方式與教科書上的演算法流程不同。你不會在生產級的 AES 程式碼中看到依序呼叫 SubBytes()、ShiftRows()、MixColumns() 這三個函式——那樣太沒效率。

快速的 AES 軟體改用兩種特殊技巧：基於查表的實作與原生指令。

基於查表的實作#

基於查表的 AES 實作，把 SubBytes-ShiftRows-MixColumns 這個序列，替換成一組 XOR 加上對硬編碼於程式中、執行期載入記憶體之表格的查找。

這之所以可行，是因為 MixColumns 等價於把四個 32 位元值 XOR 起來，其中每個值只依賴狀態中的一個位元組以及 SubBytes。因此你可以建四張各 256 筆的表（每個位元組值一筆），然後用「查四個 32 位元值再 XOR 起來」的方式實作 SubBytes-MixColumns 序列。

例如 OpenSSL 工具包中基於查表的 C 實作長這樣：

/* round 1: */
t0 = Te0[s0 >> 24] ^ Te1[(s1 >> 16) & 0xff] ^ Te2[(s2 >> 8) & 0xff] ^ Te3[s3 & 0xff] ^ rk[ 4];
t1 = Te0[s1 >> 24] ^ Te1[(s2 >> 16) & 0xff] ^ Te2[(s3 >> 8) & 0xff] ^ Te3[s0 & 0xff] ^ rk[ 5];
t2 = Te0[s2 >> 24] ^ Te1[(s3 >> 16) & 0xff] ^ Te2[(s0 >> 8) & 0xff] ^ Te3[s1 & 0xff] ^ rk[ 6];
t3 = Te0[s3 >> 24] ^ Te1[(s0 >> 16) & 0xff] ^ Te2[(s1 >> 8) & 0xff] ^ Te3[s2 & 0xff] ^ rk[ 7];
/* round 2: */
s0 = Te0[t0 >> 24] ^ Te1[(t1 >> 16) & 0xff] ^ Te2[(t2 >> 8) & 0xff] ^ Te3[t3 & 0xff] ^ rk[ 8];
s1 = Te0[t1 >> 24] ^ Te1[(t2 >> 16) & 0xff] ^ Te2[(t3 >> 8) & 0xff] ^ Te3[t0 & 0xff] ^ rk[ 9];
s2 = Te0[t2 >> 24] ^ Te1[(t3 >> 16) & 0xff] ^ Te2[(t0 >> 8) & 0xff] ^ Te3[t1 & 0xff] ^ rk[10];
s3 = Te0[t3 >> 24] ^ Te1[(t0 >> 16) & 0xff] ^ Te2[(t1 >> 8) & 0xff] ^ Te3[t2 & 0xff] ^ rk[11];
--snip--

記憶體開銷#

一個基本的查表式 AES 加密實作需要 4 KB 的表格：每張表存 256 個 32 位元值，佔 256 × 32 = 8192 位元，也就是 1 KB。解密還需要另外四張表，因此再多 4 KB。

不過有一些技巧能把儲存量從 4 KB 降到 1 KB，甚至更少。

致命弱點：快取時序攻擊#

查表式實作易受快取時序攻擊（cache-timing attacks）——這類攻擊利用程式讀寫快取記憶體元素時的時間差異。

依被存取元素在快取記憶體中的相對位置不同，存取時間會有變化。時序因此洩漏了「哪個元素被存取」的資訊，進而洩漏所涉秘密的資訊。

快取時序攻擊很難避免。一個顯而易見的解法是完全捨棄查找表，改寫一支執行時間不依賴其輸入的程式——但這幾乎不可能在維持相同速度的前提下做到。

因此晶片製造商選了一條激進的路：不再依賴可能有漏洞的軟體，改為依賴硬體。

原生指令（AES-NI）#

AES 原生指令（AES-NI，AES native instructions）解決了 AES 軟體實作的快取時序攻擊問題。

要理解 AES-NI 如何運作，得先想想軟體在硬體上執行的方式：微處理器把二進位碼翻譯成一連串由積體電路元件執行的指令。例如兩個 32 位元值之間的 MUL 組語指令，會啟動微處理器中實作 32 位元乘法器的電晶體。

實作密碼演算法時，我們通常就是表達這類基本運算（加法、乘法、XOR 等）的組合，然後微處理器按照指定順序啟動它的加法器、乘法器與 XOR 電路。

AES 原生指令把這件事推到全新的層次：它提供開發者專用的組語指令來計算 AES。

使用 AES-NI 時，你不必把一輪 AES 寫成一串組語指令，只要呼叫 AESENC 指令，晶片就會為你算完那一輪。

一個典型的 AES 原生指令實作長這樣：

PXOR       %xmm5, %xmm0
AESENC     %xmm6, %xmm0
AESENC     %xmm7, %xmm0
AESENC     %xmm8, %xmm0
AESENC     %xmm9, %xmm0
AESENC     %xmm10, %xmm0
AESENC     %xmm11, %xmm0
AESENC     %xmm12, %xmm0
AESENC     %xmm13, %xmm0
AESENC     %xmm14, %xmm0
AESENCLAST %xmm15, %xmm0

這段程式碼加密最初存放在暫存器 xmm0 中的 128 位元明文，假設暫存器 xmm5 到 xmm15 存放預先算好的輪金鑰，每個指令把結果寫回 xmm0。

• 開頭的 PXOR 指令在計算第一輪之前先 XOR 第一把輪金鑰。
• 最後的 AESENCLAST 指令執行與其他輪略有不同的最末輪（省略 MixColumns）。

效能#

在實作了原生指令的平台上，AES 大約快十倍。在本書寫作時，這幾乎涵蓋所有筆電、桌機與伺服器微處理器，以及多數手機與平板。

具體數字：在最新的 Intel 微架構上，AESENC 指令的延遲是 4 個週期，倒數吞吐量是 1 個週期——意味著一次 AESENC 呼叫要 4 個週期完成，但每個週期就能發出一次新呼叫。