|
0
Foreword
Chapter 1
Mathematical background
1.1
Number theory
1.1.1
Basic definitions
1.1.2
Euclidean algorithms
1.1.3
Congruences
1.2
Algebra
1.2.1
Groups
1.2.2
Rings
1.2.3
Fields
1.2.4
Polynomials
1.2.5
Congruences of polynomials
1.3
Finite fields
1.3.1
Basic properties
1.3.2
Field extensions
1.3.3
Roots of irreducible polynomials
1.3.4
Bases of finite fields
1.3.5
Finite field GF(2m)
1.4
References
Chapter 2 Mod
m reduction
2.1
Integer division
2.1.1
Digit recurrrence algorithms
2.1.2
Non-restoring reducer
2.1.3
SRT reducer
2.2
Reduction mod 2k -- a
2.3
Pre-computation of 2i.k mod m
2.4
Barrett reduction algorithm
2.4.1
n-digit to (k + t)-digit reduction
2.4.2
An approximation of q
2.5
Comparison
2.6
Specific circuits
2.6.1
Mod 239 reducer
2.6.2
Mod (2192 -- 264 -- 1) reducer
2.7
FPGA implementations
2.7.1
Non-restoring reducers
2.7.2
SRT reducers
2.7.3
Reduction mod 2k -- a
2.7.4
Pre-computation of 2i.k mod m
2.7.5
Barrett reduction
2.7.6
Specific circuits
2.8
Comments and conclusions
2.9
References
Chapter 3 Mod
m operations
3.1
Addition mod m
3.2
Subtraction mod m
3.3
Adder- – subtractor mod m
3.4
Multiplication mod m
3.4.1
Multiply and reduce
3.4.2
Double, add, and reduce
3.4.3
Montgomery multiplication
3.4.3.1
Montgomery arithmetic
3.4.3.2
Montgomery product
3.4.4
Comparison
3.5
Exponentiation
3.6
FPGA implementations
3.7
Comments and conclusions
3.98
References
Chapter 4
Operations over GF(p)
4.1
Euclidean algorithm
4.1.1
Integer division
4.1.2
Multiplication and subtraction
4.1.3
Mod p division
4.2
Binary algorithm
4.3
Plus-minus algorithm
4.4
Fermat’s little theorem
4.5
Comparison
4.6
FPGA implementations
4.6.1
Euclidean algorithm
4.6.2
Binary algorithm
4.6.3
Plus-minus algorithm
4.6.4
Fermat's little theorem
4.7
Comments and conclusions
4.8
References
Chapter 5
Operations over Zp [x] / f(x)
5.1
Addition and subtraction mod f(x)
5.2
Multiplication mod f(x)
5.2.1
Two-step multiplication
5.2.2
Serial multiplication
5.3
Exponentiation mod f(x)
5.4
Optimal extension fields
5.5
FPGA implementations
5.6
Comments and conclusions
5.7
References
Chapter 6
Operations over GF(pn)
6.1.
Euclidean algorithm
6.2. Binary
algorithm
6.3.
Reduction to multiplications over GF(pm) and inversion over Zp
6.4
Optimal extension fields
6.5
FPGA implementations
6.6
Comments and conclusions
6.7
References
Chapter 7
Operations over GF(2m) - —Polynomial bases
7.1
Multiplication
7.1.1
Two-step classic multiplication
7.1.2
Interleaved multiplication
7.1.3
Matrix-vector multipliers
7.1.4
Montgomery multiplication
7.2
Squaring
7.3
Exponentiation
7.4
Inversion
7.5
Important irreducible polynomials
7.5.1
Equally spaced polynomials (ESPs)
7.5.2
General irreducible polynomials
7.5.3
All-one polynomials (AOPs)
7.5.4
Trinomials
7.5.5
Pentanomials
7.6
FPGA implementations
7.7
Comments and conclusions
7.8
References
Chapter 8
Operations over GF(2m) - —Normal bases
8.1
Some properties of normal bases
8.2
Squaring
8.3
Multiplication
8.4
Exponentiation
8.5
Inversion
8.6
Optimal normal bases
8.7
FPGA implementations
8.8
Comments and conclusions
8.9
References
Chapter 9
Operations over GF(2m) - —Other bases
9.1
Dual bases
9.2
Triangular bases
9.3
References
Chapter 10
Elliptic curve cryptography
10.1
Public-key cryptography
10.2
Elliptic curve over a finite field
10.3
Group law
10.4
Point multiplication
10.4.1
Definition
10.4.2 Basic
algorithms
10.4.3 Some
alternative methods
10.4.3.1
Non-adjacent forms
10.4.3.2
Projective coordinates
10.4.3.3
Montgomery algorithm
10.4.3.4
Frobenius map
10.5
Example of implementation
10.5.1
Computation resources
10.5.2
Point addition
10.5.3 Point
multiplication
10.6
FPGA implementations
10.7
References
Appendix A:
p = 2192 - 264 - 1
Appendix B:
oOptimal eExtension fFields
B.1
GF(23917)
B.2
GF((232 - 387)6)
Appendix C:
Bbinary Ffields
C.1 GF(2163)
C.2 GF(2233)
Appendix D:
Ada vs. VHDL
|
