臺灣博碩士論文加值系統

隨著計算機技術的進步與成本下滑，使得電腦運算能力大幅提昇，對於目前正在通用金鑰為56位元的數據加密標準(Data Encryption Standard，簡稱DES)而言，安全性已漸受質疑，美國國家標準與技術學會(National Institute of Standards and Technology，簡稱NIST)將採用安全性更高的三重數據加密標準(Triple Data Encryption Standard，簡稱Triple DES)與先進加密標準(Advanced Encryption Standard，簡稱AES)取代舊有的DES，成為未來通行的加密標準。由於Triple DES的運算高達48回合，安全性雖然提高，但在效能方面卻反而降低。在這論文中，提出了一個高效能的Triple DES區塊加解密器，利用管線化架構的方式提高其加解密效率，並經由暫存器存取控制的設計來縮減I/O Pin腳的數目，以達到Core Bound的效果，使晶片面積不至於因為I/O Pin腳過多而導致製作成本的浪費。此外我們也提出了一個新的金匙產生器架構，使Triple DES的子金匙(Subkey)能同步產生，在加密與解密時，不用花多餘時間等候金匙的產生，亦可節省儲存子金匙的記憶體。
由於Triple DES加密與解密的架構相似，為了使用上方便與節省硬體資源，我們將加密與解密的架構設計在同一晶片中。為了驗證我們所提出的架構是可行的，我們實際採用台積電0.35微米單層多晶矽四層金屬的互補式金氧半場效電晶體製成技術來實作整個設計流程。本晶片的面積為4.50 X 4.50 mm2，最高的工作頻率83.33 MHz，功率消耗205 mW。

Although Data Encryption Standard (DES) is widely used for information security in the past twenty years, it is not secure now. Computer technology keeps progressing, and chips are faster and cheaper. Triple Data Encryption Standard (Tripe DES) and Advanced Encryption Standard (AES) were selected by NIST (National Institute of Standards and Technology), which will replace DES in a few years. Triple DES is more secure than DES, but the efficiency is not as good as DES.
In this thesis, a high performance VLSI architecture of the symmetric block cipher, Triple DES, for data encryption and decryption is presented. This cipher works on blocks of 64 bits and has three 56 bits keys. In our design, based on the fully pipelined structure, limited I/O pins and fast encryption and decryption are achieved. In the design, we use registers to emulate substitution boxes instead of 12KByte memory. We also employ a new architecture for the Triple DES key generator, which can generate all subkeys on the fly at same time. Our key generator does not need additional memory to store subkeys. In addition, the duration for initialization is reduced.
Our design use 0.35μm CMOS technology with four layers of metal. The design allows encryption and decryption to be achieved in a single chip. The chip requires silicon area 4.50 x 4.50 mm2. Its gate counts is 127k. The throughput is 635.76 Mbytes/sec, and the power consumption is 205mW.

第一章 簡介 ………………………………… 1
1.1 研究動機 …………………………… 2
1.2 研究目的 ………………………………… 3
1.3 密碼學原理 ……………………………… 3
1.3.1 安全攻擊 ……………………………… 4
1.3.2 安全服務 ……………………………… 6
1.3.3 密碼破解 ……………………………… 7
1.4 論文架構 …………………………………… 9
第二章 相關研究 ………………………………… 10
2.1 管線化架構的Triple DES做法 ………… 10
2.1.1 Chueng, Yusoff and Sha’ameri的做法 ……… 10
2.1.2 Hämäläinen, Hännikäinen, Hämäläinen, and
Saarinen的做法 …………… 12
2.1.3 McLoone and McCanny的做法 ………………… 14
2.1.4 Verbauwhede, Hoornaert, Vandewalle and
De Man的做法 ……………… 15
2.2 安全性與效能研究 ………………………………… 17
第三章 研究方法 ……………………………………… 19
3.1 研究架構 ………………………………………… 19
3.2 研究步驟 ………………………………………… 20
3.2.1 DES與Triple DES演算法 ………………… 22
3.2.2 平行處理架構 ………………………………… 22
3.2.3 管線化架構 …………………………………… 23
3.3 研究工具 ……………………………………… 26
第四章 Triple DES演算法介紹 …………………… 28
4.1 Triple DES的起源 ……………………………… 28
4.2 Triple DES加密流程 ………………………… 29
4.2.1 Triple DES單一加/解密回合 ……………… 33
4.2.2 F Function運算 …………………………… 35
4.2.3 子金匙產生 ………………………………… 39
4.3 Triple DES的使用模式 ……………………… 42
4.3.1 TDEA電子編碼模式 ………………………… 43
4.3.2 TDEA密文塊串連模式 ……………………… 44
4.3.3 TDEA密文塊串連交替模式 ………………… 45
4.3.4 TDEA密文反饋模式 ………………………… 46
4.3.5 TDEA密文反饋管線化模式 ………………… 48
4.3.6 TDEA輸出反饋模式 ………………………… 49
4.3.7 TDEA輸出反饋交替模式 …………………… 50
第五章 高效能Triple DES密碼器實作 ………… 51
5.1 高效能Triple DES密碼器架構設計 ……… 51
5.2 高效能Triple DES密碼器之設計 ………… 53
5.2.1 加密核心 ……………………………… 54
5.2.2 Triple DES單一回合 ………………… 56
5.2.3 F Function …………………………… 57
5.2.4 子金匙產生器 ………………………… 59
5.2.5 控制電路 ……………………………… 65
第六章 高效能Triple DES密碼器電路測試與比較 …… 67
6.1 電路測試與波形模擬 …………………………… 67
6.1.1 加密波形模擬 ……………………………… 70
6.1.2 解密波形模擬 ……………………………… 77
6.2 高效能Triple DES密碼器晶片規格 ……………… 84
6.3 Triple DES密碼器效能比較 ……………………… 85
第七章 討論與未來工作 ……………………………… 88
參考資料 ………………………………………………… 90

[1]E. Biham and A. Shamir, “Differential Fault Analysis of Secret Key Cryptosystems,” Advances in Cryptology – CRYPTO’97, Page(s): 513-525.
[2]T. P. Chueng, Z.M. Yusoff and A.Z. Sha'ameri, “Implementation of Pipelined Data Encryption Standard (DES) Using Altera CPLD,” Proceedings of TENCON 2000, Volume: 2, 2000 Page(s): 17 -21 vol.3.
[3]F.A. Feldman, “A New Spectral Test for Nonrandomness and the DES,” Proceedings of IEEE Transactions on Software Engineering, Volume: 16 Issue: 3, March 1990 Page(s): 261 –267.
[4]H. Guendouz and S. Bouaziz, “Rapid Prototype of a Fast Data Encryption Standard with Integrity Processing for Cryptographic Applications,” Proceedings of the 1998 IEEE International Symposium on Circuits and Systems 1998, Volume: 6, 1998 Page(s): 434 -437 vol.6.
[5]G. Gong and S.W. Golomb, “Transform Domain Analysis of DES,” Proceedings of IEEE Transactions on Information Theory, Volume: 45 Issue: 6, Sept. 1999 Page(s): 2065 –2073.
[6]P. Hämäläinen, M. Hännikäinen, T. Hämäläinen and J. Saarinen, “Configurable Hardware Implementation of Triple-DES Encryption Algorithm for Wireless Local Area Network,” Proceedings of 2001 IEEE International Conference on Acoustics Speech and Signal Processing 2001, Volume: 2, 2001 Page(s): 1221 -1224 vol.2
[7]S.J. Han, H.S. Oh and J. Park, ”The Improved Data Encryption Standard (DES) Algorithm,” Proceedings of IEEE 4th International Symposium on Spread Spectrum Techniques and Applications 1996, Volume: 3, 1996 Page(s): 1310 -1314 vol.3.
[8] J.L. Hennessy and D.A. Patterson, Computer Architecture A Quantitative Approach, Second Edition, Morgan Kaufmann Publishers, INC., 1996.
[9]T. Korkishko and A. Melnyk, “Crypto Graphic Processor Architectures for DES Algorithm,” Proceedings of 1999 IEEE Africon, Volume: 1, 1999 Page(s): 175 -180 vol.1.
[10]L.R. Knudsen and B. Preneel, “MacDES: MAC Algorithm Based on DES,” Proceedings of Electronics Letters, Volume: 34 Issue: 9, 30 April 1998 Page(s): 871 –873.
[11]Y.W. Lim, “Efficient 8-Cycle DES Implementation”, Proceedings of the Second IEEE Asia Pacific Conference on ASIC 2000, Page(s): 175 –178.
[12]M. McLoone and J.V. McCanny, “A High Performance FPGA Implementation of DES,” Proceedings of 2000 IEEE Workshop on Signal Processing Systems 2000, Page(s): 374 –383.
[13]National Institute of Standards and Technology, Advanced Encryption Standard (AES), Federal Information Processing Standards (FIPS) PUB 197, November 2001.
[14] National Institute of Standards and Technology, Data Encryption Standard (DES), U.S. Department of Commerce. Federal Information Processing Standards (FIPS) PUB 46-3, October 1999.
[15]C. Patterson, “High Performance DES Encryption in Virtex TM FPGAs Using JBitsTM,“ Proceedings of 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, Page(s): 113 –121.
[16]R.R. Pai, S. J. Han and M. Lowy, “Design and Implementation of the Extended Data Encryption Standard,” Proceedings of International Conference on Digest of Technical Papers Consumer Electronics 1996, June 5-7 1996 Page(s): 160.
[17]Security Technology Group Computer Security Division, National Institute of Standards and Technology, Modes of Operation Validation System for the Triple Data Encryption Algorithm (TMOVS): Requirements and Procedures, NIST Special Publication 800-20, April 2000.
[18]W. Stallings, Cryptography and Network Security, Principles and Practice, Second Edition, Prentice Hall International, Inc., 1999.
[19]M.E. Smid and D.K. Branstad, “Data Encryption Standard: Past and Future,” Proceedings of the IEEE, Volume: 76 Issue: 5, May 1988 Page(s): 550 –559.
[20]P.L. Siu, C.S. Choy, J. Butas and C.F. Chan, “A Low Power Asynchronous DES,” Proceedings of 2001 IEEE International Symposium on Circuits and Systems 2001, Volume: 4, 2001 Page(s): 538 -541 vol. 4.
[21]T. Schaffer, A. Glaser, S. Rao and P. Franzon, “A Flip-Chip Implementation of the Data Encryption Standard (DES),” Proceedings of 1997 IEEE Multi-Chip Module Conference 1997, Page(s): 13 –17.
[22]R.G. Sixel, R.S. Monteiro and M.L. Anido, “A High Level Language Implementation of the Data Encryption Standard and a Bit-Slice Architecture,” Proceedings of the 43rd IEEE Midwest Symposium on Circuits and Systems 2000, Volume: 1, 2000 Page(s): 266 -269 vol.1.
[23]I. Verbauwhede, F. Hoornaert, J. Vandewalle and H.J. De Man, “Security and Performance Optimization of a New DES Data Encryption Chip,” IEEE Journal of Solid-State Circuits, Volume: 23 Issue: 3, June 1988 Page(s): 647 –656.
[24]I. Verbauwhede, F. Hoornaert, J. Vandewalle and H.J. De Man, “ASIC Cryptographical Processor Based on DES,” Proceedings of Euro ASIC '91, 1991 Page(s): 292 –295.
[25]L.Y. Wang, C.S. Laih, H.G. Tsai and N.M. Huang, “On the Hardware Design for DES Cipher in Tamper Resistant Devices Against Differential Fault Analysis,” Proceedings of 2000 IEEE International Symposium on Circuits and Systems 2000, Volume: 2, 2000 Page(s): 697 -700 vol.2.
[26]L. Wu, C. Weaver and T. Austin, “CryptoManiac: A Fast Flexible Architecture for Secure Communication,” Proceedings of 28th Annual International Symposium on Computer Architecture 2001, Page(s): 110 –119.
[27]K. Wong, M. Wark and E. Dawson, “A Single-Chip FPGA Implementation of the Data Encryption Standard (DES) Algorithm”, Proceedings of IEEE Global Telecommunications Conference, Volume: 2, 1998 Page(s): 827 -832 vol.2.