curve25519-donna-helpers.h 2.32 KB
Newer Older
Andrew M's avatar
Andrew M committed
1 2 3 4 5 6 7 8 9 10 11 12 13
/*
	Public domain by Andrew M. <liquidsun@gmail.com>
	See: https://github.com/floodyberry/curve25519-donna

	Curve25519 implementation agnostic helpers
*/

/*
 * In:  b =   2^5 - 2^0
 * Out: b = 2^250 - 2^0
 */
static void
curve25519_pow_two5mtwo0_two250mtwo0(bignum25519 b) {
14
	bignum25519 ALIGN(16) t0,c;
Andrew M's avatar
Andrew M committed
15 16 17

	/* 2^5  - 2^0 */ /* b */
	/* 2^10 - 2^5 */ curve25519_square_times(t0, b, 5);
18
	/* 2^10 - 2^0 */ curve25519_mul_noinline(b, t0, b);
Andrew M's avatar
Andrew M committed
19
	/* 2^20 - 2^10 */ curve25519_square_times(t0, b, 10);
20
	/* 2^20 - 2^0 */ curve25519_mul_noinline(c, t0, b);
Andrew M's avatar
Andrew M committed
21
	/* 2^40 - 2^20 */ curve25519_square_times(t0, c, 20);
22
	/* 2^40 - 2^0 */ curve25519_mul_noinline(t0, t0, c);
Andrew M's avatar
Andrew M committed
23
	/* 2^50 - 2^10 */ curve25519_square_times(t0, t0, 10);
24
	/* 2^50 - 2^0 */ curve25519_mul_noinline(b, t0, b);
Andrew M's avatar
Andrew M committed
25
	/* 2^100 - 2^50 */ curve25519_square_times(t0, b, 50);
26
	/* 2^100 - 2^0 */ curve25519_mul_noinline(c, t0, b);
Andrew M's avatar
Andrew M committed
27
	/* 2^200 - 2^100 */ curve25519_square_times(t0, c, 100);
28
	/* 2^200 - 2^0 */ curve25519_mul_noinline(t0, t0, c);
Andrew M's avatar
Andrew M committed
29
	/* 2^250 - 2^50 */ curve25519_square_times(t0, t0, 50);
30
	/* 2^250 - 2^0 */ curve25519_mul_noinline(b, t0, b);
Andrew M's avatar
Andrew M committed
31 32 33 34 35 36 37
}

/*
 * z^(p - 2) = z(2^255 - 21)
 */
static void
curve25519_recip(bignum25519 out, const bignum25519 z) {
38
	bignum25519 ALIGN(16) a,t0,b;
Andrew M's avatar
Andrew M committed
39 40 41

	/* 2 */ curve25519_square_times(a, z, 1); /* a = 2 */
	/* 8 */ curve25519_square_times(t0, a, 2);
42 43
	/* 9 */ curve25519_mul_noinline(b, t0, z); /* b = 9 */
	/* 11 */ curve25519_mul_noinline(a, b, a); /* a = 11 */
Andrew M's avatar
Andrew M committed
44
	/* 22 */ curve25519_square_times(t0, a, 1);
45
	/* 2^5 - 2^0 = 31 */ curve25519_mul_noinline(b, t0, b);
Andrew M's avatar
Andrew M committed
46 47
	/* 2^250 - 2^0 */ curve25519_pow_two5mtwo0_two250mtwo0(b);
	/* 2^255 - 2^5 */ curve25519_square_times(b, b, 5);
48
	/* 2^255 - 21 */ curve25519_mul_noinline(out, b, a);
Andrew M's avatar
Andrew M committed
49 50 51 52 53 54 55
}

/*
 * z^((p-5)/8) = z^(2^252 - 3)
 */
static void
curve25519_pow_two252m3(bignum25519 two252m3, const bignum25519 z) {
56
	bignum25519 ALIGN(16) b,c,t0;
Andrew M's avatar
Andrew M committed
57 58 59

	/* 2 */ curve25519_square_times(c, z, 1); /* c = 2 */
	/* 8 */ curve25519_square_times(t0, c, 2); /* t0 = 8 */
60 61
	/* 9 */ curve25519_mul_noinline(b, t0, z); /* b = 9 */
	/* 11 */ curve25519_mul_noinline(c, b, c); /* c = 11 */
Andrew M's avatar
Andrew M committed
62
	/* 22 */ curve25519_square_times(t0, c, 1);
63
	/* 2^5 - 2^0 = 31 */ curve25519_mul_noinline(b, t0, b);
Andrew M's avatar
Andrew M committed
64 65
	/* 2^250 - 2^0 */ curve25519_pow_two5mtwo0_two250mtwo0(b);
	/* 2^252 - 2^2 */ curve25519_square_times(b, b, 2);
66
	/* 2^252 - 3 */ curve25519_mul_noinline(two252m3, b, z);
Andrew M's avatar
Andrew M committed
67
}