ecc-curve25519.c

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