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

李秋瑩；范家禎；葉為勳

有限場 ； 多位元串列 ； Karatsuba

資訊安全通訊

20卷2期（2014 / 04 / 01）

119 - 136

繁體中文

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

1. Fan, H.,Hasan, M. A.(2007).A new approach to subquadratic space complexity parallel multipliers for extended binary fields.IEEE Trans. on Computers,56(2),224-233.
2. Fenn, S. T. J.,Benaissa, M.,Taylor, O.(1997).Dual basis systolic multipliers for GF(2m).IEEE Computers and Digital Techniques,144(1),43-46.
3. Ge, Zhengzheng,Shou, Guochu,Hu, Yihong,Guo, Zhigang(2011).Design of Low Complexity GF(2m) multiplier based on karatsuba algorithm.IEEE 13th International Conference on Communication Technology(ICCT)
4. Grabbe, C.,Bednara, M.,Teich, J.,von zur Gathen, J.,Shokrollahi, J.(2003).FPGA designs of parallel high performance GF(2333) multipliers.Proc. Int. Symp. Circuits Syst. (ISCAS)
5. Hariri, A.,Reyhani-Masoleh, A.(2008).Digit-serial structures for the shifted polynomial basis multiplication over binary extension fields.Lecture notes in computer,5130,103-116.
6. Karatsuba, A.,Yu, Ofman(1963).Multiplication of multi-digit mumbers on automata.Soviet Physics Doklady,7,595-596.
7. Koblitz, N.(1987).Elliptic curve cryptosystems.Mathematics of Computation,48(177),203-209.
8. Kumar, S.,Wollinger, T.,Paar, C.(2006).Optimum digit serial GF(2m) multipliers for curve-based cryptography.IEEE Trans. on Computers,55(10),1306-1311.
9. Lee, C. Y.(2006).Low-complexity bit-parallel systolic multipliers over GF(2m).IEEE International Conference on Systems
10. Lee, C. Y.,Chiou, C. W.(2012).Scalable gaussian normal basis multipliers over GF(2m) using hankel matrix-Vector representation.J. Signal Processing Systems,69(2),197-211.
11. Lee, C. Y.,Chiou, C. W.,Lin, J. M.,Hang, C. C.(2007).Scalable and systolic Montgomery multiplier over GF(2m) generated by trinomials.IET Circuits, Devices & System,1(6),477-484.
12. Lee, C. Y.,Lu, E. H.,Lee, J. Y.(2001).Bit-parallel systolic multipliers for GF(2m) fields defined by all-one and equally spaced polynomials.IEEE Trans. on Computers,50(5),385-393.
13. Meher, P. K.(2009).On efficient implementation of accumulation in finite field over GF(2m) and its applications.IEEE Trans. On Very Large Scale Integration (VLSI) Systems,17(4),541-550.
14. Meher, Pramod Kumar(2009).Systolic and Non-Systolic Scalable Modular Designs of Finite Field Mulitipliers for Reed-Solomon Codec.IEEE Transactions on Very Large Scale Integration (VLSI) Systems
15. Miller, V. S.(1986).Use of elliptic curves in cryptography.Lecture notes in computer,417-429.
16. Morales-Sandoval, M.,Feregrino-Uribe, C.,Kitsos, P.(2011).Bit-serial and digit-serial GF(2m) Montgomery multipliers using linear feedback shift registers.Proc. of Computers & Digital Techniques (IET)
17. Selimis, G. N.,Fournaris, A. P.,Michail, H. E.,Koufopavlou, O.(2009).Improved throughput bit-serial multiplier for GF(2m) fields.Integration, Proc. of the VLSI journal,42,217-226.
18. Talapatra, S.,Rahaman, H.,Mathew, J.(2010).Low complexity digit serial systolic Montgomery multipliers for special class of GF(2m).IEEE Trans. on Very Large Scale Integr. (VLSI) Syst.,18(5),487-852.
19. Xie, J.,Meher, P. K.,He, J.(2012).Low-complexity multiplier for GF(2m) based on all-one polynomials.IEEE Trans. on Very Large Scale Integr. (VLSI) Syst.,99,1-5.