1This Source Code Form is subject to the terms of the Mozilla Public 2License, v. 2.0. If a copy of the MPL was not distributed with this 3file, You can obtain one at http://mozilla.org/MPL/2.0/. 4 5The ECL exposes routines for constructing and converting curve 6parameters for internal use. 7 8 9HEADER FILES 10============ 11 12ecl-exp.h - Exports data structures and curve names. For use by code 13that does not have access to mp_ints. 14 15ecl-curve.h - Provides hex encodings (in the form of ECCurveParams 16structs) of standardizes elliptic curve domain parameters and mappings 17from ECCurveName to ECCurveParams. For use by code that does not have 18access to mp_ints. 19 20ecl.h - Interface to constructors for curve parameters and group object, 21and point multiplication operations. Used by higher level algorithms 22(like ECDH and ECDSA) to actually perform elliptic curve cryptography. 23 24ecl-priv.h - Data structures and functions for internal use within the 25library. 26 27ecp.h - Internal header file that contains all functions for point 28arithmetic over prime fields. 29 30DATA STRUCTURES AND TYPES 31========================= 32 33ECCurveName (from ecl-exp.h) - Opaque name for standardized elliptic 34curve domain parameters. 35 36ECCurveParams (from ecl-exp.h) - Provides hexadecimal encoding 37of elliptic curve domain parameters. Can be generated by a user 38and passed to ECGroup_fromHex or can be generated from a name by 39EC_GetNamedCurveParams. ecl-curve.h contains ECCurveParams structs for 40the standardized curves defined by ECCurveName. 41 42ECGroup (from ecl.h and ecl-priv.h) - Opaque data structure that 43represents a group of elliptic curve points for a particular set of 44elliptic curve domain parameters. Contains all domain parameters (curve 45a and b, field, base point) as well as pointers to the functions that 46should be used for point arithmetic and the underlying field GFMethod. 47Generated by either ECGroup_fromHex or ECGroup_fromName. 48 49GFMethod (from ecl-priv.h) - Represents a field underlying a set of 50elliptic curve domain parameters. Contains the irreducible that defines 51the field (either the prime or the binary polynomial) as well as 52pointers to the functions that should be used for field arithmetic. 53 54ARITHMETIC FUNCTIONS 55==================== 56 57Higher-level algorithms (like ECDH and ECDSA) should call ECPoint_mul 58or ECPoints_mul (from ecl.h) to do point arithmetic. These functions 59will choose which underlying algorithms to use, based on the ECGroup 60structure. 61 62Point Multiplication 63-------------------- 64 65ecl_mult.c provides the ECPoints_mul and ECPoint_mul wrappers. 66It also provides two implementations for the pts_mul operation - 67ec_pts_mul_basic (which computes kP, lQ, and then adds kP + lQ) and 68ec_pts_mul_simul_w2 (which does a simultaneous point multiplication 69using a table with window size 2*2). 70 71ec_naf.c provides an implementation of an algorithm to calculate a 72non-adjacent form of a scalar, minimizing the number of point 73additions that need to be done in a point multiplication. 74 75Point Arithmetic over Prime Fields 76---------------------------------- 77 78ecp_aff.c provides point arithmetic using affine coordinates. 79 80ecp_jac.c provides point arithmetic using Jacobian projective 81coordinates and mixed Jacobian-affine coordinates. (Jacobian projective 82coordinates represent a point (x, y) as (X, Y, Z), where x=X/Z^2, 83y=Y/Z^3). 84 85ecp_jm.c provides point arithmetic using Modified Jacobian 86coordinates and mixed Modified_Jacobian-affine coordinates. 87(Modified Jacobian coordinates represent a point (x, y) 88as (X, Y, Z, a*Z^4), where x=X/Z^2, y=Y/Z^3, and a is 89the linear coefficient in the curve defining equation). 90 91ecp_192.c and ecp_224.c provide optimized field arithmetic. 92 93Field Arithmetic 94---------------- 95 96ecl_gf.c provides constructors for field objects (GFMethod) with the 97functions GFMethod_cons*. It also provides wrappers around the basic 98field operations. 99 100Prime Field Arithmetic 101---------------------- 102 103The mpi library provides the basic prime field arithmetic. 104 105ecp_mont.c provides wrappers around the Montgomery multiplication 106functions from the mpi library and adds encoding and decoding functions. 107It also provides the function to construct a GFMethod object using 108Montgomery multiplication. 109 110ecp_192.c and ecp_224.c provide optimized modular reduction for the 111fields defined by nistp192 and nistp224 primes. 112 113ecl_gf.c provides wrappers around the basic field operations. 114 115Field Encoding 116-------------- 117 118By default, field elements are encoded in their basic form. It is 119possible to use an alternative encoding, however. For example, it is 120possible to Montgomery representation of prime field elements and 121take advantage of the fast modular multiplication that Montgomery 122representation provides. The process of converting from basic form to 123Montgomery representation is called field encoding, and the opposite 124process would be field decoding. All internal point operations assume 125that the operands are field encoded as appropriate. By rewiring the 126underlying field arithmetic to perform operations on these encoded 127values, the same overlying point arithmetic operations can be used 128regardless of field representation. 129 130ALGORITHM WIRING 131================ 132 133The EC library allows point and field arithmetic algorithms to be 134substituted ("wired-in") on a fine-grained basis. This allows for 135generic algorithms and algorithms that are optimized for a particular 136curve, field, or architecture, to coexist and to be automatically 137selected at runtime. 138 139Wiring Mechanism 140---------------- 141 142The ECGroup and GFMethod structure contain pointers to the point and 143field arithmetic functions, respectively, that are to be used in 144operations. 145 146The selection of algorithms to use is handled in the function 147ecgroup_fromNameAndHex in ecl.c. 148 149Default Wiring 150-------------- 151 152Curves over prime fields by default use montgomery field arithmetic, 153point multiplication using 5-bit window non-adjacent-form with 154Modified Jacobian coordinates, and 2*2-bit simultaneous point 155multiplication using Jacobian coordinates. 156(Wiring in function ECGroup_consGFp_mont in ecl.c.) 157 158Curves over prime fields that have optimized modular reduction (i.e., 159secp160r1, nistp192, and nistp224) do not use Montgomery field 160arithmetic. Instead, they use basic field arithmetic with their 161optimized reduction (as in ecp_192.c and ecp_224.c). They 162use the same point multiplication and simultaneous point multiplication 163algorithms as other curves over prime fields. 164