A novel unified algorithm and hardware architecture for integrated modular division and multiplication in GF(p) and GF(2[superscript]n) suitable for public-key cryptography Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/8336h455m

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • The spread of the internet and communications techniques increases the necessity for security in applications that involves sharing or exchange of secret or private infor- mation. Public-key cryptography is widely used in establishing secure communication channels between the users on the Internet, for E-commerce transactions, and in net- work security protocols. Public-key cryptography relies on algorithms from computer arithmetic, number theory and algebra. The modular arithmetic operations, modular division, and modular multiplication over ¯nite ¯elds (GF(p) and GF(2n)) are exten- sively used in many public-key cryptosystems, such as RSA, ElGamal cryptosystem, Di±e-Hellman key exchange algorithm, elliptic curve cryptography (ECC), and the Dig- ital Signature Standard including the Elliptic Curve Digital Signature Algorithm. In our research, we have mainly concentrated on hardware realization of the ECC since it seems to provide similar amount of security using smaller key size. The modular multiplication operation with a large modulus is very important in many public-key cryptosystems. One of the most e±cient ways to compute modular mul- tiplication is the Montgomery algorithm. Many e±cient Montgomery multiplier designs were proposed up to now. On the other hand, computing modular division (inverse) is a time-consuming process and cannot be avoided completely. It was claimed that a gain in performance can be obtained when implementing the division (inverse) in hardware. In this work, we propose, with a mathematical proof, an e±cient uni¯ed division algorithm to compute the modular division operation in GF(p) and GF(2n). The al- gorithm uses a counter to keep track of the di®erence between two ¯eld elements and this way eliminates the need for comparisons which are usually expensive and time- consuming. An hardware architecture implementing the algorithm is also proposed. The uni¯ed division algorithm is integrated with a uni¯ed Montgomery multipli- cation algorithm to obtain a novel Uni¯ed Division/Multiplication Algorithm (UDMA). The UDMA computes division (inverse) and multiplication in a very e±cient way in both GF(p) and GF(2n) ¯elds. Also, we propose a uni¯ed hardware architecture that e±ciently supports all operations in the UDMA and uses carry-save uni¯ed adders for re- duced critical path delay, making the proposed architecture faster than other previously proposed designs. Experimental results obtained by synthesizing the hardware design for AMI 0:5¹m CMOS technology and FPGA V ertixII chip (xc2vp50 ¡ 7ff148 technology) are shown and compared with other proposed dividers and multipliers.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Language
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2009-02-09T23:27:02Z (GMT) No. of bitstreams: 1 Lo'ai_A_Tawalbeh.pdf: 414491 bytes, checksum: f6928af66b0f940919473d7d66643a6d (MD5)
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2009-02-09T23:32:29Z (GMT) No. of bitstreams: 1 Lo'ai_A_Tawalbeh.pdf: 414491 bytes, checksum: f6928af66b0f940919473d7d66643a6d (MD5)
  • description.provenance : Made available in DSpace on 2009-02-09T23:32:29Z (GMT). No. of bitstreams: 1 Lo'ai_A_Tawalbeh.pdf: 414491 bytes, checksum: f6928af66b0f940919473d7d66643a6d (MD5)
  • description.provenance : Submitted by Philip Vue (vuep@onid.orst.edu) on 2009-02-09T22:19:55Z No. of bitstreams: 1 Lo'ai_A_Tawalbeh.pdf: 414491 bytes, checksum: f6928af66b0f940919473d7d66643a6d (MD5)

Relationships

In Administrative Set:
Last modified: 08/08/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items