Please use this identifier to cite or link to this item:
Type: Theses
Title: Modular multiplication in the residue number system
Author: Kong, Yinan
Issue Date: 2009
School/Discipline: School of Electrical and Electronic Engineering
Abstract: Public-key cryptography is a mechanism for secret communication between parties who have never before exchanged a secret message. This thesis contributes arithmetic algorithms and hardware architectures for the modular multiplication Z = A × B mod M. This operation is the basis of many public-key cryptosystems including RSA and Elliptic Curve Cryptography. The Residue Number System (RNS) is used to speed up long word length modular multiplication because this number system performs certain long word length operations, such as multiplication and addition, much more efficiently than positional systems. A survey of current modular multiplication algorithms shows that most work in a positional number system, e.g. binary. A new classification is developed which classes these algorithms as Classical, Sum of Residues, Montgomery or Barrett. Each class of algorithm is analyzed in detail, new developments are described, and the improved algorithms are implemented and compared using FPGA hardware. Few modular multiplication algorithms for use in the RNS have been published. Most are concerned with short word lengths and are not applicable to public-key cryptosystems that require long word length operations. This thesis sets out the hypothesis that each of the four classes of modular multiplication algorithms possible in positional number systems can also be used for long word length modular multiplication in the RNS; moreover using the RNS in this way will lead to faster implementations than those which restrict themselves to positional number systems. This hypothesis is addressed by developing new Classical, Sum of Residues and Barrett algorithms for modular multiplication in the RNS. Existing Montgomery RNS algorithms are also discussed. The new Sum of Residues RNS algorithm results in a hardware implementation that is novel in many aspects: a highly parallel structure using short arithmetic operations within the RNS; fully scalable hardware; and the fastest ever FPGA implementation of the 1024-bit RSA cryptosystem at 0.4 ms per decryption.
Advisor: Phillips, Braden Jace
Dissertation Note: Thesis (Ph.D.) -- University of Adelaide, School of Electrical and Electronic Engineering, 2009.
Keywords: modular multiplication
residue number system
public-key cryptography
Provenance: This electronic version is made publicly available by the University of Adelaide in accordance with its open access policy for student theses. Copyright in this thesis remains with the author. This thesis may incorporate third party material which has been used by the author pursuant to Fair Dealing exceptions. If you are the owner of any included third party copyright material you wish to be removed from this electronic version, please complete the take down form located at:
Appears in Collections:Research Theses

Files in This Item:
File Description SizeFormat 
01front.pdf102.44 kBAdobe PDFView/Open
02whole.pdf805.35 kBAdobe PDFView/Open
  Restricted Access
Library staff access only373.45 kBAdobe PDFView/Open
  Restricted Access
Library staff access only1.3 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.