DOC PREVIEW
MASON ECE 646 - Modular Reduction of Large Integers Using Classical, Barrett, Montgomery Algorithms

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

INTRODUCTION and BACKGROUNDClassical AlgorithmBarrett AlgorithmMontgomery Algorithm:APPROACHA. Language, Platform, and Compiler Used for ImplementatioB. Input/Output SpecificationsC. Test ProcedureB. Barrett AlgorithmC. Montgomery AlgorithmANALYSISAPPLICATIONCONCLUSIONIP1 1Modular Reduction of Large Integers Using Classical, Barrett, Montgomery Algorithms M. Johnson, B. Phung, T. Shackelford, S. Rueangvivatanakij Abstract— Current public-key cryptosystems (RSA algorithm) are based mainly on modular operations (modular multiplication and modular exponentiation) of very large integers, ranging on the order of 38-616 decimal digits, or 128-2048 binary bits. Performing computation of numbers of this large size with multiple precisions is not easy or fast to implement. Most methods rely on modular reduction algorithm functions to reduce the size and complexity of the required arithmetic operations to carry out their public-key cryptosystem implementations more efficiently. In this paper we focus on three well-known modular reduction algorithms frequently used to reduce the arithmetic operations in Zm - integers modulo m – where m is a very large positive integer. Specifically, we examine the Classical, Barrett, and Montgomery algorithms. These algorithms are a time critical step in the implementation of the modular multiplication and exponentiation operations. We consider application in the modular exponentiation operation for each of these algorithms. Conclusions are drawn regarding the accuracy, performance, and computational efficiency of the algorithms based on the results obtained. Index Terms— Barrett modular reduction, Classical modular reduction, modular exponentiation, Montgomery modular reduction. I. INTRODUCTION AND BACKGROUND any public-key cryptosystems require efficient methods of performing multiplication and exponentiation in Zm. The efficiency of a particular cryptosystem will depend on a number of factors, such as parameter size, time-memory tradeoffs, available processing power, software and/or hardware optimization, and mathematical algorithms. This project is primarily concerned with the mathematical algorithms for efficiently carrying out these modular computations. Since modular reduction of large numbers is the basic operation in public-key cryptosystems, efficient implementation of this operation will enable software implementations to run faster than previously possible. The Classical, Barrett, and Montgomery algorithms are well-known modular reduction algorithms for large integers used in public-key cryptosystems. Each algorithm has its own unique characteristics resulting in a specific field of application. Below are descriptions of the algorithms. The descriptions and pseudo code for the Classical, Barrett, and Montgomery algorithms come from the “Comparison of Three Modular Reduction Functions” paper by Bosselaers, Govaerts, and Vandewalle. A. Classical Algorithm The classical algorithm is a formalization of the ordinary l-k (l is size of argument, k is size of m) step pencil-and-paper method, each step of which is the division of a (k+1) digit number x by the k-digit divisor m. This yields the one-digit quotient q and the k digit remainder r. Each remainder r is less than m, so that it can be combined with the next digit of the dividend into the (k+1) digit number rb + (next digit of dividend) to be used as the new x in the next step. The pseudo code of the classical algorithm given mk -1 ≥ b/2⌡ follows: if (x > mbl-k ) then x = x - mbl-k for (i = L-1; i > k-1; i--) do { if (xi == mk -1 ) then q = b-1; else q = (xib + xi-1) div mk-1; while (q(mk-1b + mk-2) > xib2 + xi-1b + xi-2 ) do q = q-1; x = x – qmbi-k; if (x < 0) then x = x + mb i-k; } B. Barrett Algorithm The Barrett algorithm for modular reduction of large integers is based on a very simple idea, similar to the way you perform calculations using your calculator. Barrett introduced the idea of estimating the quotient x div m with operations that are either less expensive in time than a multi-precision division by m or can be done as a pre-calculation for a given m. The estimate for q of x div m is obtained by replacing the floating-point divisions in q’ = [(x/b2k-t)(b2k/m)/bt] by integer divisions q’ = [(x div b2k-t)µ) div bt. MIP1 2 INPUT: positive integers x = (x2k-1 … x1x0)b, m = (mk-1 …m1m0)b (with mk-1 !=0), and u = b2k/m. OUTPUT: r = x mod m. 1. q1 ← x/bk-1, q2 ← q1 * u, q3 ← q2=bk+1. 2. r1 ← x mod bk+1, r2 ← q3 * m mod bk+1, r ← r1 - r2. 3. if r < 0 then r ← r + bk+1. 4. while r >= m do: r ← r-m. 5. Return(r). The pseudo code of Barrett’s algorithm given µ = b2k div m follows: q = ((x div b k+1) µ ) div b k+1 ; x = x mod b k+1– (qm) mod b k+1 ; if (x < 0) then x = x + b k+1 ; while (x ≥ m) do x = x – m; C. Montgomery Algorithm: The basic idea of Montgomery’s theorem is to make x a multiple of R by adding multiples of m. Instead of computing all of t at once, one can compute one digit ti at a time, add timbi to x, and repeat. This change allows the computation of m’0 = -m0-1 mod b instead of m’. The pseudo code of Montgomery’s algorithm follows: for (i=0; i < k; i++) do { ti = (xi • m’0) mod b; x = x + timbi; } if (x ≥ m) then x = x – m; II. APPROACH The three algorithms were used to compute x mod n in terms of addition, subtraction, multiplication, and single precision division of both single and multiple precision integers. A. Language, Platform, and Compiler Used for Implementation Microsoft C++6.0 with service pack 5 was chosen as the primary programming language. C++ was selected due to its portability, high execution speed, and suitability for performing large amount of computational work. Development and time trials were completed on a Pentium III 600 MHz processor, with 256 RAM, 10 Gb hard drive, and Windows XP Professional operating systems. B. Input/Output Specifications The program requires input and output as indicated below: • INPUT: large positive integers read in via command line variables from a batch file; there were 20 numbers in each of the following ranges {128, 256, 384, 512, 768, 1024, and 2048 bits}. The input numbers were generated pseudo-randomly in a decimal format and converted to hexadecimal to ensure that the correct number of characters/bits was used in the timing trials. The input files contained an integer set that meets the


View Full Document

MASON ECE 646 - Modular Reduction of Large Integers Using Classical, Barrett, Montgomery Algorithms

Documents in this Course
Load more
Download Modular Reduction of Large Integers Using Classical, Barrett, Montgomery Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Modular Reduction of Large Integers Using Classical, Barrett, Montgomery Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Modular Reduction of Large Integers Using Classical, Barrett, Montgomery Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?