ed25519-donna-impl-base.h 13.8 KB
Newer Older
1 2 3 4
/*
	conversions
*/

5
DONNA_INLINE static void
6 7 8 9 10 11
ge25519_p1p1_to_partial(ge25519 *r, const ge25519_p1p1 *p) {
	curve25519_mul(r->x, p->x, p->t);
	curve25519_mul(r->y, p->y, p->z);
	curve25519_mul(r->z, p->z, p->t); 
}

12
DONNA_INLINE static void
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
ge25519_p1p1_to_full(ge25519 *r, const ge25519_p1p1 *p) {
	curve25519_mul(r->x, p->x, p->t);
	curve25519_mul(r->y, p->y, p->z);
	curve25519_mul(r->z, p->z, p->t); 
	curve25519_mul(r->t, p->x, p->y); 
}

static void
ge25519_full_to_pniels(ge25519_pniels *p, const ge25519 *r) {
	curve25519_sub(p->ysubx, r->y, r->x);
	curve25519_add(p->xaddy, r->y, r->x);
	curve25519_copy(p->z, r->z);
	curve25519_mul(p->t2d, r->t, ge25519_ec2d);
}

/*
	adding & doubling
*/

32 33
static void
ge25519_add_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519 *q) {
Bernd Paysan's avatar
Bernd Paysan committed
34
	bignum25519 a,b,c,d,t,u;
35 36 37 38 39 40 41 42 43 44

	curve25519_sub(a, p->y, p->x);
	curve25519_add(b, p->y, p->x);
	curve25519_sub(t, q->y, q->x);
	curve25519_add(u, q->y, q->x);
	curve25519_mul(a, a, t);
	curve25519_mul(b, b, u);
	curve25519_mul(c, p->t, q->t);
	curve25519_mul(c, c, ge25519_ec2d);
	curve25519_mul(d, p->z, q->z);
45
	curve25519_add(d, d, d);
46 47
	curve25519_sub(r->x, b, a);
	curve25519_add(r->y, b, a);
48 49
	curve25519_add_after_basic(r->z, d, c);
	curve25519_sub_after_basic(r->t, d, c);
50 51 52
}


53 54
static void
ge25519_double_p1p1(ge25519_p1p1 *r, const ge25519 *p) {
Bernd Paysan's avatar
Bernd Paysan committed
55
	bignum25519 a,b,c;
56 57 58 59 60 61 62

	curve25519_square(a, p->x);
	curve25519_square(b, p->y);
	curve25519_square(c, p->z);
	curve25519_add_reduce(c, c, c);
	curve25519_add(r->x, p->x, p->y);
	curve25519_square(r->x, r->x);
63 64 65 66
	curve25519_add(r->y, b, a);
	curve25519_sub(r->z, b, a);
	curve25519_sub_after_basic(r->x, r->x, r->y);
	curve25519_sub_after_basic(r->t, c, r->z);
67 68 69 70 71 72
}

static void
ge25519_nielsadd2_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519_niels *q, unsigned char signbit) {
	const bignum25519 *qb = (const bignum25519 *)q;
	bignum25519 *rb = (bignum25519 *)r;
Bernd Paysan's avatar
Bernd Paysan committed
73
	bignum25519 a,b,c;
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

	curve25519_sub(a, p->y, p->x);
	curve25519_add(b, p->y, p->x);
	curve25519_mul(a, a, qb[signbit]); /* x for +, y for - */
	curve25519_mul(r->x, b, qb[signbit^1]); /* y for +, x for - */
	curve25519_add(r->y, r->x, a);
	curve25519_sub(r->x, r->x, a);
	curve25519_mul(c, p->t, q->t2d);
	curve25519_add_reduce(r->t, p->z, p->z);
	curve25519_copy(r->z, r->t);
	curve25519_add(rb[2+signbit], rb[2+signbit], c); /* z for +, t for - */
	curve25519_sub(rb[2+(signbit^1)], rb[2+(signbit^1)], c); /* t for +, z for - */
}

static void
ge25519_pnielsadd_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519_pniels *q, unsigned char signbit) {
	const bignum25519 *qb = (const bignum25519 *)q;
	bignum25519 *rb = (bignum25519 *)r;
Bernd Paysan's avatar
Bernd Paysan committed
92
	bignum25519 a,b,c;
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109

	curve25519_sub(a, p->y, p->x);
	curve25519_add(b, p->y, p->x);
	curve25519_mul(a, a, qb[signbit]); /* ysubx for +, xaddy for - */
	curve25519_mul(r->x, b, qb[signbit^1]); /* xaddy for +, ysubx for - */
	curve25519_add(r->y, r->x, a);
	curve25519_sub(r->x, r->x, a);
	curve25519_mul(c, p->t, q->t2d);
	curve25519_mul(r->t, p->z, q->z);
	curve25519_add_reduce(r->t, r->t, r->t);
	curve25519_copy(r->z, r->t);
	curve25519_add(rb[2+signbit], rb[2+signbit], c); /* z for +, t for - */
	curve25519_sub(rb[2+(signbit^1)], rb[2+(signbit^1)], c); /* t for +, z for - */
}

static void
ge25519_double_partial(ge25519 *r, const ge25519 *p) {
110
	ge25519_p1p1 t;
111 112 113 114 115 116
	ge25519_double_p1p1(&t, p);
	ge25519_p1p1_to_partial(r, &t);
}

static void
ge25519_double(ge25519 *r, const ge25519 *p) {
117
	ge25519_p1p1 t;
118 119 120 121
	ge25519_double_p1p1(&t, p);
	ge25519_p1p1_to_full(r, &t);
}

122
STATIC void
123
ge25519_add(ge25519 *r, const ge25519 *p,  const ge25519 *q) {
124
	ge25519_p1p1 t;
125 126 127 128
	ge25519_add_p1p1(&t, p, q);
	ge25519_p1p1_to_full(r, &t);
}

129 130
static void
ge25519_nielsadd2(ge25519 *r, const ge25519_niels *q) {
Bernd Paysan's avatar
Bernd Paysan committed
131
	bignum25519 a,b,c,e,f,g,h;
132 133 134 135 136 137 138 139

	curve25519_sub(a, r->y, r->x);
	curve25519_add(b, r->y, r->x);
	curve25519_mul(a, a, q->ysubx);
	curve25519_mul(e, b, q->xaddy);
	curve25519_add(h, e, a);
	curve25519_sub(e, e, a);
	curve25519_mul(c, r->t, q->t2d);
140 141 142
	curve25519_add(f, r->z, r->z);
	curve25519_add_after_basic(g, f, c);
	curve25519_sub_after_basic(f, f, c);
143 144 145 146 147 148 149 150
	curve25519_mul(r->x, e, f);
	curve25519_mul(r->y, h, g);
	curve25519_mul(r->z, g, f);
	curve25519_mul(r->t, e, h);
}

static void
ge25519_pnielsadd(ge25519_pniels *r, const ge25519 *p, const ge25519_pniels *q) {
Bernd Paysan's avatar
Bernd Paysan committed
151
	bignum25519 a,b,c,x,y,z,t;
152 153 154 155 156 157 158 159 160

	curve25519_sub(a, p->y, p->x);
	curve25519_add(b, p->y, p->x);
	curve25519_mul(a, a, q->ysubx);
	curve25519_mul(x, b, q->xaddy);
	curve25519_add(y, x, a);
	curve25519_sub(x, x, a);
	curve25519_mul(c, p->t, q->t2d);
	curve25519_mul(t, p->z, q->z);
161 162 163
	curve25519_add(t, t, t);
	curve25519_add_after_basic(z, t, c);
	curve25519_sub_after_basic(t, t, c);
164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
	curve25519_mul(r->xaddy, x, t);
	curve25519_mul(r->ysubx, y, z);
	curve25519_mul(r->z, z, t);
	curve25519_mul(r->t2d, x, y);
	curve25519_copy(y, r->ysubx);
	curve25519_sub(r->ysubx, r->ysubx, r->xaddy);
	curve25519_add(r->xaddy, r->xaddy, y);
	curve25519_mul(r->t2d, r->t2d, ge25519_ec2d);
}


/*
	pack & unpack
*/

Bernd Paysan's avatar
Bernd Paysan committed
179
STATIC void
180
ge25519_pack(unsigned char r[32], const ge25519 *p) {
Bernd Paysan's avatar
Bernd Paysan committed
181
	bignum25519 tx, ty, zi;
182 183 184 185 186 187 188 189 190
	unsigned char parity[32];
	curve25519_recip(zi, p->z);
	curve25519_mul(tx, p->x, zi);
	curve25519_mul(ty, p->y, zi);
	curve25519_contract(r, ty);
	curve25519_contract(parity, tx);
	r[31] ^= ((parity[0] & 1) << 7);
}

191
STATIC int ge25519_unpack_negative_vartime(ge25519 *r, const unsigned char p[32]) {
192
	static const unsigned char zero[32] = {0};
Bernd Paysan's avatar
Bernd Paysan committed
193
	static const bignum25519 one = {1};
194 195
	unsigned char parity = p[31] >> 7;
	unsigned char check[32];
Bernd Paysan's avatar
Bernd Paysan committed
196
	bignum25519 t, root, num, den, d3;
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244

	curve25519_expand(r->y, p);
	curve25519_copy(r->z, one);
	curve25519_square(num, r->y); /* x = y^2 */
	curve25519_mul(den, num, ge25519_ecd); /* den = dy^2 */
	curve25519_sub_reduce(num, num, r->z); /* x = y^1 - 1 */
	curve25519_add(den, den, r->z); /* den = dy^2 + 1 */

	/* Computation of sqrt(num/den) */
	/* 1.: computation of num^((p-5)/8)*den^((7p-35)/8) = (num*den^7)^((p-5)/8) */
	curve25519_square(t, den);
	curve25519_mul(d3, t, den);
	curve25519_square(r->x, d3);
	curve25519_mul(r->x, r->x, den);
	curve25519_mul(r->x, r->x, num);
	curve25519_pow_two252m3(r->x, r->x);

	/* 2. computation of r->x = num * den^3 * (num*den^7)^((p-5)/8) */
	curve25519_mul(r->x, r->x, d3);
	curve25519_mul(r->x, r->x, num);

	/* 3. Check if either of the roots works: */
	curve25519_square(t, r->x);
	curve25519_mul(t, t, den);
	curve25519_sub_reduce(root, t, num);
	curve25519_contract(check, root);
	if (!ed25519_verify(check, zero, 32)) {
		curve25519_add_reduce(t, t, num);
		curve25519_contract(check, t);
		if (!ed25519_verify(check, zero, 32))
			return 0;
		curve25519_mul(r->x, r->x, ge25519_sqrtneg1);
	}

	curve25519_contract(check, r->x);
	if ((check[0] & 1) == parity) {
		curve25519_copy(t, r->x);
		curve25519_neg(r->x, t);
	}
	curve25519_mul(r->t, r->x, r->y);
	return 1;
}


/*
	scalarmults
*/

245
DONNA_INLINE static void ge25519_set_neutral(ge25519 *r)
246 247 248 249 250 251
{
 	memset(r, 0, sizeof(ge25519));
	r->y[0] = 1;
	r->z[0] = 1;
}

252
#define S1_SWINDOWSIZE 5
253 254 255 256
#define S1_TABLE_SIZE (1<<(S1_SWINDOWSIZE-2))
#define S2_SWINDOWSIZE 7
#define S2_TABLE_SIZE (1<<(S2_SWINDOWSIZE-2))

257
/* computes [s1]p1 + [s2]base */
258
STATIC void ge25519_double_scalarmult_vartime(ge25519 *r, const ge25519 *p1, const bignum256modm s1, const bignum256modm s2) {
259
	signed char slide1[256], slide2[256];
Bernd Paysan's avatar
Bernd Paysan committed
260 261 262
	ge25519_pniels pre1[S1_TABLE_SIZE];
	ge25519 d1;
	ge25519_p1p1 t;
263 264 265 266 267 268 269 270 271 272
	int32_t i;

	contract256_slidingwindow_modm(slide1, s1, S1_SWINDOWSIZE);
	contract256_slidingwindow_modm(slide2, s2, S2_SWINDOWSIZE);

	ge25519_double(&d1, p1);
	ge25519_full_to_pniels(pre1, p1);
	for (i = 0; i < S1_TABLE_SIZE - 1; i++)
		ge25519_pnielsadd(&pre1[i+1], &d1, &pre1[i]);

273
	ge25519_set_neutral(r);
274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295

	i = 255;
	while ((i >= 0) && !(slide1[i] | slide2[i]))
		i--;

	for (; i >= 0; i--) {
		ge25519_double_p1p1(&t, r);

		if (slide1[i]) {
			ge25519_p1p1_to_full(r, &t);
			ge25519_pnielsadd_p1p1(&t, r, &pre1[abs(slide1[i]) / 2], (unsigned char)slide1[i] >> 7);
		}

		if (slide2[i]) {
			ge25519_p1p1_to_full(r, &t);
			ge25519_nielsadd2_p1p1(&t, r, &ge25519_niels_sliding_multiples[abs(slide2[i]) / 2], (unsigned char)slide2[i] >> 7);
		}

		ge25519_p1p1_to_partial(r, &t);
	}
}

296
/* computes [s1]p1 */
297
STATIC void ge25519_scalarmult_vartime(ge25519 *r, const ge25519 *p1, const bignum256modm s1) {
298
	signed char slide1[256];
Bernd Paysan's avatar
Bernd Paysan committed
299 300 301
	ge25519_pniels pre1[S1_TABLE_SIZE];
	ge25519 d1;
	ge25519_p1p1 t;
302 303 304 305 306 307 308 309 310 311
	int32_t i;

	contract256_slidingwindow_modm(slide1, s1, S1_SWINDOWSIZE);

	ge25519_double(&d1, p1);
	ge25519_full_to_pniels(pre1, p1);
	for (i = 0; i < S1_TABLE_SIZE - 1; i++)
		ge25519_pnielsadd(&pre1[i+1], &d1, &pre1[i]);

	/* set neutral */
312
	ge25519_set_neutral(r);
313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328

	i = 255;
	while ((i >= 0) && !slide1[i])
		i--;

	for (; i >= 0; i--) {
		ge25519_double_p1p1(&t, r);

		if (slide1[i]) {
			ge25519_p1p1_to_full(r, &t);
			ge25519_pnielsadd_p1p1(&t, r, &pre1[abs(slide1[i]) / 2], (unsigned char)slide1[i] >> 7);
		}

		ge25519_p1p1_to_partial(r, &t);
	}
}
329

Bernd Paysan's avatar
Bernd Paysan committed
330 331 332 333
/*
 * The following conditional move stuff uses conditional moves.
 * I will check on which compilers this works, and provide suitable
 * workarounds for those where it doesn't.
Bernd Paysan's avatar
Bernd Paysan committed
334 335 336 337
 *
 * This works on gcc 4.x and above with -O3.  Don't use -O2, this will
 * cause the code to not generate conditional moves.  Don't use any -march=
 * with less than i686 on x86
Bernd Paysan's avatar
Bernd Paysan committed
338
 */
Bernd Paysan's avatar
Bernd Paysan committed
339
DONNA_INLINE static void ge25519_cmove_stride4(long * r, long * p, long * pos, long * n, int stride) {
340 341 342
  int i;
  long x0=r[0], x1=r[1], x2=r[2], x3=r[3], y0, y1, y2, y3;
  for(; p<n; p+=stride) {
343
    int flag=(p==pos);
344 345 346 347
    y0 = p[0];
    y1 = p[1];
    y2 = p[2];
    y3 = p[3];
348 349 350 351
    x0 = flag ? y0 : x0;
    x1 = flag ? y1 : x1;
    x2 = flag ? y2 : x2;
    x3 = flag ? y3 : x3;
352 353 354 355 356 357 358 359 360
  }
  r[0] = x0;
  r[1] = x1;
  r[2] = x2;
  r[3] = x3;
}
#define HAS_CMOVE_STRIDE4

DONNA_INLINE static void ge25519_cmove_stride4b(long * r, long * p, long * pos, long * n, int stride) {
361
  int i;
Bernd Paysan's avatar
Bernd Paysan committed
362
  long x0=p[0], x1=p[1], x2=p[2], x3=p[3], y0, y1, y2, y3;
363
  for(p+=stride; p<n; p+=stride) {
364
    int flag=(p==pos);
365 366 367 368
    y0 = p[0];
    y1 = p[1];
    y2 = p[2];
    y3 = p[3];
369 370 371 372
    x0 = flag ? y0 : x0;
    x1 = flag ? y1 : x1;
    x2 = flag ? y2 : x2;
    x3 = flag ? y3 : x3;
373 374 375 376 377 378
  }
  r[0] = x0;
  r[1] = x1;
  r[2] = x2;
  r[3] = x3;
}
379
#define HAS_CMOVE_STRIDE4B
380

381
STATIC void ge25519_move_conditional_pniels_array(ge25519_pniels * r, const ge25519_pniels * p, int pos, int n) {
382
#ifdef HAS_CMOVE_STRIDE4B
Bernd Paysan's avatar
Bernd Paysan committed
383 384
  int i;
  for(i=0; i<sizeof(ge25519_pniels)/sizeof(long); i+=4) {
385 386 387 388 389
    ge25519_cmove_stride4b(((long*)r)+i,
			   ((long*)p)+i,
			   ((long*)(p+pos))+i,
			   ((long*)(p+n))+i,
			   sizeof(ge25519_pniels)/sizeof(long));
Bernd Paysan's avatar
Bernd Paysan committed
390 391
  }
#else
392
  int i;
Bernd Paysan's avatar
Bernd Paysan committed
393 394
  for(i=0; i<n; i++) {
    ge25519_move_conditional_pniels(r, p+i, pos==i);
395
  }
Bernd Paysan's avatar
Bernd Paysan committed
396
#endif
397 398
}

399
STATIC void ge25519_move_conditional_niels_array(ge25519_niels * r, const uint8_t p[8][96], int pos, int n) {
Bernd Paysan's avatar
Bernd Paysan committed
400
  int i;
Bernd Paysan's avatar
Bernd Paysan committed
401
  for(i=0; i<96/sizeof(long); i+=4) {
402
    ge25519_cmove_stride4(((long*)r)+i,
Bernd Paysan's avatar
Bernd Paysan committed
403 404 405
			  ((long*)p)+i,
			  ((long*)(p+pos))+i,
			  ((long*)(p+n))+i,
406
			  96/sizeof(long));
407 408 409
  }
}

410
/* computes [s1]p1, constant time */
411
STATIC void ge25519_scalarmult(ge25519 *r, const ge25519 *p1, const bignum256modm s1) {
412
	signed char slide1[64];
Bernd Paysan's avatar
Bernd Paysan committed
413 414 415 416
	ge25519_pniels pre1[9];
	ge25519_pniels pre;
	ge25519 d1, r1;
	ge25519_p1p1 t;
417 418
	int32_t i, j;

419
	contract256_window4_modm(slide1, s1);
420 421 422 423

	/* set neutral */
	ge25519_set_neutral(r);

424 425 426 427
	ge25519_full_to_pniels(pre1, r);
	ge25519_full_to_pniels(pre1+1, p1);
	ge25519_double(&d1, p1);
	ge25519_full_to_pniels(pre1+2, &d1);
428
	for (i = 1; i < 7; i++) {
429 430 431 432 433 434 435 436
		ge25519_pnielsadd(&pre1[i+2], &d1, &pre1[i]);
	}

	for (i = 63; i >= 0; i--) {
		int k=abs(slide1[i]);
		ge25519_double_partial(r, r);
		ge25519_double_partial(r, r);
		ge25519_double_partial(r, r);
437
		ge25519_double_p1p1(&t, r);
438
		ge25519_move_conditional_pniels_array(&pre, pre1, k, 9);
439
		ge25519_p1p1_to_full(r, &t);
440
		ge25519_pnielsadd_p1p1(&t, r, &pre, (unsigned char)slide1[i] >> 7);
441 442 443 444
		ge25519_p1p1_to_partial(r, &t);
	}
}

Bernd Paysan's avatar
Bernd Paysan committed
445 446 447 448 449 450 451
#if !defined(HAVE_GE25519_SCALARMULT_BASE_CHOOSE_NIELS)

DONNA_INLINE static uint32_t
ge25519_windowb_equal(uint32_t b, uint32_t c) {
	return ((b ^ c) - 1) >> 31;
}

452
#include <stdio.h>
453
static void
454
ge25519_scalarmult_base_choose_niels(ge25519_niels *t, const uint8_t table[256][96], uint32_t pos, signed char b) {
Bernd Paysan's avatar
Bernd Paysan committed
455
	bignum25519 neg;
456 457 458 459 460
	uint32_t sign = (uint32_t)((unsigned char)b >> 7);
	uint32_t mask = ~(sign - 1);
	uint32_t u = (b + mask) ^ mask;
	uint32_t i;

461 462 463 464
	/* ysubx, xaddy, t2d in packed form. initialize to ysubx = 1, xaddy = 1, t2d = 0 */
	uint8_t packed[96] = {0};
	packed[0] = 1;
	packed[32] = 1;
465

466
	ge25519_move_conditional_niels_array(packed, &table[pos*8], u-1, 8);
467 468 469 470 471

	/* expand in to t */
	curve25519_expand(t->ysubx, packed +  0);
	curve25519_expand(t->xaddy, packed + 32);
	curve25519_expand(t->t2d  , packed + 64);
472

473
	/* adjust for sign */
474 475
	curve25519_swap_conditional(t->ysubx, t->xaddy, sign);	
	curve25519_neg(neg, t->t2d);
476
	curve25519_swap_conditional(t->t2d, neg, sign);
477 478
}

479 480
#endif /* HAVE_GE25519_SCALARMULT_BASE_CHOOSE_NIELS */

481 482 483

/* computes [s]basepoint */
static void
484
ge25519_scalarmult_base_niels(ge25519 *r, const uint8_t basepoint_table[256][96], const bignum256modm s) {
485 486
	signed char b[64];
	uint32_t i;
487
	ge25519_niels t;
488 489

	contract256_window4_modm(b, s);
490

491
	ge25519_scalarmult_base_choose_niels(&t, basepoint_table, 0, b[1]);
492 493 494 495 496
	curve25519_sub_reduce(r->x, t.xaddy, t.ysubx);
	curve25519_add_reduce(r->y, t.xaddy, t.ysubx);
	memset(r->z, 0, sizeof(bignum25519));
	curve25519_copy(r->t, t.t2d);
	r->z[0] = 2;	
497 498
	for (i = 3; i < 64; i += 2) {
		ge25519_scalarmult_base_choose_niels(&t, basepoint_table, i / 2, b[i]);
499 500 501 502 503 504
		ge25519_nielsadd2(r, &t);
	}
	ge25519_double_partial(r, r);
	ge25519_double_partial(r, r);
	ge25519_double_partial(r, r);
	ge25519_double(r, r);
505
	ge25519_scalarmult_base_choose_niels(&t, basepoint_table, 0, b[0]);
506 507 508
	curve25519_mul(t.t2d, t.t2d, ge25519_ecd);
	ge25519_nielsadd2(r, &t);
	for(i = 2; i < 64; i += 2) {
509
		ge25519_scalarmult_base_choose_niels(&t, basepoint_table, i / 2, b[i]);
510 511 512 513
		ge25519_nielsadd2(r, &t);
	}
}

514 515 516
STATIC void ge25519_scalarmult_base(ge25519 *r, const bignum256modm s) {
	ge25519_scalarmult_base_niels(r, ge25519_niels_base_multiples, s);
}