Cryptography Arithmetic: Algorithms and Hardware Architectures (Advances in Information Security Book 77)

Modern cryptosystems, used in numerous applications that require secrecy or privacy - electronic mail, financial transactions, medical-record keeping, government affairs, social media etc. - are based on sophisticated mathematics and algorithms that in implementation involve much computer arithmetic. And for speed it is necessary that the arithmetic be realized at the hardware (chip) level. This book is an introduction to the implementation of cryptosystems at that level. The aforementioned arithmetic is mostly the arithmetic of finite fields, and the book is essentially one on the arithmetic of prime fields and binary fields in the context of cryptography. The book has three main parts. The first part is on generic algorithms and hardware architectures for the basic arithmetic operations: addition, subtraction, multiplication, and division. The second part is on the arithmetic of prime fields. And the third part is on the arithmetic of binary fields. The mathematical fundamentals necessary for the latter two parts are included, as are descriptions of various types of cryptosystems, to provide appropriate context. This book is intended for advanced-level students in Computer Science, Computer Engineering, and Electrical and Electronic Engineering. Practitioners too will find it useful, as will those with a general interest in "hard" applications of mathematics. -- Provided by publisher cryptogarifm.pdf......Page 0 Preface......Page 7 Acknowledgements......Page 9 Contents......Page 10 Part I......Page 14 1 Basic Computer Arithmetic......Page 15 1.1 Addition......Page 16 1.1.1 Serial......Page 17 1.1.2 Carry-Ripple......Page 20 1.1.3 Parallel-Prefix......Page 21 1.1.4 Carry-Select......Page 29 1.1.5 High Precision......Page 32 1.1.6 Signed Numbers and Subtraction......Page 33 Ones'-Complement......Page 35 Two's Complement......Page 38 1.2 Multiplication......Page 41 1.2.1 Sequential......Page 43 1.2.2 High Radix......Page 47 1.2.3 Parallel and Sequential-Parallel......Page 53 1.2.4 High Precision......Page 55 1.2.6 Squaring......Page 57 1.3 Division......Page 59 Signed Operands......Page 76 References......Page 79 Part II......Page 81 2.1 Congruences......Page 82 2.2.1 Addition, Subtraction, and Multiplication......Page 84 2.2.2 Division......Page 85 2.3 Generators and Primitive Roots......Page 86 Discrete Logarithm Problem......Page 88 2.4 Quadratic Residues and Square Roots......Page 89 2.5 The Chinese Remainder Theorem......Page 93 2.6 Residue Number Systems......Page 96 References......Page 98 3 Modular-Arithmetic Cryptosystems......Page 99 3.1.1 RSA Algorithm......Page 100 3.1.2 Rabin Algorithm......Page 103 3.1.3 El-Gamal Algorithm......Page 104 3.1.4 Massey-Omura Algorithm......Page 105 3.1.5 Goldwasser-Micali Algorithm......Page 107 3.2 Key Agreement......Page 109 3.3.1 El-Gamal Algorithm......Page 110 3.3.2 NIST Algorithm......Page 112 References......Page 113 4 Modular Reduction......Page 115 4.1 Barrett Reduction......Page 116 4.1.1 Basic Algorithm......Page 118 4.1.2 Extension of Basic Algorithm......Page 122 4.1.3 Implementation......Page 124 4.2 Montgomery Reduction......Page 128 4.2.1 Algorithm......Page 129 4.2.2 Implementation......Page 132 4.3 Lookup-Table Reduction......Page 139 4.4 Special-Moduli Reduction......Page 142 Implementation......Page 144 References......Page 150 5.1 Addition......Page 152 5.1.1 Generic Structures......Page 153 5.1.2 Special-Moduli......Page 156 5.1.3 Subtraction......Page 160 Special Moduli......Page 161 5.2 Multiplication......Page 163 5.2.1 Multiplication with Direct Reduction......Page 165 5.2.2 Multiplication with Barrett Reduction......Page 172 5.2.3 Multiplication with Montgomery Reduction......Page 174 5.2.4 Multiplication with Special Moduli......Page 181 References......Page 189 6.1 Exponentiation......Page 191 Exponentiation with Direct Reduction......Page 195 Exponentiation with Montgomery Reduction......Page 197 6.2 Inversion and Division......Page 201 References......Page 209 Part III......Page 210 7.1.1 Groups......Page 211 7.1.2 Fields......Page 215 7.2 Ordinary Polynomial Arithmetic......Page 217 7.3 Polynomial Arithmetic Over Finite Fields......Page 222 7.4 Construction of GF(pm)......Page 225 References......Page 230 8.1 Basic Curves......Page 231 8.1.1 Point Addition: Geometric Interpretation......Page 232 8.1.2 Point Addition and Multiplication: Algebraic Interpretation......Page 234 8.2 Elliptic Curves Over Finite Fields......Page 236 8.2.1 y2 = x3 + ax + b Over GF(p)......Page 237 8.2.2 y2 + xy = x3 + ax + b Over GF(2m)......Page 239 8.3 Point-Multiplication Implementation......Page 242 8.4 Projective Coordinates......Page 244 References......Page 247 9 Elliptic-Curve Cryptosystems......Page 248 9.1 Message Encryption......Page 249 9.1.2 Massey-Omura System......Page 250 9.1.3 Menezes-Vanstone System......Page 251 9.2.1 Diffie-Hellman System......Page 252 9.2.3 Menezes-Qu-Vanstone System......Page 253 9.3 Digital Signatures......Page 254 References......Page 256 10.1 Addition and Subtraction......Page 258 10.2 Multiplication and Squaring......Page 260 10.2.1 Direct Multiplication......Page 261 10.2.2 Montgomery Multiplication and Squaring......Page 272 10.3 Reduction......Page 277 10.4 Exponentiation, Inversion, and Division......Page 282 References......Page 292 11 Normal-Basis Arithmetic......Page 293 11.1 Addition, Subtraction, and Squaring......Page 294 11.2 Multiplication......Page 296 Implementation......Page 305 11.3 Exponentiation, Inversion, and Division......Page 307 References......Page 316 A.1 Part II of Main Text......Page 318 A.2 Part III of Main Text......Page 328 References......Page 334 Index......Page 335