Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Cryptographic Algorithms on Reconfigurable Hardware- P4: 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. | 4 1 Basic Concepts of the Elementary Theory of Numbers 69 Algorithm 4.2 Extended Euclidean Algorithm as Reported in 228 Require Two positive integers a and b where a b. Ensure d gcd a 6 and the two integers x y that satisfy the equation ax by d. 1 if 6 0 then 2 d a x 1 y 0 3 Return d x y 4 end if 5 xi 0 x2 1 yi 1 y2 0 6 while b 0 do 7 q a div b r a mod b 8 x x2 - qxi y y2 - qyi 9 a b b r x2 xi 10 xi x y2 yi yi y 11 end while 12 d a x x2 y y2 13 Return d x y it can be seen that the exponentiation problem can be solved by multiplying numbers that never exceed the modulus m. Rather than computing the exponentiation by performing e 1 modular multiplications as e lmults. b a a . a mod m we employ a much more efficient method that has complexity O log e . For example if we want to compute 1226 mod23 we can proceed as follows 122 144 6 mod 23 124 62 36 13 mod 23 128 132 169 8 mod 23 1216 82 64 18 mod 23. Then 1226 i2 16 8 2 1216 128 122 18 8 6 864 13 mod 23. This algorithm is known as the binary exponentiation algorithm 178 whose details will be discussed in 5.4. Chinese Remainder Theorem CRT This theorem has a tremendous importance in cryptography. It can be defined as follows Let pi for i 1 2 . k be pairwise relatively prime integers i.e. gcd pi pj 1 for Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 70 4. Mathematical Background Given Ui G 0 Pi 1 for i 1 2 . k the Chinese remainder theorem states that there exists a unique integer u in the range 0 P 1 where P P1P2 Pk such that u Ui mod pt . 4.2 Finite Fields We start with some basic definitions and then arithmetic operations for the finite fields are explained. 4.2.1 Rings A ring R is a set whose objects can be added and multiplied satisfying the following conditions Under addition R is an additive Abelian group. For all x y z G R we have x y z xy xz y z x yx zx For all x t G R we have xy z x yz . There exists an element e G R such that ex xe x for all x G R. The integer numbers the .
