Rapid hardware implementations of classical modular multiplication Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/6m311s68g

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Modular multiplication is a mathematical operation fundamental to the RSA cryptosystern, a public-key cryptosystem with many applications in privacy, security, and authenticity. However, cryptosecurity requires that the numbers involved be extremely large, typically ranging from 512-1024 bits in length. Calculations on numbers of this magnitude are cumbersome and lengthy; this limits the speed of RSA. This thesis examines the problem of speeding up modular multiplication of large numbers in hardware, using the classical (add-and-shift) multiplication algorithm. The problem is broken down, and it is shown that the primary computational bottleneck occurs in the modular reduction step performed on each cycle. This reduction consists of an integer division step, a broadcast step, and a multiplication step. Various methods of speeding up these steps are examined, both for the special case of radix-2 multipliers (those shifting a single bit at a time) and the general case of radix-2r multipliers (those shifting r bits on every cycle.) The impacts of these techniques, both on cycle time and on chip area, are discussed. The scalability of these systems is examined, and several implementations of modular multiplication found in the literature are analyzed. Most significantly, the technique of pipelining of modular multipliers is examined. It is shown that it is possible to pipeline the modular reduction sequence, effectively eliminating the cycle time's dependence on either the size of the modulus, or on the size of the radius. Furthermore, a technique for constructing such multipliers is given. It is demonstrated that this technique is scalable with respect to time, and that pipelining eliminates many of the disadvantages inherent in previous high-radix implementations. It is also demonstrated that such multipliers have an area requirement which is linear with respect to both radix and modulus size.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-11-21T22:45:52Z (GMT) No. of bitstreams: 1 JohnsonScottAndrew1995.pdf: 3354797 bytes, checksum: 8697c80f25d51504e5d16b7e45924380 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-11-21T18:38:43Z (GMT) No. of bitstreams: 1 JohnsonScottAndrew1995.pdf: 3354797 bytes, checksum: 8697c80f25d51504e5d16b7e45924380 (MD5)
  • description.provenance : Made available in DSpace on 2012-11-21T22:45:52Z (GMT). No. of bitstreams: 1 JohnsonScottAndrew1995.pdf: 3354797 bytes, checksum: 8697c80f25d51504e5d16b7e45924380 (MD5) Previous issue date: 1995-03-08
  • description.provenance : Submitted by Kirsten Clark (kcscannerosu@gmail.com) on 2012-11-19T22:31:58Z No. of bitstreams: 1 JohnsonScottAndrew1995.pdf: 3354797 bytes, checksum: 8697c80f25d51504e5d16b7e45924380 (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items