diff options
Diffstat (limited to 'security/nss/lib/freebl/ecl/README')
| -rw-r--r-- | security/nss/lib/freebl/ecl/README | 267 |
1 files changed, 267 insertions, 0 deletions
diff --git a/security/nss/lib/freebl/ecl/README b/security/nss/lib/freebl/ecl/README new file mode 100644 index 000000000..04a8b3b01 --- /dev/null +++ b/security/nss/lib/freebl/ecl/README @@ -0,0 +1,267 @@ +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 +============ + +ecl-exp.h - Exports data structures and curve names. For use by code +that does not have access to mp_ints. + +ecl-curve.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. + +ecl-priv.h - Data structures and functions for internal use within the +library. + +ecp.h - Internal header file that contains all functions for point +arithmetic over prime fields. + +DATA STRUCTURES AND TYPES +========================= + +ECCurveName (from ecl-exp.h) - Opaque name for standardized elliptic +curve domain parameters. + +ECCurveParams (from ecl-exp.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. ecl-curve.h contains ECCurveParams structs for +the standardized curves defined by ECCurveName. + +ECGroup (from ecl.h and ecl-priv.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 ecl-priv.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 +==================== + +Higher-level 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 +non-adjacent 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 Jacobian-affine 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_Jacobian-affine 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 ("wired-in") on a fine-grained 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 5-bit window non-adjacent-form with +Modified Jacobian coordinates, and 2*2-bit 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 233-bit 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. |