植基於Karatsuba演算法實現低複雜度多位元串列GF(2^m)乘法器

Low Complexity Digit-Serial Multiplier Over GF(2^m) Using Karatsuba Algorithm

范家禎(Chia-Chen Fan)

指導教授 ： 李宗演

國立臺北科技大學/電資學院/電腦與通訊研究所/碩士(2013年)

https://doi.org/10.6841/NTUT.2013.00761

摘要

近年來，由於無線通訊的普遍，資訊安全成為重要的研究議題，密碼系統也是其中重要的一環。本文提出一個新的低複雜度多位元串列 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]，並且當乘法器相乘的位元數越多時，本架構可降低的時間×空間複雜度越大。

關鍵字

Karatsuba ； 有限場 ； 多位元串列

並列摘要

In recent year, information security and cryptography is important. This work presents a low complexity digit-serial GF(2^m) multiplier, we are using digit-serial of concept to combine the principle of Karatsuba multiplier which can reduce circuit space complexity, also it is suitable for Elliptic Curve Cryptography (ECC) technology. As we know cryptography’s core operand is a multiplier, however, due to the cryptography of multiplier field are big, so it is necessary to reduce the space and time complexity. This work uses Karatsuba multiplier principle to coordinate digit-serial concept to implement a low complexity multiplier by FPGA. The space of proposed method is composed of 3dm/m AND gates, 6m+n+(3dm/2)+(m/2)+d-7 XORs and 3m-3 registers. This work uses Altera FPGA Quartus II to simulate four different multipliers, 36×36, 84×84, 126×126 and 204×204, and implemented on Cyclone II EP2C70F896C8 experimental platform. The experimental results show that the proposed multipliers have lower time complexity than [13], [15] and [19]. The proposed architecture can reduce the time × space complexity decreasing when the bit-sign of multiplier is increasing.

並列關鍵字

Karatsuba ； Finite field ； Digit-serial

參考文獻

[1] V. S. Miller, “Use of elliptic curves in cryptography,” Lecture notes in computer, pp. 417-429, 1986.

[2] N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, vol. 48, No. 177, pp. 203-209, 1987.

[3] C. Y. Lee, “Low-complexity bit-parallel systolic multipliers over GF(2m),” IEEE International Conference on Systems, vol. 2, pp. 1160-1165, Oct. 2006.

[4] C. Y. Lee, C. W. Chiou, J. M. Lin, and C. C. Hang, “Scalable and systolic Montgomery multiplier over GF(2m) generated by trinomials,” IET Circuits, Devices & System, vol.1, No. 6, pp. 477-484, Dec. 2007.

[5] S. T. J. Fenn, M. Benaissa, and O. Taylor, “Dual basis systolic multipliers for GF(2m),” IEEE Computers and Digital Techniques, vol. 144, No. 1, pp. 43-46, Jan. 1997.