ecc-256.c

   1 /* ecc-256.c.c */
   2
   3 /* Compile time constant (but machine dependent) tables. */
   4
   5 /* nettle, low-level cryptographics library
   6  *
   7  * Copyright (C) 2013 Niels Möller
   8  *
   9  * The nettle library is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU Lesser General Public License as published by
  11  * the Free Software Foundation; either version 2.1 of the License, or (at your
  12  * option) any later version.
  13  *
  14  * The nettle library is distributed in the hope that it will be useful, but
  15  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  16  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  17  * License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public License
  20  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  21  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  22  * MA 02111-1301, USA.
  23  */
  24
  25 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  26
  27 #if HAVE_CONFIG_H
  28 # include "config.h"
  29 #endif
  30
  31 #include <assert.h>
  32
  33 #include "ecc-internal.h"
  34
  35 #if HAVE_NATIVE_ecc_256_redc
  36 # define USE_REDC 1
  37 #else
  38 # define USE_REDC (ECC_REDC_SIZE != 0)
  39 #endif
  40
  41 #include "ecc-256.h"
  42
  43 #if HAVE_NATIVE_ecc_256_redc
  44 # define ecc_256_redc nettle_ecc_256_redc
  45 void
  46 ecc_256_redc (const struct ecc_curve *ecc, mp_limb_t *rp);
  47 #else /* !HAVE_NATIVE_ecc_256_redc */
  48 # define ecc_256_redc ecc_generic_redc
  49 #endif
  50
  51 #if ECC_BMODP_SIZE < ECC_LIMB_SIZE
  52 #define ecc_256_modp ecc_generic_modp
  53 #define ecc_256_modq ecc_generic_modq
  54 #elif GMP_NUMB_BITS == 64
  55
  56 static void
  57 ecc_256_modp (const struct ecc_curve *ecc, mp_limb_t *rp)
  58 {
  59   mp_limb_t u1, u0;
  60   mp_size_t n;
  61
  62   n = 2*ecc->size;
  63   u1 = rp[--n];
  64   u0 = rp[n-1];
  65
  66   /* This is not particularly fast, but should work well with assembly implementation. */
  67   for (; n >= ecc->size; n--)
  68     {
  69       mp_limb_t q2, q1, q0, t, cy;
  70
  71       /* <q2, q1, q0> = v * u1 + <u1,u0>, with v = 2^32 - 1:
  72
  73            +---+---+
  74            | u1| u0|
  75            +---+---+
  76                |-u1|
  77              +-+-+-+
  78              | u1|
  79        +---+-+-+-+-+
  80        | q2| q1| q0|
  81        +---+---+---+
  82       */
  83       q1 = u1 - (u1 > u0);
  84       q0 = u0 - u1;
  85       t = u1 << 32;
  86       q0 += t;
  87       t = (u1 >> 32) + (q0 < t) + 1;
  88       q1 += t;
  89       q2 = q1 < t;
  90
  91       /* Compute candidate remainder */
  92       u1 = u0 + (q1 << 32) - q1;
  93       t = -(mp_limb_t) (u1 > q0);
  94       u1 -= t & 0xffffffff;
  95       q1 += t;
  96       q2 += t + (q1 < t);
  97
  98       assert (q2 < 2);
  99
 100       /* We multiply by two low limbs of p, 2^96 - 1, so we could use
 101          shifts rather than mul. */
 102       t = mpn_submul_1 (rp + n - 4, ecc->p, 2, q1);
 103       t += cnd_sub_n (q2, rp + n - 3, ecc->p, 1);
 104       t += (-q2) & 0xffffffff;
 105
 106       u0 = rp[n-2];
 107       cy = (u0 < t);
 108       u0 -= t;
 109       t = (u1 < cy);
 110       u1 -= cy;
 111       u1 += cnd_add_n (t, rp + n - 4, ecc->p, 3);
 112       u1 -= (-t) & 0xffffffff;
 113     }
 114   rp[2] = u0;
 115   rp[3] = u1;
 116 }
 117
 118 static void
 119 ecc_256_modq (const struct ecc_curve *ecc, mp_limb_t *rp)
 120 {
 121   mp_limb_t u2, u1, u0;
 122   mp_size_t n;
 123
 124   n = 2*ecc->size;
 125   u2 = rp[--n];
 126   u1 = rp[n-1];
 127
 128   /* This is not particularly fast, but should work well with assembly implementation. */
 129   for (; n >= ecc->size; n--)
 130     {
 131       mp_limb_t q2, q1, q0, t, c1, c0;
 132
 133       u0 = rp[n-2];
 134
 135       /* <q2, q1, q0> = v * u2 + <u2,u1>, same method as above.
 136
 137            +---+---+
 138            | u2| u1|
 139            +---+---+
 140                |-u2|
 141              +-+-+-+
 142              | u2|
 143        +---+-+-+-+-+
 144        | q2| q1| q0|
 145        +---+---+---+
 146       */
 147       q1 = u2 - (u2 > u1);
 148       q0 = u1 - u2;
 149       t = u2 << 32;
 150       q0 += t;
 151       t = (u2 >> 32) + (q0 < t) + 1;
 152       q1 += t;
 153       q2 = q1 < t;
 154
 155       /* Compute candidate remainder, <u1, u0> - <q2, q1> * (2^128 - 2^96 + 2^64 - 1)
 156          <u1, u0> + 2^64 q2 + (2^96 - 2^64 + 1) q1 (mod 2^128)
 157
 158            +---+---+
 159            | u1| u0|
 160            +---+---+
 161            | q2| q1|
 162            +---+---+
 163            |-q1|
 164          +-+-+-+
 165          | q1|
 166        --+-+-+-+---+
 167            | u2| u1|
 168            +---+---+
 169       */
 170       u2 = u1 + q2 - q1;
 171       u1 = u0 + q1;
 172       u2 += (u1 < q1);
 173       u2 += (q1 << 32);
 174
 175       t = -(mp_limb_t) (u2 >= q0);
 176       q1 += t;
 177       q2 += t + (q1 < t);
 178       u1 += t;
 179       u2 += (t << 32) + (u1 < t);
 180
 181       assert (q2 < 2);
 182
 183       c0 = cnd_sub_n (q2, rp + n - 3, ecc->q, 1);
 184       c0 += (-q2) & ecc->q[1];
 185       t = mpn_submul_1 (rp + n - 4, ecc->q, 2, q1);
 186       c0 += t;
 187       c1 = c0 < t;
 188
 189       /* Construct underflow condition. */
 190       c1 += (u1 < c0);
 191       t = - (mp_limb_t) (u2 < c1);
 192
 193       u1 -= c0;
 194       u2 -= c1;
 195
 196       /* Conditional add of p */
 197       u1 += t;
 198       u2 += (t<<32) + (u0 < t);
 199
 200       t = cnd_add_n (t, rp + n - 4, ecc->q, 2);
 201       u1 += t;
 202       u2 += (u1 < t);
 203     }
 204   rp[2] = u1;
 205   rp[3] = u2;
 206 }
 207
 208 #else
 209 #error Unsupported parameters
 210 #endif
 211
 212 const struct ecc_curve nettle_secp_256r1 =
 213 {
 214   256,
 215   ECC_LIMB_SIZE,
 216   ECC_BMODP_SIZE,
 217   ECC_BMODQ_SIZE,
 218   USE_REDC,
 219   ECC_REDC_SIZE,
 220   ECC_PIPPENGER_K,
 221   ECC_PIPPENGER_C,
 222   ecc_p,
 223   ecc_b,
 224   ecc_q,
 225   ecc_g,
 226   ecc_redc_g,
 227   ecc_256_modp,
 228   ecc_256_redc,
 229   USE_REDC ? ecc_256_redc : ecc_256_modp,
 230   ecc_256_modq,
 231   ecc_Bmodp,
 232   ecc_Bmodp_shifted,
 233   ecc_pp1h,
 234   ecc_redc_ppm1,
 235   ecc_unit,
 236   ecc_Bmodq,
 237   ecc_Bmodq_shifted,
 238   ecc_qp1h,
 239   ecc_table
 240 };