1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/ecl/README Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,330 @@
1.4 +***** BEGIN LICENSE BLOCK *****
1.5 +Version: MPL 1.1/GPL 2.0/LGPL 2.1
1.6 +
1.7 +The contents of this file are subject to the Mozilla Public License Version
1.8 +1.1 (the "License"); you may not use this file except in compliance with
1.9 +the License. You may obtain a copy of the License at
1.10 +http://www.mozilla.org/MPL/
1.11 +
1.12 +Software distributed under the License is distributed on an "AS IS" basis,
1.13 +WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
1.14 +for the specific language governing rights and limitations under the
1.15 +License.
1.16 +
1.17 +The Original Code is the elliptic curve math library.
1.18 +
1.19 +The Initial Developer of the Original Code is Sun Microsystems, Inc.
1.20 +Portions created by Sun Microsystems, Inc. are Copyright (C) 2003
1.21 +Sun Microsystems, Inc. All Rights Reserved.
1.22 +
1.23 +Contributor(s):
1.24 + Stephen Fung <fungstep@hotmail.com> and
1.25 + Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
1.26 +
1.27 +Alternatively, the contents of this file may be used under the terms of
1.28 +either the GNU General Public License Version 2 or later (the "GPL"), or
1.29 +the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
1.30 +in which case the provisions of the GPL or the LGPL are applicable instead
1.31 +of those above. If you wish to allow use of your version of this file only
1.32 +under the terms of either the GPL or the LGPL, and not to allow others to
1.33 +use your version of this file under the terms of the MPL, indicate your
1.34 +decision by deleting the provisions above and replace them with the notice
1.35 +and other provisions required by the GPL or the LGPL. If you do not delete
1.36 +the provisions above, a recipient may use your version of this file under
1.37 +the terms of any one of the MPL, the GPL or the LGPL.
1.38 +
1.39 +***** END LICENSE BLOCK *****
1.40 +
1.41 +The ECL exposes routines for constructing and converting curve
1.42 +parameters for internal use.
1.43 +
1.44 +
1.45 +HEADER FILES
1.46 +============
1.47 +
1.48 +ecl-exp.h - Exports data structures and curve names. For use by code
1.49 +that does not have access to mp_ints.
1.50 +
1.51 +ecl-curve.h - Provides hex encodings (in the form of ECCurveParams
1.52 +structs) of standardizes elliptic curve domain parameters and mappings
1.53 +from ECCurveName to ECCurveParams. For use by code that does not have
1.54 +access to mp_ints.
1.55 +
1.56 +ecl.h - Interface to constructors for curve parameters and group object,
1.57 +and point multiplication operations. Used by higher level algorithms
1.58 +(like ECDH and ECDSA) to actually perform elliptic curve cryptography.
1.59 +
1.60 +ecl-priv.h - Data structures and functions for internal use within the
1.61 +library.
1.62 +
1.63 +ec2.h - Internal header file that contains all functions for point
1.64 +arithmetic over binary polynomial fields.
1.65 +
1.66 +ecp.h - Internal header file that contains all functions for point
1.67 +arithmetic over prime fields.
1.68 +
1.69 +DATA STRUCTURES AND TYPES
1.70 +=========================
1.71 +
1.72 +ECCurveName (from ecl-exp.h) - Opaque name for standardized elliptic
1.73 +curve domain parameters.
1.74 +
1.75 +ECCurveParams (from ecl-exp.h) - Provides hexadecimal encoding
1.76 +of elliptic curve domain parameters. Can be generated by a user
1.77 +and passed to ECGroup_fromHex or can be generated from a name by
1.78 +EC_GetNamedCurveParams. ecl-curve.h contains ECCurveParams structs for
1.79 +the standardized curves defined by ECCurveName.
1.80 +
1.81 +ECGroup (from ecl.h and ecl-priv.h) - Opaque data structure that
1.82 +represents a group of elliptic curve points for a particular set of
1.83 +elliptic curve domain parameters. Contains all domain parameters (curve
1.84 +a and b, field, base point) as well as pointers to the functions that
1.85 +should be used for point arithmetic and the underlying field GFMethod.
1.86 +Generated by either ECGroup_fromHex or ECGroup_fromName.
1.87 +
1.88 +GFMethod (from ecl-priv.h) - Represents a field underlying a set of
1.89 +elliptic curve domain parameters. Contains the irreducible that defines
1.90 +the field (either the prime or the binary polynomial) as well as
1.91 +pointers to the functions that should be used for field arithmetic.
1.92 +
1.93 +ARITHMETIC FUNCTIONS
1.94 +====================
1.95 +
1.96 +Higher-level algorithms (like ECDH and ECDSA) should call ECPoint_mul
1.97 +or ECPoints_mul (from ecl.h) to do point arithmetic. These functions
1.98 +will choose which underlying algorithms to use, based on the ECGroup
1.99 +structure.
1.100 +
1.101 +Point Multiplication
1.102 +--------------------
1.103 +
1.104 +ecl_mult.c provides the ECPoints_mul and ECPoint_mul wrappers.
1.105 +It also provides two implementations for the pts_mul operation -
1.106 +ec_pts_mul_basic (which computes kP, lQ, and then adds kP + lQ) and
1.107 +ec_pts_mul_simul_w2 (which does a simultaneous point multiplication
1.108 +using a table with window size 2*2).
1.109 +
1.110 +ec_naf.c provides an implementation of an algorithm to calculate a
1.111 +non-adjacent form of a scalar, minimizing the number of point
1.112 +additions that need to be done in a point multiplication.
1.113 +
1.114 +Point Arithmetic over Prime Fields
1.115 +----------------------------------
1.116 +
1.117 +ecp_aff.c provides point arithmetic using affine coordinates.
1.118 +
1.119 +ecp_jac.c provides point arithmetic using Jacobian projective
1.120 +coordinates and mixed Jacobian-affine coordinates. (Jacobian projective
1.121 +coordinates represent a point (x, y) as (X, Y, Z), where x=X/Z^2,
1.122 +y=Y/Z^3).
1.123 +
1.124 +ecp_jm.c provides point arithmetic using Modified Jacobian
1.125 +coordinates and mixed Modified_Jacobian-affine coordinates.
1.126 +(Modified Jacobian coordinates represent a point (x, y)
1.127 +as (X, Y, Z, a*Z^4), where x=X/Z^2, y=Y/Z^3, and a is
1.128 +the linear coefficient in the curve defining equation).
1.129 +
1.130 +ecp_192.c and ecp_224.c provide optimized field arithmetic.
1.131 +
1.132 +Point Arithmetic over Binary Polynomial Fields
1.133 +----------------------------------------------
1.134 +
1.135 +ec2_aff.c provides point arithmetic using affine coordinates.
1.136 +
1.137 +ec2_proj.c provides point arithmetic using projective coordinates.
1.138 +(Projective coordinates represent a point (x, y) as (X, Y, Z), where
1.139 +x=X/Z, y=Y/Z^2).
1.140 +
1.141 +ec2_mont.c provides point multiplication using Montgomery projective
1.142 +coordinates.
1.143 +
1.144 +ec2_163.c, ec2_193.c, and ec2_233.c provide optimized field arithmetic.
1.145 +
1.146 +Field Arithmetic
1.147 +----------------
1.148 +
1.149 +ecl_gf.c provides constructors for field objects (GFMethod) with the
1.150 +functions GFMethod_cons*. It also provides wrappers around the basic
1.151 +field operations.
1.152 +
1.153 +Prime Field Arithmetic
1.154 +----------------------
1.155 +
1.156 +The mpi library provides the basic prime field arithmetic.
1.157 +
1.158 +ecp_mont.c provides wrappers around the Montgomery multiplication
1.159 +functions from the mpi library and adds encoding and decoding functions.
1.160 +It also provides the function to construct a GFMethod object using
1.161 +Montgomery multiplication.
1.162 +
1.163 +ecp_192.c and ecp_224.c provide optimized modular reduction for the
1.164 +fields defined by nistp192 and nistp224 primes.
1.165 +
1.166 +ecl_gf.c provides wrappers around the basic field operations.
1.167 +
1.168 +Binary Polynomial Field Arithmetic
1.169 +----------------------------------
1.170 +
1.171 +../mpi/mp_gf2m.c provides basic binary polynomial field arithmetic,
1.172 +including addition, multiplication, squaring, mod, and division, as well
1.173 +as conversion ob polynomial representations between bitstring and int[].
1.174 +
1.175 +ec2_163.c, ec2_193.c, and ec2_233.c provide optimized field mod, mul,
1.176 +and sqr operations.
1.177 +
1.178 +ecl_gf.c provides wrappers around the basic field operations.
1.179 +
1.180 +Field Encoding
1.181 +--------------
1.182 +
1.183 +By default, field elements are encoded in their basic form. It is
1.184 +possible to use an alternative encoding, however. For example, it is
1.185 +possible to Montgomery representation of prime field elements and
1.186 +take advantage of the fast modular multiplication that Montgomery
1.187 +representation provides. The process of converting from basic form to
1.188 +Montgomery representation is called field encoding, and the opposite
1.189 +process would be field decoding. All internal point operations assume
1.190 +that the operands are field encoded as appropriate. By rewiring the
1.191 +underlying field arithmetic to perform operations on these encoded
1.192 +values, the same overlying point arithmetic operations can be used
1.193 +regardless of field representation.
1.194 +
1.195 +ALGORITHM WIRING
1.196 +================
1.197 +
1.198 +The EC library allows point and field arithmetic algorithms to be
1.199 +substituted ("wired-in") on a fine-grained basis. This allows for
1.200 +generic algorithms and algorithms that are optimized for a particular
1.201 +curve, field, or architecture, to coexist and to be automatically
1.202 +selected at runtime.
1.203 +
1.204 +Wiring Mechanism
1.205 +----------------
1.206 +
1.207 +The ECGroup and GFMethod structure contain pointers to the point and
1.208 +field arithmetic functions, respectively, that are to be used in
1.209 +operations.
1.210 +
1.211 +The selection of algorithms to use is handled in the function
1.212 +ecgroup_fromNameAndHex in ecl.c.
1.213 +
1.214 +Default Wiring
1.215 +--------------
1.216 +
1.217 +Curves over prime fields by default use montgomery field arithmetic,
1.218 +point multiplication using 5-bit window non-adjacent-form with
1.219 +Modified Jacobian coordinates, and 2*2-bit simultaneous point
1.220 +multiplication using Jacobian coordinates.
1.221 +(Wiring in function ECGroup_consGFp_mont in ecl.c.)
1.222 +
1.223 +Curves over prime fields that have optimized modular reduction (i.e.,
1.224 +secp160r1, nistp192, and nistp224) do not use Montgomery field
1.225 +arithmetic. Instead, they use basic field arithmetic with their
1.226 +optimized reduction (as in ecp_192.c and ecp_224.c). They
1.227 +use the same point multiplication and simultaneous point multiplication
1.228 +algorithms as other curves over prime fields.
1.229 +
1.230 +Curves over binary polynomial fields by default use generic field
1.231 +arithmetic with montgomery point multiplication and basic kP + lQ
1.232 +computation (multiply, multiply, and add). (Wiring in function
1.233 +ECGroup_cons_GF2m in ecl.c.)
1.234 +
1.235 +Curves over binary polynomial fields that have optimized field
1.236 +arithmetic (i.e., any 163-, 193, or 233-bit field) use their optimized
1.237 +field arithmetic. They use the same point multiplication and
1.238 +simultaneous point multiplication algorithms as other curves over binary
1.239 +fields.
1.240 +
1.241 +Example
1.242 +-------
1.243 +
1.244 +We provide an example for plugging in an optimized implementation for
1.245 +the Koblitz curve nistk163.
1.246 +
1.247 +Suppose the file ec2_k163.c contains the optimized implementation. In
1.248 +particular it contains a point multiplication function:
1.249 +
1.250 + mp_err ec_GF2m_nistk163_pt_mul(const mp_int *n, const mp_int *px,
1.251 + const mp_int *py, mp_int *rx, mp_int *ry, const ECGroup *group);
1.252 +
1.253 +Since only a pt_mul function is provided, the generic pt_add function
1.254 +will be used.
1.255 +
1.256 +There are two options for handling the optimized field arithmetic used
1.257 +by the ..._pt_mul function. Say the optimized field arithmetic includes
1.258 +the following functions:
1.259 +
1.260 + mp_err ec_GF2m_nistk163_add(const mp_int *a, const mp_int *b,
1.261 + mp_int *r, const GFMethod *meth);
1.262 + mp_err ec_GF2m_nistk163_mul(const mp_int *a, const mp_int *b,
1.263 + mp_int *r, const GFMethod *meth);
1.264 + mp_err ec_GF2m_nistk163_sqr(const mp_int *a, const mp_int *b,
1.265 + mp_int *r, const GFMethod *meth);
1.266 + mp_err ec_GF2m_nistk163_div(const mp_int *a, const mp_int *b,
1.267 + mp_int *r, const GFMethod *meth);
1.268 +
1.269 +First, the optimized field arithmetic could simply be called directly
1.270 +by the ..._pt_mul function. This would be accomplished by changing
1.271 +the ecgroup_fromNameAndHex function in ecl.c to include the following
1.272 +statements:
1.273 +
1.274 + if (name == ECCurve_NIST_K163) {
1.275 + group = ECGroup_consGF2m(&irr, NULL, &curvea, &curveb, &genx,
1.276 + &geny, &order, params->cofactor);
1.277 + if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
1.278 + MP_CHECKOK( ec_group_set_nistk163(group) );
1.279 + }
1.280 +
1.281 +and including in ec2_k163.c the following function:
1.282 +
1.283 + mp_err ec_group_set_nistk163(ECGroup *group) {
1.284 + group->point_mul = &ec_GF2m_nistk163_pt_mul;
1.285 + return MP_OKAY;
1.286 + }
1.287 +
1.288 +As a result, ec_GF2m_pt_add and similar functions would use the
1.289 +basic binary polynomial field arithmetic ec_GF2m_add, ec_GF2m_mul,
1.290 +ec_GF2m_sqr, and ec_GF2m_div.
1.291 +
1.292 +Alternatively, the optimized field arithmetic could be wired into the
1.293 +group's GFMethod. This would be accomplished by putting the following
1.294 +function in ec2_k163.c:
1.295 +
1.296 + mp_err ec_group_set_nistk163(ECGroup *group) {
1.297 + group->meth->field_add = &ec_GF2m_nistk163_add;
1.298 + group->meth->field_mul = &ec_GF2m_nistk163_mul;
1.299 + group->meth->field_sqr = &ec_GF2m_nistk163_sqr;
1.300 + group->meth->field_div = &ec_GF2m_nistk163_div;
1.301 + group->point_mul = &ec_GF2m_nistk163_pt_mul;
1.302 + return MP_OKAY;
1.303 + }
1.304 +
1.305 +For an example of functions that use special field encodings, take a
1.306 +look at ecp_mont.c.
1.307 +
1.308 +TESTING
1.309 +=======
1.310 +
1.311 +The ecl/tests directory contains a collection of standalone tests that
1.312 +verify the correctness of the elliptic curve library.
1.313 +
1.314 +Both ecp_test and ec2_test take the following arguments:
1.315 +
1.316 + --print Print out results of each point arithmetic test.
1.317 + --time Benchmark point operations and print results.
1.318 +
1.319 +The set of curves over which ecp_test and ec2_test run is coded into the
1.320 +program, but can be changed by editing the source files.
1.321 +
1.322 +BUILDING
1.323 +========
1.324 +
1.325 +The ecl can be built as a standalone library, separate from NSS,
1.326 +dependent only on the mpi library. To build the library:
1.327 +
1.328 + > cd ../mpi
1.329 + > make libs
1.330 + > cd ../ecl
1.331 + > make libs
1.332 + > make tests # to build test files
1.333 + > make test # to run automated tests
