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

   1 /* ecc-25519.c
   2
   3    Arithmetic and tables for curve25519,
   4
   5    Copyright (C) 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 #if HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #include <assert.h>
  39
  40 #include "ecc.h"
  41 #include "ecc-internal.h"
  42
  43 #define USE_REDC 0
  44
  45 #include "ecc-25519.h"
  46
  47 #define PHIGH_BITS (GMP_NUMB_BITS * ECC_LIMB_SIZE - 255)
  48
  49 #if HAVE_NATIVE_ecc_25519_modp
  50
  51 #define ecc_25519_modp nettle_ecc_25519_modp
  52 void
  53 ecc_25519_modp (const struct ecc_modulo *m, mp_limb_t *rp);
  54 #else
  55
  56 #if PHIGH_BITS == 0
  57 #error Unsupported limb size */
  58 #endif
  59
  60 static void
  61 ecc_25519_modp(const struct ecc_modulo *m UNUSED, mp_limb_t *rp)
  62 {
  63   mp_limb_t hi, cy;
  64
  65   cy = mpn_addmul_1 (rp, rp + ECC_LIMB_SIZE, ECC_LIMB_SIZE,
  66                      (mp_limb_t) 19 << PHIGH_BITS);
  67   hi = rp[ECC_LIMB_SIZE-1];
  68   cy = (cy << PHIGH_BITS) + (hi >> (GMP_NUMB_BITS - PHIGH_BITS));
  69   rp[ECC_LIMB_SIZE-1] = (hi & (GMP_NUMB_MASK >> PHIGH_BITS))
  70     + sec_add_1 (rp, rp, ECC_LIMB_SIZE - 1, 19 * cy);
  71 }
  72 #endif /* HAVE_NATIVE_ecc_25519_modp */
  73
  74 #define QHIGH_BITS (GMP_NUMB_BITS * ECC_LIMB_SIZE - 252)
  75
  76 #if QHIGH_BITS == 0
  77 #error Unsupported limb size */
  78 #endif
  79
  80 static void
  81 ecc_25519_modq (const struct ecc_modulo *q, mp_limb_t *rp)
  82 {
  83   mp_size_t n;
  84   mp_limb_t cy;
  85
  86   /* n is the offset where we add in the next term */
  87   for (n = ECC_LIMB_SIZE; n-- > 0;)
  88     {
  89       cy = mpn_submul_1 (rp + n,
  90                          q->B_shifted, ECC_LIMB_SIZE,
  91                          rp[n + ECC_LIMB_SIZE]);
  92       /* Top limb of mBmodq_shifted is zero, so we get cy == 0 or 1 */
  93       assert (cy < 2);
  94       cnd_add_n (cy, rp+n, q->m, ECC_LIMB_SIZE);
  95     }
  96
  97   cy = mpn_submul_1 (rp, q->m, ECC_LIMB_SIZE,
  98                      rp[ECC_LIMB_SIZE-1] >> (GMP_NUMB_BITS - QHIGH_BITS));
  99   assert (cy < 2);
 100   cnd_add_n (cy, rp, q->m, ECC_LIMB_SIZE);
 101 }
 102
 103 /* Needs 2*ecc->size limbs at rp, and 2*ecc->size additional limbs of
 104    scratch space. No overlap allowed. */
 105 static void
 106 ecc_mod_pow_2kp1 (const struct ecc_modulo *m,
 107                   mp_limb_t *rp, const mp_limb_t *xp,
 108                   unsigned k, mp_limb_t *tp)
 109 {
 110   if (k & 1)
 111     {
 112       ecc_mod_sqr (m, tp, xp);
 113       k--;
 114     }
 115   else
 116     {
 117       ecc_mod_sqr (m, rp, xp);
 118       ecc_mod_sqr (m, tp, rp);
 119       k -= 2;
 120     }
 121   while (k > 0)
 122     {
 123       ecc_mod_sqr (m, rp, tp);
 124       ecc_mod_sqr (m, tp, rp);
 125       k -= 2;
 126     }
 127   ecc_mod_mul (m, rp, tp, xp);
 128 }
 129
 130 /* Computes a^{(p-5)/8} = a^{2^{252}-3} mod m. Needs 5 * n scratch
 131    space. */
 132 static void
 133 ecc_mod_pow_252m3 (const struct ecc_modulo *m,
 134                    mp_limb_t *rp, const mp_limb_t *ap, mp_limb_t *scratch)
 135 {
 136 #define a7 scratch
 137 #define t0 (scratch + ECC_LIMB_SIZE)
 138 #define t1 (scratch + 3*ECC_LIMB_SIZE)
 139
 140   /* a^{2^252 - 3} = a^{(p-5)/8}, using the addition chain
 141      2^252 - 3
 142      = 1 + (2^252-4)
 143      = 1 + 4 (2^250-1)
 144      = 1 + 4 (2^125+1)(2^125-1)
 145      = 1 + 4 (2^125+1)(1+2(2^124-1))
 146      = 1 + 4 (2^125+1)(1+2(2^62+1)(2^62-1))
 147      = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(2^31-1))
 148      = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^28-1)))
 149      = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^14-1)))
 150      = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^7+1)(2^7-1)))
 151      = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^7+1)(1+2(2^6-1))))
 152      = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^7+1)(1+2(2^3+1)*7)))
 153   */
 154
 155   ecc_mod_pow_2kp1 (m, t0, ap, 1, t1);  /* a^3 */
 156   ecc_mod_sqr (m, rp, t0);              /* a^6 */
 157   ecc_mod_mul (m, a7, rp, ap);          /* a^7 */
 158   ecc_mod_pow_2kp1 (m, rp, a7, 3, t0);  /* a^63 = a^{2^6-1} */
 159   ecc_mod_sqr (m, t0, rp);              /* a^{2^7-2} */
 160   ecc_mod_mul (m, rp, t0, ap);          /* a^{2^7-1} */
 161   ecc_mod_pow_2kp1 (m, t0, rp, 7, t1);  /* a^{2^14-1}*/
 162   ecc_mod_pow_2kp1 (m, rp, t0, 14, t1); /* a^{2^28-1} */
 163   ecc_mod_sqr (m, t0, rp);              /* a^{2^29-2} */
 164   ecc_mod_sqr (m, t1, t0);              /* a^{2^30-4} */
 165   ecc_mod_sqr (m, t0, t1);              /* a^{2^31-8} */
 166   ecc_mod_mul (m, rp, t0, a7);          /* a^{2^31-1} */
 167   ecc_mod_pow_2kp1 (m, t0, rp, 31, t1); /* a^{2^62-1} */
 168   ecc_mod_pow_2kp1 (m, rp, t0, 62, t1); /* a^{2^124-1}*/
 169   ecc_mod_sqr (m, t0, rp);              /* a^{2^125-2} */
 170   ecc_mod_mul (m, rp, t0, ap);          /* a^{2^125-1} */
 171   ecc_mod_pow_2kp1 (m, t0, rp, 125, t1);/* a^{2^250-1} */
 172   ecc_mod_sqr (m, rp, t0);              /* a^{2^251-2} */
 173   ecc_mod_sqr (m, t0, rp);              /* a^{2^252-4} */
 174   ecc_mod_mul (m, rp, t0, ap);          /* a^{2^252-3} */
 175 #undef t0
 176 #undef t1
 177 #undef a7
 178 }
 179
 180 /* Needs 5*ECC_LIMB_SIZE scratch space. */
 181 #define ECC_25519_INV_ITCH (5*ECC_LIMB_SIZE)
 182
 183 static void ecc_25519_inv (const struct ecc_modulo *p,
 184                            mp_limb_t *rp, const mp_limb_t *ap,
 185                            mp_limb_t *scratch)
 186 {
 187 #define t0 scratch
 188
 189   /* Addition chain
 190
 191        p - 2 = 2^{255} - 21
 192              = 1 + 2 (1 + 4 (2^{252}-3))
 193   */
 194   ecc_mod_pow_252m3 (p, rp, ap, t0);
 195   ecc_mod_sqr (p, t0, rp);
 196   ecc_mod_sqr (p, rp, t0);
 197   ecc_mod_mul (p, t0, ap, rp);
 198   ecc_mod_sqr (p, rp, t0);
 199   ecc_mod_mul (p, t0, ap, rp);
 200   mpn_copyi (rp, t0, ECC_LIMB_SIZE); /* FIXME: Eliminate copy? */
 201 #undef t0
 202 }
 203
 204 /* First, do a canonical reduction, then check if zero */
 205 static int
 206 ecc_25519_zero_p (const struct ecc_modulo *p, mp_limb_t *xp)
 207 {
 208   mp_limb_t cy;
 209   mp_limb_t w;
 210   mp_size_t i;
 211 #if PHIGH_BITS > 0
 212   mp_limb_t hi = xp[ECC_LIMB_SIZE-1];
 213   xp[ECC_LIMB_SIZE-1] = (hi & (GMP_NUMB_MASK >> PHIGH_BITS))
 214     + sec_add_1 (xp, xp, ECC_LIMB_SIZE - 1, 19 * (hi >> (GMP_NUMB_BITS - PHIGH_BITS)));
 215 #endif
 216   cy = mpn_sub_n (xp, xp, p->m, ECC_LIMB_SIZE);
 217   cnd_add_n (cy, xp, p->m, ECC_LIMB_SIZE);
 218
 219   for (i = 0, w = 0; i < ECC_LIMB_SIZE; i++)
 220     w |= xp[i];
 221   return w == 0;
 222 }
 223
 224 /* Compute x such that x^2 = u/v (mod p). Returns one on success, zero
 225    on failure. We use the e = 2 special case of the Shanks-Tonelli
 226    algorithm (see http://www.math.vt.edu/people/brown/doc/sqrts.pdf,
 227    or Henri Cohen, Computational Algebraic Number Theory, 1.5.1).
 228
 229    To avoid a separate inversion, we also use a trick of djb's, to
 230    compute the candidate root as
 231
 232      x = (u/v)^{(p+3)/8} = u v^3 (u v^7)^{(p-5)/8}.
 233 */
 234 #if ECC_SQRT_E != 2
 235 #error Broken curve25519 parameters
 236 #endif
 237
 238 /* Needs 4*n space + scratch for ecc_mod_pow_252m3. */
 239 #define ECC_25519_SQRT_ITCH (9*ECC_LIMB_SIZE)
 240
 241 static int
 242 ecc_25519_sqrt(const struct ecc_modulo *p, mp_limb_t *rp,
 243                const mp_limb_t *up, const mp_limb_t *vp,
 244                mp_limb_t *scratch)
 245 {
 246   int pos, neg;
 247
 248 #define uv3 scratch
 249 #define uv7 (scratch + ECC_LIMB_SIZE)
 250 #define uv7p (scratch + 2*ECC_LIMB_SIZE)
 251 #define v2 (scratch + 2*ECC_LIMB_SIZE)
 252 #define uv (scratch + 3*ECC_LIMB_SIZE)
 253 #define v4 (scratch + 3*ECC_LIMB_SIZE)
 254
 255 #define scratch_out (scratch + 4 * ECC_LIMB_SIZE)
 256
 257 #define x2 scratch
 258 #define vx2 (scratch + ECC_LIMB_SIZE)
 259 #define t0 (scratch + 2*ECC_LIMB_SIZE)
 260
 261                                         /* Live values */
 262   ecc_mod_sqr (p, v2, vp);              /* v2 */
 263   ecc_mod_mul (p, uv, up, vp);          /* uv, v2 */
 264   ecc_mod_mul (p, uv3, uv, v2);         /* uv3, v2 */
 265   ecc_mod_sqr (p, v4, v2);              /* uv3, v4 */
 266   ecc_mod_mul (p, uv7, uv3, v4);        /* uv3, uv7 */
 267   ecc_mod_pow_252m3 (p, uv7p, uv7, scratch_out); /* uv3, uv7p */
 268   ecc_mod_mul (p, rp, uv7p, uv3);       /* none */
 269
 270   /* Check sign. If square root exists, have v x^2 = ±u */
 271   ecc_mod_sqr (p, x2, rp);
 272   ecc_mod_mul (p, vx2, x2, vp);
 273   ecc_mod_add (p, t0, vx2, up);
 274   neg = ecc_25519_zero_p (p, t0);
 275   ecc_mod_sub (p, t0, up, vx2);
 276   pos = ecc_25519_zero_p (p, t0);
 277
 278   ecc_mod_mul (p, t0, rp, ecc_sqrt_z);
 279   cnd_copy (neg, rp, t0, ECC_LIMB_SIZE);
 280   return pos | neg;
 281
 282 #undef uv3
 283 #undef uv7
 284 #undef uv7p
 285 #undef v2
 286 #undef v4
 287 #undef scratch_out
 288 #undef x2
 289 #undef vx2
 290 #undef t0
 291 }
 292
 293 const struct ecc_curve _nettle_curve25519 =
 294 {
 295   {
 296     255,
 297     ECC_LIMB_SIZE,
 298     ECC_BMODP_SIZE,
 299     0,
 300     ECC_25519_INV_ITCH,
 301     ECC_25519_SQRT_ITCH,
 302
 303     ecc_p,
 304     ecc_Bmodp,
 305     ecc_Bmodp_shifted,
 306     NULL,
 307     ecc_pp1h,
 308
 309     ecc_25519_modp,
 310     ecc_25519_modp,
 311     ecc_25519_inv,
 312     ecc_25519_sqrt,
 313   },
 314   {
 315     253,
 316     ECC_LIMB_SIZE,
 317     ECC_BMODQ_SIZE,
 318     0,
 319     ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
 320     0,
 321
 322     ecc_q,
 323     ecc_Bmodq,
 324     ecc_mBmodq_shifted, /* Use q - 2^{252} instead. */
 325     NULL,
 326     ecc_qp1h,
 327
 328     ecc_25519_modq,
 329     ecc_25519_modq,
 330     ecc_mod_inv,
 331     NULL,
 332   },
 333
 334   0, /* No redc */
 335   ECC_PIPPENGER_K,
 336   ECC_PIPPENGER_C,
 337
 338   ECC_ADD_EHH_ITCH (ECC_LIMB_SIZE),
 339   ECC_MUL_A_EH_ITCH (ECC_LIMB_SIZE),
 340   ECC_MUL_G_EH_ITCH (ECC_LIMB_SIZE),
 341   ECC_EH_TO_A_ITCH (ECC_LIMB_SIZE, ECC_25519_INV_ITCH),
 342
 343   ecc_add_ehh,
 344   ecc_mul_a_eh,
 345   ecc_mul_g_eh,
 346   ecc_eh_to_a,
 347
 348   ecc_d, /* Use the Edwards curve constant. */
 349   ecc_g,
 350   ecc_edwards,
 351   ecc_unit,
 352   ecc_table
 353 };