ANSI X9.62 (1998) - The Elliptic Curve Digital Signature Algorithm (ECDSA)

Cover......Page 1
ToC......Page 3
List of Tables......Page 7
Foreword......Page 8
2.1 Definitions and Abbreviations......Page 14
2.2 Symbols and Notation......Page 19
3.2 the Use of the ECDSA Algorithm......Page 22
3.4 Annexes......Page 23
4 Mathematical Conventions......Page 24
4.1.2 The Finite Field F_{2^M}......Page 25
4.2.1 Point Compression Technique for Elliptic Curves over F_p (Optional)......Page 30
4.3.1 Integer-to-Octet-String Conversion......Page 31
4.3.2 Octet-String-to-Integer Conversion......Page 32
4.3.4 Octet-String-to-Field-Element Conversion......Page 33
4.3.6 Point-to-Octet-String Conversion......Page 34
4.3.7 Octet-String-to-Point Conversion......Page 35
5 The Elliptic Curve Digital Signature Algorithm (ECDSA)......Page 36
5.1.1 Elliptic Curve Domain Parameters and their Validation over F_p......Page 37
5.1.2 Elliptic Curve Domain Parameters and their Validation over F_{2^M}......Page 38
5.2.2 Public Key Validation (Optional)......Page 40
5.3 Signature Generation......Page 41
5.3.4 The Signature......Page 42
5.4.2 Modular Computations......Page 43
6.1 Syntax for Finite Field Identification......Page 44
6.3 Syntax for Elliptic Curve Domain Parameters......Page 47
6.4 Syntax for Public Keys......Page 48
6.6 ASN.1 Module......Page 52
A.1.1 The MOV Condition......Page 57
A.2.1 A Probabilistic Primality Test......Page 58
A.2.2 Checking for Near Primality......Page 59
A.3.2 Selecting an Appropriate Curve and Point......Page 60
A.3.3 Selecting an Elliptic Curve Verifiably at Random......Page 62
A.3.4 Verifying that an Elliptic Curve was Generated at Random......Page 64
A.4.1 Algorithm Derived From Fips 186......Page 65
B.1 the Finite Field F_p......Page 68
B.2.1 Polynomial Bases......Page 69
B.2.3 Normal Bases......Page 72
B.2.4 Gaussian Normal Bases......Page 73
B.3 Elliptic Curves Over F_p......Page 74
B.4 Elliptic Curves Over F_{2^M}......Page 76
C.1 Table of Gnb for F_{2^M}......Page 80
C.2 Irreducible Trinomials Over F 2......Page 91
C.3 Irreducible Pentanomials Over F 2......Page 95
C.4 Table of Fields F_{2^M} Which Have Both an ONB and a TPB Over F_2......Page 101
D.1.2 Inversion in a Finite Field......Page 102
D.1.3 Generating Lucas Sequences......Page 103
D.1.4 Finding Square Roots Modulo a Prime......Page 104
D.1.5 Trace and Half-Trace Functions......Page 105
D.1.6 Solving Quadratic Equations over F_{2^M}......Page 106
D.1.8 Computing the Order of a Given Integer Modulo a Prime......Page 107
D.2.1 GCD's over a Finite Field......Page 108
D.2.3 Change of Basis......Page 109
D.2.4 Checking Binary Polynomials for Irreducibility......Page 112
D.3.1 Finding a Point on an Elliptic Curve......Page 113
D.3.2 Scalar Multiplication (Computing a Multiple of an Elliptic Curve Point)......Page 114
E.1.1 Evaluating Jacobi Symbols......Page 116
E.1.3 Exponentiation Modulo a Polynomial......Page 118
E.1.4 Factoring Polynomials over F_p (Special Case)......Page 119
E.2.1 Overview......Page 120
E.2.2 Class Group and Class Number......Page 121
E.2.3 Reduced Class Polynomials......Page 122
E.3.1 Overview......Page 125
E.3.2 Finding a Nearly Prime Order over F_p......Page 126
E.3.3 Finding a Nearly Prime Order over F_{2^M}......Page 130
E.3.4 Constructing a Curve and Point (Prime Case)......Page 132
E.3.5 Constructing a Curve and Point (Binary Case)......Page 135
Annex F (Informative) An Overview of Elliptic Curve Systems......Page 138
Annex G (Informative) The Elliptic Curve Analog of the Dsa (ECDSA)......Page 139
H.1 the Elliptic Curve Discrete Logarithm Problem......Page 142
H.1.1 Software Attacks......Page 143
H.1.2 Hardware Attacks......Page 144
H.1.3 Key Length Considerations......Page 145
H.2 Elliptic Curve Domain Parameters......Page 146
H.3 Key Pairs......Page 148
H.4 ECDSA......Page 149
1.3 Signature Generation for ECDSA......Page 151
I.4 Signature Verification for ECDSA......Page 152
J.1 Examples of Data Conversion Methods......Page 154
J.2.1 An Example with m = 191 (Trinomial Basis)......Page 158
J.2.2 An Example with m = 239 (Trinomial Basis)......Page 161
J.3.1 An Example with a 192-bit Prime p......Page 165
J.3.2 An Example with a 239-bit Prime p......Page 168
J.4.1 3 Examples with m = 163......Page 172
J.4.2 An Example with m = 176......Page 174
J.4.3 5 Examples with m = 191......Page 175
J.4.5 5 Examples with m = 239......Page 178
J.4.6 An Example with m = 272......Page 181
J.4.7 An Example with m = 304......Page 182
J.4.8 An Example with m = 359......Page 183
J.4.9 An Example with m = 368......Page 184
J.4.10 An Example with m = 431......Page 185
J.5.1 3 Examples with a 192-bit Prime......Page 186
J.5.2 3 Examples with a 239-bit Prime......Page 188
J.5.3 An Example with a 256-bit Prime......Page 190
Annex K (Informative) References......Page 191