Page 10 - Hardware Implementation of Finite-Field Arithmetic
P. 10
Co n t e n t s ix
10.3 Group Law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
10.4 Point Multiplication . . . . . . . . . . . . . . . . . . . . . 292
10.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . 292
10.4.2 Basic Algorithms . . . . . . . . . . . . . . . . . 293
10.4.3 Some Alternative Methods . . . . . . . . 294
10.5 Example of Implementation . . . . . . . . . . . . . . 304
10.5.1 Computation Resources . . . . . . . . . . . 305
10.5.2 Point Addition . . . . . . . . . . . . . . . . . . . 305
10.5.3 Point Multiplication . . . . . . . . . . . . . . 306
10.6 FPGA Implementation . . . . . . . . . . . . . . . . . . . 310
10.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
192
A p = 2 – 2 – 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
64
A.1 Hexadecimal Representation . . . . . . . . . . . . . . 313
A.2 mod p Reduction . . . . . . . . . . . . . . . . . . . . . . . . 313
A.2.1 Generic Sequential Circuit . . . . . . . . . . . 313
A.2.2 Specific Combinational Circuit. . . . . . . . 314
A.2.3 FPGA Implementation . . . . . . . . . . . . . 314
A.3 mod p Addition and Subtraction . . . . . . . . . . . 314
A.4 mod p Multiplication . . . . . . . . . . . . . . . . . . . . . 315
A.4.1 Generic Circuit . . . . . . . . . . . . . . . . . . . 315
A.4.2 Specific Circuit . . . . . . . . . . . . . . . . . . . 315
A.5 mod p Exponentiation . . . . . . . . . . . . . . . . . . . . 316
A.6 mod p Division . . . . . . . . . . . . . . . . . . . . . . . . . . 317
B Optimal Extension Fields . . . . . . . . . . . . . . . . . . . . . . 319
17
B.1 GF(239 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
B.1.1 VHDL Models and Constant
Definitions . . . . . . . . . . . . . . . . . . . . . . . 319
B.1.2 FPGA Implementations . . . . . . . . . . . . 320
B.2 GF((2 − 387) ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
32
6
B.2.1 Constants . . . . . . . . . . . . . . . . . . . . . . . . 321
B.2.2 mod p Reduction . . . . . . . . . . . . . . . . . . 323
B.2.3 mod p Addition and Subtraction . . . . . . 323
B.2.4 mod p Multiplication . . . . . . . . . . . . . . 324
B.2.5 mod p Division . . . . . . . . . . . . . . . . . . . 324
B.2.6 mod (x − 2) Multiplication . . . . . . . . . 325
6
B.2.7 mod (x − 2) Division . . . . . . . . . . . . . . 326
6
C Binary Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
C.1 GF(2 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
163
C.1.1 mod f(x) Multiplication . . . . . . . . . . . . 331
C.1.2 mod f(x) Division . . . . . . . . . . . . . . . . . 331
C.1.3 Squaring . . . . . . . . . . . . . . . . . . . . . . . . . 332
C.1.4 Elliptic-Curve Operations . . . . . . . . . . 332
