1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297

This Source Code Form is subject to the terms of the Mozilla Public
License, v. 2.0. If a copy of the MPL was not distributed with this
file, You can obtain one at http://mozilla.org/MPL/2.0/.
The ECL exposes routines for constructing and converting curve
parameters for internal use.
HEADER FILES
============
eclexp.h  Exports data structures and curve names. For use by code
that does not have access to mp_ints.
eclcurve.h  Provides hex encodings (in the form of ECCurveParams
structs) of standardizes elliptic curve domain parameters and mappings
from ECCurveName to ECCurveParams. For use by code that does not have
access to mp_ints.
ecl.h  Interface to constructors for curve parameters and group object,
and point multiplication operations. Used by higher level algorithms
(like ECDH and ECDSA) to actually perform elliptic curve cryptography.
eclpriv.h  Data structures and functions for internal use within the
library.
ec2.h  Internal header file that contains all functions for point
arithmetic over binary polynomial fields.
ecp.h  Internal header file that contains all functions for point
arithmetic over prime fields.
DATA STRUCTURES AND TYPES
=========================
ECCurveName (from eclexp.h)  Opaque name for standardized elliptic
curve domain parameters.
ECCurveParams (from eclexp.h)  Provides hexadecimal encoding
of elliptic curve domain parameters. Can be generated by a user
and passed to ECGroup_fromHex or can be generated from a name by
EC_GetNamedCurveParams. eclcurve.h contains ECCurveParams structs for
the standardized curves defined by ECCurveName.
ECGroup (from ecl.h and eclpriv.h)  Opaque data structure that
represents a group of elliptic curve points for a particular set of
elliptic curve domain parameters. Contains all domain parameters (curve
a and b, field, base point) as well as pointers to the functions that
should be used for point arithmetic and the underlying field GFMethod.
Generated by either ECGroup_fromHex or ECGroup_fromName.
GFMethod (from eclpriv.h)  Represents a field underlying a set of
elliptic curve domain parameters. Contains the irreducible that defines
the field (either the prime or the binary polynomial) as well as
pointers to the functions that should be used for field arithmetic.
ARITHMETIC FUNCTIONS
====================
Higherlevel algorithms (like ECDH and ECDSA) should call ECPoint_mul
or ECPoints_mul (from ecl.h) to do point arithmetic. These functions
will choose which underlying algorithms to use, based on the ECGroup
structure.
Point Multiplication

ecl_mult.c provides the ECPoints_mul and ECPoint_mul wrappers.
It also provides two implementations for the pts_mul operation 
ec_pts_mul_basic (which computes kP, lQ, and then adds kP + lQ) and
ec_pts_mul_simul_w2 (which does a simultaneous point multiplication
using a table with window size 2*2).
ec_naf.c provides an implementation of an algorithm to calculate a
nonadjacent form of a scalar, minimizing the number of point
additions that need to be done in a point multiplication.
Point Arithmetic over Prime Fields

ecp_aff.c provides point arithmetic using affine coordinates.
ecp_jac.c provides point arithmetic using Jacobian projective
coordinates and mixed Jacobianaffine coordinates. (Jacobian projective
coordinates represent a point (x, y) as (X, Y, Z), where x=X/Z^2,
y=Y/Z^3).
ecp_jm.c provides point arithmetic using Modified Jacobian
coordinates and mixed Modified_Jacobianaffine coordinates.
(Modified Jacobian coordinates represent a point (x, y)
as (X, Y, Z, a*Z^4), where x=X/Z^2, y=Y/Z^3, and a is
the linear coefficient in the curve defining equation).
ecp_192.c and ecp_224.c provide optimized field arithmetic.
Point Arithmetic over Binary Polynomial Fields

ec2_aff.c provides point arithmetic using affine coordinates.
ec2_proj.c provides point arithmetic using projective coordinates.
(Projective coordinates represent a point (x, y) as (X, Y, Z), where
x=X/Z, y=Y/Z^2).
ec2_mont.c provides point multiplication using Montgomery projective
coordinates.
ec2_163.c, ec2_193.c, and ec2_233.c provide optimized field arithmetic.
Field Arithmetic

ecl_gf.c provides constructors for field objects (GFMethod) with the
functions GFMethod_cons*. It also provides wrappers around the basic
field operations.
Prime Field Arithmetic

The mpi library provides the basic prime field arithmetic.
ecp_mont.c provides wrappers around the Montgomery multiplication
functions from the mpi library and adds encoding and decoding functions.
It also provides the function to construct a GFMethod object using
Montgomery multiplication.
ecp_192.c and ecp_224.c provide optimized modular reduction for the
fields defined by nistp192 and nistp224 primes.
ecl_gf.c provides wrappers around the basic field operations.
Binary Polynomial Field Arithmetic

../mpi/mp_gf2m.c provides basic binary polynomial field arithmetic,
including addition, multiplication, squaring, mod, and division, as well
as conversion ob polynomial representations between bitstring and int[].
ec2_163.c, ec2_193.c, and ec2_233.c provide optimized field mod, mul,
and sqr operations.
ecl_gf.c provides wrappers around the basic field operations.
Field Encoding

By default, field elements are encoded in their basic form. It is
possible to use an alternative encoding, however. For example, it is
possible to Montgomery representation of prime field elements and
take advantage of the fast modular multiplication that Montgomery
representation provides. The process of converting from basic form to
Montgomery representation is called field encoding, and the opposite
process would be field decoding. All internal point operations assume
that the operands are field encoded as appropriate. By rewiring the
underlying field arithmetic to perform operations on these encoded
values, the same overlying point arithmetic operations can be used
regardless of field representation.
ALGORITHM WIRING
================
The EC library allows point and field arithmetic algorithms to be
substituted ("wiredin") on a finegrained basis. This allows for
generic algorithms and algorithms that are optimized for a particular
curve, field, or architecture, to coexist and to be automatically
selected at runtime.
Wiring Mechanism

The ECGroup and GFMethod structure contain pointers to the point and
field arithmetic functions, respectively, that are to be used in
operations.
The selection of algorithms to use is handled in the function
ecgroup_fromNameAndHex in ecl.c.
Default Wiring

Curves over prime fields by default use montgomery field arithmetic,
point multiplication using 5bit window nonadjacentform with
Modified Jacobian coordinates, and 2*2bit simultaneous point
multiplication using Jacobian coordinates.
(Wiring in function ECGroup_consGFp_mont in ecl.c.)
Curves over prime fields that have optimized modular reduction (i.e.,
secp160r1, nistp192, and nistp224) do not use Montgomery field
arithmetic. Instead, they use basic field arithmetic with their
optimized reduction (as in ecp_192.c and ecp_224.c). They
use the same point multiplication and simultaneous point multiplication
algorithms as other curves over prime fields.
Curves over binary polynomial fields by default use generic field
arithmetic with montgomery point multiplication and basic kP + lQ
computation (multiply, multiply, and add). (Wiring in function
ECGroup_cons_GF2m in ecl.c.)
Curves over binary polynomial fields that have optimized field
arithmetic (i.e., any 163, 193, or 233bit field) use their optimized
field arithmetic. They use the same point multiplication and
simultaneous point multiplication algorithms as other curves over binary
fields.
Example

We provide an example for plugging in an optimized implementation for
the Koblitz curve nistk163.
Suppose the file ec2_k163.c contains the optimized implementation. In
particular it contains a point multiplication function:
mp_err ec_GF2m_nistk163_pt_mul(const mp_int *n, const mp_int *px,
const mp_int *py, mp_int *rx, mp_int *ry, const ECGroup *group);
Since only a pt_mul function is provided, the generic pt_add function
will be used.
There are two options for handling the optimized field arithmetic used
by the ..._pt_mul function. Say the optimized field arithmetic includes
the following functions:
mp_err ec_GF2m_nistk163_add(const mp_int *a, const mp_int *b,
mp_int *r, const GFMethod *meth);
mp_err ec_GF2m_nistk163_mul(const mp_int *a, const mp_int *b,
mp_int *r, const GFMethod *meth);
mp_err ec_GF2m_nistk163_sqr(const mp_int *a, const mp_int *b,
mp_int *r, const GFMethod *meth);
mp_err ec_GF2m_nistk163_div(const mp_int *a, const mp_int *b,
mp_int *r, const GFMethod *meth);
First, the optimized field arithmetic could simply be called directly
by the ..._pt_mul function. This would be accomplished by changing
the ecgroup_fromNameAndHex function in ecl.c to include the following
statements:
if (name == ECCurve_NIST_K163) {
group = ECGroup_consGF2m(&irr, NULL, &curvea, &curveb, &genx,
&geny, &order, params>cofactor);
if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
MP_CHECKOK( ec_group_set_nistk163(group) );
}
and including in ec2_k163.c the following function:
mp_err ec_group_set_nistk163(ECGroup *group) {
group>point_mul = &ec_GF2m_nistk163_pt_mul;
return MP_OKAY;
}
As a result, ec_GF2m_pt_add and similar functions would use the
basic binary polynomial field arithmetic ec_GF2m_add, ec_GF2m_mul,
ec_GF2m_sqr, and ec_GF2m_div.
Alternatively, the optimized field arithmetic could be wired into the
group's GFMethod. This would be accomplished by putting the following
function in ec2_k163.c:
mp_err ec_group_set_nistk163(ECGroup *group) {
group>meth>field_add = &ec_GF2m_nistk163_add;
group>meth>field_mul = &ec_GF2m_nistk163_mul;
group>meth>field_sqr = &ec_GF2m_nistk163_sqr;
group>meth>field_div = &ec_GF2m_nistk163_div;
group>point_mul = &ec_GF2m_nistk163_pt_mul;
return MP_OKAY;
}
For an example of functions that use special field encodings, take a
look at ecp_mont.c.
TESTING
=======
The ecl/tests directory contains a collection of standalone tests that
verify the correctness of the elliptic curve library.
Both ecp_test and ec2_test take the following arguments:
print Print out results of each point arithmetic test.
time Benchmark point operations and print results.
The set of curves over which ecp_test and ec2_test run is coded into the
program, but can be changed by editing the source files.
BUILDING
========
The ecl can be built as a standalone library, separate from NSS,
dependent only on the mpi library. To build the library:
> cd ../mpi
> make libs
> cd ../ecl
> make libs
> make tests # to build test files
> make test # to run automated tests
