博碩士論文 88521071 詳細資訊


姓名 莊志強(Zh-Qiang Zhuang )  查詢紙本館藏   畢業系所 電機工程研究所
論文名稱 應用於橢圓曲線密碼系統之低複雜性有限場乘法器設計
檔案 [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 最近,由於在網際網路和電子商務快速的成長使得網路安全變成一個重要的課題,現今有非常多的工作,如購物,匯寄,電話,電子銀行,電子商務和金融交易等,都是在網際網路中送訊息。因此,在資訊的秘密性和可信賴性就特別重要。而為了保障重要資料不被竊取、破壞或任意更改,一套安全的密碼系統是非常重要的。
在這篇論文,我們專注在討論橢圓曲線密碼學(ECC)的發展改良其乘法器演算法和架構,我們主要的工作是集中在實現有限場中適用於橢圓曲線密碼學所須要用的低複雜度和高速之實現乘法運算。
我們根據改良式乘法器演算法來設計出新的第二型乘法器(Type-II multiplier)。在和Massey-Omura設計的第二型乘法器比較中,它有降低硬體中的複雜性和提高乘法器運算速度的優點。如在硬體上,新的第二型乘法器可省下25%的XOR閘的數目。另外,值得一提是在有效實現橢圓曲線密碼系統考量下,我們可利用它和第一型乘法器(Type-I multiplier)組合成新的合成第二型乘法器(Composite Type-II multiplier)。將使橢圓曲線密碼系統之乘法位元數大小(bit-size)有更好的選擇性和效能。而所得到的效能無論在硬體上的複雜性或時間的因素下,幾乎可以與第一型乘法器一樣好。最後應用所提出來的乘法器來完成在橢圓曲線密碼學中整個算術核心電路。
關鍵字(中) ★ 乘法器
★  密碼
★  有限場
★  橢圓曲線
關鍵字(英)
論文目次 Contents
Contents II
List of Figures V
List of Tables VIII
CHAPTER 1INTRODUCTION1
1.1OVERVIEW OF CRYPTOGRAPHY1
1.2OVERVIEW OF ECC CRYPTOGRAPHY2
1.3MOTIVATION AND GOAL5
1.4CONTRIBUTION OF THE THESIS7
1.5THESIS ORGANIZATION8
CHAPTER 2ELLIPTIC CURVE CRYPTOSYSTEMS10
2.1HISTORY OF ELLIPTIC CURVES10
2.2MATHEMATIC BACKGROUND ON ELLIPTIC CURVES12
2.2.1THE GROUP LAW14
2.2.2ELLIPTIC CURVE ADDITION15
2.2.3ELLIPTIC CURVES OVER GF(2M)19
2.2.4POINT MULTIPLICATION ON ELLIPTIC CURVES21
2.2.5GROUP OPERATION WITH PROJECTIVE COORDINATES22
2.3SUMMARY OF ENCRYPTION/DECRYPTION IN ECC25
CHAPTER 3FINITE FIELD ARITHMETIC26
3.1CHOOSING A FIELD27
3.2REPRESENTATION OF FINITE FIELD ELEMENTS28
3.3COMPUTER ARITHMETIC IN FINITE FIELDS30
3.3.1FINITE FIELD ADDITION (FFA)30
3.3.2SQUARING IN GF(2M)32
3.3.3FINITE FIELD MULTIPLICATION (FFM)33
CHAPTER 4DESIGN OF LOW-COMPLEXITY COMPOSITE FIELDS GF((2N)M) MULTIPLIERS38
4.1PROPOSED NORMAL BASIS TYPE-II MULTIPLIER39
4.1.1IMPROVED MULTIPLICATION ALGORITHM41
4.1.2MULTIPLICATION EXAMPLE43
4.1.3COMPARISON OF MULTIPLICATION ALGORITHMS45
4.2DESIGN OF EFFICIENT NORMAL BASIS MULTIPLIER IN COMPOSITE FIELDS48
4.2.1REVIEW OF TYPE-I ONB MULTIPLIER48
4.2.2PROPOSED TYPE-II COMPOSITE FIELDS MULTIPLIER49
4.2.3COMPARISON OF OTHER MULTIPLIERS53
CHAPTER 5THE DESIGN OF ECC PROCESSOR AND SIMULATION57
5.1ARCHITECTURAL DESIGN OF ECC PROCESSOR58
5.1.1DESIGN OF POINT MULTIPLICATION UNIT58
5.1.2DESIGN OF CONTROL UNIT61
5.1.3ECC PROCESSOR DESIGN63
5.2SIMULATION RESULT67
5.2.1VERIFICATION OF OUR ARCHITECTURE67
5.2.2OTHER TESTING CASES70
CHAPTER 6CONCLUSION73
參考文獻 [1]A.J. Menezes, Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publishers,Boston, MA,1993.
[2]N.Koblitz. A Course in Number Theory and Cryptography. Springer, Berlin, Germany, Second edition, 1994.
[3]I. Blake, G.Seroussi, and N. Smart. Elliptic Curve in Cryptography. Cambridge University Press, New York, NY, 1999.
[4]A.K. Lenstra and E. R. Verheul. Selecting cryptographic key sizes. In The 3rd Workshop on Elliptic Curve Cryptography (ECC 99), Waterloo, Canada, November 1-3 1999.
[5]S.C. Pohlig and M.E. Hellamn. An Improved Algorithm for Computing Logarithms if GF(p) and Its Cryptographic Significance. IEEE Transactions on Information Theory, v.24,n. 1, pp.106-111, Jan 1978.
[6]R.L. Rivest, A. Shamir, and L.M. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communication of the ACM, v.21,n.2, pp.120-126, Feb 1978.
[7]R.L. Rivest, A. Shamir, and L.M. Adleman. On Digital Signatures and Public Key Cryptosystems. MIT Laboratory for Computer Science, Technical Report, MIT/LCS/TR-212, Jan 1979.
[8]Bruce Schneier. Applied Cryptography; Protocols, Algorithms and Source code in C. John Wiley & Sons, Inc., 1994.
[9]C.C.Wang, T.K. Truong, H.M. Shao, L.J. Deutsch, J.K. Omura, and I.S. Reed. VLSI Architecture for Computing Multiplications and Inverses in GF(2m). IEEE Tran. Comput., vol. C-34, pp. 709-717, Aug. 1985.
[10]M.A. Hasan, M.Z. Wang, and V.K. Bhargava. A Modified Massey-Omura Parallel Multiplier for a Class of Finite fields. IEEE Trans. Computers, vol. 42, no. 10, pp. 1,278-1,280, Oct. 1993.
[11]S. Oh, C.H. Kim, J.Lim, D.H. Cheon. Efficient Normal Basis Multipliers in Composite Fields. IEEE Trans. Computers, vol.49, no. 10, pp. 1133-1138,Oct. 2000.
[12]E.R. Berlekamp. Algebraic Coding Theory. Mc-Graw Hill Book Company, 1968.
[13]R.Lidl and H. Niederreiter. Introduction to Finite Fields and Their Applications. New York NY: Cambridge Univerisity Press 1994.
[14]R.J. McEliece. Finite fields for Computer Scientists and Engineers. Boston MA: Kluwer Academic Publishers 1987.
[15]A.J. Menezes. Applications of Finite Fields. Boston MA: Kluwer Academic Publisher 1993.
[16]R.Lidl and H. Niederreiter. Finite Fields, in Encyclopedia of Mathematics and its Applications. G.-C. Rota, editor, Addison-Wesley, 1983.
[17]J. Omura and J. Massey. Computational method and apparatus for finite field arithmetic. U.S. Patent number 4587627, May 1986.
[18]R.Mullin, I. Onyszchuk, U.A. vanstone and R. Wilson. Optimal normal bases in GF(pn). Discrete Appl. Math., 22, 149-161, 1988/89.
[19]S.Gao, H.W. Lenstra. Optimal normal bases. Designs, Codes and Cryptography, 2, 315-323, 1992.
[20]G. Agnew, R. Mullin, I. Onyszchuk, S. Vanstone. An implementation for a fast public-key cryptosystem. Journal of Cryptology, 3(1991), 63-79.
[21]P.K.S. Wah and M.Z. Wang. Realization and application of the Massey-Omura lock. Presented at the Int. Zurich Sem., 1984.
[22]M.A. Hasan, M.Z. Wang, V.K. Bhargava. Modular construction of low complexity parallel multipliers for a class of finite fields GF(2m). IEEE Trans. Comput., vol. 41, pp. 962-971, Aug. 1992.
[23]T. Itoh and S. tsujii. Structure of parallel multipliers for a class of fields GF(2m). Inform. Comp., vol. 83, pp. 21-40, 1989.
[24]T.Itoh., Teechai and S. Tsujii. A fast algorithm for computing multiplicative inverses in GF(2t) using normal bases. J. Society for Electronic Communication 44:31-36, 1986.
[25]J. Silverman. The arithmetic of elliptic curves. Springer-Verlag, New-York, 1986.
[26]A. Menezes, T. Okamoto and S. Vanstone. Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field., IEEE Transactions on Information Theory, 39(1993), 1639-1646.
[27]D.E. Knuth. The Art of Computer Programming. Volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, Massachusetts, 2nd edition.
[28]A. Menezes, M. Qu, and S. Vanstone. Elliptic Curve systems. Proposed IEEE P1363 Standard, pages 1-42, April 1995.
[29]J.H. Silverman and J. Tate. Rational Points on Elliptic Curves. Springer-Verlag, 1992.
[30]C. Paar, P. Fleischmann, and P. Poelse. Efficient Mulitplier Architecture for Galois Fields. IEEE Trans Computers, vol. 47, no. 2, pp.162-170, Feb. 1998.
[31]AMERICAN NATIONAL STANDARD X9.62-1998. public key cryptography for the financial services industry. The Elliptic Curve Digital Signature Alogorithm (ECDSA).
[32]B. Sunar, Low-Complexity Bit-Parallel Canonical and Normal basis Multipliers for a Class of Finite Fields. IEEE Trans. Computers, vol. 47, no. 3, pp. 353-356, Mar. 1998.
[33]M.A. Hasan, M.Z. Wang, and V.K. Bhargava. Modular Construction of Low Complexity Parallel Multipliers for a Class of Finite Fileds GF(2^m). IEEE Trans Comput., vol. 41, no.8,pp. 962-971, Aug. 1992.
指導教授 周世傑(Shyh-Jye Jou) 審核日期 2001-6-28

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡