The Tor Browser: security/nss/lib/freebl/ecl/README.FP@6474c204b198 (annotated)

security/nss/lib/freebl/ecl/README.FP@6474c204b198 (annotated)

security/nss/lib/freebl/ecl/README.FP

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 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.
 The floating point code of the ECL provides algorithms for performing
 elliptic-curve point multiplications in floating point.
 The point multiplication algorithms perform calculations almost
 exclusively in floating point for efficiency, but have the same
 (integer) interface as the ECL for compatibility and to be easily
 wired-in to the ECL.  Please see README file (not this README.FP file)
 for information on wiring-in.
 This has been implemented for 3 curves as specified in [1]:
 	secp160r1
 	secp192r1
 	secp224r1
 RATIONALE
 =========
 Calculations are done in the  floating-point unit (FPU) since it
 gives better performance on the UltraSPARC III chips.  This is
 because the FPU allows for faster multiplication than the integer unit.
 The integer unit has a longer multiplication instruction latency, and
 does not allow full pipelining, as described in [2].
 Since performance is an important selling feature of Elliptic Curve
 Cryptography (ECC), this implementation was created.
 DATA REPRESENTATION
 ===================
 Data is primarily represented in an array of double-precision floating
 point numbers.  Generally, each array element has 24 bits of precision
 (i.e. be x * 2^y, where x is an integer of at most 24 bits, y some positive
 integer), although the actual implementation details are more complicated.
 e.g. a way to store an 80 bit number might be:
 double p[4] = { 632613 * 2^0, 329841 * 2^24, 9961 * 2^48, 51 * 2^64 };
 See section ARITHMETIC OPERATIONS for more details.
 This implementation assumes that the floating-point unit rounding mode
 is round-to-even as specified in IEEE 754
 (as opposed to chopping, rounding up, or rounding down).
 When subtracting integers represented as arrays of floating point
 numbers, some coefficients (array elements) may become negative.
 This effectively gives an extra bit of precision that is important
 for correctness in some cases.
 The described number presentation limits the size of integers to 1023 bits.
 This is due to an upper bound of 1024 for the exponent of a double precision
 floating point number as specified in IEEE-754.
 However, this is acceptable for ECC key sizes of the foreseeable future.
 DATA STRUCTURES
 ===============
 For more information on coordinate representations, see [3].
 ecfp_aff_pt
 -----------
 Affine EC Point Representation.  This is the basic
 representation (x, y) of an elliptic curve point.
 ecfp_jac_pt
 -----------
 Jacobian EC Point.  This stores a point as (X, Y, Z), where
 the affine point corresponds to (X/Z^2, Y/Z^3).  This allows
 for fewer inversions in calculations.
 ecfp_chud_pt
 ------------
 Chudnovsky Jacobian Point.  This representation stores a point
 as (X, Y, Z, Z^2, Z^3), the same as a Jacobian representation
 but also storing Z^2 and Z^3 for faster point additions.
 ecfp_jm_pt
 ----------
 Modified Jacobian Point.  This representation stores a point
 as (X, Y, Z, a*Z^4), the same as Jacobian representation but
 also storing a*Z^4 for faster point doublings.  Here "a" represents
 the linear coefficient of x defining the curve.
 EC_group_fp
 -----------
 Stores information on the elliptic curve group for floating
 point calculations.  Contains curve specific information, as
 well as function pointers to routines, allowing different
 optimizations to be easily wired in.
 This should be made accessible from an ECGroup for the floating
 point implementations of point multiplication.
 POINT MULTIPLICATION ALGORITHMS
 ===============================
 Elliptic Curve Point multiplication can be done at a higher level orthogonal
 to the implementation of point additions and point doublings.  There
 are a variety of algorithms that can be used.
 The following algorithms have been implemented:
 -bit Window (Jacobian Coordinates)
 Double & Add (Jacobian & Affine Coordinates)
 -bit Non-Adjacent Form (Modified Jacobian & Chudnovsky Jacobian)
 Currently, the fastest algorithm for multiplying a generic point
 is the 5-bit Non-Adjacent Form.
 See comments in ecp_fp.c for more details and references.
 SOURCE / HEADER FILES
 =====================
 ecp_fp.c
 --------
 Main source file for floating point calculations.  Contains routines
 to convert from floating-point to integer (mp_int format), point
 multiplication algorithms, and several other routines.
 ecp_fp.h
 --------
 Main header file.  Contains most constants used and function prototypes.
 ecp_fp[160, 192, 224].c
 -----------------------
 Source files for specific curves.  Contains curve specific code such
 as specialized reduction based on the field defining prime.  Contains
 code wiring-in different algorithms and optimizations.
 ecp_fpinc.c
 -----------
 Source file that is included by ecp_fp[160, 192, 224].c.  This generates
 functions with different preprocessor-defined names and loop iterations,
 allowing for static linking and strong compiler optimizations without
 code duplication.
 TESTING
 =======
 The test suite can be found in ecl/tests/ecp_fpt.  This tests and gets
 timings of the different algorithms for the curves implemented.
 ARITHMETIC OPERATIONS
 ---------------------
 The primary operations in ECC over the prime fields are modular arithmetic:
 i.e. n * m (mod p) and n + m (mod p).  In this implementation, multiplication,
 addition, and reduction are implemented as separate functions.  This
 enables computation of formulae with fewer reductions, e.g.
 (a * b) + (c * d) (mod p) rather than:
 ((a * b) (mod p)) + ((c * d) (mod p)) (mod p)
 This takes advantage of the fact that the double precision mantissa in
 floating point can hold numbers up to 2^53, i.e. it has some leeway to
 store larger intermediate numbers.  See further detail in the section on
 FLOATING POINT PRECISION.
 Multiplication
 --------------
 Multiplication is implemented in a standard polynomial multiplication
 fashion.  The terms in opposite factors are pairwise multiplied and
 added together appropriately.  Note that the result requires twice
 as many doubles for storage, as the bit size of the product is twice
 that of the multiplicands.
 e.g. suppose we have double n[3], m[3], r[6], and want to calculate r = n * m
 r[0] = n[0] * m[0]
 r[1] = n[0] * m[1] + n[1] * m[0]
 r[2] = n[0] * m[2] + n[1] * m[1] + n[2] * m[0]
 r[3] = n[1] * m[2] + n[2] * m[1]
 r[4] = n[2] * m[2]
 r[5] = 0 (This is used later to hold spillover from r[4], see tidying in
 the reduction section.)
 Addition
 --------
 Addition is done term by term.  The only caveat is to be careful with
 the number of terms that need to be added.  When adding results of
 multiplication (before reduction), twice as many terms need to be added
 together.  This is done in the addLong function.
 e.g. for double n[4], m[4], r[4]:  r = n + m
 r[0] = n[0] + m[0]
 r[1] = n[1] + m[1]
 r[2] = n[2] + m[2]
 r[3] = n[3] + m[3]
 Modular Reduction
 -----------------
 For the curves implemented, reduction is possible by fast reduction
 for Generalized Mersenne Primes, as described in [4].  For the
 floating point implementation, a significant step of the reduction
 process is tidying:  that is, the propagation of carry bits from
 low-order to high-order coefficients to reduce the precision of each
 coefficient to 24 bits.
 This is done by adding and then subtracting
 ecfp_alpha, a large floating point number that induces precision roundoff.
 See [5] for more details on tidying using floating point arithmetic.
 e.g. suppose we have r = 961838 * 2^24 + 519308
 then if we set alpha = 3 * 2^51 * 2^24,
 FP(FP(r + alpha) - alpha) = 961838 * 2^24, because the precision for
 the intermediate results is limited.  Our values of alpha are chosen
 to truncate to a desired number of bits.
 The reduction is then performed as in [4], adding multiples of prime p.
 e.g. suppose we are working over a polynomial of 10^2.  Take the number
 * 10^8 + 11 * 10^6 + 53 * 10^4 + 23 * 10^2 + 95, stored in 5 elements
 for coefficients of 10^0, 10^2, ..., 10^8.
 We wish to reduce modulo p = 10^6 - 2 * 10^4 + 1
 We can subtract off from the higher terms
 (2 * 10^8 + 11 * 10^6 + 53 * 10^4 + 23 * 10^2 + 95) - (2 * 10^2) * (10^6 - 2 * 10^4 + 1)
 = 15 * 10^6 + 53 * 10^4 + 21 * 10^2 + 95
 = 15 * 10^6 + 53 * 10^4 + 21 * 10^2 + 95 - (15) * (10^6 - 2 * 10^4 + 1)
 = 83 * 10^4 + 21 * 10^2 + 80
 Integrated Example
 ------------------
 This example shows how multiplication, addition, tidying, and reduction
 work together in our modular arithmetic.  This is simplified from the
 actual implementation, but should convey the main concepts.
 Working over polynomials of 10^2 and with p as in the prior example,
 Let a = 16 * 10^4 + 53 * 10^2 + 33
 let b = 81 * 10^4 + 31 * 10^2 + 49
 let c = 22 * 10^4 +  0 * 10^2 + 95
 And suppose we want to compute a * b + c mod p.
 We first do a multiplication:  then a * b =
 * 10^10 + 1296 * 10^8 + 4789 * 10^6 + 5100 * 10^4 + 3620 * 10^2 + 1617
 Then we add in c before doing reduction, allowing us to get a * b + c =
 * 10^10 + 1296 * 10^8 + 4789 * 10^6 + 5122 * 10^4 + 3620 * 10^2 + 1712
 We then perform a tidying on the upper half of the terms:
 * 10^10 + 1296 * 10^8 + 4789 * 10^6
 * 10^10 + (1296 + 47) * 10^8 + 89 * 10^6
 * 10^10 + 1343 * 10^8 + 89 * 10^6
 * 10^10 + 43 * 10^8 + 89 * 10^6
 which then gives us
 * 10^10 + 43 * 10^8 + 89 * 10^6 + 5122 * 10^4 + 3620 * 10^2 + 1712
 we then reduce modulo p similar to the reduction example above:
 * 10^10 + 43 * 10^8 + 89 * 10^6 + 5122 * 10^4 + 3620 * 10^2 + 1712
 	- (13 * 10^4 * p)
 * 10^8 + 89 * 10^6 + 5109 * 10^4 + 3620 * 10^2 + 1712
 	- (69 * 10^2 * p)
 * 10^6 + 5109 * 10^4 + 3551 * 10^2 + 1712
 	- (227 * p)
 * 10^4 + 3551 * 10^2 + 1485
 finally, we do tidying to get the precision of each term down to 2 digits
 * 10^4 + 3565 * 10^2 + 85
 * 10^4 + 65 * 10^2 + 85
 * 10^6 + 98 * 10^4 + 65 * 10^2 + 85
 and perform another reduction step
 	- (55 * p)
 * 10^4 + 65 * 10^2 + 30
 There may be a small number of further reductions that could be done at
 this point, but this is typically done only at the end when converting
 from floating point  to an integer unit representation.
 FLOATING POINT PRECISION
 ========================
 This section discusses the precision of floating point numbers, which
 one writing new formulae or a larger bit size should be aware of.  The
 danger is that an intermediate result may be required to store a
 mantissa larger than 53 bits, which would cause error by rounding off.
 Note that the tidying with IEEE rounding mode set to round-to-even
 allows negative numbers, which actually reduces the size of the double
 mantissa to 23 bits - since it rounds the mantissa to the nearest number
 modulo 2^24, i.e. roughly between -2^23 and 2^23.
 A multiplication increases the bit size to 2^46 * n, where n is the number
 of doubles to store a number.  For the 224 bit curve, n = 10.  This gives
 doubles of size 5 * 2^47.  Adding two of these doubles gives a result
 of size 5 * 2^48, which is less than 2^53, so this is safe.
 Similar analysis can be done for other formulae to ensure numbers remain
 below 2^53.
 Extended-Precision Floating Point
 ---------------------------------
 Some platforms, notably x86 Linux, may use an extended-precision floating
 point representation that has a 64-bit mantissa.  [6]  Although this
 implementation is optimized for the IEEE standard 53-bit mantissa,
 it should work with the 64-bit mantissa.  A check is done at run-time
 in the function ec_set_fp_precision that detects if the precision is
 greater than 53 bits, and runs code for the 64-bit mantissa accordingly.
 REFERENCES
 ==========
 [1] Certicom Corp., "SEC 2: Recommended Elliptic Curve Domain Parameters", Sept. 20, 2000.  www.secg.org
 [2] Sun Microsystems Inc.  UltraSPARC III Cu User's Manual, Version 1.0, May 2002, Table 4.4
 [3] H. Cohen, A. Miyaji, and T. Ono, "Efficient Elliptic Curve Exponentiation Using Mixed Coordinates".
 [4] Henk C.A. van Tilborg, Generalized Mersenne Prime.  http://www.win.tue.nl/~henkvt/GenMersenne.pdf
 [5] Daniel J. Bernstein, Floating-Point Arithmetic and Message Authentication, Journal of Cryptology, March 2000, Section 2.
 [6] Daniel J. Bernstein, Floating-Point Arithmetic and Message Authentication, Journal of Cryptology, March 2000, Section 2 Notes.

The Tor Browser / annotate

security/nss/lib/freebl/ecl/README.FP@6474c204b198 (annotated)

security/nss/lib/freebl/ecl/README.FP