- iv -
6 ASN.1 SYNTAX............................................................................................................................................... 18
6.1 S
YNTAX FOR FINITE FIELD IDENTIFICATION................................................................................................... 18
6.2 S
YNTAX FOR FINITE FIELD ELEMENTS AND ELLIPTIC CURVE POINTS ............................................................ 20
6.3 S
YNTAX FOR ELLIPTIC CURVE DOMAIN PARAMETERS .................................................................................. 20
6.4 S
YNTAX FOR PUBLIC KEYS............................................................................................................................ 21
6.5 S
YNTAX FOR DIGITAL SIGNATURES............................................................................................................... 24
6.6 ASN.1 M
ODULE............................................................................................................................................ 24
ANNEX A (NORMATIVE) NORMATIVE NUMBER-THEORETIC ALGORITHMS .................................... 29
A.1 A
VOIDING CRYPTOGRAPHICALLY WEAK CURVES ......................................................................................... 29
A.1.1 The MOV Condition............................................................................................................................ 29
A.1.2 The Anomalous Condition................................................................................................................... 29
A.2 P
RIMALITY .................................................................................................................................................... 29
A.2.1 A Probabilistic Primality Test............................................................................................................. 29
A.2.2 Checking for Near Primality............................................................................................................... 30
A.3 E
LLIPTIC CURVE ALGORITHMS...................................................................................................................... 30
A.3.1 Finding a Point of Large Prime Order ............................................................................................... 30
A.3.2 Selecting an Appropriate Curve and Point ......................................................................................... 30
A.3.3 Selecting an Elliptic Curve Verifiably at Random .............................................................................. 31
A.3.4 Verifying that an Elliptic Curve was Generated at Random ............................................................... 32
A.4 P
SEUDORANDOM NUMBER GENERATION...................................................................................................... 33
A.4.1 Algorithm Derived from FIPS 186...................................................................................................... 33
ANNEX B (INFORMATIVE) MATHEMATICAL BACKGROUND .................................................................. 35
B.1 T
HE FINITE FIELD F
p
...................................................................................................................................... 35
B.2 T
HE FINITE FIELD F
2
m
.................................................................................................................................... 35
B.2.1 Polynomial Bases................................................................................................................................ 36
B.2.2 Trinomial and Pentanomial Bases ...................................................................................................... 37
B.2.3 Normal Bases...................................................................................................................................... 37
B.2.4 Gaussian Normal Bases ...................................................................................................................... 38
B.3 E
LLIPTIC CURVES OVER F
p
............................................................................................................................ 38
B.4 E
LLIPTIC CURVES OVER F
2
m
.......................................................................................................................... 39
ANNEX C (INFORMATIVE) TABLES OF TRINOMIALS, PENTANOMIALS, AND GAUSSIAN NORMAL
BASES........................................................................................................................................................................ 43
C.1 T
ABLE OF GNB FOR F
2
m
................................................................................................................................43
C.2 I
RREDUCIBLE TRINOMIALS OVER F
2
.............................................................................................................. 54
C.3 I
RREDUCIBLE PENTANOMIALS OVER F
2
......................................................................................................... 58
C.4 T
ABLE OF FIELDS F
2
m
WHICH HAVE BOTH AN ONB AND A TPB OVER F
2
...................................................... 64
ANNEX D (INFORMATIVE) INFORMATIVE NUMBER-THEORETIC ALGORITHMS............................. 65
D.1 F
INITE FIELDS AND MODULAR ARITHMETIC.................................................................................................. 65
D.1.1 Exponentiation in a Finite Field ......................................................................................................... 65
D.1.2 Inversion in a Finite Field .................................................................................................................. 65
D.1.3 Generating Lucas Sequences .............................................................................................................. 65
D.1.4 Finding Square Roots Modulo a Prime .............................................................................................. 66
D.1.5 Trace and Half-Trace Functions......................................................................................................... 66
D.1.6 Solving Quadratic Equations over F
2
m
............................................................................................... 67
D.1.7 Checking the Order of an Integer Modulo a Prime ............................................................................67
D.1.8 Computing the Order of a Given Integer Modulo a Prime ................................................................. 68
D.1.9 Constructing an Integer of a Given Order Modulo a Prime ............................................................... 68
D.2 P
OLYNOMIALS OVER A FINITE FIELD ............................................................................................................. 68
D.2.1 GCD’s over a Finite Field................................................................................................................... 68