Modular multiplication using Montgomery method(ECE545 Final Project)BackgroundIntroduction of Montgomery methodBasic IdeaVerificationEfficiencyEvaluationApply Montgomery Method to Modular ExponentiationImplementation & ComparisonImplementation & Comparison (con’t)ConclusionReferenceModular multiplication using Montgomery method(ECE545 Final Project)Haoxin (Larry) SongID:000132603Date: 12/15/20002Background The widely use of Public key Crytosystem Two way of implementation High Level Language: Portable (one implementation works on different processor), but SLOW. Assembly Language:Not portable (Development effort repeated for different processor), FAST Solution: Use efficient algorithm in portable Language to approch the speed of assembly Language.3Introduction of Montgomery method Modular multiplication:Basic operation of public key cryptosystems(The performance depends mostly on speed of operation AEmod N) Montgomery method:An algorithm to speed up modular multiplication4Basic Idea Transfer the operant to fast domain:A’=AR mod NB’=BR mod N Redefine Multiplication in the new domain:C’=Product’(A,B,N,R)=ABR-1mod N Transfer the result back to original domain:C=C’ R-1mod N5Verification Verification: C’=Product’(A’,B’,N,R)=(AR mod N)(BR mod N) R-1mod N=ABR mod N; C = C’ R-1mod N= ABRR-1mod N= AB mod N6Efficiency Montgomery Theorem:(T+MN)/R=TR-1mod NWhere N and R be relatively-prime integers, M=TN’ mod R, N’=-N-1mod R Replace modular division by N with multiplication followed by divisio by R.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.7EvaluationNumber of single precision multiplication: Classic reduction A mod N: (n-t)(t+2)(n: size of A; t: size of N) Montgomery reduction TR-1mod N: t(t+1)(t: size of N)bittimeSize of N*(Note time for Montgomery is independent of input)8Apply Montgomery Method to Modular ExponentiationNote: The extra transfomation C->C’, A->A’, C’->C execute only once before or after the loop;Within the loop, use Montgomery Multiplication instead of Classic Method to speed up the procedure.9Implementation & Comparison Montgomery Method was implemented according to Algorithm described in Ref.1 (14.36) Comparison of Montgomery and Classic Method10Implementation & Comparison (con’t)Pic.2 log(time) vs. size forModular ExponentiationPic.1 log(time) vs. size forModular Multiplicationooooo*****bitlog(time sec)******oooooobitlog(time sec)O: Montgomery Implementation*: Classic Implementation11Conclusion 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.12Reference 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, 1985Thank
View Full Document
Unlocking...