Page 9 - Hardware Implementation of Finite-Field Arithmetic

viii Co n t e n t s

7.7.4 Mastrovito Multipliers, Second
Version . . . . . . . . . . . . . . . . . . . . . . . . . . 225
7.7.5 Interleaved Multiplication,
Advanced Version . . . . . . . . . . . . . . . 225
7.7.6 Montgomery Multipliers . . . . . . . . . . 225
7.7.7 Classic Squaring . . . . . . . . . . . . . . . . . 227
7.7.8 LSB First Squarer, Second
Version . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.7.9 Montgomery Squarer . . . . . . . . . . . . . 228
7.7.10 Binary Exponentiation . . . . . . . . . . . . 228
7.7.11 Montgomery Exponentiation . . . . . . . 229
7.7.12 Division . . . . . . . . . . . . . . . . . . . . . . . . . 229
7.7.13 Extended Euclidean Algorithm
(EEA) for Inversion . . . . . . . . . . . . . . . 229
7.7.14 Modified Almost Inverse Algorithm

(MAIA) for Inversion . . . . . . . . . . . . . 230
7.7.15 Important Irreducible
Polynomials . . . . . . . . . . . . . . . . . . . . . 230
7.8 Comments and Conclusions . . . . . . . . . . . . . . 231
7.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

m
8 Operations over GF(2 )—Normal Bases . . . . . . . . . 235
8.1 Some Properties of Normal Bases . . . . . . . . . . 236
8.2 Squaring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.3 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.4 Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . 249
8.5 Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
8.6 Optimal Normal Bases . . . . . . . . . . . . . . . . . . . 259
8.7 FPGA Implementations . . . . . . . . . . . . . . . . . . 264
8.7.1 Multiplier . . . . . . . . . . . . . . . . . . . . . . . 265
8.7.2 Exponentiation . . . . . . . . . . . . . . . . . . . 265
8.7.3 Inversion . . . . . . . . . . . . . . . . . . . . . . . . 266
8.7.4 Type-I Optimal Normal Basis
Multiplier with AOPs . . . . . . . . . . . . . 266
8.8 Comments and Conclusions . . . . . . . . . . . . . . 266
8.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
m
9 Operations over GF(2 )—Other Bases . . . . . . . . . . 269
9.1 Dual Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
9.2 Triangular Bases . . . . . . . . . . . . . . . . . . . . . . . . . 277
9.3 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284

10 An Example of Application—Elliptic Curve
Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
10.1 Public-Key Cryptography . . . . . . . . . . . . . . . . 287
10.2 Elliptic Curve over a Finite Field . . . . . . . . . . 288