SPI-2 Specification Team Members: Michael Johnson, Bich-Ha Phung, Sukhonthip Rueangvivatanakij, Thomas Shackelford Title: Project SPI-2 - Modulo reduction of large integers using classical, Barrett, Montgomery, and Selby-Mitchell algorithms. 1. Language, platform, and compiler used for a primary implementation (e.g., gnu C under Unix). The program portability to other platforms. • Microsoft C++ 6.0 on a Window XP Professional Platform 2. Additional software required (e.g., a library of arithmetic operations on large numbers, RSA Reference Library, etc.). • We will incorporate libraries for arithmetic operations on large integers to test a proven implementation against our implementations. 3. Detailed specification of the input and output of the program(s), including the exact format of input/output files. • INPUT: large positive integers read from a text file; there will be 20 numbers in each of the following ranges {128, 256, 512, 768, 1024, …2048}. The input numbers will be generated pseudo-randomly, and will be written in hexadecimal. The input file will contain an integer set that meets the input parameters for each of the algorithms. x = (x 2k-1…..x1, x0)b’ m = (m k-1…..m1, m0)b (with m k-1 !=0) >E 2k/m] For Selby-Mitchell, x = k[ ] (a 2n-word number) (k[0], k[1], …, k[n-1]) = (k[0] + 232k[1] + 264k[2] + …+ 232(n-1)k[2n-1]) (k[0] is least significant bit & k[2n-1] is most significant bit) m = d[ ] (an odd n-word constant where d >= 231n and d/232 >= ½ ) = (d[0], …, d[n-1])• OUTPUT: results will be written to a text file and will include for each input integer, the initial integer in hexadecimal notation, its size, the remainder (x mod m), the computation time delta, and the number of steps taken during the operation. 4. Brief description of the function performed by the program(s), including any specific references to standards and detailed descriptions of algorithms in the literature. 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. The description and pseudo code for the Selby-Mitchell algorithm comes from their Algorithms for software implementations of RSA paper. • Classical algorithm: The classical algorithm is a formalization of the ordinary l-k 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 reminder r. Each reminder 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 E 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; } • Barrett modular reduction 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 areeither less expensive in time than a multiprecision division by m or can be done as a precalculation 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 GLY Et. The pseudo code of Barrett’s algorithm given E2k div m follows: q = ((x div b k+1 GLY E k+1 ; x = x mod b k+1– (qm) mod b k+1 ; if (x < 0) then x = x + b k+1 ; while (x P Go x = x – m; • Montgomery modular reduction 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; } x = x div bk; if (x P WKHQ x = x – m; • Selby-Mitchell modular reduction algorithm: Given a 64n-bit number k and a 32n-bit modulus d it outputs a 32n-bit number k’, where k’ NPRGXOR G 7KLV WDVN LV UDSLGO\ SHUIRUPHG E\ XVLQJ D ORRN-up table of values pre-computed using modulus d, with the pre-computations dependent on a global fixed value. The idea is to reduce the length of k by 8 bits at a time. The beginning of each step assumes that k is 4n + i + 1 bytes long, (where i ranges from 4n – 1 down to 0), together with an extra bit at the most significant end which may be 1 or 0 (left over from the previous iteration). At each step the largest multiple of d that can be subtracted from k without leaving it negative is subtracted. Only the most significant 9 bits of k are examined each step, and the pre-computed table is used to determine the largest safe multiple of d. The resultant value of k has the byte under consideration set to either 0 or 1, forming the left over bit for the next subtraction.The pseudo code of the Selby-Mitchell algorithm follows: Set up the look-up table atab[i][j] (0 <= i <= 511, 0 <= j <= n) as follows: atab[0][ ] = 0; For i = 1 to 511 do { Let g be the unique integer satisfying int(g * d/232) = i – 1 and int((g + 1) * d/232) = i; atab[i][ ] = gd } where atab[i][ ] represents k, the number stored in the n + 1 words atab[i][0], …, atab[i][n] no division or exponentiation is done, merely examination of the two most significant bytes of k. Given the restrictions on d, g < 1022 for every i. for I = 4n – 1 to 0 step –1 do { j = int(k[ ] / (28i * 232)); k[ ] = k[ ] - 28i * atab[j][ ] } where it may be necessary to subtract either d or 2d from the final k in order to ensure that it is less than 232. At most one further subtraction of d will ensure that the result is less than d. 5. Procedures for testing the functionality and performance of the algorithms. The source of test vectors. We will use the same input into each of the four algorithms, although the input
View Full Document
Unlocking...