1 /*
2 Public domain by Andrew M. <liquidsun@gmail.com>
3 See: https://github.com/floodyberry/curve25519-donna
4
5 Curve25519 implementation agnostic helpers
6 */
7
8 /*
9 * In: b = 2^5 - 2^0
10 * Out: b = 2^250 - 2^0
11 */
12 static void
curve25519_pow_two5mtwo0_two250mtwo0(bignum25519 b)13 curve25519_pow_two5mtwo0_two250mtwo0(bignum25519 b) {
14 bignum25519 ALIGN(16) t0,c;
15
16 /* 2^5 - 2^0 */ /* b */
17 /* 2^10 - 2^5 */ curve25519_square_times(t0, b, 5);
18 /* 2^10 - 2^0 */ curve25519_mul_noinline(b, t0, b);
19 /* 2^20 - 2^10 */ curve25519_square_times(t0, b, 10);
20 /* 2^20 - 2^0 */ curve25519_mul_noinline(c, t0, b);
21 /* 2^40 - 2^20 */ curve25519_square_times(t0, c, 20);
22 /* 2^40 - 2^0 */ curve25519_mul_noinline(t0, t0, c);
23 /* 2^50 - 2^10 */ curve25519_square_times(t0, t0, 10);
24 /* 2^50 - 2^0 */ curve25519_mul_noinline(b, t0, b);
25 /* 2^100 - 2^50 */ curve25519_square_times(t0, b, 50);
26 /* 2^100 - 2^0 */ curve25519_mul_noinline(c, t0, b);
27 /* 2^200 - 2^100 */ curve25519_square_times(t0, c, 100);
28 /* 2^200 - 2^0 */ curve25519_mul_noinline(t0, t0, c);
29 /* 2^250 - 2^50 */ curve25519_square_times(t0, t0, 50);
30 /* 2^250 - 2^0 */ curve25519_mul_noinline(b, t0, b);
31 }
32
33 /*
34 * z^(p - 2) = z(2^255 - 21)
35 */
36 static void
curve25519_recip(bignum25519 out,const bignum25519 z)37 curve25519_recip(bignum25519 out, const bignum25519 z) {
38 bignum25519 ALIGN(16) a,t0,b;
39
40 /* 2 */ curve25519_square_times(a, z, 1); /* a = 2 */
41 /* 8 */ curve25519_square_times(t0, a, 2);
42 /* 9 */ curve25519_mul_noinline(b, t0, z); /* b = 9 */
43 /* 11 */ curve25519_mul_noinline(a, b, a); /* a = 11 */
44 /* 22 */ curve25519_square_times(t0, a, 1);
45 /* 2^5 - 2^0 = 31 */ curve25519_mul_noinline(b, t0, b);
46 /* 2^250 - 2^0 */ curve25519_pow_two5mtwo0_two250mtwo0(b);
47 /* 2^255 - 2^5 */ curve25519_square_times(b, b, 5);
48 /* 2^255 - 21 */ curve25519_mul_noinline(out, b, a);
49 }
50
51 static const unsigned char curve25519_packedone[32] = {
52 1, 0, 0, 0, 0, 0, 0, 0,
53 0, 0, 0, 0, 0, 0, 0, 0,
54 0, 0, 0, 0, 0, 0, 0, 0,
55 0, 0, 0, 0, 0, 0, 0, 0,
56 };
57
58 static void
curve25519_setone(bignum25519 out)59 curve25519_setone(bignum25519 out) {
60 // (cathugger) this hopefuly will get inlined by compiler because im lazy
61 curve25519_expand(out, curve25519_packedone);
62 }
63
64 /*
65 * (cathugger)
66 * idk if recip is same as invert but I hope it is
67 * if that's the case then we're doing batch invert there
68 */
69 static void
curve25519_batchrecip(bignum25519 * out[],bignum25519 tmp[],bignum25519 * const in[],size_t num)70 curve25519_batchrecip(bignum25519 *out[], bignum25519 tmp[], bignum25519 * const in[], size_t num) {
71 bignum25519 ALIGN(16) acc, tmpacc;
72 size_t i;
73
74 curve25519_setone(acc);
75
76 for (i = 0; i < num; ++i) {
77 curve25519_copy(tmp[i], acc);
78 curve25519_mul(acc, acc, *in[i]);
79 }
80
81 curve25519_recip(acc, acc);
82
83 i = num;
84 while (i--) {
85 curve25519_mul(tmpacc, acc, *in[i]);
86 curve25519_mul(*out[i], acc, tmp[i]);
87 curve25519_copy(acc, tmpacc);
88 }
89 }
90
91 /*
92 * z^((p-5)/8) = z^(2^252 - 3)
93 */
94 static void
curve25519_pow_two252m3(bignum25519 two252m3,const bignum25519 z)95 curve25519_pow_two252m3(bignum25519 two252m3, const bignum25519 z) {
96 bignum25519 ALIGN(16) b,c,t0;
97
98 /* 2 */ curve25519_square_times(c, z, 1); /* c = 2 */
99 /* 8 */ curve25519_square_times(t0, c, 2); /* t0 = 8 */
100 /* 9 */ curve25519_mul_noinline(b, t0, z); /* b = 9 */
101 /* 11 */ curve25519_mul_noinline(c, b, c); /* c = 11 */
102 /* 22 */ curve25519_square_times(t0, c, 1);
103 /* 2^5 - 2^0 = 31 */ curve25519_mul_noinline(b, t0, b);
104 /* 2^250 - 2^0 */ curve25519_pow_two5mtwo0_two250mtwo0(b);
105 /* 2^252 - 2^2 */ curve25519_square_times(b, b, 2);
106 /* 2^252 - 3 */ curve25519_mul_noinline(two252m3, b, z);
107 }
108