The Tor Browser / file comparison
comparison: security/nss/lib/freebl/ecl/README
security/nss/lib/freebl/ecl/README
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:27f6e15622e4 |
|---|---|
| 1 ***** BEGIN LICENSE BLOCK ***** | |
| 2 Version: MPL 1.1/GPL 2.0/LGPL 2.1 | |
| 3 | |
| 4 The contents of this file are subject to the Mozilla Public License Version | |
| 5 1.1 (the "License"); you may not use this file except in compliance with | |
| 6 the License. You may obtain a copy of the License at | |
| 7 http://www.mozilla.org/MPL/ | |
| 8 | |
| 9 Software distributed under the License is distributed on an "AS IS" basis, | |
| 10 WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License | |
| 11 for the specific language governing rights and limitations under the | |
| 12 License. | |
| 13 | |
| 14 The Original Code is the elliptic curve math library. | |
| 15 | |
| 16 The Initial Developer of the Original Code is Sun Microsystems, Inc. | |
| 17 Portions created by Sun Microsystems, Inc. are Copyright (C) 2003 | |
| 18 Sun Microsystems, Inc. All Rights Reserved. | |
| 19 | |
| 20 Contributor(s): | |
| 21 Stephen Fung <fungstep@hotmail.com> and | |
| 22 Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories | |
| 23 | |
| 24 Alternatively, the contents of this file may be used under the terms of | |
| 25 either the GNU General Public License Version 2 or later (the "GPL"), or | |
| 26 the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), | |
| 27 in which case the provisions of the GPL or the LGPL are applicable instead | |
| 28 of those above. If you wish to allow use of your version of this file only | |
| 29 under the terms of either the GPL or the LGPL, and not to allow others to | |
| 30 use your version of this file under the terms of the MPL, indicate your | |
| 31 decision by deleting the provisions above and replace them with the notice | |
| 32 and other provisions required by the GPL or the LGPL. If you do not delete | |
| 33 the provisions above, a recipient may use your version of this file under | |
| 34 the terms of any one of the MPL, the GPL or the LGPL. | |
| 35 | |
| 36 ***** END LICENSE BLOCK ***** | |
| 37 | |
| 38 The ECL exposes routines for constructing and converting curve | |
| 39 parameters for internal use. | |
| 40 | |
| 41 | |
| 42 HEADER FILES | |
| 43 ============ | |
| 44 | |
| 45 ecl-exp.h - Exports data structures and curve names. For use by code | |
| 46 that does not have access to mp_ints. | |
| 47 | |
| 48 ecl-curve.h - Provides hex encodings (in the form of ECCurveParams | |
| 49 structs) of standardizes elliptic curve domain parameters and mappings | |
| 50 from ECCurveName to ECCurveParams. For use by code that does not have | |
| 51 access to mp_ints. | |
| 52 | |
| 53 ecl.h - Interface to constructors for curve parameters and group object, | |
| 54 and point multiplication operations. Used by higher level algorithms | |
| 55 (like ECDH and ECDSA) to actually perform elliptic curve cryptography. | |
| 56 | |
| 57 ecl-priv.h - Data structures and functions for internal use within the | |
| 58 library. | |
| 59 | |
| 60 ec2.h - Internal header file that contains all functions for point | |
| 61 arithmetic over binary polynomial fields. | |
| 62 | |
| 63 ecp.h - Internal header file that contains all functions for point | |
| 64 arithmetic over prime fields. | |
| 65 | |
| 66 DATA STRUCTURES AND TYPES | |
| 67 ========================= | |
| 68 | |
| 69 ECCurveName (from ecl-exp.h) - Opaque name for standardized elliptic | |
| 70 curve domain parameters. | |
| 71 | |
| 72 ECCurveParams (from ecl-exp.h) - Provides hexadecimal encoding | |
| 73 of elliptic curve domain parameters. Can be generated by a user | |
| 74 and passed to ECGroup_fromHex or can be generated from a name by | |
| 75 EC_GetNamedCurveParams. ecl-curve.h contains ECCurveParams structs for | |
| 76 the standardized curves defined by ECCurveName. | |
| 77 | |
| 78 ECGroup (from ecl.h and ecl-priv.h) - Opaque data structure that | |
| 79 represents a group of elliptic curve points for a particular set of | |
| 80 elliptic curve domain parameters. Contains all domain parameters (curve | |
| 81 a and b, field, base point) as well as pointers to the functions that | |
| 82 should be used for point arithmetic and the underlying field GFMethod. | |
| 83 Generated by either ECGroup_fromHex or ECGroup_fromName. | |
| 84 | |
| 85 GFMethod (from ecl-priv.h) - Represents a field underlying a set of | |
| 86 elliptic curve domain parameters. Contains the irreducible that defines | |
| 87 the field (either the prime or the binary polynomial) as well as | |
| 88 pointers to the functions that should be used for field arithmetic. | |
| 89 | |
| 90 ARITHMETIC FUNCTIONS | |
| 91 ==================== | |
| 92 | |
| 93 Higher-level algorithms (like ECDH and ECDSA) should call ECPoint_mul | |
| 94 or ECPoints_mul (from ecl.h) to do point arithmetic. These functions | |
| 95 will choose which underlying algorithms to use, based on the ECGroup | |
| 96 structure. | |
| 97 | |
| 98 Point Multiplication | |
| 99 -------------------- | |
| 100 | |
| 101 ecl_mult.c provides the ECPoints_mul and ECPoint_mul wrappers. | |
| 102 It also provides two implementations for the pts_mul operation - | |
| 103 ec_pts_mul_basic (which computes kP, lQ, and then adds kP + lQ) and | |
| 104 ec_pts_mul_simul_w2 (which does a simultaneous point multiplication | |
| 105 using a table with window size 2*2). | |
| 106 | |
| 107 ec_naf.c provides an implementation of an algorithm to calculate a | |
| 108 non-adjacent form of a scalar, minimizing the number of point | |
| 109 additions that need to be done in a point multiplication. | |
| 110 | |
| 111 Point Arithmetic over Prime Fields | |
| 112 ---------------------------------- | |
| 113 | |
| 114 ecp_aff.c provides point arithmetic using affine coordinates. | |
| 115 | |
| 116 ecp_jac.c provides point arithmetic using Jacobian projective | |
| 117 coordinates and mixed Jacobian-affine coordinates. (Jacobian projective | |
| 118 coordinates represent a point (x, y) as (X, Y, Z), where x=X/Z^2, | |
| 119 y=Y/Z^3). | |
| 120 | |
| 121 ecp_jm.c provides point arithmetic using Modified Jacobian | |
| 122 coordinates and mixed Modified_Jacobian-affine coordinates. | |
| 123 (Modified Jacobian coordinates represent a point (x, y) | |
| 124 as (X, Y, Z, a*Z^4), where x=X/Z^2, y=Y/Z^3, and a is | |
| 125 the linear coefficient in the curve defining equation). | |
| 126 | |
| 127 ecp_192.c and ecp_224.c provide optimized field arithmetic. | |
| 128 | |
| 129 Point Arithmetic over Binary Polynomial Fields | |
| 130 ---------------------------------------------- | |
| 131 | |
| 132 ec2_aff.c provides point arithmetic using affine coordinates. | |
| 133 | |
| 134 ec2_proj.c provides point arithmetic using projective coordinates. | |
| 135 (Projective coordinates represent a point (x, y) as (X, Y, Z), where | |
| 136 x=X/Z, y=Y/Z^2). | |
| 137 | |
| 138 ec2_mont.c provides point multiplication using Montgomery projective | |
| 139 coordinates. | |
| 140 | |
| 141 ec2_163.c, ec2_193.c, and ec2_233.c provide optimized field arithmetic. | |
| 142 | |
| 143 Field Arithmetic | |
| 144 ---------------- | |
| 145 | |
| 146 ecl_gf.c provides constructors for field objects (GFMethod) with the | |
| 147 functions GFMethod_cons*. It also provides wrappers around the basic | |
| 148 field operations. | |
| 149 | |
| 150 Prime Field Arithmetic | |
| 151 ---------------------- | |
| 152 | |
| 153 The mpi library provides the basic prime field arithmetic. | |
| 154 | |
| 155 ecp_mont.c provides wrappers around the Montgomery multiplication | |
| 156 functions from the mpi library and adds encoding and decoding functions. | |
| 157 It also provides the function to construct a GFMethod object using | |
| 158 Montgomery multiplication. | |
| 159 | |
| 160 ecp_192.c and ecp_224.c provide optimized modular reduction for the | |
| 161 fields defined by nistp192 and nistp224 primes. | |
| 162 | |
| 163 ecl_gf.c provides wrappers around the basic field operations. | |
| 164 | |
| 165 Binary Polynomial Field Arithmetic | |
| 166 ---------------------------------- | |
| 167 | |
| 168 ../mpi/mp_gf2m.c provides basic binary polynomial field arithmetic, | |
| 169 including addition, multiplication, squaring, mod, and division, as well | |
| 170 as conversion ob polynomial representations between bitstring and int[]. | |
| 171 | |
| 172 ec2_163.c, ec2_193.c, and ec2_233.c provide optimized field mod, mul, | |
| 173 and sqr operations. | |
| 174 | |
| 175 ecl_gf.c provides wrappers around the basic field operations. | |
| 176 | |
| 177 Field Encoding | |
| 178 -------------- | |
| 179 | |
| 180 By default, field elements are encoded in their basic form. It is | |
| 181 possible to use an alternative encoding, however. For example, it is | |
| 182 possible to Montgomery representation of prime field elements and | |
| 183 take advantage of the fast modular multiplication that Montgomery | |
| 184 representation provides. The process of converting from basic form to | |
| 185 Montgomery representation is called field encoding, and the opposite | |
| 186 process would be field decoding. All internal point operations assume | |
| 187 that the operands are field encoded as appropriate. By rewiring the | |
| 188 underlying field arithmetic to perform operations on these encoded | |
| 189 values, the same overlying point arithmetic operations can be used | |
| 190 regardless of field representation. | |
| 191 | |
| 192 ALGORITHM WIRING | |
| 193 ================ | |
| 194 | |
| 195 The EC library allows point and field arithmetic algorithms to be | |
| 196 substituted ("wired-in") on a fine-grained basis. This allows for | |
| 197 generic algorithms and algorithms that are optimized for a particular | |
| 198 curve, field, or architecture, to coexist and to be automatically | |
| 199 selected at runtime. | |
| 200 | |
| 201 Wiring Mechanism | |
| 202 ---------------- | |
| 203 | |
| 204 The ECGroup and GFMethod structure contain pointers to the point and | |
| 205 field arithmetic functions, respectively, that are to be used in | |
| 206 operations. | |
| 207 | |
| 208 The selection of algorithms to use is handled in the function | |
| 209 ecgroup_fromNameAndHex in ecl.c. | |
| 210 | |
| 211 Default Wiring | |
| 212 -------------- | |
| 213 | |
| 214 Curves over prime fields by default use montgomery field arithmetic, | |
| 215 point multiplication using 5-bit window non-adjacent-form with | |
| 216 Modified Jacobian coordinates, and 2*2-bit simultaneous point | |
| 217 multiplication using Jacobian coordinates. | |
| 218 (Wiring in function ECGroup_consGFp_mont in ecl.c.) | |
| 219 | |
| 220 Curves over prime fields that have optimized modular reduction (i.e., | |
| 221 secp160r1, nistp192, and nistp224) do not use Montgomery field | |
| 222 arithmetic. Instead, they use basic field arithmetic with their | |
| 223 optimized reduction (as in ecp_192.c and ecp_224.c). They | |
| 224 use the same point multiplication and simultaneous point multiplication | |
| 225 algorithms as other curves over prime fields. | |
| 226 | |
| 227 Curves over binary polynomial fields by default use generic field | |
| 228 arithmetic with montgomery point multiplication and basic kP + lQ | |
| 229 computation (multiply, multiply, and add). (Wiring in function | |
| 230 ECGroup_cons_GF2m in ecl.c.) | |
| 231 | |
| 232 Curves over binary polynomial fields that have optimized field | |
| 233 arithmetic (i.e., any 163-, 193, or 233-bit field) use their optimized | |
| 234 field arithmetic. They use the same point multiplication and | |
| 235 simultaneous point multiplication algorithms as other curves over binary | |
| 236 fields. | |
| 237 | |
| 238 Example | |
| 239 ------- | |
| 240 | |
| 241 We provide an example for plugging in an optimized implementation for | |
| 242 the Koblitz curve nistk163. | |
| 243 | |
| 244 Suppose the file ec2_k163.c contains the optimized implementation. In | |
| 245 particular it contains a point multiplication function: | |
| 246 | |
| 247 mp_err ec_GF2m_nistk163_pt_mul(const mp_int *n, const mp_int *px, | |
| 248 const mp_int *py, mp_int *rx, mp_int *ry, const ECGroup *group); | |
| 249 | |
| 250 Since only a pt_mul function is provided, the generic pt_add function | |
| 251 will be used. | |
| 252 | |
| 253 There are two options for handling the optimized field arithmetic used | |
| 254 by the ..._pt_mul function. Say the optimized field arithmetic includes | |
| 255 the following functions: | |
| 256 | |
| 257 mp_err ec_GF2m_nistk163_add(const mp_int *a, const mp_int *b, | |
| 258 mp_int *r, const GFMethod *meth); | |
| 259 mp_err ec_GF2m_nistk163_mul(const mp_int *a, const mp_int *b, | |
| 260 mp_int *r, const GFMethod *meth); | |
| 261 mp_err ec_GF2m_nistk163_sqr(const mp_int *a, const mp_int *b, | |
| 262 mp_int *r, const GFMethod *meth); | |
| 263 mp_err ec_GF2m_nistk163_div(const mp_int *a, const mp_int *b, | |
| 264 mp_int *r, const GFMethod *meth); | |
| 265 | |
| 266 First, the optimized field arithmetic could simply be called directly | |
| 267 by the ..._pt_mul function. This would be accomplished by changing | |
| 268 the ecgroup_fromNameAndHex function in ecl.c to include the following | |
| 269 statements: | |
| 270 | |
| 271 if (name == ECCurve_NIST_K163) { | |
| 272 group = ECGroup_consGF2m(&irr, NULL, &curvea, &curveb, &genx, | |
| 273 &geny, &order, params->cofactor); | |
| 274 if (group == NULL) { res = MP_UNDEF; goto CLEANUP; } | |
| 275 MP_CHECKOK( ec_group_set_nistk163(group) ); | |
| 276 } | |
| 277 | |
| 278 and including in ec2_k163.c the following function: | |
| 279 | |
| 280 mp_err ec_group_set_nistk163(ECGroup *group) { | |
| 281 group->point_mul = &ec_GF2m_nistk163_pt_mul; | |
| 282 return MP_OKAY; | |
| 283 } | |
| 284 | |
| 285 As a result, ec_GF2m_pt_add and similar functions would use the | |
| 286 basic binary polynomial field arithmetic ec_GF2m_add, ec_GF2m_mul, | |
| 287 ec_GF2m_sqr, and ec_GF2m_div. | |
| 288 | |
| 289 Alternatively, the optimized field arithmetic could be wired into the | |
| 290 group's GFMethod. This would be accomplished by putting the following | |
| 291 function in ec2_k163.c: | |
| 292 | |
| 293 mp_err ec_group_set_nistk163(ECGroup *group) { | |
| 294 group->meth->field_add = &ec_GF2m_nistk163_add; | |
| 295 group->meth->field_mul = &ec_GF2m_nistk163_mul; | |
| 296 group->meth->field_sqr = &ec_GF2m_nistk163_sqr; | |
| 297 group->meth->field_div = &ec_GF2m_nistk163_div; | |
| 298 group->point_mul = &ec_GF2m_nistk163_pt_mul; | |
| 299 return MP_OKAY; | |
| 300 } | |
| 301 | |
| 302 For an example of functions that use special field encodings, take a | |
| 303 look at ecp_mont.c. | |
| 304 | |
| 305 TESTING | |
| 306 ======= | |
| 307 | |
| 308 The ecl/tests directory contains a collection of standalone tests that | |
| 309 verify the correctness of the elliptic curve library. | |
| 310 | |
| 311 Both ecp_test and ec2_test take the following arguments: | |
| 312 | |
| 313 --print Print out results of each point arithmetic test. | |
| 314 --time Benchmark point operations and print results. | |
| 315 | |
| 316 The set of curves over which ecp_test and ec2_test run is coded into the | |
| 317 program, but can be changed by editing the source files. | |
| 318 | |
| 319 BUILDING | |
| 320 ======== | |
| 321 | |
| 322 The ecl can be built as a standalone library, separate from NSS, | |
| 323 dependent only on the mpi library. To build the library: | |
| 324 | |
| 325 > cd ../mpi | |
| 326 > make libs | |
| 327 > cd ../ecl | |
| 328 > make libs | |
| 329 > make tests # to build test files | |
| 330 > make test # to run automated tests |
