Cryptographic Algorithms on Reconfigurable Hardware- P7: This chapter presents a complete outhne for this Book. It explains the main goals pursued, the strategies chosen to achieve those goals, and a summary of the material to be covered throughout this Book. | Field Multiplication 159 Algorithm Modular Reduction Using General Irreducible Polynomials Require The degree m of the irreducible polynomial the operand C to be reduced and k the number of bits that can be reduced at once. Ensure The field polynomial defined as C C mod P with a length of m bits. i Nk VI 2 shift 2m 2 k 1 3 for i from 0 to Nk do 4 A C n k i n k i l n k-i k l J 5 S Highdivtable A - 6 Pshifted LeftShift Paddedtable S shift - 7 C C Pshifted- 8 shift shift fc 9 end for 10 Return C is computed the amount of shift needed to apply properly the method outlined in figure . Then in each iteration of the loop in lines 3-9 k bits of C are reduced. In line 4 the k bits of C to be reduced are obtained. This information is used in line 5 to compute the appropriate scalar S needed to obtain the result of equation . In line 6 the S-th entry of the table Paddedtable is left shifted shift positions so that in line 7 the operation C 2shlft S P can be finally computed allowing the effective reduction of k bits at once. Then in line 8 the variable shift is updated in order to continue the reduction process. Algorithm performs a total of Nk iterations. At each iteration of the algorithm the look-up tables Highdivtable and Paddedtable are accessed once each. In line 7 and XOR addition is executed implying that the complexity cost of the general reduction method discussed in this section is given as Additions 2Nk . Look-up table size in bits 2k rn 2k . Interleaving Multiplication In this Subsection we discuss one of the simplest and most economical binary field multiplier schemes the serial interleaving multiplication algorithm. Multiplication by a Primitive Element Let P x po pix pix2 . pm-ixm 1 xm be an m-degree irreducible polynomial over GF 2 . Let also a be a root of p x . p a 0. Then the set 1 a a2 . am-1 is a basis for GF 2m commonly called the polynomial canonical basis of the field 221 An element A e GF 2m is expressed m l in this basis
