成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	劉可玉 Liu, Ke-Yu
論文名稱：	橢圓曲線密碼系統之硬體實現 Hardware Implementation of Elliptic Curve Cryptosystem
指導教授：	廖德祿 Liao, Teh-Lu
學位類別：	碩士 Master
系所名稱：	工學院 - 工程科學系 Department of Engineering Science
論文出版年：	2003
畢業學年度：	91
語文別：	英文
論文頁數：	63
中文關鍵詞：	橢圓曲線
外文關鍵詞：	ECC
相關次數：	點閱：59 下載：4
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

現今，由於網際網路的普及與行動通訊的廣泛應用，個人秘密資料在公共通道中傳輸的次數也因此更加頻繁，例如網路報稅、電子商務、線上銀行及其它形式的網路交易等等，每個人勢必將透過網路來傳送個人資料，因此資訊傳輸的安全性愈加顯得重要。為了保護個人資料在傳輸過程中不被第三者擷取，加密是達到資訊安全的有效方法之一。公開金鑰密碼系統和秘密金鑰密碼系統皆能滿足對資料加密的需求[1]，但是秘密金鑰密碼系統有著金匙分配的問題、金匙數目太大及無法達到不可否認性的問題存在。而公開金鑰密碼系統可解決以上的問題，因此我們選擇公開金鑰密碼系統作為此論文的加密系統。
公開金鑰密碼系統的安全性都是建立在數學問題的複雜度。目前最被廣泛應用的公開金鑰密碼系統可分為三類：大整數因數分解系統(RSA)、離散對數系統(ElGamal)和橢圓曲線密碼系統(ECC)。在密碼系統中為了提高系統的安全性，通常需要增加金匙的位數，但是增加金匙的長度除了導致運算速度降低外，也會增加硬體成本。在西元1985年，Miller和Koblitz提出一套安全性更高、實現效能更好的橢圓曲線密碼系統(Elliptic Curve Cryptosystem)，其安全性是基於橢圓曲線離散對數問題(ECDLP)。
使用ECC當作公開金鑰密碼系統的最大優點是，在相同的安全性下，ECC所需的金匙長度遠較其它系統(如RSA，DSA)為短。而這個優點可以被應用在智慧卡或是行動電話這類記憶體跟運算效能受限的系統，同時因為金匙長度變小可提昇系統的運算速度。而且ECC不像RSA有專利的限制，可以自由的發展。
本篇論文是依據ElGamal的加解密流程並利用Verilog硬體描述語言來撰寫此橢圓曲線密碼系統之演算法。系統架構包含三個部分: Shift Register, ECC Unit和Divider。Shift Register 是利用Linear Feedback Shift Register設計而成的亂數產生器。而ECC Unit 則採用了C.K. Koc和B. Sunar所提出的乘法器。因為此乘法器有著結構規則, 容易擴展其位元數，而且所需邏輯閘數和延遲時間較其它乘法器少及低的優點，容易用積體電路來實現。Divider則是利用Xilinx Language Templates裡的除法器並予以改良。在數學運算方面採用了Projective space，如此可將有限場裡的除法運算轉化成乘法運算，而大大的降低運算結果的時間。
　　在本論文中利用電路共用的觀念，將加解密的功能共構在晶片之上，減少硬體的浪費，並考慮到模組的分享、重複使用，因此設計出來的硬體有著結構簡單，高安全性及高運算效能的優點。

Because the internet and mobile communication are getting popular [3], the transmission of the private data on the public channel is more frequent, for examples E-commerce, E-bank, and etc. Hence the security of private information transmission becomes more and more important. In general, encryption is an efficient method to protect the data from intruder’s attack. The public-key cryptosystem (PKC) and the secrete-key cryptosystem (SKC) are two major systems in data cryptosystem [1]. Since SKC has some unsolved drawbacks, we adopt PKC here.
The security of public-key cryptosystems is based on the difficulty and complexity of mathematical problems. Now, there are three well-known types of cryptosystems: integer factorization systems (RSA), Elliptic curve discrete logarithm systems (elliptic curve cryptosystems) and discrete logarithm systems (ElGamal) [2]. In order to have higher security, a longer length of key size is needed. The increment of key size not only decreases the performance but also increases the cost of hardware. In 1985, Miller and Koblitz proposed the elliptic curve theory for the implementation of public-key cryptosystem. Hence the elliptic curve theory can be used to realize the ElGamal public-key cryptosystem. Its security is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP).
The advantage of ECC is that its key sizes are smaller than those of existing public-key cryptosystem (RSA, DSA) with equivalent levels of security so that it can be implemented in the devices that have memory and power constrains, like smart card or mobile phone. ECC is not a patent of any corporation so it can be applied freely.
In this thesis, we adopt the ElGamal protocol and developed the hardware implementation of the elliptic curve cryptosystem by using Verilog HDL. The architecture of system consists of three parts: Shift Register, ECC Unit and Divider. Shift Register is design by using the concept of Linear Feedback Shift Register so that we can use an 8-bits register to generate a 255-bits pseudo sequence. The multiplier used in this thesis was suggested by C.K Koc and B. Sunar. Because its structures are very regular, it is easy to expend the bit size of multiplier. And it needs fewer gate counts and gate time delays than other multipliers, so it can be implemented in hardware. We adopt the Pipelined Divider attached in Xilinx Language Templates and improve its functions for using in the proposed ECC system. In addition, we adopt the concept of the Projective Space in order to convert the coordinates so that we can solve the operation complexity of inverse.
Furthermore, we use a Low-Complexity Bit-Parallel Canonical and Normal Basis Multiplier. We use the concept of resource-sharing to avoid waste of hardware. Therefore, the hardware design of ECC is regular, secure and high performance.

Chinese Abstract.........................................................………..…….....III
English Abstract................................................................................…...V
Acknowledgement.................................................................................VII
Contents...............................................................................................VIII
List of Tables....................................................................................…...X
List of Figures.........................................................................................XI

Chapter1 Introduction of Cryptosystem................................................1
1 Introduction………………..............................................................................1
2 Organization…………….................................................................................2

Chapter 2 Finite Field GF(2m) Fundamentals…....................................3
1 Mathematical background…............................................................................3
2 Basis in Finite Fields........................................................................................5
2.1 Polynomial Basis………………………………..................…..............6
2.2 Normal Basis………………………………………..............................6
3 Field Multiplication..........................................................................................7
3.1 All One Polynomial (AOP) ...................................................................7
3.2 Canonical Basis Multiplier………………….........................................8
3.3 Normal Basis Multiplier…………………...........................................13
4 Conclusions....................................................................................................15

Chapter 3 Theorems of Elliptic Curves................................................16
1 Background  ................................................................................................16
2 Arithmetic in Elliptic Curves.........................................................................16
2.1 Mathematics……………….................................................................17
2.2 Group Law............................................................................................17
3 Elliptic Curves over Real Numbers ...............................................................17
3.1 Addition of the dissimilar points P and Q............................................18
3.2 Doubling the point P…………………………………………………20
4 Elliptic Curves over  …………..............................................................22
4.1 Adding the dissimilar points P and Q..........................................…….22

4.2 Doubling the point P…………………………………………………23
5 Elliptic Curves over  ………..........................................................…..24
5.1 Adding the dissimilar points P and Q..........................................…….24
5.2 Doubling the point P…………………………………………………25
6 Projective Space……..……...……..........................................................…..27
7 The Elliptic Curve Discrete Logarithm Problem (ECDLP)...........................30
8 Conclusions………........................................................................................31

Chapter 4 Protocols in Elliptic Curve Cryptograph...........................32
1 Elliptic curve Diffie-Hellman (ECDH) Key Exchange .................................32
2 Elliptic Curve Digital Signature Algorithm (ECDSA)...................................33
3 Analog of ElGamal Cryptosystem with Elliptic Curve..................................35
4 Proposed IEEE Standard……………………………………………………37
5 Standards for Elliptic Curve Cryptograph.................................................….38

Chapter 5 Implementation of ECC....………......................................40
1 Shift Register..................................................................................................40
1.1 Linear Feedback Shift Register (LFSR)………………………………41
2 ECC Unit........................................................................................................43
2.1 Finite State Machine………………………………………………..…45
2.2 Multiplier……………………………………………………………...51
2.3 XOR………………………………………………………………… .54
3 Divider…........................................................................................................55
4 System............................................................................................................56

Chapter 6 Future Works and Conclusions.......................................…60
1 Conclusions....................................................................................................60
2 Future Works..................................................................................................61

References..............................................................................…..............62
                                    

[1]Chi Sung Laih, Leih Harn and Chin Chen Chang, “Contemporary Cryptography and Its Applications”, 松崗電腦圖書資料股份有限公司.
[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]P.K.S. Wah, “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.
[4]J.J. Botes and W.T. Penzhorn “PUBLIC-KEY CRYPTOSYSTEM BASED ON ELLIPTIC CURVES”, IEEE 1993.
[5]W. Diffie and M. Hellman, “New directions in cryptography”, IEEE Trans. Inform. Theory, vol. IT-22, pp. 644-654, 1976.
[6]Neal Koblitz, “Elliptic Curve Cryptosystems”, Mathematics of Computation, 48n.177 (1987), Pg. 203-209.
[7]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.
[8]Elsayed Mohammed, A.E.Emarah and Hh. El-Shennawy, “Elliptic Curve Cryptosystems on Smart Cards”.
[9]Leilei Song and Keshab K. Parhi, “Low-Area Dual Basis Divider over GF(2M) ”, IEEE 1997.
[10]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.
[11]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.
[12]T. Itoh ans S. Tsujii,"Structure of Parallel Multipliers for a Class of Finite Fields GF(2m),"Information and Computation,vol.83,pp.21-40,1989.
[13]E.D Mastrovito, "VLSI Architectures for Multiplication Over Finite Field GF(2m),"Applied Algebra, Algebraic Algorithms,
[14]Certicom, “Elliptic Curve Cryptography”,http://www.certicom.com/research/online.html
[15]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.
[16]Julio Lopez and Ricardo Dahab, “An Overview of Elliptic Curve Cryptography”, Relat rio T cnico IC-00-10.
[17]S. Vanstone, “Responses to NIST’s Proposal”, Communications of the ACM, 35,July 1992, 50-52 (communicated by John Anderson).
[18]Neal Koblitz, Alfred Menezes and Scott Vanstone, “The State of Elliptic Curve Cryptography”, Design, Codes and Cryptography, 19,173-193 (2000).
[19]IEEE P1363. Standard Specifications for Public-Key Cryptography, Draft. 13, IEEE Working Group, November 1999. Available from http://grouper.ieee.org/groups/1363/
[20]A. Menezes, M.Qu, and S. Vanstone. "Elliptic curve systems. Proposed IEEE P1368 Standard," page 1-42, April 1995.
[21]FIPS 186-2, “Digital Signature Standard”, Federal Information Proceeding Standards Publication 180-2,200. Available from http://www.itl.nist.gov/fipspubs/
[22]Shu Lin and Daniel J. Costello, JR., “ERROR CONTROL CODING Fundamentals and Applications”.
[23]FIPS 180-1, “SECURE HASH STANDARD” Federal Information Proceeding Standards Publication 180-2,200. Available from http://www.itl.nist.gov/fipspubs/
[24]ANSI X9.62-1998, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), American Bankers Association, 1999.
[25]Cheng Chieh Chang, “Hardware Implementation of Mathematical Operation Unit in Elliptic Curve Cryptosystems”.

校內：2008-08-18公開
校外：2008-08-18公開

簡易檢索 / 詳目顯示

相關論文