Frobenius 加法快速傅立葉轉換以及其 AES-GCM 的應用

Frobenius Additive FFT and Its Application to AES-GCM

陳昱嘉(Yu-Jia Chen)

指導教授 ： 鄭振牟

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201802679

摘要

李文鼎等人在 ISSAC 2018 中提出一個方法在加法快速傅立葉轉換中使用 Frobenius 映射,並稱之為 Frobenius 加法快速傅立葉轉換。這是第一次在低次方的多項式乘法中,比較位元運算次數,用快速傅立葉轉換加速會優於用 Karatsuba 快速相乘算法加速。到目前為止,還沒有任何關於 Frobenius 加法快速傅立葉轉換的硬體實作。我們提出一個方法用來設計基於 Frobenius 加法快速傅立葉轉換的管線化體乘法器,接著使用這個乘法器來設計一個高吞吐量的 AES-GCM,並實作於現場可程式化邏輯閘陣列中。最後拿我們的實驗結果和之前的 AES-GCM 的現場可程式化邏輯閘陣列實作做比較,其中,之前 AES-GCM 的實作所使用的體乘法器是基於 Karatsuba 快速相乘算法來設計的。

關鍵字

加法快速傅立葉轉換 ； Frobenius 加法快速傅立葉轉換 ； 基於 Frobenius 加法快速傅立葉轉換的管線化體乘法器 ； AES-GCM ； 現場可程式化邏輯閘陣列

並列摘要

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.

並列關鍵字

Additive FFT ； Frobenius Additive FFT ； Pipelined FAFFT-Based Multiplier ； AES-GCM ； FPGAs

參考文獻

[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.