git.samba.org - gd/nettle/blob - ecc-256.c

   1 /* ecc-256.c
   2
   3    Compile time constant (but machine dependent) tables.
   4
   5    Copyright (C) 2013, 2014 Niels Möller
   6
   7    This file is part of GNU Nettle.
   8
   9    GNU Nettle is free software: you can redistribute it and/or
  10    modify it under the terms of either:
  11
  12      * the GNU Lesser General Public License as published by the Free
  13        Software Foundation; either version 3 of the License, or (at your
  14        option) any later version.
  15
  16    or
  17
  18      * the GNU General Public License as published by the Free
  19        Software Foundation; either version 2 of the License, or (at your
  20        option) any later version.
  21
  22    or both in parallel, as here.
  23
  24    GNU Nettle is distributed in the hope that it will be useful,
  25    but WITHOUT ANY WARRANTY; without even the implied warranty of
  26    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27    General Public License for more details.
  28
  29    You should have received copies of the GNU General Public License and
  30    the GNU Lesser General Public License along with this program.  If
  31    not, see http://www.gnu.org/licenses/.
  32 */
  33
  34 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  35
  36 #if HAVE_CONFIG_H
  37 # include "config.h"
  38 #endif
  39
  40 #include <assert.h>
  41
  42 #include "ecc.h"
  43 #include "ecc-internal.h"
  44
  45 #if HAVE_NATIVE_ecc_256_redc
  46 # define USE_REDC 1
  47 #else
  48 # define USE_REDC (ECC_REDC_SIZE != 0)
  49 #endif
  50
  51 #include "ecc-256.h"
  52
  53 #if HAVE_NATIVE_ecc_256_redc
  54 # define ecc_256_redc nettle_ecc_256_redc
  55 void
  56 ecc_256_redc (const struct ecc_modulo *p, mp_limb_t *rp);
  57 #else /* !HAVE_NATIVE_ecc_256_redc */
  58 # if ECC_REDC_SIZE > 0
  59 #   define ecc_256_redc ecc_pp1_redc
  60 # elif ECC_REDC_SIZE == 0
  61 #   define ecc_256_redc NULL
  62 # else
  63 #  error Configuration error
  64 # endif
  65 #endif /* !HAVE_NATIVE_ecc_256_redc */
  66
  67 #if ECC_BMODP_SIZE < ECC_LIMB_SIZE
  68 #define ecc_256_modp ecc_mod
  69 #define ecc_256_modq ecc_mod
  70 #elif GMP_NUMB_BITS == 64
  71
  72 static void
  73 ecc_256_modp (const struct ecc_modulo *p, mp_limb_t *rp)
  74 {
  75   mp_limb_t u1, u0;
  76   mp_size_t n;
  77
  78   n = 2*p->size;
  79   u1 = rp[--n];
  80   u0 = rp[n-1];
  81
  82   /* This is not particularly fast, but should work well with assembly implementation. */
  83   for (; n >= p->size; n--)
  84     {
  85       mp_limb_t q2, q1, q0, t, cy;
  86
  87       /* <q2, q1, q0> = v * u1 + <u1,u0>, with v = 2^32 - 1:
  88
  89            +---+---+
  90            | u1| u0|
  91            +---+---+
  92                |-u1|
  93              +-+-+-+
  94              | u1|
  95        +---+-+-+-+-+
  96        | q2| q1| q0|
  97        +---+---+---+
  98       */
  99       q1 = u1 - (u1 > u0);
 100       q0 = u0 - u1;
 101       t = u1 << 32;
 102       q0 += t;
 103       t = (u1 >> 32) + (q0 < t) + 1;
 104       q1 += t;
 105       q2 = q1 < t;
 106
 107       /* Compute candidate remainder */
 108       u1 = u0 + (q1 << 32) - q1;
 109       t = -(mp_limb_t) (u1 > q0);
 110       u1 -= t & 0xffffffff;
 111       q1 += t;
 112       q2 += t + (q1 < t);
 113
 114       assert (q2 < 2);
 115
 116       /*
 117          n-1 n-2 n-3 n-4
 118         +---+---+---+---+
 119         | u1| u0| u low |
 120         +---+---+---+---+
 121           - | q1(2^96-1)|
 122             +-------+---+
 123             |q2(2^.)|
 124             +-------+
 125
 126          We multiply by two low limbs of p, 2^96 - 1, so we could use
 127          shifts rather than mul.
 128       */
 129       t = mpn_submul_1 (rp + n - 4, p->m, 2, q1);
 130       t += cnd_sub_n (q2, rp + n - 3, p->m, 1);
 131       t += (-q2) & 0xffffffff;
 132
 133       u0 = rp[n-2];
 134       cy = (u0 < t);
 135       u0 -= t;
 136       t = (u1 < cy);
 137       u1 -= cy;
 138
 139       cy = cnd_add_n (t, rp + n - 4, p->m, 2);
 140       u0 += cy;
 141       u1 += (u0 < cy);
 142       u1 -= (-t) & 0xffffffff;
 143     }
 144   rp[2] = u0;
 145   rp[3] = u1;
 146 }
 147
 148 static void
 149 ecc_256_modq (const struct ecc_modulo *q, mp_limb_t *rp)
 150 {
 151   mp_limb_t u2, u1, u0;
 152   mp_size_t n;
 153
 154   n = 2*q->size;
 155   u2 = rp[--n];
 156   u1 = rp[n-1];
 157
 158   /* This is not particularly fast, but should work well with assembly implementation. */
 159   for (; n >= q->size; n--)
 160     {
 161       mp_limb_t q2, q1, q0, t, c1, c0;
 162
 163       u0 = rp[n-2];
 164
 165       /* <q2, q1, q0> = v * u2 + <u2,u1>, same method as above.
 166
 167            +---+---+
 168            | u2| u1|
 169            +---+---+
 170                |-u2|
 171              +-+-+-+
 172              | u2|
 173        +---+-+-+-+-+
 174        | q2| q1| q0|
 175        +---+---+---+
 176       */
 177       q1 = u2 - (u2 > u1);
 178       q0 = u1 - u2;
 179       t = u2 << 32;
 180       q0 += t;
 181       t = (u2 >> 32) + (q0 < t) + 1;
 182       q1 += t;
 183       q2 = q1 < t;
 184
 185       /* Compute candidate remainder, <u1, u0> - <q2, q1> * (2^128 - 2^96 + 2^64 - 1)
 186          <u1, u0> + 2^64 q2 + (2^96 - 2^64 + 1) q1 (mod 2^128)
 187
 188            +---+---+
 189            | u1| u0|
 190            +---+---+
 191            | q2| q1|
 192            +---+---+
 193            |-q1|
 194          +-+-+-+
 195          | q1|
 196        --+-+-+-+---+
 197            | u2| u1|
 198            +---+---+
 199       */
 200       u2 = u1 + q2 - q1;
 201       u1 = u0 + q1;
 202       u2 += (u1 < q1);
 203       u2 += (q1 << 32);
 204
 205       t = -(mp_limb_t) (u2 >= q0);
 206       q1 += t;
 207       q2 += t + (q1 < t);
 208       u1 += t;
 209       u2 += (t << 32) + (u1 < t);
 210
 211       assert (q2 < 2);
 212
 213       c0 = cnd_sub_n (q2, rp + n - 3, q->m, 1);
 214       c0 += (-q2) & q->m[1];
 215       t = mpn_submul_1 (rp + n - 4, q->m, 2, q1);
 216       c0 += t;
 217       c1 = c0 < t;
 218
 219       /* Construct underflow condition. */
 220       c1 += (u1 < c0);
 221       t = - (mp_limb_t) (u2 < c1);
 222
 223       u1 -= c0;
 224       u2 -= c1;
 225
 226       /* Conditional add of p */
 227       u1 += t;
 228       u2 += (t<<32) + (u1 < t);
 229
 230       t = cnd_add_n (t, rp + n - 4, q->m, 2);
 231       u1 += t;
 232       u2 += (u1 < t);
 233     }
 234   rp[2] = u1;
 235   rp[3] = u2;
 236 }
 237
 238 #else
 239 #error Unsupported parameters
 240 #endif
 241
 242 const struct ecc_curve _nettle_secp_256r1 =
 243 {
 244   {
 245     256,
 246     ECC_LIMB_SIZE,
 247     ECC_BMODP_SIZE,
 248     ECC_REDC_SIZE,
 249     ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
 250     0,
 251
 252     ecc_p,
 253     ecc_Bmodp,
 254     ecc_Bmodp_shifted,
 255     ecc_redc_ppm1,
 256
 257     ecc_pp1h,
 258     ecc_256_modp,
 259     USE_REDC ? ecc_256_redc : ecc_256_modp,
 260     ecc_mod_inv,
 261     NULL,
 262   },
 263   {
 264     256,
 265     ECC_LIMB_SIZE,
 266     ECC_BMODQ_SIZE,
 267     0,
 268     ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
 269     0,
 270
 271     ecc_q,
 272     ecc_Bmodq,
 273     ecc_Bmodq_shifted,
 274     NULL,
 275     ecc_qp1h,
 276
 277     ecc_256_modq,
 278     ecc_256_modq,
 279     ecc_mod_inv,
 280     NULL,
 281   },
 282
 283   USE_REDC,
 284   ECC_PIPPENGER_K,
 285   ECC_PIPPENGER_C,
 286
 287   ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE),
 288   ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
 289   ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
 290   ECC_J_TO_A_ITCH (ECC_LIMB_SIZE),
 291
 292   ecc_add_jjj,
 293   ecc_mul_a,
 294   ecc_mul_g,
 295   ecc_j_to_a,
 296
 297   ecc_b,
 298   ecc_g,
 299   NULL,
 300   ecc_unit,
 301   ecc_table
 302 };
 303
 304 const struct ecc_curve *nettle_get_secp_256r1(void)
 305 {
 306   return &_nettle_secp_256r1;
 307 }