高級加密標準

SubBytes是AES演演算法四步驟之一。

進階加密標準（Advanced Encryption Standard，縮寫：AES），又稱Rijndael加密法（音似英文的「Rhine doll」），是美國聯邦政府採用的一種區塊加密標準。這個標準用來替代原先的DES，已經被多方分析且廣為全世界所使用。經過五年的甄選流程，進階加密標準由美國國家標準與技術研究院（NIST）於2001年11月26日發佈於FIPS PUB 197，並在2002年5月26日成為有效的標準。現在，進階加密標準已然成為對稱密鑰加密中最流行的演演算法之一。

該演演算法為比利時密碼學家Joan Daemen和Vincent Rijmen所設計，結合兩位作者的名字，以Rijndael為名投稿進階加密標準的甄選流程。

## 沿革

Rijndael是由Daemen和Rijmen早期所設計的Square (cipher)改良而來；而Square則是由SHARK發展而來。

不同於它的前任標準DES，Rijndael使用的是代換-置換網路，而非Feistel架構。

## 密碼說明

嚴格地說，AES和Rijndael加密法並不完全一樣（雖然在實際應用中兩者可以互換），因為Rijndael加密法可以支援更大範圍的區塊和密鑰長度：AES的區塊長度固定為128位元，密鑰長度則可以是128，192或256位元；而Rijndael使用的密鑰和區塊長度均可以是128，192或256位元。加密過程中使用的密鑰是由Rijndael密鑰生成方案產生。

大多數 AES 計算是在一個特別的有限域完成的。

AES 加密過程是在一個 4×4 的列/行主序矩陣上運作，以 16 個位元組 構成，這個矩陣又稱為「體（state）」：

$$\begin{bmatrix} b_0 & b_4 & b_8 & b_{12} \\ b_1 & b_5 & b_9 & b_{13} \\ b_2 & b_6 & b_{10} & b_{14} \\ b_3 & b_7 & b_{11} & b_{15} \end{bmatrix}$$

（Rijndael 加密法可以透過增加矩陣的「行數（column number）」支援更大的區塊）

金鑰長度決定了加密的回合數（rounds）。對於不同長度的金鑰，回合數如下：

- 128 位元金鑰：10 回合
- 192 位元金鑰：12 回合
- 256 位元金鑰：14 回合

加密時，各輪AES加密迴圈（除最後一輪外）均包含4個步驟：

- AddRoundKey—矩陣中的每一個位元組都與該次密鑰次序表（round key）做XOR運算；每個子密鑰由密鑰生成方案產生。
- SubBytes—透過一個非線性的替換函數，用查找表的方式把每個字節替換成對應的字節。
- ShiftRows—將矩陣中的每個橫列進行循環式移位。
- MixColumns—為了充分混合矩陣中各個直行的操作。這個步驟使用線性轉換來混合每行內的四個字節。最後一個加密迴圈中省略MixColumns步驟，而以另一個AddRoundKey取代。

### AddRoundKey步驟

<image>

AddRoundKey步驟，回合金鑰將會與原矩陣合併。在每次的加密迴圈中，都會由主密鑰產生一把回合金鑰（透過Rijndael密鑰生成方案產生），這把金鑰大小會跟原矩陣一樣，以與原矩陣中每個對應的位元組作異或（⊕）加法。

### SubBytes步驟

<image>

在SubBytes步驟中，矩陣中的各字節透過一個8位元的S-box進行轉換。這個步驟提供了加密法非線性的變換能力。S-box與$GF(2^8)$上的乘法反元素有關，已知具有良好的非線性特性。為了避免簡單代數性質的攻擊，S-box結合了乘法反元素及一個可逆的仿射變換矩陣建構而成。此外在建構S-box時，刻意避開了不動點與反不動點，即以S-box替換字節的結果會相當於錯排的結果。Rijndael S-box條目有針對S-box的詳細描述。

### ShiftRows步驟

<image>

ShiftRows描述矩陣的行操作。在此步驟中，每一行都向左循環位移某個偏移量。在AES中（區塊大小128位元），第一行維持不變，第二行裡的每個位元組都向左循環移動一格。同理，第三行及第四行向左循環位移的偏移量就分別是2和3。128位元和192位元的區塊在此步驟的循環位移的模式相同。經過ShiftRows之後，矩陣中每一豎列，都是由輸入矩陣中的每個不同列中的元素組成。Rijndael演演算法的版本中，偏移量和AES有少許不同；對於長度256位元的區塊，第一行仍然維持不變，第二行、第三行、第四行的偏移量分別是1位元組、2位元組、3位元組。除此之外，ShiftRows操作步驟在Rijndael和AES中完全相同。

### MixColumns步驟

<image>

在MixColumns步驟，每一列的四個位元組透過線性變換互相結合。每一列的四個元素分別當作$1 , x , x^2 , x^3$的係數，合併即為$GF(2^8)$中的一個多項式，接著將此多項式和一個固定的多項式$c (x) = 3x^3 + x^2 + x + 2$在模$x^4+1$下相乘。此步驟亦可視為Rijndael有限域之下的矩陣乘法。MixColumns函數接受4個位元組的輸入，輸出4個位元組，每一個輸入的位元組都會對輸出的四個位元組造成影響。因此ShiftRows和MixColumns兩步驟為這個密碼系統提供了擴散性。

以下條目有對MixColumns更加詳細的描述：Rijndael mix columns

### 加密演演算法優化

使用32或更多位元定址的系統，可以事先對所有可能的輸入建立對應表，利用查表來實作SubBytes，ShiftRows和MixColumns步驟以達到加速的效果。這麼作需要產生4個表，每個表都有256個格子，一個格子記載32位元的輸出；約佔去4KB（4096位元組）記憶體空間，即每個表佔去1KB的記憶體空間。如此一來，在每個加密迴圈中，只需要查16次表，作12次32位元的XOR運算，以及AddRoundKey步驟中4次32位元XOR運算。若使用的平台記憶體空間不足4KB，也可以利用循環交換的方式一次查一個256格32位元的表。

然而，實際實作中應避免使用這樣的對應表，否則可能因為產生快取命中與否的差別而使旁道攻擊成為可能。

## 安全性

截至2006年，針對AES唯一的成功攻擊是旁道攻擊或社會工程學攻擊。美國國家安全局審核了所有的參與競選AES的最終入圍者（包括Rijndael），認為他們均能夠滿足美國政府傳遞非機密文件的安全需要。2003年6月，美國政府宣布AES可以用於加密機密文件：

（譯：AES加密演演算法（使用128，192，和256位元密鑰的版本）的安全性，在設計結構及密鑰的長度上俱已到達保護機密資訊的標準。最高機密資訊的傳遞，則至少需要192或256位元的密鑰長度。用以傳遞國家安全資訊的AES實作產品，必須先由國家安全局審核認證，方能被發放使用。）

這標誌著，由美國國家安全局NSA批准在最高機密資訊上使用的加密系統首次可以被公開使用。許多大眾化產品只使用128位元密鑰當作預設值；由於最高機密文件的加密系統必須保證數十年以上的安全性，故推測NSA可能認為128位元太短，才以更長的密鑰長度為最高機密的加密保留了安全空間。

通常破解一個區塊加密系統最常見的方式，是先對其較弱版本（加密迴圈次數較少）嘗試各種攻擊。AES中128位元密鑰版本有10個加密迴圈，192位元密鑰版本有12個加密迴圈，256位元密鑰版本則有14個加密迴圈。至2006年為止，最著名的攻擊是針對AES 7次加密迴圈的128位元密鑰版本，8次加密迴圈的192位元密鑰版本，和9次加密迴圈的256位元密鑰版本所作的攻擊。

由於已遭破解的弱版的AES，其加密迴圈數和原本的加密迴圈數相差無幾，有些密碼學家開始擔心AES的安全性：要是有人能將該著名的攻擊加以改進，這個區塊加密系統就會被破解。在密碼學的意義上，只要存在一個方法，比窮舉法還要更有效率，就能被視為一種「破解」。故一個針對AES 128位元密鑰的攻擊若「只」需要2120計算複雜度（少於窮舉法2128），128位元密鑰的AES就算被破解了；即便該方法在目前還不實用。從應用的角度來看，這種程度的破解依然太不切實際。最著名的暴力攻擊法是distributed.net針對64位元密鑰RC5所作的攻擊。

其他的爭議則著重於AES的數學結構。不像其他區塊加密系統，AES具有相當井然有序的代數結構。雖然相關的代數攻擊尚未出現，但有許多學者認為，把安全性建立於未經透徹研究過的結構上是有風險的。Ferguson，Schroeppel和Whiting因此寫道：「...我們很擔心Rijndael演演算法應用在機密系統上的安全性。」

2002年，Nicolas Courtois和Josef Pieprzyk發表名為XSL攻擊的理論性攻擊，試圖展示AES一個潛在的弱點。但該攻擊的數學分析有點問題，推測應是作者的計算有誤。因此，這種攻擊法是否對AES奏效，仍是未解之謎。就現階段而言，XSL攻擊AES的效果不十分顯著，故將之應用於實際情況的可能性並不高。

### 旁道攻擊

旁道攻擊，又稱旁路攻擊、側信道攻擊，是一種基於從密碼系統的物理實現中獲取的資訊的攻擊方式。它不攻擊加密演算法本身，而是攻擊那些基於不安全系統（會在不經意間洩漏資訊）上的加密系統。

2005年4月，D.J. Bernstein公佈了一種緩存時序攻擊法，他以此破解了一個裝載OpenSSL AES加密系統的客戶伺服器。為了設計使該伺服器公佈所有的時序資訊，攻擊演算法使用了2億多條篩選過的明碼。對於需要多個跳躍的國際網際網路而言，這樣的攻擊方法並不實用。Bruce Schneier稱此攻擊為「好的時序攻擊法」。

2005年10月， Eran Tromer 和另外兩個研究員發表了一篇論文，展示了數種針對AES的緩存時序攻擊法。

## 外部連結

- The Rijndael Page（Forwards automatically to the AES Lounge; use old version link to browse）
- The Rijndael Page (old version)
- Literature survey on AES
- Recordings of the pronunciation of "Rijndael"（85 KB wav file）
- The archive of the old official AES website
- FIPS PUB 197: the official AES standard（PDF file）
- John Savard's description of the AES algorithm

### 實現

- 參考代碼
- 65+種AES硬體實施方案
- A Javascript AES calculator showing intermediate values
- Brian Gladman's BSD licensed implementations of AES
- http://www.esat.kuleuven.ac.be/~rijmen/rijndael/rijndael-fst-3.0.zip Paulo Barreto公布的AES的C語言演算法
- D.J. Bernstein所寫的開放版權AES實施代碼
- The GPL-licensed Nettle library also includes an AES implementation
- Compact AES implementation in hardware by IP Cores
- AES加密在Windows系統的實現 (自由公開源碼)
- LGPL授權的AES實現的C語言原始碼
- 廣泛的AES硬體實施方案，Helion Technology
- FPGA Based AES Implementation using Nios-II Processor