Name : Haoxin (Larry) SongTable of content:ECE 543 Final Project Report Modular Multiplication using Montgomery method Name : Haoxin (Larry) Song ID:000132603 Professor: Dr. Kris Gaj Table of content: 1.introduction 2 2.Analysis 2 2.1 Basic idea 2.2 Verification 2.3 Montgomery Theorem 2.4 Efficiency 3. Implementation 3 3.1 Montgomery Multiplication algorithm 3. 2 Program output 4. Result and analysis 5 5. Conclusion 7 6. Reference 7 Appendix A (Source code) 8 main() function 8 generate operands 11 Montgomery Multiplication 12 Classic Multiplication 13 Modular Exponentiation (Montgomery) 16 Modular Exponentiation (Classic) 17 A’=AR mod N 18 C’=A’B’R-1 mod N 20 C=C’R-1 mod N 22 Basic function (shift, add, sub etc.) 241. Introduction: Montgomery method is considered as a fastest algorithm for modular multiplication reported in the open literature. It is an algorithm to speed up modular multiplication, thus speedup modular exponentiation and porformance of the cryposystem. 2. Analysis : 2.1 Basic idea : • Transfer the operant to fast domain: A’=AR mod N B’=BR mod N • Redefine Multiplication in the new domain: C’=Product’(A,B,N,R)=ABR-1 mod N • Transfer the result back to original domain: C=C’ R-1 mod N 2.2 Verification: C’=Product’(A’,B’,N,R) =(AR mod N)(BR mod N) R-1 mod N =ABR mod N; C = C’ R-1 mod N = ABRR-1 mod N = AB mod N 2.3 Montgomery Theorem: (T+MN)/R=TR-1 mod N Where N and R be relatively-prime integers, (M=TN’ mod R, N’=-N-1 mod R) Replace modular division by N with multiplication followed by divisio by R. 2.4 Efficiency : Choose R as power of base (i.e. 2n, if multiple precision integers are represented with base 2) , division by R and modulo R become simple.3. Implementation : 3.1 Montgomery Multiplication algorithm : INPUT: integers A = (An-1 … A1 A0)b, B = (Bn-1 _ _ _ B1 B0)b, N = (Nn-1 … N1 N0)bwith 0 < A,B < N, R = bn with gcd(N; b) =1,and N’ = -N-1 mod b. OUTPUT: ABR-1 mod N. 1. X 0. (Notation: X = (Xn Xn-1 …X1 X0) b.) 2. For i from 0 to (n - 1) do the following: 2.1 ui= (X0+ Ai B0)N’ mod b. 2.2 X =(X + AiB + uiN)/b. 3. If X>N then X=X-N. 4. Return(X). 3. 2 Program output: Input size of operand, program will generate big interge randomly : r ECE543 project SCI-3 Montgomery Multiplication. s: to choose the size of operatant. m: to compute multiplication with Montgomery Method. c: to compute multiplication with Classic Method. e: to compute exp with Montgomery Method. E: to compute Exp with Classic Mothod. q: to quit. s Input size of operant (8-2048):128 Big integer A, B, N, was randomly generated! Run Modular Multiplication in both Montgomery and Classic Method: s: to choose the size of operatant. m: to compute multiplication with Montgomery Method. c: to compute multiplication with Classic Method. e: to compute exp with Montgomery Method. E: to compute Exp with Classic Mothod. q: to quit.m Computing AB mod N in Montgomery Method, please wait... Time used for Montgomery Multiplication: 0sec 20ms Finished! AB mod N(Montgomery), time used: 0sec 70ms s: to choose the size of operatant. m: to compute multiplication with Montgomery Method. c: to compute multiplication with Classic Method. e: to compute exp with Montgomery Method. E: to compute Exp with Classic Mothod. q: to quit. c Computing AB mod N in Classic Method, please wait... Finished! AB mod N(Classic), time used: 0sec 30ms Run Modular Exponentiation in both Montgomery and Classic Method: s: to choose the size of operatant. m: to compute multiplication with Montgomery Method. c: to compute multiplication with Classic Method. e: to compute exp with Montgomery Method. E: to compute Exp with Classic Mothod. q: to quit. e Computing A^B mod N in Montgomery Method, please wait... Finished! A^B mod N(Montgomery), time used: 3sec 335ms s: to choose the size of operatant. m: to compute multiplication with Montgomery Method. c: to compute multiplication with Classic Method. e: to compute exp with Montgomery Method. E: to compute Exp with Classic Mothod. q: to quit. E Computing A^B mod N in Classic Method, please wait...Finished! A^B mod N(Classic), time used: 4sec 787ms Quit: s: to choose the size of operatant. m: to compute multiplication with Montgomery Method. c: to compute multiplication with Classic Method. e: to compute exp with Montgomery Method. E: to compute Exp with Classic Mothod. q: to quit. q 4. Result and analysis:By observing these table and curves obtained from Montgomery implementation, we verified from the practice point of view that Montgomery Multiplication can be used to speedup the Modular Multiplication.5. Conclusion: Montgomery Method, integrated with multiple-precision multiplication, can be used to speedup Modular Exponentiation, thus improve the performance of Public Key Cryposystems. It can be used concurrently with other approch which focus on reducing the number of Multiplicaton and reduction. 6. Reference: 1. "A Cryptographic Library for the Motorola DSP56000," Proc. EUROCRYPT'90, 2. "Handbook of Applied Cryptology," chapter 14.3.2 3. "Comparison of Three Modular Reduction Functions," Proc. CRYPTO'93, 4. "Modular Multiplication without Trial Division," Mathematics of Computation, vol. 44, 1985Appendix A: (Source code) #include "stdio.h" #include "stdlib.h" #include "string.h" #include "math.h" #include "time.h" #include <sys/timeb.h> short unsigned int A[128], B[128], N[128], R[129]; int n=2048; int NumOfInt; void start(); void gen_op(); // void expe(); void multi(); void ClassicMult(); void ClassicExp(); // void MontMult(); void MultPreMult(); void Addition(); void Subtraction(); void LeftShiftArray(); void RightShiftArray(); void MontReduct(); // int GetValue(); void Set1(); void Set0(); int compare(); // //Main////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// main() { int Index; //initialize A, B, N for (Index=0;Index<=127; Index++) { A[Index]=2*rand()+1; B[Index]=2*rand()+1; N[Index]=2*rand()+1; R[Index]=0; } //set A,B as odd, N as odd /////////////////////////// printf("ECE543 project SCI-3 Montgomery Multiplication.\n"); start(); return 0; }//Start//////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////
View Full Document
Unlocking...