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

Abstract

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

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.