1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/ecl/ecp_fp.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,372 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +#ifndef __ecp_fp_h_
1.9 +#define __ecp_fp_h_
1.10 +
1.11 +#include "mpi.h"
1.12 +#include "ecl.h"
1.13 +#include "ecp.h"
1.14 +
1.15 +#include <sys/types.h>
1.16 +#include "mpi-priv.h"
1.17 +
1.18 +#ifdef ECL_DEBUG
1.19 +#include <assert.h>
1.20 +#endif
1.21 +
1.22 +/* Largest number of doubles to store one reduced number in floating
1.23 + * point. Used for memory allocation on the stack. */
1.24 +#define ECFP_MAXDOUBLES 10
1.25 +
1.26 +/* For debugging purposes */
1.27 +#ifndef ECL_DEBUG
1.28 +#define ECFP_ASSERT(x)
1.29 +#else
1.30 +#define ECFP_ASSERT(x) assert(x)
1.31 +#endif
1.32 +
1.33 +/* ECFP_Ti = 2^(i*24) Define as preprocessor constants so we can use in
1.34 + * multiple static constants */
1.35 +#define ECFP_T0 1.0
1.36 +#define ECFP_T1 16777216.0
1.37 +#define ECFP_T2 281474976710656.0
1.38 +#define ECFP_T3 4722366482869645213696.0
1.39 +#define ECFP_T4 79228162514264337593543950336.0
1.40 +#define ECFP_T5 1329227995784915872903807060280344576.0
1.41 +#define ECFP_T6 22300745198530623141535718272648361505980416.0
1.42 +#define ECFP_T7 374144419156711147060143317175368453031918731001856.0
1.43 +#define ECFP_T8 6277101735386680763835789423207666416102355444464034512896.0
1.44 +#define ECFP_T9 105312291668557186697918027683670432318895095400549111254310977536.0
1.45 +#define ECFP_T10 1766847064778384329583297500742918515827483896875618958121606201292619776.0
1.46 +#define ECFP_T11 29642774844752946028434172162224104410437116074403984394101141506025761187823616.0
1.47 +#define ECFP_T12 497323236409786642155382248146820840100456150797347717440463976893159497012533375533056.0
1.48 +#define ECFP_T13 8343699359066055009355553539724812947666814540455674882605631280555545803830627148527195652096.0
1.49 +#define ECFP_T14 139984046386112763159840142535527767382602843577165595931249318810236991948760059086304843329475444736.0
1.50 +#define ECFP_T15 2348542582773833227889480596789337027375682548908319870707290971532209025114608443463698998384768703031934976.0
1.51 +#define ECFP_T16 39402006196394479212279040100143613805079739270465446667948293404245\
1.52 +721771497210611414266254884915640806627990306816.0
1.53 +#define ECFP_T17 66105596879024859895191530803277103982840468296428121928464879527440\
1.54 +5791236311345825189210439715284847591212025023358304256.0
1.55 +#define ECFP_T18 11090678776483259438313656736572334813745748301503266300681918322458\
1.56 +485231222502492159897624416558312389564843845614287315896631296.0
1.57 +#define ECFP_T19 18607071341967536398062689481932916079453218833595342343206149099024\
1.58 +36577570298683715049089827234727835552055312041415509848580169253519\
1.59 +36.0
1.60 +
1.61 +#define ECFP_TWO160 1461501637330902918203684832716283019655932542976.0
1.62 +#define ECFP_TWO192 6277101735386680763835789423207666416102355444464034512896.0
1.63 +#define ECFP_TWO224 26959946667150639794667015087019630673637144422540572481103610249216.0
1.64 +
1.65 +/* Multiplicative constants */
1.66 +static const double ecfp_two32 = 4294967296.0;
1.67 +static const double ecfp_two64 = 18446744073709551616.0;
1.68 +static const double ecfp_twom16 = .0000152587890625;
1.69 +static const double ecfp_twom128 =
1.70 + .00000000000000000000000000000000000000293873587705571876992184134305561419454666389193021880377187926569604314863681793212890625;
1.71 +static const double ecfp_twom129 =
1.72 + .000000000000000000000000000000000000001469367938527859384960920671527807097273331945965109401885939632848021574318408966064453125;
1.73 +static const double ecfp_twom160 =
1.74 + .0000000000000000000000000000000000000000000000006842277657836020854119773355907793609766904013068924666782559979930620520927053718196475529111921787261962890625;
1.75 +static const double ecfp_twom192 =
1.76 + .000000000000000000000000000000000000000000000000000000000159309191113245227702888039776771180559110455519261878607388585338616290151305816094308987472018268594098344692611135542392730712890625;
1.77 +static const double ecfp_twom224 =
1.78 + .00000000000000000000000000000000000000000000000000000000000000000003709206150687421385731735261547639513367564778757791002453039058917581340095629358997312082723208437536338919136001159027049567384892725385725498199462890625;
1.79 +
1.80 +/* ecfp_exp[i] = 2^(i*ECFP_DSIZE) */
1.81 +static const double ecfp_exp[2 * ECFP_MAXDOUBLES] = {
1.82 + ECFP_T0, ECFP_T1, ECFP_T2, ECFP_T3, ECFP_T4, ECFP_T5,
1.83 + ECFP_T6, ECFP_T7, ECFP_T8, ECFP_T9, ECFP_T10, ECFP_T11,
1.84 + ECFP_T12, ECFP_T13, ECFP_T14, ECFP_T15, ECFP_T16, ECFP_T17, ECFP_T18,
1.85 + ECFP_T19
1.86 +};
1.87 +
1.88 +/* 1.1 * 2^52 Uses 2^52 to truncate, the .1 is an extra 2^51 to protect
1.89 + * the 2^52 bit, so that adding alphas to a negative number won't borrow
1.90 + * and empty the important 2^52 bit */
1.91 +#define ECFP_ALPHABASE_53 6755399441055744.0
1.92 +/* Special case: On some platforms, notably x86 Linux, there is an
1.93 + * extended-precision floating point representation with 64-bits of
1.94 + * precision in the mantissa. These extra bits of precision require a
1.95 + * larger value of alpha to truncate, i.e. 1.1 * 2^63. */
1.96 +#define ECFP_ALPHABASE_64 13835058055282163712.0
1.97 +
1.98 +/*
1.99 + * ecfp_alpha[i] = 1.5 * 2^(52 + i*ECFP_DSIZE) we add and subtract alpha
1.100 + * to truncate floating point numbers to a certain number of bits for
1.101 + * tidying */
1.102 +static const double ecfp_alpha_53[2 * ECFP_MAXDOUBLES] = {
1.103 + ECFP_ALPHABASE_53 * ECFP_T0,
1.104 + ECFP_ALPHABASE_53 * ECFP_T1,
1.105 + ECFP_ALPHABASE_53 * ECFP_T2,
1.106 + ECFP_ALPHABASE_53 * ECFP_T3,
1.107 + ECFP_ALPHABASE_53 * ECFP_T4,
1.108 + ECFP_ALPHABASE_53 * ECFP_T5,
1.109 + ECFP_ALPHABASE_53 * ECFP_T6,
1.110 + ECFP_ALPHABASE_53 * ECFP_T7,
1.111 + ECFP_ALPHABASE_53 * ECFP_T8,
1.112 + ECFP_ALPHABASE_53 * ECFP_T9,
1.113 + ECFP_ALPHABASE_53 * ECFP_T10,
1.114 + ECFP_ALPHABASE_53 * ECFP_T11,
1.115 + ECFP_ALPHABASE_53 * ECFP_T12,
1.116 + ECFP_ALPHABASE_53 * ECFP_T13,
1.117 + ECFP_ALPHABASE_53 * ECFP_T14,
1.118 + ECFP_ALPHABASE_53 * ECFP_T15,
1.119 + ECFP_ALPHABASE_53 * ECFP_T16,
1.120 + ECFP_ALPHABASE_53 * ECFP_T17,
1.121 + ECFP_ALPHABASE_53 * ECFP_T18,
1.122 + ECFP_ALPHABASE_53 * ECFP_T19
1.123 +};
1.124 +
1.125 +/*
1.126 + * ecfp_alpha[i] = 1.5 * 2^(63 + i*ECFP_DSIZE) we add and subtract alpha
1.127 + * to truncate floating point numbers to a certain number of bits for
1.128 + * tidying */
1.129 +static const double ecfp_alpha_64[2 * ECFP_MAXDOUBLES] = {
1.130 + ECFP_ALPHABASE_64 * ECFP_T0,
1.131 + ECFP_ALPHABASE_64 * ECFP_T1,
1.132 + ECFP_ALPHABASE_64 * ECFP_T2,
1.133 + ECFP_ALPHABASE_64 * ECFP_T3,
1.134 + ECFP_ALPHABASE_64 * ECFP_T4,
1.135 + ECFP_ALPHABASE_64 * ECFP_T5,
1.136 + ECFP_ALPHABASE_64 * ECFP_T6,
1.137 + ECFP_ALPHABASE_64 * ECFP_T7,
1.138 + ECFP_ALPHABASE_64 * ECFP_T8,
1.139 + ECFP_ALPHABASE_64 * ECFP_T9,
1.140 + ECFP_ALPHABASE_64 * ECFP_T10,
1.141 + ECFP_ALPHABASE_64 * ECFP_T11,
1.142 + ECFP_ALPHABASE_64 * ECFP_T12,
1.143 + ECFP_ALPHABASE_64 * ECFP_T13,
1.144 + ECFP_ALPHABASE_64 * ECFP_T14,
1.145 + ECFP_ALPHABASE_64 * ECFP_T15,
1.146 + ECFP_ALPHABASE_64 * ECFP_T16,
1.147 + ECFP_ALPHABASE_64 * ECFP_T17,
1.148 + ECFP_ALPHABASE_64 * ECFP_T18,
1.149 + ECFP_ALPHABASE_64 * ECFP_T19
1.150 +};
1.151 +
1.152 +/* 0.011111111111111111111111 (binary) = 0.5 - 2^25 (24 ones) */
1.153 +#define ECFP_BETABASE 0.4999999701976776123046875
1.154 +
1.155 +/*
1.156 + * We subtract beta prior to using alpha to simulate rounding down. We
1.157 + * make this close to 0.5 to round almost everything down, but exactly 0.5
1.158 + * would cause some incorrect rounding. */
1.159 +static const double ecfp_beta[2 * ECFP_MAXDOUBLES] = {
1.160 + ECFP_BETABASE * ECFP_T0,
1.161 + ECFP_BETABASE * ECFP_T1,
1.162 + ECFP_BETABASE * ECFP_T2,
1.163 + ECFP_BETABASE * ECFP_T3,
1.164 + ECFP_BETABASE * ECFP_T4,
1.165 + ECFP_BETABASE * ECFP_T5,
1.166 + ECFP_BETABASE * ECFP_T6,
1.167 + ECFP_BETABASE * ECFP_T7,
1.168 + ECFP_BETABASE * ECFP_T8,
1.169 + ECFP_BETABASE * ECFP_T9,
1.170 + ECFP_BETABASE * ECFP_T10,
1.171 + ECFP_BETABASE * ECFP_T11,
1.172 + ECFP_BETABASE * ECFP_T12,
1.173 + ECFP_BETABASE * ECFP_T13,
1.174 + ECFP_BETABASE * ECFP_T14,
1.175 + ECFP_BETABASE * ECFP_T15,
1.176 + ECFP_BETABASE * ECFP_T16,
1.177 + ECFP_BETABASE * ECFP_T17,
1.178 + ECFP_BETABASE * ECFP_T18,
1.179 + ECFP_BETABASE * ECFP_T19
1.180 +};
1.181 +
1.182 +static const double ecfp_beta_160 = ECFP_BETABASE * ECFP_TWO160;
1.183 +static const double ecfp_beta_192 = ECFP_BETABASE * ECFP_TWO192;
1.184 +static const double ecfp_beta_224 = ECFP_BETABASE * ECFP_TWO224;
1.185 +
1.186 +/* Affine EC Point. This is the basic representation (x, y) of an elliptic
1.187 + * curve point. */
1.188 +typedef struct {
1.189 + double x[ECFP_MAXDOUBLES];
1.190 + double y[ECFP_MAXDOUBLES];
1.191 +} ecfp_aff_pt;
1.192 +
1.193 +/* Jacobian EC Point. This coordinate system uses X = x/z^2, Y = y/z^3,
1.194 + * which enables calculations with fewer inversions than affine
1.195 + * coordinates. */
1.196 +typedef struct {
1.197 + double x[ECFP_MAXDOUBLES];
1.198 + double y[ECFP_MAXDOUBLES];
1.199 + double z[ECFP_MAXDOUBLES];
1.200 +} ecfp_jac_pt;
1.201 +
1.202 +/* Chudnovsky Jacobian EC Point. This coordinate system is the same as
1.203 + * Jacobian, except it keeps z^2, z^3 for faster additions. */
1.204 +typedef struct {
1.205 + double x[ECFP_MAXDOUBLES];
1.206 + double y[ECFP_MAXDOUBLES];
1.207 + double z[ECFP_MAXDOUBLES];
1.208 + double z2[ECFP_MAXDOUBLES];
1.209 + double z3[ECFP_MAXDOUBLES];
1.210 +} ecfp_chud_pt;
1.211 +
1.212 +/* Modified Jacobian EC Point. This coordinate system is the same as
1.213 + * Jacobian, except it keeps a*z^4 for faster doublings. */
1.214 +typedef struct {
1.215 + double x[ECFP_MAXDOUBLES];
1.216 + double y[ECFP_MAXDOUBLES];
1.217 + double z[ECFP_MAXDOUBLES];
1.218 + double az4[ECFP_MAXDOUBLES];
1.219 +} ecfp_jm_pt;
1.220 +
1.221 +struct EC_group_fp_str;
1.222 +
1.223 +typedef struct EC_group_fp_str EC_group_fp;
1.224 +struct EC_group_fp_str {
1.225 + int fpPrecision; /* Set to number of bits in mantissa, 53
1.226 + * or 64 */
1.227 + int numDoubles;
1.228 + int primeBitSize;
1.229 + int orderBitSize;
1.230 + int doubleBitSize;
1.231 + int numInts;
1.232 + int aIsM3; /* True if curvea == -3 (mod p), then we
1.233 + * can optimize doubling */
1.234 + double curvea[ECFP_MAXDOUBLES];
1.235 + /* Used to truncate a double to the number of bits in the curve */
1.236 + double bitSize_alpha;
1.237 + /* Pointer to either ecfp_alpha_53 or ecfp_alpha_64 */
1.238 + const double *alpha;
1.239 +
1.240 + void (*ecfp_singleReduce) (double *r, const EC_group_fp * group);
1.241 + void (*ecfp_reduce) (double *r, double *x, const EC_group_fp * group);
1.242 + /* Performs a "tidy" operation, which performs carrying, moving excess
1.243 + * bits from one double to the next double, so that the precision of
1.244 + * the doubles is reduced to the regular precision ECFP_DSIZE. This
1.245 + * might result in some float digits being negative. */
1.246 + void (*ecfp_tidy) (double *t, const double *alpha,
1.247 + const EC_group_fp * group);
1.248 + /* Perform a point addition using coordinate system Jacobian + Affine
1.249 + * -> Jacobian. Input and output should be multi-precision floating
1.250 + * point integers. */
1.251 + void (*pt_add_jac_aff) (const ecfp_jac_pt * p, const ecfp_aff_pt * q,
1.252 + ecfp_jac_pt * r, const EC_group_fp * group);
1.253 + /* Perform a point doubling in Jacobian coordinates. Input and output
1.254 + * should be multi-precision floating point integers. */
1.255 + void (*pt_dbl_jac) (const ecfp_jac_pt * dp, ecfp_jac_pt * dr,
1.256 + const EC_group_fp * group);
1.257 + /* Perform a point addition using Jacobian coordinate system. Input
1.258 + * and output should be multi-precision floating point integers. */
1.259 + void (*pt_add_jac) (const ecfp_jac_pt * p, const ecfp_jac_pt * q,
1.260 + ecfp_jac_pt * r, const EC_group_fp * group);
1.261 + /* Perform a point doubling in Modified Jacobian coordinates. Input
1.262 + * and output should be multi-precision floating point integers. */
1.263 + void (*pt_dbl_jm) (const ecfp_jm_pt * p, ecfp_jm_pt * r,
1.264 + const EC_group_fp * group);
1.265 + /* Perform a point doubling using coordinates Affine -> Chudnovsky
1.266 + * Jacobian. Input and output should be multi-precision floating point
1.267 + * integers. */
1.268 + void (*pt_dbl_aff2chud) (const ecfp_aff_pt * p, ecfp_chud_pt * r,
1.269 + const EC_group_fp * group);
1.270 + /* Perform a point addition using coordinates: Modified Jacobian +
1.271 + * Chudnovsky Jacobian -> Modified Jacobian. Input and output should
1.272 + * be multi-precision floating point integers. */
1.273 + void (*pt_add_jm_chud) (ecfp_jm_pt * p, ecfp_chud_pt * q,
1.274 + ecfp_jm_pt * r, const EC_group_fp * group);
1.275 + /* Perform a point addition using Chudnovsky Jacobian coordinates.
1.276 + * Input and output should be multi-precision floating point integers.
1.277 + */
1.278 + void (*pt_add_chud) (const ecfp_chud_pt * p, const ecfp_chud_pt * q,
1.279 + ecfp_chud_pt * r, const EC_group_fp * group);
1.280 + /* Expects out to be an array of size 16 of Chudnovsky Jacobian
1.281 + * points. Fills in Chudnovsky Jacobian form (x, y, z, z^2, z^3), for
1.282 + * -15P, -13P, -11P, -9P, -7P, -5P, -3P, -P, P, 3P, 5P, 7P, 9P, 11P,
1.283 + * 13P, 15P */
1.284 + void (*precompute_chud) (ecfp_chud_pt * out, const ecfp_aff_pt * p,
1.285 + const EC_group_fp * group);
1.286 + /* Expects out to be an array of size 16 of Jacobian points. Fills in
1.287 + * Chudnovsky Jacobian form (x, y, z), for O, P, 2P, ... 15P */
1.288 + void (*precompute_jac) (ecfp_jac_pt * out, const ecfp_aff_pt * p,
1.289 + const EC_group_fp * group);
1.290 +
1.291 +};
1.292 +
1.293 +/* Computes r = x*y.
1.294 + * r must be different (point to different memory) than x and y.
1.295 + * Does not tidy or reduce. */
1.296 +void ecfp_multiply(double *r, const double *x, const double *y);
1.297 +
1.298 +/* Performs a "tidy" operation, which performs carrying, moving excess
1.299 + * bits from one double to the next double, so that the precision of the
1.300 + * doubles is reduced to the regular precision group->doubleBitSize. This
1.301 + * might result in some float digits being negative. */
1.302 +void ecfp_tidy(double *t, const double *alpha, const EC_group_fp * group);
1.303 +
1.304 +/* Performs tidying on only the upper float digits of a multi-precision
1.305 + * floating point integer, i.e. the digits beyond the regular length which
1.306 + * are removed in the reduction step. */
1.307 +void ecfp_tidyUpper(double *t, const EC_group_fp * group);
1.308 +
1.309 +/* Performs tidying on a short multi-precision floating point integer (the
1.310 + * lower group->numDoubles floats). */
1.311 +void ecfp_tidyShort(double *t, const EC_group_fp * group);
1.312 +
1.313 +/* Performs a more mathematically precise "tidying" so that each term is
1.314 + * positive. This is slower than the regular tidying, and is used for
1.315 + * conversion from floating point to integer. */
1.316 +void ecfp_positiveTidy(double *t, const EC_group_fp * group);
1.317 +
1.318 +/* Computes R = nP where R is (rx, ry) and P is (px, py). The parameters
1.319 + * a, b and p are the elliptic curve coefficients and the prime that
1.320 + * determines the field GFp. Elliptic curve points P and R can be
1.321 + * identical. Uses mixed Jacobian-affine coordinates. Uses 4-bit window
1.322 + * method. */
1.323 +mp_err
1.324 + ec_GFp_point_mul_jac_4w_fp(const mp_int *n, const mp_int *px,
1.325 + const mp_int *py, mp_int *rx, mp_int *ry,
1.326 + const ECGroup *ecgroup);
1.327 +
1.328 +/* Computes R = nP where R is (rx, ry) and P is the base point. The
1.329 + * parameters a, b and p are the elliptic curve coefficients and the prime
1.330 + * that determines the field GFp. Elliptic curve points P and R can be
1.331 + * identical. Uses mixed Jacobian-affine coordinates (Jacobian
1.332 + * coordinates for doubles and affine coordinates for additions; based on
1.333 + * recommendation from Brown et al.). Uses window NAF method (algorithm
1.334 + * 11) for scalar-point multiplication from Brown, Hankerson, Lopez,
1.335 + * Menezes. Software Implementation of the NIST Elliptic Curves Over Prime
1.336 + * Fields. */
1.337 +mp_err ec_GFp_point_mul_wNAF_fp(const mp_int *n, const mp_int *px,
1.338 + const mp_int *py, mp_int *rx, mp_int *ry,
1.339 + const ECGroup *ecgroup);
1.340 +
1.341 +/* Uses mixed Jacobian-affine coordinates to perform a point
1.342 + * multiplication: R = n * P, n scalar. Uses mixed Jacobian-affine
1.343 + * coordinates (Jacobian coordinates for doubles and affine coordinates
1.344 + * for additions; based on recommendation from Brown et al.). Not very
1.345 + * time efficient but quite space efficient, no precomputation needed.
1.346 + * group contains the elliptic curve coefficients and the prime that
1.347 + * determines the field GFp. Elliptic curve points P and R can be
1.348 + * identical. Performs calculations in floating point number format, since
1.349 + * this is faster than the integer operations on the ULTRASPARC III.
1.350 + * Uses left-to-right binary method (double & add) (algorithm 9) for
1.351 + * scalar-point multiplication from Brown, Hankerson, Lopez, Menezes.
1.352 + * Software Implementation of the NIST Elliptic Curves Over Prime Fields. */
1.353 +mp_err
1.354 + ec_GFp_pt_mul_jac_fp(const mp_int *n, const mp_int *px, const mp_int *py,
1.355 + mp_int *rx, mp_int *ry, const ECGroup *ecgroup);
1.356 +
1.357 +/* Cleans up extra memory allocated in ECGroup for this implementation. */
1.358 +void ec_GFp_extra_free_fp(ECGroup *group);
1.359 +
1.360 +/* Converts from a floating point representation into an mp_int. Expects
1.361 + * that d is already reduced. */
1.362 +void
1.363 + ecfp_fp2i(mp_int *mpout, double *d, const ECGroup *ecgroup);
1.364 +
1.365 +/* Converts from an mpint into a floating point representation. */
1.366 +void
1.367 + ecfp_i2fp(double *out, const mp_int *x, const ECGroup *ecgroup);
1.368 +
1.369 +/* Tests what precision floating point arithmetic is set to. This should
1.370 + * be either a 53-bit mantissa (IEEE standard) or a 64-bit mantissa
1.371 + * (extended precision on x86) and sets it into the EC_group_fp. Returns
1.372 + * either 53 or 64 accordingly. */
1.373 +int ec_set_fp_precision(EC_group_fp * group);
1.374 +
1.375 +#endif
