跳到主要內容

臺灣博碩士論文加值系統

(54.161.24.9) 您好!臺灣時間:2022/01/17 11:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張正杰
研究生(外文):Cheng-Chieh Chang
論文名稱:橢圓曲線密碼系統數學運算單元之硬體實現
論文名稱(外文):Hardware Implementation of Mathematical Operation Unit in Elliptic Curve Cryptosystems
指導教授:廖德祿
指導教授(外文):Teh-Lu Liao
學位類別:碩士
校院名稱:國立成功大學
系所名稱:工程科學系碩博士班
學門:工程學門
學類:綜合工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:66
中文關鍵詞:橢圓曲線密碼系統
外文關鍵詞:elliptic curvecryptosystem
相關次數:
  • 被引用被引用:1
  • 點閱點閱:667
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
  由於近幾年來網路的普及化,個人密秘資料在網路上傳輸的安全性更形重要,諸如網路報稅、網路商店、電子銀行及其它形式的網路交易等等。為了讓人能接受以上這些應用在網路交易的形式,一個有效且安全的公開金鑰密碼系統是非常重要的。
  公開金鑰密碼系統的安全性都是基於複雜的數學難題。我們可根據所基於的數學難題來將它們分為三類目前被認為是安全和有效的:大整數因子分解系統(代表性的有RSA)、橢圓曲線密碼系統(ECC)和離散對數系統(代表性的有DSA)。為了有愈高的安全性,更長的金鑰的位數是必需的,但是金鑰長度的增加除了導致其速度大為降低外,也會增加硬體成本。在西元1985年,Miller和Koblitz分別提出了一套安全性更高、算法實現性能更好的公鑰系統,其安全性是建立在橢圓曲線離散對數問題(ECDLP),我稱此為橢圓曲線密碼系統(ECC)。
  使用ECC當公開金鑰密碼系統的好處是,在同樣的安全性下,其所需的金鑰長度較其它系統(RSA,DSA)為短。而這個好處剛好可以被應用在智慧卡這種記憶體跟運算能有限的系統上面;且ECC不像RSA有專利的限制,可以自由的發展。
  本論文在實作方面是利用Verilog硬體描述語言來撰寫此橢圓曲線密碼系統之數學運算演算法。我們採用了C.K. Koc和B. Sunar所提出的乘法器。因為此乘法器結構很規則, 所以易於擴展其位元數,而且所需邏輯閘數和延遲時間較其它乘法器少及低,使得很容易用積體電路來實現。在運算方面我採用了Projective 座標系易用積體電路來實現。在運算方面我採用了Projective座標系,這可使我們可將除法運算變為乘法運算,而大大的降低運算結果的時間。在結果方面,我們利用Synopsys的合成軟體來將Verilog codes合成成電路,並加以模擬驗證。
  在本論文中,吾人使用了低複雜度的乘法器,及為了減少硬體的浪費,吾人考慮到模組的分享、重複使用,因此設計出來的Elliptic Curve Cryptosystem數學運算處理器可降低成本。
Because internet becomes more and more popular in recent years, the security of personal secret data such as E-commerce, E-bank, and etc., transferred in the internet becomes more and more important. In order to let everyone accept these internet transactions, a useful and safe public key cryptosystem is needed.
The security of public key cryptosystems is based on difficult and complicated mathematical problems. According to the difficult mathematical problem on which they are based, there are three types of systems classified and are thought secure: integer factorization systems (RSA is the best known example), Elliptic curve discrete logarithm systems (elliptic curve cryptosystems) and discrete logarithm systems (U.S. Government’s DSA). For higher security, a longer length of key size is needed. The increment of key size not only increases the time of computing results but also increases the cost of hardware. In 1985, Miller and Koblitz proposed independently a higher security public key cryptosystem, based on ECDLP, called elliptic curve public key cryptosystems.
The advantages of ECC are that its key sizes are smaller than those of existing public key schemes (RSA, DSA) with equivalent levels of security so that it can be implemented in smart card; ECC is not a patent of any company so that it can be developed freely, unlike RSA.
In this thesis, we developed the hardware implementations of the mathematical operations of elliptic curve cryptosystem by using Verilog HDL. The multiplier used in the processor was proposed by C.K Koc and B. Sunar. Because its operations are very regular, it is easy to expend the bit size of multiplier. Another two advantages are less gate counts and fewer gate time delays, so it is easy to be implemented in hardware. Also, the inversion is designed in the projective coordinates that will save much computation time. We synthesize our verilog codes by software of Synopsys, and confirm by simulation.
Furthermore, we use a low-complexity multiplier and in order to avoid waste of hardware, we think about resource-sharing. Therefore, the hardware design of mathematical operations processor for ECC can be reduced sufficiently.
Chinese Abstract.......................................................................................I
English Abstract.....................................................................................III
Acknowledgement....................................................................................V
Contents..................................................................................................VI
List of Tables........................................................................................VIII
List of Figures.........................................................................................IX

Chapter1 Introduction.............................................................................1
1.1 Introduction to Cryptography...........................................................................1
1.2 Organization of this thesis................................................................................2

Chapter 2 Finite Field GF(2m) Arithmetic..............................................3
2.1 Introduction to Galois Field.............................................................................3
2.2 Basis representation.........................................................................................5
2.2.1 The polynomial basis (PB)..............................5
2.2.2 The normal basis (NB)..............................6
2.3 Field Multiplication..........................................................................................7
2.3.1 All One Polynomial (AOP) ..........................................................................7
2.3.2 Low-Complexity Bit-Parallel Canonical Multiplier......................................7
2.3.3 Low-Complexity Bit-Parallel Normal Multiplier........................................13
2.3.4 Reasons of using this multiplier...................................... ...........................15
2.4 Field squaring.................................................................................................15
2.5 Field inversion and division...........................................................................16

Chapter 3 Overview of Elliptic Curves.................................................18
3.1 History............................................................................................................18
3.2 Basic theorems...............................................................................................19
3.2.0 Theorems used in Elliptic Curves...............................................................19
3.2.1 Group Law...................................................................................................21
3.3 Projective Space.............................................................................................29
3.4 The Elliptic Curve Group Structure...............................................................31
3.5 The Elliptic Curve Discrete Logarithm Problem...........................................34
3.6 The order of a point.......................................................................................35

Chapter 4 Elliptic Curve Cryptosystems (ECC).................................36
4.1 Analog of ElGamal Public Key Cryptosystem...............................................36
4.2 Elliptic curve Diffie-Hellman key exchange (ECDH) ..................................38
4.3 Elliptic Curve Digital Signature Algorithm (ECDSA) ..................................39
4.4 Standards of Elliptic Curve Cryptosystems....................................................41

Chapter 5 Implementation of Arithmetic Processor for ECC and Simulation Results..................................................................................43
5.1 Architecture....................................................................................................43
5.2 FSM................................................................................................................45
5.3 Multiplier........................................................................................................53
5.4 XOR...............................................................................................................56
5.5 System............................................................................................................58

Chapter 6 Conclusions and Further Works.........................................62
6.1 Conclusions....................................................................................................62
6.2 Further Works.................................................................................................63

Bibliography............................................................................................64
[1] W. Diffie and M. Hellman, “New directions in cryptography”, IEEE Trans. Inform. Theory, vol. IT-22, pp. 644-654, 1976.
[2]T.ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Transactions on Information Theory, vol. 31, pp. 473-481, 1985.
[3]R. Rivest, A. Shamir and L.M. Adleman, “A Method for Obtaining Digital Signatures and Public Key Cryptosystems”, Communications of the ACM, Vol. 21, pp. 120-126, 1978.
[4]Victor S. Miller, “Use of Elliptic Curves in Cryptography”, Advances in Cryptology – CRYPTO ’85 Proceedings, Lecture Notes in Computer Science, (1986) Springer-Verlag, Pg. 417-426.
[5]Neal Koblitz, “Elliptic Curve Cryptosystems”, Mathematics of Computation, 48n.177 (1987), Pg. 203-209.
[6]“Elliptic Curve Cryptosystems”, Certicom White Paper.
[7]Certicom, “Elliptic Curve Cryptography”,
http://www.certicom.com/research/online.html
[8]Mohammed, E., Emarah, A.E. and El-Shennawy, K., “Elliptic curve cryptosystems on smart cards”, Security Technology, 2001 IEEE 35th International Carnahan Conference on page(s): 213 - 222 16-19 Oct. 2001.
[9]Seroussi, G., “Elliptic curve cryptography”, Information Theory and Networking Workshop, 1999, Page(s): 41.
[10]Botes, J.J. and Penzhorn, W.T., “An implementation of an elliptic curve cryptosystem”, Communications and Signal Processing, 1994. COMSIG-94., Proceedings of the 1994 IEEE South African Symposium, Page(s): 85 -90.
[11]A. Menezes, “ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS”, Kluwer Academic Publishers, Boston, 1993.
[12]FIPS 186-2, “Digital Signature Standard”, Federal Information Proceeding Standards Publication 180-2,200. Available from
http://www.itl.nist.gov/fipspubs/
[13]FIPS 180-1, “SECURE HASH STANDARD” Federal Information Proceeding Standards Publication 180-2,200. Available from
http://www.itl.nist.gov/fipspubs/
[14]IEEE P1363. Standard Specifications for Public-Key Cryptography, Draft. 13, IEEE Working Group, November 1999. Available from
http://grouper.ieee.org/groups/1363/
[15]IEEE P1363A. Standard Specifications for Public-Key Cryptography: Additional Techniques, Draft. 4, IEEE Working Group, May 2000. Available from
http://grouper.ieee.org/groups/1363/
[16]J.S. Coron, H. handschuh, and D. Naccache, “ECC: Do We Need to Count?” Advances in Cryptology-ASIACRYPT’99, LNCS 1716, Springer, pp. 122-134, 1999.
[17]ANSI X9.62-1998, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), American Bankers Association, 1999.
[18]Hauck, O., Katoch, A. and Huss, S.A., “VLSI system design using asynchronous wave pipelines: a 0.35 /spl mu/m CMOS 1.5 GHz elliptic curve public key cryptosystem chip”, Advanced Research in Asynchronous Circuits and Systems, 2000. (ASYNC 2000) Proceedings. Sixth International Symposium, Page(s): 188 -197.
[19]C.K. Koc and B. Sunar, “Low-Complexity Bit-Parallel Canonical and Normal Basis Multipliers for a Class of Finite Fields”, IEEE Transactions on Computers, vol. 47, NO. 3, pp.353-356, March 1998.
[20]J. L. Massey and J. K. Omura, “U.S. patent 4,587,627”, May 1986.
[21]Sangho Oh, Chang Han Kim, Jongin Lim and Dong Hyeon Cheon, “Efficient normal basis multipliers in composite fields”, Computers, IEEE Transactions, Volume: 49 Issue: 10, Oct. 2000, Page(s): 1133 -1138.
[22]M. A. Hasan, M. Z. Wang and V. K. Bhargava, “A Modified Massey-Omura Parallel Multiplier for a Class of Finite Fields”, IEEE Transactions on Computers, vol. 42, NO. 10, pp. 1278-1280, October 1993.
[23]Wah, P.K.S., “Secure communication networks based on the public-key cryptosystem in GF(2m)”, Security Technology, 1991. Proceedings. 25th Annual 1991 IEEE International Carnahan Conference, Page(s): 120 -125.
[24]Sangook Moon; Yongjoo Lee; Jaemin Park; Yongsurk Lee, “A fast finite field multiplier architecture for high-security cryptographic applications”, Consumer Electronics, 2001. ICCE. International Conference, Page(s): 216 -217.
[25]Christof Paar, Peter Fleischmann and Pedro Soria-Rodriguez, “Fast Arithmetic for Public-Key Algorithms in Galois Fields with Composite Exponents”, IEEE Transactions on Computers, vol. 48, NO. 10, October 1999.
[26]Lijun Gao; Sobelman, G.E., “Improved VLSI designs for multiplication and inversion in GF(2M) over normal bases”, ASIC/SOC Conference, 2000. Proceedings. 13th Annual IEEE International , Page(s): 97 -101.
[27]Chung-Hsin Liu, ”New efficient low-complexity architecture for performing inversion and divisions”, VLSI Technology, Systems, and Applications, 2001. Proceedings of Technical Papers. 2001 International Symposium, Page(s): 299 -302.
[28]Shayan, Y.R.; Le-Ngoc, T., “The least complex parallel Massey-Omura multiplier and its LCA and VLSI designs”, Communications, Computers and Signal Processing, 1989. Conference Proceeding, IEEE Pacific Rim Conference, Page(s): 408 -411.
[29]Furness, R.; Benaissa, M.; Fenn, S.T.J., “Finite field division based on recursive division algorithm and composite fields”, Electronics Letters , Volume: 34 Issue: 18 , 3 Sept. 1998 , Page(s): 1730 -1731.
[30]Shu Lin and Daniel J. Costello, JR., “ERROR CONTROL CODING Fundamentals and Applications”.
[31]Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone and Tomik Yaghoobian, “APPLICATIONS OF FINITE FIELDS”, Kluwer Academic Publishers, Boston 1993.
[32]Kenneth H. Rosen, “Elementary Number Theory and Its Applications”, AT&T Bell Laboratories and Kenneth H. Rosen, 1993.
[33]Chi Sung Laih, Leih Harn and Chin Chen Chang, “Contemporary Cryptography and Its Applications”, 松崗電腦圖書資料股份有限公司.
[34]Shyue-Win Wei, “VLSI architectures of divider for finite field GF(2M)”, Circuits and Systems, 1998. ISCAS '98. Proceedings of the 1998 IEEE International Symposium, Volume: 2, 1998, Page(s): 482 -485 vol.2.
[35]Alfred J. Menezes, Tatsuaki Okamoto, and Scott A. Vanstone, “Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field”, IEEE Transactions on Information Theory, vol. 39, NO. 5, September 1993.
[36]B. Sunar, and C.K. Koc, “An Efficient Optimal Normal Basis Type II Multiplier”, IEEE Transactions on Computers, vol. 50, NO. 1, January 2001.
[37]Drescher, W.; Bachmann, K.; Fettweis, G., “VLSI architecture for datapath integration of arithmetic over GF(2 m) on digital signal processors”, Acoustics, Speech, and Signal Processing, 1997. ICASSP-97., 1997 IEEE International Conference on , Volume: 1 , Page(s): 631 -634 vol.1.
[38]S. Vanstone, “Responses to NIST’s Proposal”, Communications of the ACM, 35, July 1992, 50-52 (communicated by John Anderson).
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top