ecc-25519.c 8.09 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1
/* ecc-25519.c
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

   Arithmetic and tables for curve25519,

   Copyright (C) 2014 Niels Möller

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or
   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free
       Software Foundation; either version 3 of the License, or (at your
       option) any later version.

   or

     * the GNU General Public License as published by the Free
       Software Foundation; either version 2 of the License, or (at your
       option) any later version.

   or both in parallel, as here.

   GNU Nettle is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received copies of the GNU General Public License and
   the GNU Lesser General Public License along with this program.  If
   not, see http://www.gnu.org/licenses/.
*/

#if HAVE_CONFIG_H
# include "config.h"
#endif

Niels Möller's avatar
Niels Möller committed
38 39
#include <assert.h>

40
#include "ecc.h"
41 42 43 44 45 46
#include "ecc-internal.h"

#define USE_REDC 0

#include "ecc-25519.h"

47 48 49 50
#if HAVE_NATIVE_ecc_25519_modp

#define ecc_25519_modp nettle_ecc_25519_modp
void
51
ecc_25519_modp (const struct ecc_modulo *m, mp_limb_t *rp);
52 53
#else

Niels Möller's avatar
Niels Möller committed
54
#define PHIGH_BITS (GMP_NUMB_BITS * ECC_LIMB_SIZE - 255)
55

Niels Möller's avatar
Niels Möller committed
56
#if PHIGH_BITS == 0
57 58 59 60
#error Unsupported limb size */
#endif

static void
61
ecc_25519_modp(const struct ecc_modulo *m UNUSED, mp_limb_t *rp)
62 63 64 65
{
  mp_limb_t hi, cy;

  cy = mpn_addmul_1 (rp, rp + ECC_LIMB_SIZE, ECC_LIMB_SIZE,
Niels Möller's avatar
Niels Möller committed
66
		     (mp_limb_t) 19 << PHIGH_BITS);
67
  hi = rp[ECC_LIMB_SIZE-1];
Niels Möller's avatar
Niels Möller committed
68 69
  cy = (cy << PHIGH_BITS) + (hi >> (GMP_NUMB_BITS - PHIGH_BITS));
  rp[ECC_LIMB_SIZE-1] = (hi & (GMP_NUMB_MASK >> PHIGH_BITS))
70 71
    + sec_add_1 (rp, rp, ECC_LIMB_SIZE - 1, 19 * cy);
}
72 73
#endif /* HAVE_NATIVE_ecc_25519_modp */

Niels Möller's avatar
Niels Möller committed
74 75 76 77 78 79 80
#define QHIGH_BITS (GMP_NUMB_BITS * ECC_LIMB_SIZE - 252)

#if QHIGH_BITS == 0
#error Unsupported limb size */
#endif

static void
81
ecc_25519_modq (const struct ecc_modulo *q, mp_limb_t *rp)
Niels Möller's avatar
Niels Möller committed
82 83 84 85 86 87 88 89
{
  mp_size_t n;
  mp_limb_t cy;

  /* n is the offset where we add in the next term */
  for (n = ECC_LIMB_SIZE; n-- > 0;)
    {
      cy = mpn_submul_1 (rp + n,
90
			 q->B_shifted, ECC_LIMB_SIZE,
Niels Möller's avatar
Niels Möller committed
91 92 93
			 rp[n + ECC_LIMB_SIZE]);
      /* Top limb of mBmodq_shifted is zero, so we get cy == 0 or 1 */
      assert (cy < 2);
94
      cnd_add_n (cy, rp+n, q->m, ECC_LIMB_SIZE);
Niels Möller's avatar
Niels Möller committed
95 96
    }

97
  cy = mpn_submul_1 (rp, q->m, ECC_LIMB_SIZE,
Niels Möller's avatar
Niels Möller committed
98 99
		     rp[ECC_LIMB_SIZE-1] >> (GMP_NUMB_BITS - QHIGH_BITS));
  assert (cy < 2);
100
  cnd_add_n (cy, rp, q->m, ECC_LIMB_SIZE);
Niels Möller's avatar
Niels Möller committed
101 102
}

103 104 105
/* Needs 2*ecc->size limbs at rp, and 2*ecc->size additional limbs of
   scratch space. No overlap allowed. */
static void
106 107 108
ecc_mod_pow_2kp1 (const struct ecc_modulo *m,
		  mp_limb_t *rp, const mp_limb_t *xp,
		  unsigned k, mp_limb_t *tp)
109 110 111
{
  if (k & 1)
    {
112
      ecc_mod_sqr (m, tp, xp);
113 114 115 116
      k--;
    }
  else
    {
117 118
      ecc_mod_sqr (m, rp, xp);
      ecc_mod_sqr (m, tp, rp);
119 120 121 122
      k -= 2;
    }
  while (k > 0)
    {
123 124
      ecc_mod_sqr (m, rp, tp);
      ecc_mod_sqr (m, tp, rp);
125 126
      k -= 2;
    }
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
  ecc_mod_mul (m, rp, tp, xp);
}

/* Computes a^{2^{252-3}} mod m. Needs 5 * n scratch space. */
static void
ecc_mod_pow_252m3 (const struct ecc_modulo *m,
		   mp_limb_t *rp, const mp_limb_t *ap, mp_limb_t *scratch)
{
#define a7 scratch
#define t0 (scratch + ECC_LIMB_SIZE)
#define t1 (scratch + 3*ECC_LIMB_SIZE)

  /* a^{2^252 - 3} = a^{(p-5)/8}, using the addition chain
     2^252 - 3
     = 1 + (2^252-4)
     = 1 + 4 (2^250-1)
     = 1 + 4 (2^125+1)(2^125-1)
     = 1 + 4 (2^125+1)(1+2(2^124-1))
     = 1 + 4 (2^125+1)(1+2(2^62+1)(2^62-1))
     = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(2^31-1))
     = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^28-1)))
     = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^14-1)))
     = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^7+1)(2^7-1)))
     = 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))))
     = 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)))
  */ 
     
  ecc_mod_pow_2kp1 (m, t0, ap, 1, t1);	/* a^3 */
  ecc_mod_sqr (m, rp, t0);		/* a^6 */
  ecc_mod_mul (m, a7, rp, ap);		/* a^7 */
  ecc_mod_pow_2kp1 (m, rp, a7, 3, t0);	/* a^63 = a^{2^6-1} */
  ecc_mod_sqr (m, t0, rp);		/* a^{2^7-2} */
  ecc_mod_mul (m, rp, t0, ap);		/* a^{2^7-1} */
  ecc_mod_pow_2kp1 (m, t0, rp, 7, t1);	/* a^{2^14-1}*/
  ecc_mod_pow_2kp1 (m, rp, t0, 14, t1);	/* a^{2^28-1} */
  ecc_mod_sqr (m, t0, rp);		/* a^{2^29-2} */
  ecc_mod_sqr (m, t1, t0);		/* a^{2^30-4} */
  ecc_mod_sqr (m, t0, t1);		/* a^{2^31-8} */
  ecc_mod_mul (m, rp, t0, a7);		/* a^{2^31-1} */
  ecc_mod_pow_2kp1 (m, t0, rp, 31, t1);	/* a^{2^62-1} */  
  ecc_mod_pow_2kp1 (m, rp, t0, 62, t1);	/* a^{2^124-1}*/
  ecc_mod_sqr (m, t0, rp);		/* a^{2^125-2} */
  ecc_mod_mul (m, rp, t0, ap);		/* a^{2^125-1} */
  ecc_mod_pow_2kp1 (m, t0, rp, 125, t1);/* a^{2^250-1} */
  ecc_mod_sqr (m, rp, t0);		/* a^{2^251-2} */
  ecc_mod_sqr (m, t0, rp);		/* a^{2^252-4} */
  ecc_mod_mul (m, rp, t0, ap);	    	/* a^{2^252-3} */
#undef t0
175
#undef t1
176
#undef a7
177 178
}

179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202
/* Needs 5*ECC_LIMB_SIZE scratch space. */
#define ECC_25519_INV_ITCH (5*ECC_LIMB_SIZE)

static void ecc_25519_inv (const struct ecc_modulo *p,
			   mp_limb_t *rp, const mp_limb_t *ap,
			   mp_limb_t *scratch)
{
#define t0 scratch

  /* Addition chain
     
       p - 2 = 2^{255} - 21
             = 1 + 2 (1 + 4 (2^{252}-3))	     
  */
  ecc_mod_pow_252m3 (p, rp, ap, t0);
  ecc_mod_sqr (p, t0, rp);
  ecc_mod_sqr (p, rp, t0);
  ecc_mod_mul (p, t0, ap, rp);
  ecc_mod_sqr (p, rp, t0);
  ecc_mod_mul (p, t0, ap, rp);
  mpn_copyi (rp, t0, ECC_LIMB_SIZE); /* FIXME: Eliminate copy? */
#undef t0
}
 
203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
/* Compute x such that x^2 = a (mod p). Returns one on success, zero
   on failure. using the e == 2 special case of the Shanks-Tonelli
   algorithm (see http://www.math.vt.edu/people/brown/doc/sqrts.pdf,
   or Henri Cohen, Computational Algebraic Number Theory, 1.5.1.

   NOTE: Not side-channel silent. FIXME: Compute square root in the
   extended field if a isn't a square (mod p)? FIXME: Accept scratch
   space from caller (could allow scratch == rp). */
#if ECC_SQRT_E != 2
#error Broken curve25519 parameters
#endif
int
ecc_25519_sqrt(mp_limb_t *rp, const mp_limb_t *ap)
{
  mp_size_t itch;
  mp_limb_t *scratch;
  int res;
220
  const struct ecc_modulo *p = &nettle_curve25519.p;
221 222 223 224 225 226 227 228

  itch = 7*ECC_LIMB_SIZE;
  scratch = gmp_alloc_limbs (itch);

#define t0 scratch
#define xp (scratch + ECC_LIMB_SIZE)
#define bp (scratch + 2*ECC_LIMB_SIZE)

229
  ecc_mod_pow_252m3 (p, t0, ap, t0 + 2*ECC_LIMB_SIZE);
230 231

  /* Compute candidate root x and fudgefactor b. */
232 233
  ecc_mod_mul (p, xp, t0, ap); /* a^{(p+3)/8 */
  ecc_mod_mul (p, bp, t0, xp); /* a^{(p-1)/4} */
234
  /* Check if b == 1 (mod p) */
235 236 237
  if (mpn_cmp (bp, p->m, ECC_LIMB_SIZE) >= 0)
    mpn_sub_n (bp, bp, p->m, ECC_LIMB_SIZE);
  if (mpn_cmp (bp, ecc_unit, ECC_LIMB_SIZE) == 0)
238 239 240 241 242 243 244
    {
      mpn_copyi (rp, xp, ECC_LIMB_SIZE);
      res = 1;
    }
  else
    {
      mpn_add_1 (bp, bp, ECC_LIMB_SIZE, 1);
245
      if (mpn_cmp (bp, p->m, ECC_LIMB_SIZE) == 0)
246
	{
247
	  ecc_mod_mul (p, bp, xp, ecc_sqrt_z);
248 249 250 251 252 253 254 255 256 257 258 259
	  mpn_copyi (rp, bp, ECC_LIMB_SIZE);
	  res = 1;
	}
      else
	res = 0;
    }
  gmp_free_limbs (scratch, itch);
  return res;
#undef t0
#undef xp
#undef bp
}
260

261 262
const struct ecc_curve nettle_curve25519 =
{
Niels Möller's avatar
Niels Möller committed
263 264 265 266 267
  {
    255,
    ECC_LIMB_SIZE,
    ECC_BMODP_SIZE,
    0,
268 269
    ECC_25519_INV_ITCH,

Niels Möller's avatar
Niels Möller committed
270 271 272 273
    ecc_p,
    ecc_Bmodp,
    ecc_Bmodp_shifted,
    NULL,
274 275
    ecc_pp1h,

276 277
    ecc_25519_modp,
    ecc_25519_modp,
278
    ecc_25519_inv,
Niels Möller's avatar
Niels Möller committed
279 280 281 282 283 284
  },
  {
    253,
    ECC_LIMB_SIZE,
    ECC_BMODQ_SIZE,
    0,
285 286
    ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),

Niels Möller's avatar
Niels Möller committed
287 288 289 290
    ecc_q,
    ecc_Bmodq,  
    ecc_mBmodq_shifted, /* Use q - 2^{252} instead. */
    NULL,
291 292
    ecc_qp1h,

293 294
    ecc_25519_modq,
    ecc_25519_modq,
295
    ecc_mod_inv,
Niels Möller's avatar
Niels Möller committed
296 297
  },

298 299 300
  0, /* No redc */
  ECC_PIPPENGER_K,
  ECC_PIPPENGER_C,
301

302
  ECC_ADD_EHH_ITCH (ECC_LIMB_SIZE),
303 304
  ECC_MUL_A_EH_ITCH (ECC_LIMB_SIZE),
  ECC_MUL_G_EH_ITCH (ECC_LIMB_SIZE),
305
  ECC_EH_TO_A_ITCH (ECC_LIMB_SIZE, ECC_25519_INV_ITCH),
306

307
  ecc_add_ehh,
308 309 310 311
  ecc_mul_a_eh,
  ecc_mul_g_eh,
  ecc_eh_to_a,

312
  ecc_d, /* Use the Edwards curve constant. */
313
  ecc_g,
314
  ecc_edwards,
315 316 317
  ecc_unit,
  ecc_table
};