橢圓曲線密碼系統之低成本管線化位元－並列高斯正規基底乘法器

Low-Cost Bit-Parallel Gaussian Normal Basis Multiplier with Pipeline Structure for Elliptic Curve Cryptosystem

沈崑賢(Kun-Yin Shen)；邱綺文(Che-Wun Chiou)；唐仲儀(Jhong-Yi Tang)；洪士軒(Shih-Syuan Hong)；劉兆平(Jhao-Pian Liu)；陳郭祐(Guo-You Chen)

智慧型行動裝置 ； 橢圓曲線密碼系統 ； 乘法器 ； 公開金鑰密碼系統 ； 行動商務 ； 資訊安全

資訊安全通訊

20卷2期（2014 / 04 / 01）

137 - 150

繁體中文

智慧型行動裝置如智慧型手機、平板電腦與筆記型電腦成長將遠超過當年個人電腦及網路化的普及率。透過智慧型行動裝置進行行動電子商務的安全付款，將會是非常重要的課題，行動電子商務安全則依賴密碼系統提供的安全。因為需要之鑰匙位元長度極短，橢圓曲線密碼系統非常適合資源受限之智慧型行動裝置。橢圓曲線密碼系統核心運算為乘法器，低硬體成本之乘法器將是資源受限之智慧型行動裝置需要的。本論文將提出新型管線化位元－並列高斯正規乘法器，和現存同類乘法器比較，可再節省約66% chip area。

1. J. L. Massey and J. K. Omura, "Computational method and aparatus for finite field arithmetic," U.S. Patent Number 4,587,627, May 1986.
2. IEEE Standard 1363-2000, "IEEE standard specifications for public-key cryptography," Jan. 2000
3. FIPS 186-2, "Digital Signature Standard (DSS)," Federal Information Processing Standards Publication 186-2, Nat'l Inst. Of Standards and Technology, 2000
4. (2008).ISO/IEC 11770-3:2008, "Information technology-Security techniques-Key management-Part 3: mechanisms using asymmetric techniques," 2008..
5. (2005).ANSI X9.62-2005, "Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)," American National Standards Institute (ANSI), Nov. 2005.
6. Agnew, G.B.,Mullin, R.C.,Onyszchuk, I.M.,Vanstone, S.A.(1991).An implementation for a fast public-key cryptosystem.Journal of Cryptology,3,63-79.
7. Ash, D.W.,Blake, I.F.,Vanstone, S.A.(1989).Low complexity normal bases.Discrete Applied Math.,25,191-210.
8. Bartee, T. C.,Schneider, D. J.(1963).Computation with finite fields.Information and Computing,6,79-98.
9. Berlekamp, E. R.(1982).Bit-serial reed-solomon encoder.IEEE Trans. Inf. Theory,28(6),869-874.
10. Caelli, W.,Dawson, E.,Rea, S.(1999).PKI, Elliptic curve cryptography and digital signatures.Computer & Security,18(1),47-66.
11. Chang, P.-L.,Chen, L.-H.,Lee, C.-Y.(2009).Low-complexity dual basis digit serial GF(2m) multiplier.ICIC Express Letters,3(4),1113-1118.
12. Chang, P.-L.,Hsieh, F.-H.,Chen, L.-H.,Lee, C.-Y.(2010).Efficient digit serial dual basis GF(2m) multiplier.Proc. Of the 2010 5th IEEE Conference on Industrial Electronics and Applications, ICIEA 2010,Taichung, Taiwan:
13. Chen, L.-H.,Chang, P.-L.,Lee, C.-Y.,Yang, Y.-K.(2011).Scalable and systolic dual basis multiplier over GF(2m).International Journal of Innovative Computing, Information and Control,7(3),1193-1208.
14. Chiou, C.W.,Chuang, T.-P.,Lin, S.-S.,Lee, C.-Y.,Lin, J.-M.,Yeh, Y.-C.(2012).Palindromic-like representation for Gaussian normal basis multiplier over GF(2m) with odd type-t.IET Information Security,6(4),318-323.
15. Chiou, C.W.,Lin, J.-M.,Li, Y.-K.,Lee, C.-Y.,Chuang, T.-P.,Yeh, Y.-C.(2013).Pipeline Design of Bit-Parallel Gaussian Normal Basis Multiplier over GF(2m).The Seventh International Conference on Genetic and Evolutionary Computing,Prague, Czech Republic:
16. Chiou, C.W.,Lin, J.-M.,Li, Y.-K.,Lee, C.-Y.,Chuang, T.-P.,Yeh, Y.-C.(2013).Pipeline Design of Bit-Parallel Gaussian Normal Basis Multiplier over GF(3m).Advances in Intelligent Systems and Computing,238,369-377.
17. Chuang, T.-P.,Chiou, C. W.,Lin, S.-S.,Lee, C.-Y.(2012).Fault-tolerant Gaussian normal basis multiplier over GF(2m).IET Information Security,6(3),157-170.
18. Fan, H.,Hasan, M. A.(2007).Subquadratic computational complexity schemes for extended binary field multiplication using optimal normal bases.IEEE Trans. Computers,56(10),1435-1437.
19. Fan, H.,Hasan, M. A.(2007).A new approach to subquadratic space complexity parallel multipliers for extended binary fields.IEEE Trans. Computers,56(2),224-233.
20. Fenn, S. T. J.,Benaissa, M.,Taylor, D.(1996).GF(2m) multiplication and division over the dual basis.IEEE Trans. Computers,45(3),319-327.
21. Guo, J.-H.,Wang, C.-L.(1998).Digit-serial systolic multiplier for finite fields GF(2m).IEE Proc. Comput. Digit. Tech.,145(2),143-148.
22. Hasan, M.A.,Wang, M.Z.,Bhargava, V.K.(1993).A modified Massey-Omura parallel multiplier for a class of finite fields.IEEE Trans. Computers,42(10),1278-1280.
23. Hua, Y.Y.,Lin, J.-M.,Chiou, C.W.,Lee, C.-Y.,Liu, Y.H.(2012).A novel digit-serial dual basis Karatsuba multiplier over GF(2m).Journal of Computers,23(2),80-94.
24. Huang, W.-T.,Chang, C. H.,Chiou, C. W.,Tan, S.-Y.(2011).Non-XOR approach for low-cost bit-parallel polynomial basis multiplier over GF(2m).IET Information Security,5(3),152-162.
25. Ibrahim, M.K.,Aggoun, A.(2002).Dual basis digit serial GF(2m) multiplier.International Journal of Electronics,89(7),517-523.
26. Itoh, T.,Tsujii, S.(1989).Structure of parallel multipliers for a class of fields GF(2m).Information and Computation,83,21-40.
27. Kim, C.H.,Hong, C.P.,Kwon, S.(2005).A digit-serial multiplier for finite field GF(2m).IEEE Trans. Very Large Scale Integration (VLSI) Systems,13(4),476-483.
28. Koblitz, N.(1987).Elliptic curve cryptosystems.Math. Computal.,48,203-209.
29. Koç, Ç. K.,Sunar, B.(1998).Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields.IEEE Trans. Computers,47(3),353-356.
30. Kumar, S.,Wollinger, T.,Paar, C.(2006).Optimum digit-serial GF(2m) multipliers for curve-based cryptography.IEEE Trans. Computers,55(10),1306-1311.
31. Kwon, S.(2003).A low complexity and a low latency bit parallel systolic multiplier over GF(2m) using an optimal normal basis of type II.Proc. of the 16th IEEE Symposium on Computer Arithmetic,Santiago de Compostela, Spain:
32. 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. Computers,50(5),385-393.
33. Lee, C.-Y.,Chiou, C. W.(2012).Scalable Gaussian normal basis multipliers over GF(2m) using Hankel matrix-vector representation.Journal of Signal Processing Systems for Signal Image and Video Technology,69(2),197-211.
34. Lee, C.Y.,Chiou, C.W.(2005).Efficient design of low-complexity bit-parallel systolic Hankel multipliers to implement multiplication in normal and dual bases of GF(2m).IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science,E88-A(11),3169-3179.
35. Lidl, R.,Niederreiter, H.(1994).Introduction to Finite Fields and Their Applications.New York:Cambridge Univ. Press.
36. Mastrovito, E. D.(1988).VLSI architectures for multiplication over finite field GF(2m).Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Proc. Sixth Int'l Conf., AAECC-6,Rome:
37. Miller, V. S.(1986).Use of elliptic curves in cryptography.Advances in Cryptology Crypto'85
38. Paar, C.,Fleischmann, P.,Roelse, P.(1998).Efficient multiplier architectures for Galois Fields GF(24n).IEEE Trans. Computers,47(2),162-170.
39. Reyhani-Masoleh, A.(2006).Efficient algorithms and architectures for field multiplication using Gaussian normal bases.IEEE Trans. Computers,55(1),34-47.
40. Talapatra, S.,Rahaman, H.,Mathew, J.(2010).Low complexity digit serial systolic Montgomery multipliers for special class of GF(2m).IEEE Trans. Very Large Scale Integration (VLSI) Systems,18(5),847-852.
41. Vanstone, S.(1997).Elliptic curve cryptosystem-the answer to strong, fast public-key cryptography for securing constrained environments.Information Security Technical Report,2(2),78-87.
42. Wang, C. C.,Truong, T.K.,Shao, H. M.,Deutsch, L. J.,Omura, J. K.,Reed, I. S.(1985).VLSI architectures for computing multiplications and inverses in GF(2m).IEEE Trans. Computers,C-34(8),709-717.
43. Wang, J.-H.,Chang, H.W.,Chiou, C.W.,Liang, W.-Y.(2012).Low-complexity design of bit-parallel dual basis multiplier over GF(2m).IET Information Security,6(4),324-328.
44. Wang, M.,Blake, I.F.(1990).Bit serial multiplication in finite fields.SIAM J. Disc. Math.,3(1),140-148.
45. Wu, H.(2002).Bit-parallel finite field multiplier and squarer using polynomial basis.IEEE Trans. Computers,51(7),750-758.
46. Wu, H.,Hasan, M. A.,Blake, I. F.(1998).New low-complexity bit-parallel finite field multipliers using weakly dual bases.IEEE Trans. Computers,47(11),1223-1234.
47. Xie, J.,He, J.J.,Meher, P.K.(2013).Low latency systolic Montgomery multiplier for finite field GF(2m) based on pentanomials.IEEE Trans. VLSI Systems,21(2),385-389.
48. Xie, J.,Meher, P. K.,He, J.(2012).Low-latency area-delay-efficient systolic multiplier over GF(2m) for a wider class of trinomials using parallel register sharing.IEEE International Symposium on Circuits and Systems, (ISCAS'12),Seoul, Korea: