Report

Montgomery multiplication Algorithm Under supervision of : Dr. S. Bayat-sarmadi Mohammad Farmani 2nd. Semister,1392-93 Sharif University of Technology 1 Main Topic Montgomery modular multiplication algorithm Main Article: “Montgomery Multiplication in GF(2k)” Written by: Cetin K. KOC and Tolga Acar,1998 Copyright © 2014 Hardware Security and Trust Sharif University of Technology 2 Montgomery multiplication algorithm Outline Introduction Montgomery modular multiplication of integers Montgomery modular multiplication in GF(2k) Conclusion Copyright © 2014 Hardware Security and Trust Sharif University of Technology 3 Montgomery multiplication algorithm Introduction • The importance and applications of the arithmetic operations in the Galois field GF(2k) in : • • • • Coding theory Computer algebra Cryptography …. • Importance of the exponentiation • Using a series of multiplication for The exponentiation Copyright © 2014 Hardware Security and Trust Sharif University of Technology 4 Montgomery multiplication algorithm Introduction • Cryptographic applications require fast arithmetic operations • Proposed an effective modular multiplication of integers by P.L. Montgomery 1985 • Conversion to the Montgomery domain : a : an intger M : modulus r : Radix Copyright © 2014 Hardware Security and Trust a ar mod M 2 n 1 M 2 n n r2 Sharif University of Technology 5 Montgomery multiplication algorithm Introduction 0 0 *16 mod 11 0 1 1*16 mod 11 5 • Example: M = 11 , r = 24 = 16 2 2 *16 mod 11 10 3 3 *16 mod 11 4 4 4 *16 mod 11 9 • There is a one-to-one correspondence between integers and Montgomery residues for 0 < a < M-1 5 5 *16 mod 11 3 6 6 *16 mod 11 8 7 7 *16 mod 11 2 8 8 *16 mod 11 7 9 9 *16 mod 11 1 10 10 *16 mod 11 6 Copyright © 2014 Hardware Security and Trust Sharif University of Technology 6 Montgomery multiplication algorithm Outline Introduction Montgomery modular multiplication of integers Montgomery modular multiplication in GF(2k) Conclusion Copyright © 2014 Hardware Security and Trust Sharif University of Technology 7 Montgomery multiplication algorithm Montgomery multiplication of Integers • Define: z MM ( x , y ) x yr 1 mod M • r-1 is the inverse of r mod M: • r-1r = 1 (mod M) z x yr 1 mod M ( xr )( yr )r 1 mod M xyr mod M zr mod M Copyright © 2014 Hardware Security and Trust Sharif University of Technology 8 Montgomery multiplication algorithm Montgomery multiplication of Integers • Example : 1 r 16, r 9 (16 * 9 mod 11 1) MM (5,7) 5 * 7 * 9 mod 11 7 Copyright © 2014 Hardware Security and Trust Sharif University of Technology 9 Montgomery multiplication algorithm Montgomery multiplication of Integers • Montgomery multiplication algorithm • requires no hard division just shifting • In radix 2 Input: X,Y,M Output: = , = 2− Z = 0 for i = 0 to n-1 Z = Z + xi•Y if Z is odd then Z = Z + M Z = Z/2 if Z ≥ M then Z = Z – M Copyright © 2014 Hardware Security and Trust Sharif University of Technology 10 Montgomery multiplication algorithm Montgomery multiplication of Integers • Example : • X = 7 = 0111 • Y = 5 = 0101 • M = 11 = 1011 • • • • • Z initially 0 Z = (0 + 5 + 11) / 2 = 8 Z = (8 + 5 + 11) / 2 = 12 Z = (12 + 5 + 11) / 2 = 14 Z = (14 + 0) / 2 = 7 (final result) Copyright © 2014 Hardware Security and Trust Z = 0 for i = 0 to n-1 Z = Z + xi•Y if Z is odd then Z = Z + M Z = Z/2 if Z ≥ M then Z = Z – M Sharif University of Technology 11 Montgomery multiplication algorithm Montgomery multiplication of Integers • Conversion using MM Conversion of integers to/from Montgomery residues with one MM operation x MM ( x, r 2 ) xr 2 r 1 mod M xr mod M x MM ( x ,1) x1r 1 mod M xr1r 1 mod M x Copyright © 2014 Hardware Security and Trust Sharif University of Technology 12 Montgomery multiplication algorithm Montgomery multiplication of Integers r2 x X’ 1 MM MM X’ X Copyright © 2014 Hardware Security and Trust Sharif University of Technology 13 Montgomery multiplication algorithm Outline Introduction Montgomery modular multiplication of integers Montgomery modular multiplication in GF(2k) Conclusion Copyright © 2014 Hardware Security and Trust Sharif University of Technology 14 Montgomery multiplication algorithm Montgomery multiplication in GF(2k) • Based on polynomial representation • ∈ 2 is a polynomial of length k and degree less than or equal to − 1 : • = −1 =0 = −1 −1 + −2 −2 + . . . +1 + 0 • Need an irreducible polynomial of degree • Instead of computing . in (2 ) propose to compute . . −1 in (2 ) Copyright © 2014 Hardware Security and Trust Sharif University of Technology 15 Montgomery multiplication algorithm Montgomery multiplication in GF(2k) • r : element of the field, presented by the polynomial : () • i.e. if = ( −1 … 1 0 ), then = −1 … 1 0 • = • very useful in obtaining fast implementations = 1, then there exist −1 () and ′ that : −1 + ′ = 1 • −1 () and ′ can be computed using EEA algorithm.(taught in class) • If gcd , Copyright © 2014 Hardware Security and Trust Sharif University of Technology 16 Montgomery multiplication algorithm Montgomery multiplication in GF(2k) • Definition: = −1 () • Can be computed using the following algorithm Copyright © 2014 Hardware Security and Trust Sharif University of Technology 17 Montgomery multiplication algorithm Montgomery multiplication in GF(2k) • Algorithm for Montgomery Multiplication Input : Output : Step 1. Step 2. Step 3. , , , ′() = −1 () = = ′ () = + /() Copyright © 2014 Hardware Security and Trust Sharif University of Technology 18 Montgomery multiplication algorithm Montgomery multiplication in GF(2k) • The proposed algorithm is similar to MM of integers • Only difference : the final subtraction step in the integer case is not necessary in the polynomial case • Proof: deg ≤ max deg , deg + deg − deg ≤ max 2 − 2, − 1 + − ≤−1 • Thus, c(x) is already reduced Copyright © 2014 Hardware Security and Trust Sharif University of Technology 19 Montgomery multiplication algorithm Montgomery multiplication in GF(2k) • The modular Mult. and Div. in Step 2, 3 are fast operations • Since = • The remainder operation : simply ignoring the term , ≥ • Div. by : shifting the polynomial to the right by places • Precompute ′() for step 2 • Avoided if the coefficients of () are scanned one bit at a time. Copyright © 2014 Hardware Security and Trust Sharif University of Technology 20 Montgomery multiplication algorithm Montgomery multiplication in GF(2k) = −1 () = • Can be written : = − • Recall : = − −1 =0 () = −1 −1 +−2 −2 … 1 + 0 () Copyright © 2014 Hardware Security and Trust Sharif University of Technology 21 Montgomery multiplication algorithm Montgomery multiplication in GF(2k) • = () • Starting from MSB to LSB : =0 = − 1 0 = + = () Copyright © 2014 Hardware Security and Trust Sharif University of Technology 22 Montgomery multiplication algorithm Montgomery multiplication in GF(2k) • = () − • The shift factor reverses the direction of summation(LSB to MSB) =0 = 0 − 1 = + = ()/ Copyright © 2014 Hardware Security and Trust Sharif University of Technology 23 Montgomery multiplication algorithm Montgomery multiplication in GF(2k) Bit-Level Algorithm for Montgomery Multiplication Input: , , () Output: = − Step 1. =0 Step 2. = 0 − 1 Step 3. = + () Step 4. = + 0 () Step 5. = ()/ Copyright © 2014 Hardware Security and Trust Sharif University of Technology 24 Montgomery multiplication algorithm Outline Introduction Montgomery modular multiplication of integers Montgomery modular multiplication in GF(2k) Conclusion Copyright © 2014 Hardware Security and Trust Sharif University of Technology 25 Montgomery multiplication algorithm Conclusion • We have described the bit-level algorithm for computing the product . . −1 in the (2 ) • The MMM operation would be significantly faster in SW and HW • Since, • Division changes to simple shifting • Remainder operation simply done by ignoring , ≥ • We can speed up more if we use Word-level algorithm for SW implementation Copyright © 2014 Hardware Security and Trust Sharif University of Technology 26 End of presentation, Any question?