Rijndael

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

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

## 沿革

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

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

## 密碼說明

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

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

AES 加密過程是在一個 4×4 的位元組矩陣上運作，這個矩陣又稱為「體（state）」，其初值就是一個明文區塊（矩陣中一個元素大小就是明文區塊中的一個 Byte）。（Rijndael 加密法因支援更大的區塊，其矩陣的「列數（Row number）」可視情況增加）加密時，各輪 AES 加密迴圈（除最後一輪外）均包含 4 個步驟：

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

### AddRoundKey 步驟

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

### SubBytes 步驟

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

### ShiftRows 步驟

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

### MixColumns 步驟

在 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 可以用於加密機密檔案：

> The design and strength of all key lengths of the AES algorithm（i.e., 128, 192 and 256）are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use.  
> 
> 

（譯：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 的快取時序攻擊法。

## 注釋

## 參考文獻

### 參照

### 書目

* Nicolas Courtois, Josef Pieprzyk, "Cryptanalysis of Block Ciphers with Overdefined Systems of Equations". pp267–287, ASIACRYPT 2002.
* Joan Daemen, Steve Borg and Vincent Rijmen, "The Design of Rijndael: AES - The Advanced Encryption Standard." Springer-Verlag, 2002. ISBN 3-540-42580-2.

## 外部連結

* 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 （頁面存檔備份，存於網際網路檔案館）

## 參見

* 進階加密標準評選過程