1 /*
2 Public domain by Olivier Chéron <olivier.cheron@gmail.com>
3
4 Arithmetic extensions to Ed25519-donna
5 */
6
7
8 /*
9 Scalar functions
10 */
11
12 void
ED25519_FN(ed25519_scalar_encode)13 ED25519_FN(ed25519_scalar_encode) (unsigned char out[32], const bignum256modm in) {
14 contract256_modm(out, in);
15 }
16
17 void
ED25519_FN(ed25519_scalar_decode_long)18 ED25519_FN(ed25519_scalar_decode_long) (bignum256modm out, const unsigned char *in, size_t len) {
19 expand256_modm(out, in, len);
20 }
21
22 int
ED25519_FN(ed25519_scalar_eq)23 ED25519_FN(ed25519_scalar_eq) (const bignum256modm a, const bignum256modm b) {
24 bignum256modm_element_t e = 0;
25
26 for (int i = 0; i < bignum256modm_limb_size; i++) {
27 e |= a[i] ^ b[i];
28 }
29
30 return (int) (1 & ((e - 1) >> bignum256modm_bits_per_limb));
31 }
32
33 void
ED25519_FN(ed25519_scalar_add)34 ED25519_FN(ed25519_scalar_add) (bignum256modm r, const bignum256modm x, const bignum256modm y) {
35 add256_modm(r, x, y);
36 }
37
38 void
ED25519_FN(ed25519_scalar_mul)39 ED25519_FN(ed25519_scalar_mul) (bignum256modm r, const bignum256modm x, const bignum256modm y) {
40 mul256_modm(r, x, y);
41 }
42
43
44 /*
45 Point functions
46 */
47
48 void
ED25519_FN(ed25519_point_encode)49 ED25519_FN(ed25519_point_encode) (unsigned char r[32], const ge25519 *p) {
50 ge25519_pack(r, p);
51 }
52
53 int
ED25519_FN(ed25519_point_decode_vartime)54 ED25519_FN(ed25519_point_decode_vartime) (ge25519 *r, const unsigned char p[32]) {
55 unsigned char p_neg[32];
56
57 // invert parity bit of X coordinate so the point is negated twice
58 // (once here, once in ge25519_unpack_negative_vartime)
59 for (int i = 0; i < 31; i++) {
60 p_neg[i] = p[i];
61 }
62 p_neg[31] = p[31] ^ 0x80;
63
64 return ge25519_unpack_negative_vartime(r, p_neg);
65 }
66
67 int
ED25519_FN(ed25519_point_eq)68 ED25519_FN(ed25519_point_eq) (const ge25519 *p, const ge25519 *q) {
69 bignum25519 a, b;
70 unsigned char contract_a[32], contract_b[32];
71 int eq;
72
73 // pX * qZ = qX * pZ
74 curve25519_mul(a, p->x, q->z);
75 curve25519_contract(contract_a, a);
76 curve25519_mul(b, q->x, p->z);
77 curve25519_contract(contract_b, b);
78 eq = ed25519_verify(contract_a, contract_b, 32);
79
80 // pY * qZ = qY * pZ
81 curve25519_mul(a, p->y, q->z);
82 curve25519_contract(contract_a, a);
83 curve25519_mul(b, q->y, p->z);
84 curve25519_contract(contract_b, b);
85 eq &= ed25519_verify(contract_a, contract_b, 32);
86
87 return eq;
88 }
89
90 static int
ED25519_FN(ed25519_point_is_identity)91 ED25519_FN(ed25519_point_is_identity) (const ge25519 *p) {
92 static const unsigned char zero[32] = {0};
93 unsigned char check[32];
94 bignum25519 d;
95 int eq;
96
97 // pX = 0
98 curve25519_contract(check, p->x);
99 eq = ed25519_verify(check, zero, 32);
100
101 // pY - pZ = 0
102 curve25519_sub_reduce(d, p->y, p->z);
103 curve25519_contract(check, d);
104 eq &= ed25519_verify(check, zero, 32);
105
106 return eq;
107 }
108
109 void
ED25519_FN(ed25519_point_negate)110 ED25519_FN(ed25519_point_negate) (ge25519 *r, const ge25519 *p) {
111 curve25519_neg(r->x, p->x);
112 curve25519_copy(r->y, p->y);
113 curve25519_copy(r->z, p->z);
114 curve25519_neg(r->t, p->t);
115 }
116
117 void
ED25519_FN(ed25519_point_add)118 ED25519_FN(ed25519_point_add) (ge25519 *r, const ge25519 *p, const ge25519 *q) {
119 ge25519_add(r, p, q);
120 }
121
122 void
ED25519_FN(ed25519_point_double)123 ED25519_FN(ed25519_point_double) (ge25519 *r, const ge25519 *p) {
124 ge25519_double(r, p);
125 }
126
127 void
ED25519_FN(ed25519_point_mul_by_cofactor)128 ED25519_FN(ed25519_point_mul_by_cofactor) (ge25519 *r, const ge25519 *p) {
129 ge25519_double_partial(r, p);
130 ge25519_double_partial(r, r);
131 ge25519_double(r, r);
132 }
133
134 void
ED25519_FN(ed25519_point_base_scalarmul)135 ED25519_FN(ed25519_point_base_scalarmul) (ge25519 *r, const bignum256modm s) {
136 ge25519_scalarmult_base_niels(r, ge25519_niels_base_multiples, s);
137 }
138
139 #if defined(ED25519_64BIT)
140 typedef uint64_t ed25519_move_cond_word;
141 #else
142 typedef uint32_t ed25519_move_cond_word;
143 #endif
144
145 /* out = (flag) ? in : out */
146 DONNA_INLINE static void
ed25519_move_cond_pniels(ge25519_pniels * out,const ge25519_pniels * in,uint32_t flag)147 ed25519_move_cond_pniels(ge25519_pniels *out, const ge25519_pniels *in, uint32_t flag) {
148 const int word_count = sizeof(ge25519_pniels) / sizeof(ed25519_move_cond_word);
149 const ed25519_move_cond_word nb = (ed25519_move_cond_word) flag - 1, b = ~nb;
150
151 ed25519_move_cond_word *outw = (ed25519_move_cond_word *) out;
152 const ed25519_move_cond_word *inw = (const ed25519_move_cond_word *) in;
153
154 // ge25519_pniels has 4 coordinates, so word_count is divisible by 4
155 for (int i = 0; i < word_count; i += 4) {
156 outw[i + 0] = (outw[i + 0] & nb) | (inw[i + 0] & b);
157 outw[i + 1] = (outw[i + 1] & nb) | (inw[i + 1] & b);
158 outw[i + 2] = (outw[i + 2] & nb) | (inw[i + 2] & b);
159 outw[i + 3] = (outw[i + 3] & nb) | (inw[i + 3] & b);
160 }
161 }
162
163 static void
ed25519_point_scalarmul_w_choose_pniels(ge25519_pniels * t,const ge25519_pniels table[15],uint32_t pos)164 ed25519_point_scalarmul_w_choose_pniels(ge25519_pniels *t, const ge25519_pniels table[15], uint32_t pos) {
165 // initialize t to identity, i.e. (1, 1, 1, 0)
166 memset(t, 0, sizeof(ge25519_pniels));
167 t->ysubx[0] = 1;
168 t->xaddy[0] = 1;
169 t->z[0] = 1;
170
171 // move one entry from table matching requested position,
172 // scanning all table to avoid cache-timing attack
173 //
174 // when pos == 0, no entry matches and this returns
175 // identity as expected
176 for (uint32_t i = 1; i < 16; i++) {
177 uint32_t flag = ((i ^ pos) - 1) >> 31;
178 ed25519_move_cond_pniels(t, table + i - 1, flag);
179 }
180 }
181
182 void
ED25519_FN(ed25519_point_scalarmul)183 ED25519_FN(ed25519_point_scalarmul) (ge25519 *r, const ge25519 *p, const bignum256modm s) {
184 ge25519_pniels mult[15];
185 ge25519_pniels pn;
186 ge25519_p1p1 t;
187 unsigned char ss[32];
188
189 // transform scalar as little-endian number
190 contract256_modm(ss, s);
191
192 // initialize r to identity, i.e. ge25519 (0, 1, 1, 0)
193 memset(r, 0, sizeof(ge25519));
194 r->y[0] = 1;
195 r->z[0] = 1;
196
197 // precompute multiples of P: 1.P, 2.P, ..., 15.P
198 ge25519_full_to_pniels(&mult[0], p);
199 for (int i = 1; i < 15; i++) {
200 ge25519_pnielsadd(&mult[i], p, &mult[i-1]);
201 }
202
203 // 4-bit fixed window, still 256 doublings but 64 additions
204 for (int i = 31; i >= 0; i--) {
205 // higher bits in ss[i]
206 ed25519_point_scalarmul_w_choose_pniels(&pn, mult, ss[i] >> 4);
207 ge25519_pnielsadd_p1p1(&t, r, &pn, 0);
208 ge25519_p1p1_to_partial(r, &t);
209
210 ge25519_double_partial(r, r);
211 ge25519_double_partial(r, r);
212 ge25519_double_partial(r, r);
213 ge25519_double(r, r);
214
215 // lower bits in ss[i]
216 ed25519_point_scalarmul_w_choose_pniels(&pn, mult, ss[i] & 0x0F);
217 ge25519_pnielsadd_p1p1(&t, r, &pn, 0);
218 if (i > 0) {
219 ge25519_p1p1_to_partial(r, &t);
220
221 ge25519_double_partial(r, r);
222 ge25519_double_partial(r, r);
223 ge25519_double_partial(r, r);
224 ge25519_double(r, r);
225 } else {
226 ge25519_p1p1_to_full(r, &t);
227 }
228 }
229 }
230
231 void
ED25519_FN(ed25519_base_double_scalarmul_vartime)232 ED25519_FN(ed25519_base_double_scalarmul_vartime) (ge25519 *r, const bignum256modm s1, const ge25519 *p2, const bignum256modm s2) {
233 // computes [s1]basepoint + [s2]p2
234 ge25519_double_scalarmult_vartime(r, p2, s2, s1);
235 }
236
237 int
ED25519_FN(ed25519_point_has_prime_order)238 ED25519_FN(ed25519_point_has_prime_order) (const ge25519 *p) {
239 static const bignum256modm sc_zero = {0};
240 ge25519 q;
241
242 // computes Q = m.P, vartime allowed because m is not secret
243 ED25519_FN(ed25519_base_double_scalarmul_vartime) (&q, sc_zero, p, modm_m);
244
245 return ED25519_FN(ed25519_point_is_identity) (&q);
246 }
247