臺灣博碩士論文加值系統

加密與解密計算至今已經被開發出各式各樣的演算法，針對不同使用上的需求提供不同的計算方式，已經幾乎成為網路傳輸中不可或缺的重要角色。然而，加密與解密的過程是需要龐大的CPU計算時間和資源，對一個支援加密傳輸的web server而言，往往web server本身會花60%至70%的資源在執行加解密的計算，對執行效率來說是很大的瓶頸。本研究探討這限制之最根本的原因，就是加解密過程耗費過多CPU資源，因此提出使用GPU（圖形處理器）來加速這些加解密的計算，以減少CPU的負擔，讓CPU可以更專注於其他web service的服務。
本論文並非是目前為止第一個利用了GPU的計算能力，來加速加解密運算之研究。然而加解密的密碼文件(cipher)種類相當多，我們針對計算量相當龐大的3-DES演算法進行研究，將用來原本該在CPU上之邏輯運算，轉換成可以在GPU上平行處理的演算法。在我們的實作中，隨著檔案大小的增加，我們觀察到在GPU提供了超過5倍目前CPU所能提供之運算能力，並大幅減少CPU所耗損的資源，有效的提供web server更好的服務品質。

Various cryptography algorithms have been developed to date to provide different levels of data security for application domains, such as storage security, personal identification, and secure web browsing. Although these algorithms do a very good job of protecting your privacy, they consume massive amount of resource on the server-side while processing encrypting and decrypting requests from clients. Generally speaking, a web server supporting transport security (TLS/SSL) could spend up to 60%~70% of its computing resource in encrypting and decrypting data and leave 30%~40% for actual client request processing. Therefore in this research, we try to address the performance issue by using GPU (Graphics Processing Unit) to speed up the data encryption and decryption to reduce the computing resource spent on security and ultimately improve the web server throughput.
In this paper, we chose the widely-used 3-DES and implemented it on GPU. In our implementation, we observed the GPU cipher performs 5 times faster than the OpenSSL implementation on CPU. As a result, we show a promising direction for offloading the data encryption and decryption onto GPU.

摘要 i
Abstract ii
Acknowledgement iii
Table of Contents iv
List of Figure vi
List of Tables vii
Chapter 1 Introduction 1
1.1. Preface 1
1.2. Motivation 2
Chapter 2 Background and Related work 3
2.1. GPU (Graphics Processor Unit) introduction 3
2.2. CUDA (Compute Unified Device Architecture) 4
2.3. CUDA memory introduction 7
2.4. Related Work 10
2.4.1. Related Work: AES speed up in CUDA 10
Chapter 3 System Architecture 12
3.1. DES and 3DES Introduction 12
3.1.1. DES Architecture 12
3.1.2. 3-DES Architecture 13
3.2. Implement 3-DES in CUDA 15
3.2.1. Facing problems in CUDA program 15
3.2.2. 3-DES Architecture for CUDA programming 17
3.3. Integrate 3-DES with web server 19
Chapter 4 Experimental Results and Analysis 21
4.1. 3-DES implementation in GPU 21
4.1.1. Move data from CPU to GPU 21
4.1.2. Initial permutation 23
4.1.3. Round function 24
4.2. 3-DES Encode implementation 25
4.3. 3-DES Decode implementation 29
4.4. Configuration 33
4.4.1. Hardware configuration 33
4.4.2. Software Configuration 34
4.5. Evaluation and Analysis 34
Chapter 5 Conclusion and Future works 38
5.1. Conclusion 38
5.2. Future work 39
Bibliography 41

[1] E.Biham and A. Shamir, “ Differential Cryptanalysis of DES-like Cryptosystems.” Journal of Cryptology, Vol.4, pp.3-72, (1911).
[2] National Institute of Standards and Technology (NIST), “FIPS 197: Advanced Encryption Standard (AES)”, 2001.
[3] E.Biham and A.Shamir, “ Differential Cryptanalysis of FEAL and N-Hash, “ Advance in Cryptology – EUROCRYPT’91, Lecture Note in Computer Science, Vol.547, p.1-16, (1991).
[4] E.Biham and A.Shamir, “Differential Cryptanalysis of the full 16-round DES, “ CRYPTO’92 Extended Abstracts, p.12-1-12-5, (1992).
[5] General Purpose Computation Using Graphics Hardware,
http://www.gpgpu.org.
[6] NVidia CUDA , http://developer.NVidia.com/object/CUDA.html.
[7] OpenGL Shading Language Specification, Version 1.20
http://www.opengl.org/registry/doc/GLSLangSpec.Full.1.20.8.pdf
[8] AMD CTM, http://ati.amd.com/companyinfo/researcher/documents.html.
[9] NVIDIA CUDA Programming Guide, Version 0.8.2
http://developer.download.nvidia.com/compute/cuda/0_81/NVIDIA_CUDA_Programming_Guide_0.8.2.pdf

[10] I. Buck, A. Lefohn, P. McCormick, J. Owens, T. Purcell, R. Strodka, “General Purpose Computation on Graphics Hardware”. IEEE Visualization 05, Minneapolis, USA, 2005.
[11] OpenGL Architecture Review Board, M. Woo, J. Neider, T. Davis, D. Shreiner, “The OpenGL Programming Guide: The Official Guide to Learning OpenGL, Version 2”, 5th edition. ISBN 0321335732, Addison-Wesley, New York, 2005.
[12] D. L. Cook, A. D. Keroymytis, “Cryptographics: Exploiting Graphics Cards for Security”, Advancements in Information Security series, Springer, 2006.
[13] Svetlin A. Manavski, CUDA Compatible GPU as an Efficient Hardware Accelerator for AES Cryprography, Springer-Verlag, New York, 2007.
[14] A.Tardy-Corfdir and H.Gilbert, “A Known Plaintext Attack of FEAL-4 and FEAL-6, “ Advances in Cryptology – CRYPTO’91, Lecture Notes in Computer Science, Vol.576, (1991).
[15] M. Matsui and A. Yamagishi, “A New Method for Known Plaintext Attack of FEAL Cipher, “ Advances in Cryptology – EUROCRY’92, Lecture Notes in Computer Science, Vol.658 , (1992).
[16] A. Shamir, “ On the Security of DES, “ Advances in Cryptology –CRYPTO’85, Lecture Notes in Computer Science, (1985).
[17] R.A.Rueppel, “Analysis and Design of stream Cipher, “Springer Verlag, (1986).
[18] Federal Information Processing Standards Publication (FIPS PUB) 46-2, Data Encryption Standard (DES), National Institute of Standards and Technology, Washington, DC, 1993.
[19] M. J. Wiener, “Efficient DES Key Search,” Technical Federal Information Processing Standards Publication (FIPS PUB) 46-2, Data Encryption Standard (DES), National Institute of Standards and Technology, Washington, DC, 1993.
[20] M. J. Wiener, “Efficient DES Key Search,” Technical Report TR-244, School of Computer Science, Carleton University, Ottawa, Canada, May 1994. Presented at the rump session of Crypto’93.
[21] F. Hendessi and M. R. Aref, “A Successful Attack Against the DES,” Information Theory and Application, Third Canadian Workshop Proceedings, 1994, pp. 78-90.
[22] Frank Rubin, “Foiling an Exhaustive Key-Search Attack,” CRYPTOLOGIA 11, No. 2, 102-107 (April 1987).
[23] M. Hellman, “A Cryptanalytic Time-Memory Trade-off,” IEEE Trans. Info. Theory IT-26, No. 4, 401-406 (1980).
[22] E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, New York, 1993.
[24] E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, New York, 1993.
[25] M. Matsui, “The First Experimental Cryptanalysis of the Data Encryption Standard,” Lecture Notes in Computer Science 839, Advances in Cryptology-Crypto ’94 Proceedings, Springer-Verlag, New York, 1994.
[26] D. Coppersmith, “The Data Encryption Standard (DES) and Its Strength Against Attacks,” IBM J. Res. Devebp. 38, NO. 3, 243-250 (1994).
[27] B. S. Kaliski, Jr. and M. J. B. Robshaw, “Multiple Encryption: Weighing Security and Performance,” Dr. Dobb’s Journal 21, No. 1, 123-127 (1996)
[28] J. Daemen, V. Rijmen, “AES Proposal: Rijndael”. Original AES Submission to NIST, 1999.
[29] OpenSSL Open Source Project, http://www.openssl.org.
[30] C. Su, T. Lin, C. Huang, C. Wu, “A High-Throughput Low-Cost AES processor”. IEEE Communications Magazine, vol. 41, no. 12, pp. 86-91, 2003.
[31] J. Wolkerstorfer, E. Oswald, M. Lamberger, “An ASIC Implementation of the AES Sboxes”. RSA Conference 02, San Jose CA, 2002.
[32] A. Hodjat, I. Verbauwhede, “Minimum Area Cost for a 30 to 70 Gbits/s AES Processor”. IEEE Computer Society Annual Symposium on VLSI (ISVLSI 2004), Eerging Trends in VLSI System Design, pp 83-88, 2004.