請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/70765
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 鄭振牟 | |
dc.contributor.author | Yu-Jia Chen | en |
dc.contributor.author | 陳昱嘉 | zh_TW |
dc.date.accessioned | 2021-06-17T04:37:41Z | - |
dc.date.available | 2020-08-13 | |
dc.date.copyright | 2018-08-13 | |
dc.date.issued | 2018 | |
dc.date.submitted | 2018-08-08 | |
dc.identifier.citation | [1] W.-D. Li, M.-S. Chen, P.-C. Kuo, C.-M. Cheng, and B.-Y. Yang, “Frobeniusadditive fast fourier transform,” arXiv preprint arXiv:1802.03932, 2018.
[2] M.-S. Chen, C.-M. Cheng, P.-C. Kuo, W.-D. Li, and B.-Y. Yang, “Faster multiplication for long binary polynomials,” arXiv preprint arXiv:1708.09746, 2017. [3] G. Zhou, H. Michalik, and L. Hinsenkamp, “Improving throughput of aes-gcm with pipelined karatsuba multipliers on fpgas,” in International Workshop on Applied Reconfigurable Computing. Springer, 2009, pp. 193–203. [4] M. J. Dworkin, “Sp 800-38d. recommendation for block cipher modes of operation: Galois/counter mode (gcm) and gmac,” 2007. [5] N. F. Pub, “197: Advanced encryption standard (aes),” Federal information processing standards publication, vol. 197, no. 441, p. 0311, 2001. [6] P.Gallagher, “Federal information processing standards publication digital signature standard (dss),” Fips pub 186-3, 2009. [7] M. Qu, “Sec 2: Recommended elliptic curve domain parameters,” Certicom Res., Mississauga, ON, Canada, Tech. Rep. SEC2-Ver-0.6, 1999. [8] D. J. Bernstein, “Batch binary edwards,” in Advances in cryptology-CRYPTO 2009. Springer, 2009, pp. 317–336. [9] J. Van Der Hoeven, “The truncated fourier transform and applications,” in Proceedings of the 2004 international symposium on Symbolic and algebraic computation. ACM, 2004, pp. 290–296. [10] J. van der Hoeven, Notes on the truncated Fourier transform. Université de Paris-Sud. Département de Mathématique, 2005. [11] T. Mateer, “Fast fourier transform algorithms with applications,” Ph.D. dissertation, Clemson University, 2008. [12] L. Henzen and W. Fichtner, “Fpga parallel-pipelined aes-gcm core for 100g ethernet applications,” in ESSCIRC, 2010 Proceedings of the. IEEE, 2010, pp. 202–205. [13] K. M. Abdellatif, R. Chotin-Avot, and H. Mehrez, “Fpga-based high performance aes-gcm using efficient karatsuba ofman algorithm,” in International Symposium on Applied Reconfigurable Computing. Springer, 2014, pp. 13–24. [14] B. Buhrow, K. Fritz, B. Gilbert, and E. Daniel, “A highly parallel aes-gcm core for authenticated encryption of 400 gb/s network protocols,” in ReConFigurable Computing and FPGAs (ReConFig), 2015 International Conference on. IEEE, 2015, pp. 1–7. [15] A. Satoh, T. Sugawara, and T. Aoki, “High-speed pipelined hardware architecture for galois counter mode,” in International Conference on Information Security. Springer, 2007, pp. 118–129. [16] A. Satoh, T. Sugawara, and T. Aoki, “High-performance hardware architectures for galois counter mode,” IEEE Transactions on Computers, vol. 58, no. 7, pp. 917–930, 2009. [17] M. Mozaffari-Kermani and A. Reyhani-Masoleh, “Efficient and high-performance parallel hardware architectures for the aes-gcm,” IEEE Transactions on Computers, vol. 61, no. 8, pp. 1165–1178, 2012. [18] S.-J. Lin, W.-H. Chung, and Y. S. Han, “Novel polynomial basis and its application to reed-solomon erasure codes,” in Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on. IEEE, 2014, pp. 316–325. [19] D. G. Cantor, “On arithmetical algorithms over finite fields,” Journal of Combinatorial Theory, Series A, vol. 50, no. 2, pp. 285–300, 1989. [20] S. Gao and T. Mateer, “Additive fast fourier transforms over finite fields,” IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6265–6272, 2010. [21] Y. Wang and X. Zhu, “A fast algorithm for the fourier transform over finite fields and its vlsi implementation,” IEEE Journal on Selected Areas in Communications, vol. 6, no. 3, pp. 572–577, 1988. [22] J. Von zur Gathen and J. Gerhard, “Arithmetic and factorization of polynomial over f 2,” in Proceedings of the 1996 international symposium on Symbolic and algebraic computation. ACM, 1996, pp. 1–9. [23] M.-S. Chen, Y.-J. Chen, Y.-C. Hsu, W.-D. Li, B.-Y. Peng, B.-Y. Yang, and C.-M. Cheng, “Faster additive fft and hardware multipliers in composite binary fields,” 2017, unpublished. [24] J. Van Der Hoeven and R. Larrieu, “The frobenius fft,” 2017. [25] D.McGrew and J.Viega, “The galois/counter mode of operation (gcm),” submission to NIST Modes of Operation Process, vol. 20, 2004. [26] Virtex-4 Family Overview, v3.1 ed., Xilinx, August 2010. [27] Virtex-5 Family Overview, v5.1 ed., Xilinx, August 2015. [28] Virtex-6 Family Overview, v2.5 ed., Xilinx, August 2015. [29] 7 Series FPGAs Data Sheet: Overview, v2.6 ed., Xilinx, February 2018. [30] T. H. Cormen, Introduction to algorithms. MIT press, 2009. [31] E. Homsirikamol, F. Farahmand, W. Diehl, and K. Gaj, “Benchmarking of round 3 caesar candidates in hardware: Methodology, designs & results,” 2017. [32] (2017) Athena database of results: Rankings view. [Online]. Available: https: //cryptography.gmu.edu/athenadb/fpga_auth_cipher/rankings_view [33] (2017) Vhdl/verilog code of round 3 caesar candidates: Summary ii. [Online]. Available: https://cryptography.gmu.edu/athena/CAESAR_HW_Summary_2.html | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/70765 | - |
dc.description.abstract | 李文鼎等人在 ISSAC 2018 中提出一個方法在加法快速傅立葉轉換中使用 Frobenius 映射,並稱之為 Frobenius 加法快速傅立葉轉換。這是第一次在低次方的多項式乘法中,比較位元運算次數,用快速傅立葉轉換加速會優於用 Karatsuba 快速相乘算法加速。到目前為止,還沒有任何關於 Frobenius 加法快速傅立葉轉換的硬體實作。我們提出一個方法用來設計基於 Frobenius 加法快速傅立葉轉換的管線化體乘法器,接著使用這個乘法器來設計一個高吞吐量的 AES-GCM,並實作於現場可程式化邏輯閘陣列中。最後拿我們的實驗結果和之前的 AES-GCM 的現場可程式化邏輯閘陣列實作做比較,其中,之前 AES-GCM 的實作所使用的體乘法器是基於 Karatsuba 快速相乘算法來設計的。 | zh_TW |
dc.description.abstract | In ISSAC 2018, Li et al. presented Frobenius additive fast Fourier transform (FAFFT), which generalizes Frobenius FFT to additive FFT. To the best of their knowledge, it was the first time that FFT-based binary polynomial multiplication outperforms KOA-based binary polynomial multiplication at such a low degree-bound 231 in respect of the number of bit operations. Up to now, there is no hardware application of the Frobenius additive fast Fourier transform. In this work, we design a pipelined finite field multiplier (FFM) based on FAFFT, and we use it to present a high throughput AES-GCM hardware implementation on FPGAs. Then we compare our implementations with previous implementations with FFM based on the Karatsuba-Ofman algorithm (KOA), which is a method most often used to speed up the polynomial multiplication. | en |
dc.description.provenance | Made available in DSpace on 2021-06-17T04:37:41Z (GMT). No. of bitstreams: 1 ntu-107-R05921031-1.pdf: 2440998 bytes, checksum: 93eb667c0942a8b6047c3468d52aa70a (MD5) Previous issue date: 2018 | en |
dc.description.tableofcontents | 1 Introduction 1
1.1 Motivation 1 1.2 Our Contributions 2 1.3 Chapters Introduction 3 2 Preliminaries 4 2.1 Finite Field 4 2.2 Subspace Polynomial 5 2.3 Problem Statement 6 3 Additive Fast Fourier Transform Algorithms 7 3.1 Cantor and Von zur Gathen-Gerhard Additive FFT 8 3.1.1 Cantor Additive FFT 9 3.2 Gao-Mateer Additive FFT 10 3.2.1 Taylor Expansion at xt−x 10 3.2.2 Additive FFT of Length n = 2m (Arbitrary m) 12 3.2.3 Additive FFT of Length n = 2m (m a Power of 2) 15 3.3 Lin-Chung-Han Additive FFT 18 3.3.1 LCH Polynomial Basis 18 3.3.2 Additive FFT 20 3.3.3 Special Case with Cantor Basis 24 3.4 Concluding Remarks 26 4 Frobenius Additive Fast Fourier Transform Algorithms 27 4.1 Frobenius Additive FFT 27 4.2 Inverse Frobenius Additive FFT 31 5 Application to AES-GCM 33 5.1 GCM Algorithm 33 5.2 Pipelined FFM Based on Frobenius Additive FFT 34 5.2.1 Adding Pipeline Stages Decision Algorithm 36 5.2.2 Pipelined FFMs Based on Frobenius Additive FFT 42 5.2.3 Reduction in LCH Polynomial Basis 47 5.2.4 Experimental Results of Pipelined FFMs Based on FAFFT 50 5.3 GHASH Calculation and Precomputation of Hk 53 5.3.1 Reduction Factor 57 5.3.2 Reduce One Module of Frobenius Additive FFT 58 5.3.3 GHASH Calculation in LCH Polynomial Basis 59 5.4 High Throughput AES-GCM Architectures 61 5.5 Experimental Results 64 6 Conclusion 67 References 68 Appendix A Experimental Results of Pipelined FFMs on Virtex-4 71 Appendix B Experimental Results of Pipelined FFMs on Virtex-6 75 | |
dc.language.iso | zh-TW | |
dc.title | Frobenius 加法快速傅立葉轉換以及其 AES-GCM 的應用 | zh_TW |
dc.title | Frobenius Additive FFT and Its Application to AES-GCM | en |
dc.type | Thesis | |
dc.date.schoolyear | 106-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 陳君明,楊柏因,陳君朋,洪維志,謝致仁 | |
dc.subject.keyword | 加法快速傅立葉轉換,Frobenius 加法快速傅立葉轉換,基於 Frobenius 加法快速傅立葉轉換的管線化體乘法器,AES-GCM,現場可程式化邏輯閘陣列, | zh_TW |
dc.subject.keyword | Additive FFT,Frobenius Additive FFT,Pipelined FAFFT-Based Multiplier,AES-GCM,FPGAs, | en |
dc.relation.page | 78 | |
dc.identifier.doi | 10.6342/NTU201802679 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2018-08-08 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-107-1.pdf 目前未授權公開取用 | 2.38 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。