橢圓曲線密碼系統之位元－並列高斯正規基底乘法器的最佳成本×時間設計

Bit-Parallel Gaussian Normal Basis Multiplier over GF(2^m) with Optimum Area×Time for Elliptic Curve Cryptosystems

蕭儒珣(Ru-Syun Siao)；邱綺文(Che-Wun Chiou)；呂松諭(J Song-Yu Lyu)；廖柏維(Bo-Wei Liao)；葉耕禔(Keng-Ti Yeh)；徐子峯(Zih-Feng Hsu)

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

資訊安全通訊

20卷2期（2014 / 04 / 01）

151 - 165

繁體中文

由於智慧型行動裝置如智慧型手機、筆記型電腦、和平板電腦愈來愈普遍，利用智慧型行動裝置進行電子交易也隨之愈來愈多，所以如何保護電子交易行為安全也成為重要課題。因為橢圓曲線密碼系統使用之鑰匙長度相對RSA公開金鑰密碼系統短很多，所以適合在資源有限之智慧型行動裝置使用。乘法器是實現橢圓曲線密碼系統核心元件，如何設計有效率之乘法器是非常重要課題，所以本研究將提出最佳Chip_Area×Time之新型位元-並列高斯正規乘法器，有效實現橢圓曲線密碼系統。

1. 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.
2. ISO/IEC 11770-3:2008, "Information technology-Security techniques-Key management-Part 3: mechanisms using asymmetric techniques," 2008..
3. NanGate Standard Cell Library [Online]. Available: http://www.si2.org/openeda.si2.org/projects/nangatelib/
4. J. L. Massey and J. K. Omura, "Computational method and aparatus for finite field arithmetic," U.S. Patent Number 4,587,627, May 1986.
5. FIPS 186-2, "digital Signature Standard (DSS)," Federal Information Processing Standards Publication 186-2, Nat'l Inst. Of Standards and Technology, 2000
6. IEEE Standard 1363-2000, "IEEE standard specifications for public-key cryptography," Jan. 2000
7. 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.
8. Ash, D.W.,Blake, I.F.,Vanstone, S.A.(1989).Low complexity normal bases.Discrete Applied Math.,25,191-210.
9. Bartee, T. C.,Schneider, D. J.(1963).Computation with finite fields.Information and Computing,6,79-98.
10. Berlekamp, E. R.(1982).Bit-serial reed-solomon encoder.IEEE Trans. Inf. Theory,28(6),869-874.
11. Caelli, W.,Dawson, E.,Rea, S.(1999).PKI, Elliptic curve cryptography and digital signatures.Computer & Security,18(1),47-66.
12. 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.
13. 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:
14. 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.
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).Advances in Intelligent Systems and Computing,238,369-377.
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(2m).The Seventh International Conference on Genetic and Evolutionary Computing,Prague, Czech Republic:
17. Chiou, C.W.,Chang, H.W.,Liang, W.-Y.,Lee, C.-Y.,Lin, J.-M.,Yeh, Y.-C.(2012).Low-complexity Gaussian normal basis multiplier over GF(2m).IET Information Security,6(4),310-317.
18. 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.
19. Chuang, T.-P.,Chiou, C. W.,Lin, S.-S.(2011).Self-checking alternating logic bit-parallel Gaussian normal basis multiplier with type-t.IET Information Security,5(1),33-42.
20. Diffie, W.,Hellman, M.E.(1976).New directions in cryptography.IEEE Transactions on Information Theory,IT-22(6),644-654.
21. 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.
22. 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.
23. 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.
24. 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.
25. 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.
26. 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.
27. 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.
28. Ibrahim, M.K.,Aggoun, A.(2002).Dual basis digit serial GF(2m) multiplier.International Journal of Electronics,89(7),517-523.
29. Itoh, T.,Tsujii, S.(1989).Structure of parallel multipliers for a class of fields GF(2m).Information and Computation,83,21-40.
30. 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.
31. Koblitz, N.(1987).Elliptic curve cryptosystems.Math. Computal.,48,203-209.
32. 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.
33. Kumar, S.,Wollinger, T.,Paar, C.(2006).Optimum digit-serial GF(2m) multipliers for curve-based cryptography.IEEE Trans. Computers,55(10),1306-1311.
34. 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:
35. 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.
36. 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.
37. 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.
38. Lidl, R.,Niederreiter, H.(1994).Introduction to Finite Fields and Their Applications.New York:Cambridge Univ. Press.
39. 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:
40. Miller, V. S.(1986).Use of elliptic curves in cryptography.Advances in Cryptology Crypto'85
41. Paar, C.,Fleischmann, P.,Roelse, P.(1998).Efficient multiplier architectures for Galois Fields GF(24n).IEEE Trans. Computers,47(2),162-170.
42. Reyhani-Masoleh, A.(2006).Efficient algorithms and architectures for field multiplication using Gaussian normal bases.IEEE Trans. Computers,55(1),34-47.
43. Rivest, R.,Shamir, A.,Adleman, L.(1978).A method for obtaining digital signatures and public-key cryptosystems.Communications of the ACM,21(2),120-126.
44. 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.
45. 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.
46. 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.
47. 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.
48. Wang, M.,Blake, I.F.(1990).Bit serial multiplication in finite fields.SIAM J. Disc. Math.,3(1),140-148.
49. Wu, H.(2002).Bit-parallel finite field multiplier and squarer using polynomial basis.IEEE Trans. Computers,51(7),750-758.
50. 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.
51. 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.
52. 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: