michael@0: ***** BEGIN LICENSE BLOCK ***** michael@0: Version: MPL 1.1/GPL 2.0/LGPL 2.1 michael@0: michael@0: The contents of this file are subject to the Mozilla Public License Version michael@0: 1.1 (the "License"); you may not use this file except in compliance with michael@0: the License. You may obtain a copy of the License at michael@0: http://www.mozilla.org/MPL/ michael@0: michael@0: Software distributed under the License is distributed on an "AS IS" basis, michael@0: WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License michael@0: for the specific language governing rights and limitations under the michael@0: License. michael@0: michael@0: The Original Code is the elliptic curve math library. michael@0: michael@0: The Initial Developer of the Original Code is Sun Microsystems, Inc. michael@0: Portions created by Sun Microsystems, Inc. are Copyright (C) 2003 michael@0: Sun Microsystems, Inc. All Rights Reserved. michael@0: michael@0: Contributor(s): michael@0: Stephen Fung and michael@0: Douglas Stebila , Sun Microsystems Laboratories michael@0: michael@0: Alternatively, the contents of this file may be used under the terms of michael@0: either the GNU General Public License Version 2 or later (the "GPL"), or michael@0: the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), michael@0: in which case the provisions of the GPL or the LGPL are applicable instead michael@0: of those above. If you wish to allow use of your version of this file only michael@0: under the terms of either the GPL or the LGPL, and not to allow others to michael@0: use your version of this file under the terms of the MPL, indicate your michael@0: decision by deleting the provisions above and replace them with the notice michael@0: and other provisions required by the GPL or the LGPL. If you do not delete michael@0: the provisions above, a recipient may use your version of this file under michael@0: the terms of any one of the MPL, the GPL or the LGPL. michael@0: michael@0: ***** END LICENSE BLOCK ***** michael@0: michael@0: The ECL exposes routines for constructing and converting curve michael@0: parameters for internal use. michael@0: michael@0: michael@0: HEADER FILES michael@0: ============ michael@0: michael@0: ecl-exp.h - Exports data structures and curve names. For use by code michael@0: that does not have access to mp_ints. michael@0: michael@0: ecl-curve.h - Provides hex encodings (in the form of ECCurveParams michael@0: structs) of standardizes elliptic curve domain parameters and mappings michael@0: from ECCurveName to ECCurveParams. For use by code that does not have michael@0: access to mp_ints. michael@0: michael@0: ecl.h - Interface to constructors for curve parameters and group object, michael@0: and point multiplication operations. Used by higher level algorithms michael@0: (like ECDH and ECDSA) to actually perform elliptic curve cryptography. michael@0: michael@0: ecl-priv.h - Data structures and functions for internal use within the michael@0: library. michael@0: michael@0: ec2.h - Internal header file that contains all functions for point michael@0: arithmetic over binary polynomial fields. michael@0: michael@0: ecp.h - Internal header file that contains all functions for point michael@0: arithmetic over prime fields. michael@0: michael@0: DATA STRUCTURES AND TYPES michael@0: ========================= michael@0: michael@0: ECCurveName (from ecl-exp.h) - Opaque name for standardized elliptic michael@0: curve domain parameters. michael@0: michael@0: ECCurveParams (from ecl-exp.h) - Provides hexadecimal encoding michael@0: of elliptic curve domain parameters. Can be generated by a user michael@0: and passed to ECGroup_fromHex or can be generated from a name by michael@0: EC_GetNamedCurveParams. ecl-curve.h contains ECCurveParams structs for michael@0: the standardized curves defined by ECCurveName. michael@0: michael@0: ECGroup (from ecl.h and ecl-priv.h) - Opaque data structure that michael@0: represents a group of elliptic curve points for a particular set of michael@0: elliptic curve domain parameters. Contains all domain parameters (curve michael@0: a and b, field, base point) as well as pointers to the functions that michael@0: should be used for point arithmetic and the underlying field GFMethod. michael@0: Generated by either ECGroup_fromHex or ECGroup_fromName. michael@0: michael@0: GFMethod (from ecl-priv.h) - Represents a field underlying a set of michael@0: elliptic curve domain parameters. Contains the irreducible that defines michael@0: the field (either the prime or the binary polynomial) as well as michael@0: pointers to the functions that should be used for field arithmetic. michael@0: michael@0: ARITHMETIC FUNCTIONS michael@0: ==================== michael@0: michael@0: Higher-level algorithms (like ECDH and ECDSA) should call ECPoint_mul michael@0: or ECPoints_mul (from ecl.h) to do point arithmetic. These functions michael@0: will choose which underlying algorithms to use, based on the ECGroup michael@0: structure. michael@0: michael@0: Point Multiplication michael@0: -------------------- michael@0: michael@0: ecl_mult.c provides the ECPoints_mul and ECPoint_mul wrappers. michael@0: It also provides two implementations for the pts_mul operation - michael@0: ec_pts_mul_basic (which computes kP, lQ, and then adds kP + lQ) and michael@0: ec_pts_mul_simul_w2 (which does a simultaneous point multiplication michael@0: using a table with window size 2*2). michael@0: michael@0: ec_naf.c provides an implementation of an algorithm to calculate a michael@0: non-adjacent form of a scalar, minimizing the number of point michael@0: additions that need to be done in a point multiplication. michael@0: michael@0: Point Arithmetic over Prime Fields michael@0: ---------------------------------- michael@0: michael@0: ecp_aff.c provides point arithmetic using affine coordinates. michael@0: michael@0: ecp_jac.c provides point arithmetic using Jacobian projective michael@0: coordinates and mixed Jacobian-affine coordinates. (Jacobian projective michael@0: coordinates represent a point (x, y) as (X, Y, Z), where x=X/Z^2, michael@0: y=Y/Z^3). michael@0: michael@0: ecp_jm.c provides point arithmetic using Modified Jacobian michael@0: coordinates and mixed Modified_Jacobian-affine coordinates. michael@0: (Modified Jacobian coordinates represent a point (x, y) michael@0: as (X, Y, Z, a*Z^4), where x=X/Z^2, y=Y/Z^3, and a is michael@0: the linear coefficient in the curve defining equation). michael@0: michael@0: ecp_192.c and ecp_224.c provide optimized field arithmetic. michael@0: michael@0: Point Arithmetic over Binary Polynomial Fields michael@0: ---------------------------------------------- michael@0: michael@0: ec2_aff.c provides point arithmetic using affine coordinates. michael@0: michael@0: ec2_proj.c provides point arithmetic using projective coordinates. michael@0: (Projective coordinates represent a point (x, y) as (X, Y, Z), where michael@0: x=X/Z, y=Y/Z^2). michael@0: michael@0: ec2_mont.c provides point multiplication using Montgomery projective michael@0: coordinates. michael@0: michael@0: ec2_163.c, ec2_193.c, and ec2_233.c provide optimized field arithmetic. michael@0: michael@0: Field Arithmetic michael@0: ---------------- michael@0: michael@0: ecl_gf.c provides constructors for field objects (GFMethod) with the michael@0: functions GFMethod_cons*. It also provides wrappers around the basic michael@0: field operations. michael@0: michael@0: Prime Field Arithmetic michael@0: ---------------------- michael@0: michael@0: The mpi library provides the basic prime field arithmetic. michael@0: michael@0: ecp_mont.c provides wrappers around the Montgomery multiplication michael@0: functions from the mpi library and adds encoding and decoding functions. michael@0: It also provides the function to construct a GFMethod object using michael@0: Montgomery multiplication. michael@0: michael@0: ecp_192.c and ecp_224.c provide optimized modular reduction for the michael@0: fields defined by nistp192 and nistp224 primes. michael@0: michael@0: ecl_gf.c provides wrappers around the basic field operations. michael@0: michael@0: Binary Polynomial Field Arithmetic michael@0: ---------------------------------- michael@0: michael@0: ../mpi/mp_gf2m.c provides basic binary polynomial field arithmetic, michael@0: including addition, multiplication, squaring, mod, and division, as well michael@0: as conversion ob polynomial representations between bitstring and int[]. michael@0: michael@0: ec2_163.c, ec2_193.c, and ec2_233.c provide optimized field mod, mul, michael@0: and sqr operations. michael@0: michael@0: ecl_gf.c provides wrappers around the basic field operations. michael@0: michael@0: Field Encoding michael@0: -------------- michael@0: michael@0: By default, field elements are encoded in their basic form. It is michael@0: possible to use an alternative encoding, however. For example, it is michael@0: possible to Montgomery representation of prime field elements and michael@0: take advantage of the fast modular multiplication that Montgomery michael@0: representation provides. The process of converting from basic form to michael@0: Montgomery representation is called field encoding, and the opposite michael@0: process would be field decoding. All internal point operations assume michael@0: that the operands are field encoded as appropriate. By rewiring the michael@0: underlying field arithmetic to perform operations on these encoded michael@0: values, the same overlying point arithmetic operations can be used michael@0: regardless of field representation. michael@0: michael@0: ALGORITHM WIRING michael@0: ================ michael@0: michael@0: The EC library allows point and field arithmetic algorithms to be michael@0: substituted ("wired-in") on a fine-grained basis. This allows for michael@0: generic algorithms and algorithms that are optimized for a particular michael@0: curve, field, or architecture, to coexist and to be automatically michael@0: selected at runtime. michael@0: michael@0: Wiring Mechanism michael@0: ---------------- michael@0: michael@0: The ECGroup and GFMethod structure contain pointers to the point and michael@0: field arithmetic functions, respectively, that are to be used in michael@0: operations. michael@0: michael@0: The selection of algorithms to use is handled in the function michael@0: ecgroup_fromNameAndHex in ecl.c. michael@0: michael@0: Default Wiring michael@0: -------------- michael@0: michael@0: Curves over prime fields by default use montgomery field arithmetic, michael@0: point multiplication using 5-bit window non-adjacent-form with michael@0: Modified Jacobian coordinates, and 2*2-bit simultaneous point michael@0: multiplication using Jacobian coordinates. michael@0: (Wiring in function ECGroup_consGFp_mont in ecl.c.) michael@0: michael@0: Curves over prime fields that have optimized modular reduction (i.e., michael@0: secp160r1, nistp192, and nistp224) do not use Montgomery field michael@0: arithmetic. Instead, they use basic field arithmetic with their michael@0: optimized reduction (as in ecp_192.c and ecp_224.c). They michael@0: use the same point multiplication and simultaneous point multiplication michael@0: algorithms as other curves over prime fields. michael@0: michael@0: Curves over binary polynomial fields by default use generic field michael@0: arithmetic with montgomery point multiplication and basic kP + lQ michael@0: computation (multiply, multiply, and add). (Wiring in function michael@0: ECGroup_cons_GF2m in ecl.c.) michael@0: michael@0: Curves over binary polynomial fields that have optimized field michael@0: arithmetic (i.e., any 163-, 193, or 233-bit field) use their optimized michael@0: field arithmetic. They use the same point multiplication and michael@0: simultaneous point multiplication algorithms as other curves over binary michael@0: fields. michael@0: michael@0: Example michael@0: ------- michael@0: michael@0: We provide an example for plugging in an optimized implementation for michael@0: the Koblitz curve nistk163. michael@0: michael@0: Suppose the file ec2_k163.c contains the optimized implementation. In michael@0: particular it contains a point multiplication function: michael@0: michael@0: mp_err ec_GF2m_nistk163_pt_mul(const mp_int *n, const mp_int *px, michael@0: const mp_int *py, mp_int *rx, mp_int *ry, const ECGroup *group); michael@0: michael@0: Since only a pt_mul function is provided, the generic pt_add function michael@0: will be used. michael@0: michael@0: There are two options for handling the optimized field arithmetic used michael@0: by the ..._pt_mul function. Say the optimized field arithmetic includes michael@0: the following functions: michael@0: michael@0: mp_err ec_GF2m_nistk163_add(const mp_int *a, const mp_int *b, michael@0: mp_int *r, const GFMethod *meth); michael@0: mp_err ec_GF2m_nistk163_mul(const mp_int *a, const mp_int *b, michael@0: mp_int *r, const GFMethod *meth); michael@0: mp_err ec_GF2m_nistk163_sqr(const mp_int *a, const mp_int *b, michael@0: mp_int *r, const GFMethod *meth); michael@0: mp_err ec_GF2m_nistk163_div(const mp_int *a, const mp_int *b, michael@0: mp_int *r, const GFMethod *meth); michael@0: michael@0: First, the optimized field arithmetic could simply be called directly michael@0: by the ..._pt_mul function. This would be accomplished by changing michael@0: the ecgroup_fromNameAndHex function in ecl.c to include the following michael@0: statements: michael@0: michael@0: if (name == ECCurve_NIST_K163) { michael@0: group = ECGroup_consGF2m(&irr, NULL, &curvea, &curveb, &genx, michael@0: &geny, &order, params->cofactor); michael@0: if (group == NULL) { res = MP_UNDEF; goto CLEANUP; } michael@0: MP_CHECKOK( ec_group_set_nistk163(group) ); michael@0: } michael@0: michael@0: and including in ec2_k163.c the following function: michael@0: michael@0: mp_err ec_group_set_nistk163(ECGroup *group) { michael@0: group->point_mul = &ec_GF2m_nistk163_pt_mul; michael@0: return MP_OKAY; michael@0: } michael@0: michael@0: As a result, ec_GF2m_pt_add and similar functions would use the michael@0: basic binary polynomial field arithmetic ec_GF2m_add, ec_GF2m_mul, michael@0: ec_GF2m_sqr, and ec_GF2m_div. michael@0: michael@0: Alternatively, the optimized field arithmetic could be wired into the michael@0: group's GFMethod. This would be accomplished by putting the following michael@0: function in ec2_k163.c: michael@0: michael@0: mp_err ec_group_set_nistk163(ECGroup *group) { michael@0: group->meth->field_add = &ec_GF2m_nistk163_add; michael@0: group->meth->field_mul = &ec_GF2m_nistk163_mul; michael@0: group->meth->field_sqr = &ec_GF2m_nistk163_sqr; michael@0: group->meth->field_div = &ec_GF2m_nistk163_div; michael@0: group->point_mul = &ec_GF2m_nistk163_pt_mul; michael@0: return MP_OKAY; michael@0: } michael@0: michael@0: For an example of functions that use special field encodings, take a michael@0: look at ecp_mont.c. michael@0: michael@0: TESTING michael@0: ======= michael@0: michael@0: The ecl/tests directory contains a collection of standalone tests that michael@0: verify the correctness of the elliptic curve library. michael@0: michael@0: Both ecp_test and ec2_test take the following arguments: michael@0: michael@0: --print Print out results of each point arithmetic test. michael@0: --time Benchmark point operations and print results. michael@0: michael@0: The set of curves over which ecp_test and ec2_test run is coded into the michael@0: program, but can be changed by editing the source files. michael@0: michael@0: BUILDING michael@0: ======== michael@0: michael@0: The ecl can be built as a standalone library, separate from NSS, michael@0: dependent only on the mpi library. To build the library: michael@0: michael@0: > cd ../mpi michael@0: > make libs michael@0: > cd ../ecl michael@0: > make libs michael@0: > make tests # to build test files michael@0: > make test # to run automated tests