由於計算機技術發展迅速，電腦的運算能力大幅提昇，對於使用56 bits金鑰的DES密碼系統而言，正面臨著被破解之威脅。因此，NIST ( National Institute of Standards and Technology)美國國家標準技術局於1997年4月正式公告徵求下一代的加密標準(Advanced Encryption Standard, AES) ，以期能保護敏感(sensitive)但非機密(unclassified)的資料。2000年10月NIST公開選定Rijndael的區塊密碼系統成為AES的標準。本篇論文主要描述如何使用硬體架構及軟體方面實現AES密碼系統的演算法。在硬體架構方面，利用有限體的特性發展出不同的硬體架構，以達成AES密碼系統加解密程序中所使用到的乘法、反相(Inverse)函數之功能。軟體實現部份，除達成AES密碼系統的演算法外，論文中提出了改良型的AES密碼系統及On the Fly在系統方面的運用，及在不同設計架構下系統之效能比較。

The Standard 56 bits Cipher key DES system faces a threat of de-encryption and cracking due to the exploding development of computer techniques. In order to protect the information that is unclassified but sensitive, National Institute of Standards and Technology (NIST) announced the next generation Advanced Encryption Standard (AES) in April 1997. NIST officially adopted the Rijndael block cipher system as the standard of AES in October 2000.
This thesis focuses on how to derive fast algorithms and memory-saving architectures to implement AES security system in both hardware and software. By using the characteristic of finite field, fast field element multiplication and inversion are developed, in which parallel computation can be performed. For software implementation, table look-up and merged table look-up techniques are derived, which speed up the cipher as well as save the memory usage. Also, On the Fly mechanism is implemented to accommodate various applications. All the algorithms and the architectures are verified and the performances are compared.

目 錄
摘 要 I
Abstract II
誌 謝 III
目 錄 IV
圖 目 錄 VIII
第一章 區塊密碼系統 1
1.1 秘密金鑰系統－DES(data encryption standard) 2
1.1.1 Double DES與Triple DES 3
1.1.1.1 Double DES 3
1.1.1.2 Triple DES 4
1.1.2 DES的四種操作模式 5
1.1.2.1 ECB ( Electronic Code Book ) 模式 5
1.1.2.2 CFB ( Cipher Feedback ) 模式 6
1.1.2.3 CBC ( Cipher Block Chaining ) 模式 7
1.1.2.4 OFB ( Output Feedback ) 模式 7
1.2 AES(Advanced Encryption Standard)密碼系統 8
第二章 Rijndael數學理論、字彙及符號 10
2.1 數學理論 10
2.1.1 有限體 GF(28) 10
2.1.2 加法 10
2.1.3 乘法 11
2.1.4 基本乘法 11
2.2 字彙及符號 12
第三章 Rijndael區塊密碼系統 15
3.1 系統架構 15
3.2 明文( PlainText )、金鑰( CipherKey )的分割與回合次數(Nr) 17
3.2.1 將明文分割成State 17
3.2.2 金鑰的分割 18
3.2.3 Nb、Nk、Nr間的關係 18
3.3 系統函數 19
3.3.1 SubBytes( ) 轉換 19
3.3.2 ShiftRow( ) 轉換 21
3.3.3 MixColumn( ) 轉換 22
3.3.4 AddRoundKey( ) 轉換 23
3.4 金鑰的排程(Key schedule) 23
3.4.1 基本原理 23
3.4.2 金鑰的擴展(Key expansion) 24
3.4.2.1 SubByte( ) 27
3.4.2.2 RotByte( ) 27
3.4.2.3 Rcon( ) 27
3.4.3 RoundKey 的選擇 28
3.5 AES密碼系統的解密程序 29
3.5.1 InvShiftRow( ) 轉換 30
3.5.2 InvSubBytes( ) 轉換 30
3.5.3 InvMixColumn ( ) 轉換 31
3.5.4 AddRoundKey( ) 的反向轉換 32
第四章 AES 密碼系統效能改善 33
4.1 乘法運算 33
4.1.1 解決AES運算時的乘法問題 34
4.1.2 AND及XOR Gate的組合電路 34
4.1.2.1 利用AES密碼系統標準之irreducible polynomial 34
4.1.2.2 乘法組合電路的改良 35
4.1.2.3 AND及XOR組合電路的改進 35
4.1.3 效能比較 37
4.2 SubBytes() 轉換 37
4.2.1 查表法 37
4.2.2 直接運算 37
4.2.2.1 SubBytes()轉換 38
4.2.2.2 InvS-Box 運算 38
4.3 回合金鑰的擴展 ( RoundKey Expansion ) 40
4.3.1 將擴展之RoundKey儲存在記憶體 41
4.3.1.1 加密 41
4.3.1.2 解密 41
4.3.2 On the Fly 41
4.3.2.1 Nk=4時的RoundKey的擴展 42
4.3.2.2 Nk=6時的RoundKey的擴展 45
4.3.2.3 Nk=8時的RoundKey的擴展 46
4.4 Inverse的處理 49
4.4.1 Inverse 運算架構 49
4.4.2 改良的Inverse 運算架構 50
4.4.3 效能比較 51
4.5 修改Round工作程序 51
4.5.1 Step by Step 52
4.5.2 將Round內的四個函數組合 52
4.5.2.1 Round組合運算的修改 54
4.5.3 三種不同方式執行Round運算的比較 54
4.6 加解密使用相同的加密硬體線路 55
第五章 結論 59
附錄A 執行AES標準的加解密程序、Round使用4個Table及Round使用1個Table的結果 60
附錄A.1 AES-128 ( Nb=4、Nk=4、Nr=10 ) 61
附錄A-2 AES-192 ( Nb=4、Nk=6、Nr=12 ) 66
附錄A.3 AES-256 ( Nb=4、Nk=8、Nr=14 ) 71
附錄B 參考文獻 77

[1] Chu-Hsing Lin, “The Rijndael Cipher Algorithm” ,AES成果發表會, November , 2000.[2] Hannes Brunner,Andres Curiger,and Max Hofstetter, “On Computing Multiplicative Inverse in GF(2m)” , IEEE Transactionson Computers,Vol.42,No. 8,August 1993.
[3] Joan Daemen,Vincent Rijmen, “ The Rijndael Block Cipher ”,AES Proposal : Rijndael,March 1999.
[4] J. H. Jeng, J. M. Kuo and T. K. Truong, “A High Efficient Multiplier for the RS Decoder”.
[5] National Bureau of Standards,FIP PUB 46, “Data Encryption Stardans” , National Bureau of Standards, U.S. Deaprtment of Commerce , January 1977.
[6] 王立洋, “CPLD Implementation of Rijndael Cipher”,AES成果發表會,November,2000.
[7] 賴溪松, “AES的簡介與發展” ,AES成果發表會, November ,2000.[8] 賴溪松、韓 亮、張真誠 (民88)，近代密碼學及其應用，台北市，松崗電腦圖書。
[9] 楊吳泉 (民86)，現代密碼學入門與程式設計，台北市，全華科技圖書。
[10] 網站：http://www.esat.kuleuven.ac.be/~rijmen/rijndael/
[11] AES網站:http://csrc.nist.gov/encryption/aes/[12] 資訊安全通訊第六卷第二期:(89.03)：AES第一回合演算法的比較
[13] 資訊安全通訊第六卷第四期:(89.09)