Cryptographic Algorithms on Reconfigurable Hardware- P6: 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. | Modular Exponentiation Operation 129 P m k 2 Pre-comp mults 10 Sqrs 5 mults 17. Precomp. Sequence æ1 x2 x3. Main sequence . 2 _. 4 _ 7 14 .28 29 58 Az ds 7 ds 7 ds 7 tAz 7 ds 7 ds ds 118 2-236 2-472 2-475 950 J 1900 _ a 1903. Octal e 1903 Oil 1011011U 2 P m k 4 Pre-comp mults 9 Sqrs 3 mults 16. Precomp. Sequence x1 x2 - x3 x5 x7. Main sequence 3 _ _ r12 -4 t24 - -r29 - t58 - -r116 -r232 AZ ds ds KAZ 7 ds 7 ds 7 ds 1 r ds . 237 474 948 1896 1903 X ds 7 ds 7 ds 7 ds Hexa e 1903 011101101111 2 P m fc 6 Pre-comp mults 8 Sqrs 2 mults . 16. Precomp. Sequence x1 a 2 a 3 x6 x7 x14 a 15. Main sequence 7 . 14 28 56 112 118 236 472 AZ 7 ds ds ds . AZ 7 ds 7 ds ds 944 1888 1903 7 ds 7 ds 7 ds However none of the above deterministic methods is able to find the shortest addition chain3 for e 1903. Adaptive Window Strategy The adaptive or sliding window strategy is quite useful for exponentiations with extremely large exponents . exponents with bit length greater than 128 bits mainly because of its ability to adjust its method of computation according to the specific form of the exponent at hand. This adjustment is done by partitioning the input exponent into a series of variable-length zero and nonzero words called windows. As opposed to the traditional window method discussed in the previous section the sliding window algorithm provides a performance tradeoff in the sense that allows the processing of variable-length zero and nonzero digits. The main goal pursued by this strategy is to try to maximize the number and length of zero words while using relatively large values of k. A sliding window exponentiation algorithm is typically divided into two phases exponent partitioning and the field exponentiation computation itself. 3 Addition chains are formally defined in . Please purchase PDF Split-Merge on to remove this watermark. 130 5. Prime Finite Field Arithmetic In the first phase the exponent e is decomposed into zero and nonzero words
