基於karatsuba分解法實現低複雜度的多位元串列GF（2^m）乘法器

Abstract

近年來，由於無線通訊的普遍，資訊安全成為重要的研究議題，密碼系統也是其中重要的一環。本文提出一個新的低複雜度多位元串列GF（2^m）乘法器，利用多位元串列的概念結合Karatsuba乘法器的原理，來降低電路使用的面積複雜度，並且可適用於橢圓曲線密碼學技術。我們所熟知的密碼系統核心運算電路是乘法器，然而密碼系統中乘法器的場非常大，所以設計一個降低空間與時間複雜度的乘法器是非常必要的。本文利用Karatsuba乘法器的原理，配合多位元串列的概念，利用FPGA來實現低複雜度乘法器，本方法僅需要3dm/2個AND閘，4m + n +3dm/2 + m/2 +d-5個XOR閘以及3m-3個暫存器，本文利用Altera FPGA Quartus II軟體環境，模擬四種不同位元數的乘法器，分別為36 × 36，84 × 84，126 × 126以及204 × 204個位元的乘法器，並實現於Cyclone II EP2C70F896C8之實驗平台上。由實驗結果可知，所提出的乘法器之時間複雜度皆小於文獻［13］，［15］以及［19］，並且當乘法器相乘的位元數越多時，本架構可降低的時間×空間複雜度越大。