Date of Award

2012

Degree Type

Thesis

Degree Name

M.A.Sc.

Department

Electrical and Computer Engineering

First Advisor

Huapeng Wu

Second Advisor

Majid Ahmadi

Keywords

Crytpography, High-Speed, Mersenne Prime, Modular, Multiplication, Reduction

Rights

CC-BY-NC-ND 4.0

Abstract

The work contained in this thesis is a representation of the successful attempt to speed-up the modular reduction as an independent step of modular multiplication, which is the central operation in public-key cryptosystems. Based on the properties of Mersenne and Quasi-Mersenne primes, four distinct sets of moduli have been described, which are responsible for converting the single-precision multiplication prevalent in many of today's techniques into an addition operation and a few simple shift operations. A novel algorithm has been proposed for modular folding. With the backing of the special moduli sets, the proposed algorithm is shown to outperform (speed-wise) the Modified Barrett algorithm by 80% for operands of length 700 bits, the least speed-up being around 70% for smaller operands, in the range of around 100 bits.

Share

COinS