臺灣博碩士論文加值系統

在本篇論文裡，我們實現三種不同位元數之先進加密標準(Advanced Encryption Standard，簡稱AES)演算法，包：32 位元、 16 位元及8 位元等三種不同資料路徑寬度的硬體設計。而在AES演算法裡，共有三種流程：加密流程、直接解密流程及改良式解密流程等。在結合加密與解密流程時，一般有兩種方式：加密與直接解密流程結合、加密與改良式解密流程結合。因此，當實現32位元資料路徑寬度的AES演算法時，便有兩種不同的實現方式，而包含16位元及8位元也是。在本論文裡，我們將實現上述所有的架構且與其他文獻所提之結果做比較。
在很多文獻內提到，如何改良AES所需要的電路面積或是運算速度，透過利用不同的架構設計，針對AES部分的轉換函數做化簡以達到節省面積或是利用管線化技術提高其運算能力，而本論文的重點則是著重在如何在不大幅降低其運算能力，可以符合一般嵌入式系統的應用，且可以進一步節省AES的電路面積，使效能與電路面積予以平衡。
在我們的設計裡，對AES的電路面積有兩個改良的方式：第一，是利用架構上的設計，在不犧牲運算的回合數(cycle)下，設計出相關的轉換函數架構；第二，是利用一個共同子運算式化簡(Common Sub-expression Elimination,CSE)演算法來精簡轉換函數內的AND及XOR邏輯閘數目，以達到電路面積更精簡。三種不同位元的架構上和先前的文獻作比較，32位元、16位元及8位元架構確實有達到一個低成本考量的設計，且我們提出的8位元架構設計是以最少運算的cycle數為前提來做低成本設計，其面積和效能比，皆比其他現有的設計更好。

In this dissertation, we realize the Advanced Encryption Standard (AES) algorithm with three kinds of data paths including 32, 16, and 8 bits. There are three kinds of processes in AES algorithm: encryption, direct decryption, and modified decryption. While combining the encryption and decryption processes, two common realization methods are used including the combination of encryption and direct decryption, and the combination of encryption and modified decryption. Therefore, we have two different combination methods in the realization of the 32- or 16- or 8-bit AES designs. In this dissertation, we realize all of the AES architectures mentioned above and compare them with previous designs.
In many previous researches, they discuss how to improve the required circuit area or operation speed of AES design. They also propose different architectures to reduce the area cost of the transformation functions or utilize pipeline technologies to enhance the AES performance with additional area cost. Our dissertation focus on how to reduce the area cost in the AES realization without losing more operation capabilities and how to balance these two design factors: area and performance while applying our designs to embedded systems with restricted resource.
We propose two major methods to improve the area cost in the AES realizations. Firstly, we design the novel architectures in the realization of transformation functions without sacrificing the operation cycles of AES algorithm. Secondly, we design a common sub-expression elimination (CSE) method to further reduce the numbers of XOR and AND gates in the expressions of transformations by extracting more common factors. We observe that our designs have better performance in the ratio of throughput and area compared with previous designs, especially in 8-bit AES design.

中文摘要 1
英文摘要 2
致謝 3
目錄 4
表目錄 6
圖目錄 8
符號說明 11
一. 緒論 12
1.1 動機與目的 12
1.2 研究工具介紹 15
1.3 論文架構 15
二. 文獻探討與回顧 16
2.1 先進加密演算法及研究方向 17
2.2 相關文獻探討 21
三. AES整體設計架構 32
3.1 32位元架構設計 33
3.1.1 加密和直接解密 33
3.1.2 加密和改良式解密 42
3.2 16位元架構設計 46
3.2.1 加密和直接解密 46
3.2.2 加密和改良式解密 52
3.3 8位元架構設計 55
3.3.1 加密和直接解密 55
3.3.2 加密和改良式解密 62
3.4 共同子運算式消減演算法(Common Sub-Expression Elimination) 65四.合成數據結果 69
4.1 32位元加密和直接解密數據 69
4.2 32位元加密和改良式解密數據 72
4.3 16位元加密和直接解密數據 74
4.4 16位元加密和改良式解密數據 76
4.5 8位元加密和直接解密數據 79
4.6 8位元加密和改良式解密數據 81
五. FPGA驗證、晶片實作與比較 84
5.1 FPGA驗證與比較 84
5.2 晶片實作與比較 90
六. 結論與未來展望 100
七. 參考文獻 102
附錄一 107

[1].J. Daemen and V. Rijmen, “AES Proposal: Rijndael”, version 2, 1999. Available at http://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael.pdf.
[2].V. Rijnmen, “Efficient Implementation of the Rijndael S-box,” pp. 1-3, 2000. Available at http://www.esat.kuleuven.ac.be/~rijmen/rijndael/sbox.pdf.
[3].V. Fischer, “Realization of the Round 2 Candidates Using Altera FPGA,” The Third AES Conference (AES3), New York, April 2000. Available at http://csrc.nist.gov/CryptoToolkit/aes/round2/conf3/papers/24-vfisher.pdf.
[4].A. Rudra, P. K. Dubey, C. S. Jutla, V. Kumar, J. R. Rao, and P. Rohatgi, “Efficient Implementation of Rijndael Encryption with Composite Field Arithmetic,” Proceedings of Cryptographic Hardware and Embedded Systems (CHES 2001), pp. 171-184, May 2001.
[5].H. Kuo and I. Verbauwhede, “Architectural Optimization for a 1.82 Gbits/sec VLSI Implementation of the AES Rijndael Algorithm,” Proceedings of Cryptographic Hardware and Embedded Systems (CHES 2001), pp. 51-64, May 2001.
[6].J. Wolkerstorfer, E. Oswald, and M. Lamberger, “An ASIC Implementation of the AES MixColumn-operation,” Proceedings of the Austrochip 2001, pp.129-132, Oct. 2001.
[7].“Advanced Encryption Standard (AES)”, FIPS Publication 197, Nov. 26, 2001. Available at http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf.
[8].A. Satoh, S. Morioka, K. Takano, and S. Munetoh, “A Compact Rijndael Hardware Architecture with S-Box Optimization,” Advanced in Cryptography- ASIACRYPT 2001, pp. 239-254, Dec. 2001.
[9].Morris Dworkin, “Recommendation for Block Cipher Modes of Operation: Methods and Techniques,” NIST Special Publication 800-38A, Dec. 2001. Available at http://csrc.nist.gov/CryptoToolkit/modes/800-38_Series_Publications/SP800-38A.pdf.
[10].J. Wolkerstorfer, E. Oswald, and M. Lamberger, “An ASIC Implementation of the AES SBoxes,” Proceedings of the Cryptographer’s Track at the RSA Conference 2002 (CT-RSA 2002), pp. 67-78, Feb. 2002.
[11].C. Lu and S. Y. Tseng, “Integrated Design of AES (Advanced Encryption Standard) Encrypter and Decrypter,” Proceedings of Application-Specific Systems, Architectures and Processors, pp. 277-285, July 2002.
[12].S. Helal, “Standards for service discovery and delivery,” IEEE Pervasive Computing, Vol 1, No. 3, pp. 95-100, July 2002.
[13].S. Morioka, and A. Satoh, “An Optimized S-Box Circuit Architecture for Low Power AES Design,” Cryptographic Hardware and Embedded Systems (CHES 2002), pp. 172-186, Aug. 2002.
[14].X. Zhang and K. K. Parhi, “Implementation Approaches for the Advanced Encryption Standard Algorithm,” IEEE Circuits and Systems Magazine, Vol. 2, pp. 24-46, Fourth Quarter 2002.
[15].N. Sklavos and O. Koufopavlou, “Architecture and VLSI Implementation of the AES-Proposal Rijndael,” IEEE Transactions on Computers, Vol. 51, pp. 1454-1459, Dec. 2002.
[16].F. Rodriguez-Henriquez, N. A. Saqib, and A. Diaz-Perez, “4.2Gbit/s single-chip FPGA implementation of AES algorithm,” Electronics Letters, Vol. 39, pp. 1115-1116, July 2003.
[17].A. Satoh, and S. Morioka, “Unified Hardware Architecture for 128-Bit Block Ciphers AES and Camellia,” Cryptographic Hardware and Embedded Systems (CHES 2003), pp. 304-318, Sept. 2003.
[18].R. W. Ward and T. C. A. Molteno, “Efficient Hardware Calculation of Inverses in GF(28),” Proceedings of Electronics New Zealand Conference 2003 (ENZCon 2003), Sec. 7.4, Sept. 2003.
[19].P. Su, T. F. Lin, C. T. Huang, C. W. Wu, “A High-Throughput Low-Cost AES Processor,” IEEE Communications Magazine, Vol. 41, pp. 86-91, Dec. 2003.
[20].S. Chantarawong, P. Noo-intara, and S. Choomchuay, “An Architecture for S-Box Computation in the AES,” Proceedings of the 4th Information and Computer Engineering Postgraduate Workshop 2004 (ICEP 2004), pp. 157-162, Jan. 2004.
[21].F. K. Gurkaynak, D. Gasser, F. Hug, and H. Kaeslin, “A 2 Gb/s Balanced AES Crypto-Chip Implementation,” Proceedings of the 14th ACM Great Lakes Symposium on VLSI (GLSVLSI’04), pp. 39-44, April 2004.
[22].X. Zhang, and K. K. Parhi, “High-Speed VLSI Architectures for AES Algorithm,” IEEE Transactions on Very Large Scale Integration Systems (VLSI), Vol. 12, pp. 957-967, Sept. 2004.
[23].S. F. Hsiao, M. C. Chen, and C. S. Tu, “Memory-Free Low-Cost Designs of Advanced Encryption Standard Using Common Subexpression Elimination for Subfunctions in Transformations,” IEEE Transactions on Circuits and Systems-I: Regular Papers, Vol. 53, No. 3, pp. 615-626, March 2006.
[24].S. Morioka, and A. Satoh, “An Optimized S-box Circuit Architecture for Low Power AES Design,” Cryptographic Hardware and Embedded Systems (CHES 2002), LNCS 2523, pp.172-186, 2003.
[25].T.-F. Lin, C.-P. Su, C.-T. Huang, and C.-W. Wu, “A high-throughput low-cost AES cipher chip,” Proceedings of 3rd IEEE Asia-Pacific Conference on ASIC, pp. 85-88, Aug. 2002.
[26].M. H. Jing, Z. H. Chen, J. H. Chen, and Y. H. Chen, “Reconfigurable System for High-Speed and Diversified AES Using FPGA,” Microprocessors and Microsystems , vol.31, no.2, pp.94-102, March 2007.
[27].Ming-Haw Jing, Jian-Hong Chen, and Zih-Heng Chen, “Diversified Mixcolumn Transformation of AES,” Sixth International Conferences on Information, Communications and Signal Processing, Singapore, Dec. 2007.
[28].Chi-Wu Huang, Chi-Jeng Chang, Mao-Yuan Lin, and Hung-Yun Tai, “The FPGA Implementation of 128-bits AES AlgorithmBased on Four 32-bits Parallel Operation,” The First International Symposium on Data, Privacy, and E-Commerce (ISDPE 2007), pp. 462-464, 2007.
[29].Chi-Jeng Chang, Chi-Wu Huang, Hung-Yun Tai, and Mao-Yuan Lin, “8-bit AES Implementation in FPGA by Multiplexing 32-bit AES Operation,” The First International Symposium on Data, Privacy, and E-Commerce (ISDPE 2007), pp. 505-507, 2007.
[30].Liang-Bi Chen, Ching-Chi Hu, Yen-Ling Chen, Chi-Wei Chu, and Ing-Jer Huang, “The AES Design Space Exploration with a Soft IP Generator,” Proceedings of the 2007 IEEE International Conference on Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP''07) Kaohsiung, Taiwan, Vol.2, pp.385-388, Nov. 2007.
[31].Chi-Feng Lu, Yan-Shun Kao, Hsia-Ling Chiang, and Chung-Huang Yang, “Fast implementation of AES cryptographic algorithms in smart cards,” Proceedings of IEEE Annual International Carnahan Conference on Security Technology, pp. 573-579, October 2003.
[32].Hua Li and Jianzhou Li, “A New Compact Architecture for AES with Optimized ShiftRows Operation,” Proceedings of IEEE International Symposium on Circuit and System (ISCAS 2007), pp. 1851-1854, May 2007.
[33].C. Y. Li, C. F. Chien, and T. Y. Chang, “High Speed and Low Cost Implementations in Mix-Column/InvMix-Column,” Proceedings of VLSI/CAD Symposium, pp. 620-623, Hualian Taiwan, Aug. 2007.
[34].C. Y. Li, C. F. Chien, J. H. Hong, and T. Y. Chang, “An Efficient Area-Delay Product Design for MixColumns/InvMixColumns in AES,” Proceedings of IEEE VLSI Symposium (ISVLSI’08), pp.503-506, April 2008.
[35].L. Li, J. Han, X. Zeng, and J. Zhao, “A Full-custom Design of AES SubByte Module with Signal Independent Power Consumption,” Proceedings of 2008 IEEE International Symposium on Circuits and Systems (ISCAS 2008), pp. 3302-3305, May 2008.
[36].S. Y. Lin, and C. T. Huang, “A High-Throughput Low-Power AES Cipher for Network Applications,” Proceedings of 2007 Asia and South Pacific Design Automation Conference (ASP-DAC 2007), pp. 595-600, Jan. 2007.
[37].Z. Liu, Y. Zeng, X. Zou, and J. Lei, “A Low-power and Compact AES S-box IP in 0.25 um CMOS for Wireless Sensor Network,” Proceedings of the 2007 IEEE International Conference on Mechatronics and Automation, pp. 723-728, Aug. 2007
[38].M. A. El-Fotouh and K. Diepold, “A New Narrow Block Mode of Operations for Disk Encryption,” Proceedings of Fourth International Information Assurance and Security Conference (ISIAS’08), pp. 126-131, Sept. 2008.
[39].M. Liberatori, F. Otero, J. C. Bonadero, and J. Castineira, “AES-128 Cipher. High Speed, Low Cost FPGA Implementation,” Proceedings of 2007 3rd Southern Programmable Logic, SPL ''07, pp. 195-198, Feb. 2007.
[40].C. W. Huang, C. J. Chang, M. Y. Lin, and H. Y. Tai, “Compact FPGA implementation of 32-bits AES algorithm using Block RAM,” Proceedings of 2007 IEEE Region 10 Conference (TENCON 2007), pp. 1-4, Oct. 2007.
[41].J. H. Chen; S. J. Huang, W. C., Y. K. Lu; M. D. Shieh, “Exploration of Low-Cost Configurable S-Box Designs for AES Applications,” Proceedings of 2008 International Conference on Embedded Software and Systems (ICESS’08), pp. 422-428, July 2008.
[42].R. R. Rachh, and P. V. Ananda Mohan, “Implementation of AES S-Boxes using combinational logic,” Proceedings of 2008 IEEE International Symposium on Circuits and Systems (ISCAS 2008), pp. 3294-3297, May 2008.
[43].A. Ramachandran, Z. Zhou, and D. Huan, “Computing Cryptographic Algorithms in Portable and Embedded Devices,” Proceedings of 2007 IEEE International Conference on Portable Information Devices (PORTABLE07), pp. 1-7, May 2007.
[44].M. Alam, S. Ghosh, D. RoyChowdhury, I. Sengupta, “Single Chip Encryptor/Decryptor Core Implementation of AES Algorithm,” Proceedings of 21st International Conference on VLSI Design (VLSID 2208), pp. 693-698, Jan. 2008.
[45].M. Feldhofer, and J. Wolkerstorfer, “Strong Crypto for RFID Tags - A Comparison of Low-Power Hardware Implementations,” Proceedings of 2007 IEEE International Symposium on Circuits and Systems (ISCAS 2007), pp. 1839-1842, May 2007.
[46].Z. Liu, Y. Zeng, Y. Han, and Y. Chen, “A High-Security and Low-Power AES S-Box Full-Custom Design for Wireless Sensor Network,” Proceedings of 2007 International Conference on Wireless Communications, Networking and Mobile Computing (WiCom 2007), pp. 2499-2502, Sept. 2007.
[47].Z. Brahimi, H. Bessalah, A. Tarabet, M. K. Kholladi, “A new selective encryption technique of JPEG2000 codestream for medical images transmission,” Proceedings of 2008 IEEE Internal Multi-Conference on Systems, Signals and Devices (SSD 2008), pp. 1-4, July 2008.
[48].S. Mangard, M. Aigner, and S. Dominikus, “A highly regular and scalable AES hardware architecture,” IEEE Transactions on Computers, Vol. 52, pp. 483-491, April 2003.
[49].X. Zhang,and K. K. Parhi, ”On the Optimum Constructions of Composite Field for the AES Algorithm,”IEEE Transactions On Circuits and Systems II Express Briefs, Vol.53, No.10, pp. 1153-1157, Oct. 2006.
[50].M. H. Jing, J. H. Chen, and Z. H. Chen, ”Diversified MixColumns Transformation of AES, ”Information, Communications & Signal Processing, 2007 6th International Conference on. pp.1-3, Dec. 2007.
[51].C. Paar, ”Efficient VLSI architecture for bit-parallel computations in Galois field, ”Ph.D. dissertation, Institute for Experimental Mathemetics, University of Essen, Germany, 1994.
[52].Chang C. J., Huang C. W., Chen Y. C., Hsieh C. C., Chang K. H., “High Throughput 32-bit AES Implementation in FPGA”, ACPCAS, 2008.
[53].Jamal H., Farhan S. M., Khan S. A., “Low Power Area Efficient High Data Rate 16-bit ABS Crypto Processor”, Microelectronics, 2006. ICM ''06. International Conference on. pp.186-189, Dec. 2006.
[54].Jeon Y. S., Nam T. Y., and Lee D. H., “Low-cost Design of AES Using a Compact 8-bit Architecture”, JISE, 2008.
[55].M. Feldhofer, J. Wolkerstorfer and V. Rijmen, “AES implementation on a grain of sand”, IEE Proc. Information Security, Vol. 1, pp 13-20, 2005.
[56].J-P. Kaps and B. Sunar, “Energy Comparison of AES and SHA-l for Ubiquitous Computing”, in proc. Embedded And Ubiquitous Computing (EUC06), Seoul, Korea, pp. 372-381, 1-4, Aug. 2006.
[57].N. Pramstaller, S. Mangard, S. Dominikus, and J. Wolkerstorfer, “Efficient AES implementations on ASICs and FPGAs”, in proc. 4th conf. on the Advanced Encryption Standard (AES 2004), pages 98-112, Bonn, Germany, May 10-12, 2005.
[58].Pawel Chodowiec and Kris Gaj, “Very Compact FPGA Implementation of the AES algorithm”, CHES 2003.
[59].G. Rouvroy, F.-X. Standaert, J.-J. Quisquater and J.-D. Legat, “Compact and efficient encryption/decryption module for FPGA implementation of the AES Rijndael very well suited for small embedded applications”, Information Technology Coding and Computing, 2004.
[60].Tim Good, Mohammed Benaissa, “Very small FPGA application-specific instruction processor for AES”, IEEE Trans. Circuit and System, vol. 53, no. 7, 2006.
[61].朱其偉，黃英哲，2005，應用進階加密標準之矽智產產生器進行設計空間隻探討，國立中山大學資訊工程學系碩士論文。
[62].陳銘志，蕭勝夫，2005，使用有效率之共同子表示式消去法之低成本先進加密標準演算法設計，國立中山大學資訊工程學系博士論文。