xref: /openbmc/linux/lib/crypto/mpi/ec.c (revision 7ebf812b)
1 /* ec.c -  Elliptic Curve functions
2  * Copyright (C) 2007 Free Software Foundation, Inc.
3  * Copyright (C) 2013 g10 Code GmbH
4  *
5  * This file is part of Libgcrypt.
6  *
7  * Libgcrypt is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU Lesser General Public License as
9  * published by the Free Software Foundation; either version 2.1 of
10  * the License, or (at your option) any later version.
11  *
12  * Libgcrypt is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
19  */
20 
21 #include "mpi-internal.h"
22 #include "longlong.h"
23 
24 #define point_init(a)  mpi_point_init((a))
25 #define point_free(a)  mpi_point_free_parts((a))
26 
27 #define log_error(fmt, ...) pr_err(fmt, ##__VA_ARGS__)
28 #define log_fatal(fmt, ...) pr_err(fmt, ##__VA_ARGS__)
29 
30 #define DIM(v) (sizeof(v)/sizeof((v)[0]))
31 
32 
33 /* Create a new point option.  NBITS gives the size in bits of one
34  * coordinate; it is only used to pre-allocate some resources and
35  * might also be passed as 0 to use a default value.
36  */
mpi_point_new(unsigned int nbits)37 MPI_POINT mpi_point_new(unsigned int nbits)
38 {
39 	MPI_POINT p;
40 
41 	(void)nbits;  /* Currently not used.  */
42 
43 	p = kmalloc(sizeof(*p), GFP_KERNEL);
44 	if (p)
45 		mpi_point_init(p);
46 	return p;
47 }
48 EXPORT_SYMBOL_GPL(mpi_point_new);
49 
50 /* Release the point object P.  P may be NULL. */
mpi_point_release(MPI_POINT p)51 void mpi_point_release(MPI_POINT p)
52 {
53 	if (p) {
54 		mpi_point_free_parts(p);
55 		kfree(p);
56 	}
57 }
58 EXPORT_SYMBOL_GPL(mpi_point_release);
59 
60 /* Initialize the fields of a point object.  gcry_mpi_point_free_parts
61  * may be used to release the fields.
62  */
mpi_point_init(MPI_POINT p)63 void mpi_point_init(MPI_POINT p)
64 {
65 	p->x = mpi_new(0);
66 	p->y = mpi_new(0);
67 	p->z = mpi_new(0);
68 }
69 EXPORT_SYMBOL_GPL(mpi_point_init);
70 
71 /* Release the parts of a point object. */
mpi_point_free_parts(MPI_POINT p)72 void mpi_point_free_parts(MPI_POINT p)
73 {
74 	mpi_free(p->x); p->x = NULL;
75 	mpi_free(p->y); p->y = NULL;
76 	mpi_free(p->z); p->z = NULL;
77 }
78 EXPORT_SYMBOL_GPL(mpi_point_free_parts);
79 
80 /* Set the value from S into D.  */
point_set(MPI_POINT d,MPI_POINT s)81 static void point_set(MPI_POINT d, MPI_POINT s)
82 {
83 	mpi_set(d->x, s->x);
84 	mpi_set(d->y, s->y);
85 	mpi_set(d->z, s->z);
86 }
87 
point_resize(MPI_POINT p,struct mpi_ec_ctx * ctx)88 static void point_resize(MPI_POINT p, struct mpi_ec_ctx *ctx)
89 {
90 	size_t nlimbs = ctx->p->nlimbs;
91 
92 	mpi_resize(p->x, nlimbs);
93 	p->x->nlimbs = nlimbs;
94 	mpi_resize(p->z, nlimbs);
95 	p->z->nlimbs = nlimbs;
96 
97 	if (ctx->model != MPI_EC_MONTGOMERY) {
98 		mpi_resize(p->y, nlimbs);
99 		p->y->nlimbs = nlimbs;
100 	}
101 }
102 
point_swap_cond(MPI_POINT d,MPI_POINT s,unsigned long swap,struct mpi_ec_ctx * ctx)103 static void point_swap_cond(MPI_POINT d, MPI_POINT s, unsigned long swap,
104 		struct mpi_ec_ctx *ctx)
105 {
106 	mpi_swap_cond(d->x, s->x, swap);
107 	if (ctx->model != MPI_EC_MONTGOMERY)
108 		mpi_swap_cond(d->y, s->y, swap);
109 	mpi_swap_cond(d->z, s->z, swap);
110 }
111 
112 
113 /* W = W mod P.  */
ec_mod(MPI w,struct mpi_ec_ctx * ec)114 static void ec_mod(MPI w, struct mpi_ec_ctx *ec)
115 {
116 	if (ec->t.p_barrett)
117 		mpi_mod_barrett(w, w, ec->t.p_barrett);
118 	else
119 		mpi_mod(w, w, ec->p);
120 }
121 
ec_addm(MPI w,MPI u,MPI v,struct mpi_ec_ctx * ctx)122 static void ec_addm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
123 {
124 	mpi_add(w, u, v);
125 	ec_mod(w, ctx);
126 }
127 
ec_subm(MPI w,MPI u,MPI v,struct mpi_ec_ctx * ec)128 static void ec_subm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec)
129 {
130 	mpi_sub(w, u, v);
131 	while (w->sign)
132 		mpi_add(w, w, ec->p);
133 	/*ec_mod(w, ec);*/
134 }
135 
ec_mulm(MPI w,MPI u,MPI v,struct mpi_ec_ctx * ctx)136 static void ec_mulm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
137 {
138 	mpi_mul(w, u, v);
139 	ec_mod(w, ctx);
140 }
141 
142 /* W = 2 * U mod P.  */
ec_mul2(MPI w,MPI u,struct mpi_ec_ctx * ctx)143 static void ec_mul2(MPI w, MPI u, struct mpi_ec_ctx *ctx)
144 {
145 	mpi_lshift(w, u, 1);
146 	ec_mod(w, ctx);
147 }
148 
ec_powm(MPI w,const MPI b,const MPI e,struct mpi_ec_ctx * ctx)149 static void ec_powm(MPI w, const MPI b, const MPI e,
150 		struct mpi_ec_ctx *ctx)
151 {
152 	mpi_powm(w, b, e, ctx->p);
153 	/* mpi_abs(w); */
154 }
155 
156 /* Shortcut for
157  * ec_powm(B, B, mpi_const(MPI_C_TWO), ctx);
158  * for easier optimization.
159  */
ec_pow2(MPI w,const MPI b,struct mpi_ec_ctx * ctx)160 static void ec_pow2(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
161 {
162 	/* Using mpi_mul is slightly faster (at least on amd64).  */
163 	/* mpi_powm(w, b, mpi_const(MPI_C_TWO), ctx->p); */
164 	ec_mulm(w, b, b, ctx);
165 }
166 
167 /* Shortcut for
168  * ec_powm(B, B, mpi_const(MPI_C_THREE), ctx);
169  * for easier optimization.
170  */
ec_pow3(MPI w,const MPI b,struct mpi_ec_ctx * ctx)171 static void ec_pow3(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
172 {
173 	mpi_powm(w, b, mpi_const(MPI_C_THREE), ctx->p);
174 }
175 
ec_invm(MPI x,MPI a,struct mpi_ec_ctx * ctx)176 static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx)
177 {
178 	if (!mpi_invm(x, a, ctx->p))
179 		log_error("ec_invm: inverse does not exist:\n");
180 }
181 
mpih_set_cond(mpi_ptr_t wp,mpi_ptr_t up,mpi_size_t usize,unsigned long set)182 static void mpih_set_cond(mpi_ptr_t wp, mpi_ptr_t up,
183 		mpi_size_t usize, unsigned long set)
184 {
185 	mpi_size_t i;
186 	mpi_limb_t mask = ((mpi_limb_t)0) - set;
187 	mpi_limb_t x;
188 
189 	for (i = 0; i < usize; i++) {
190 		x = mask & (wp[i] ^ up[i]);
191 		wp[i] = wp[i] ^ x;
192 	}
193 }
194 
195 /* Routines for 2^255 - 19.  */
196 
197 #define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
198 
ec_addm_25519(MPI w,MPI u,MPI v,struct mpi_ec_ctx * ctx)199 static void ec_addm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
200 {
201 	mpi_ptr_t wp, up, vp;
202 	mpi_size_t wsize = LIMB_SIZE_25519;
203 	mpi_limb_t n[LIMB_SIZE_25519];
204 	mpi_limb_t borrow;
205 
206 	if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
207 		log_bug("addm_25519: different sizes\n");
208 
209 	memset(n, 0, sizeof(n));
210 	up = u->d;
211 	vp = v->d;
212 	wp = w->d;
213 
214 	mpihelp_add_n(wp, up, vp, wsize);
215 	borrow = mpihelp_sub_n(wp, wp, ctx->p->d, wsize);
216 	mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL));
217 	mpihelp_add_n(wp, wp, n, wsize);
218 	wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
219 }
220 
ec_subm_25519(MPI w,MPI u,MPI v,struct mpi_ec_ctx * ctx)221 static void ec_subm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
222 {
223 	mpi_ptr_t wp, up, vp;
224 	mpi_size_t wsize = LIMB_SIZE_25519;
225 	mpi_limb_t n[LIMB_SIZE_25519];
226 	mpi_limb_t borrow;
227 
228 	if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
229 		log_bug("subm_25519: different sizes\n");
230 
231 	memset(n, 0, sizeof(n));
232 	up = u->d;
233 	vp = v->d;
234 	wp = w->d;
235 
236 	borrow = mpihelp_sub_n(wp, up, vp, wsize);
237 	mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL));
238 	mpihelp_add_n(wp, wp, n, wsize);
239 	wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
240 }
241 
ec_mulm_25519(MPI w,MPI u,MPI v,struct mpi_ec_ctx * ctx)242 static void ec_mulm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
243 {
244 	mpi_ptr_t wp, up, vp;
245 	mpi_size_t wsize = LIMB_SIZE_25519;
246 	mpi_limb_t n[LIMB_SIZE_25519*2];
247 	mpi_limb_t m[LIMB_SIZE_25519+1];
248 	mpi_limb_t cy;
249 	int msb;
250 
251 	(void)ctx;
252 	if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
253 		log_bug("mulm_25519: different sizes\n");
254 
255 	up = u->d;
256 	vp = v->d;
257 	wp = w->d;
258 
259 	mpihelp_mul_n(n, up, vp, wsize);
260 	memcpy(wp, n, wsize * BYTES_PER_MPI_LIMB);
261 	wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
262 
263 	memcpy(m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB);
264 	mpihelp_rshift(m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB));
265 
266 	memcpy(n, m, wsize * BYTES_PER_MPI_LIMB);
267 	cy = mpihelp_lshift(m, m, LIMB_SIZE_25519, 4);
268 	m[LIMB_SIZE_25519] = cy;
269 	cy = mpihelp_add_n(m, m, n, wsize);
270 	m[LIMB_SIZE_25519] += cy;
271 	cy = mpihelp_add_n(m, m, n, wsize);
272 	m[LIMB_SIZE_25519] += cy;
273 	cy = mpihelp_add_n(m, m, n, wsize);
274 	m[LIMB_SIZE_25519] += cy;
275 
276 	cy = mpihelp_add_n(wp, wp, m, wsize);
277 	m[LIMB_SIZE_25519] += cy;
278 
279 	memset(m, 0, wsize * BYTES_PER_MPI_LIMB);
280 	msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB));
281 	m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19;
282 	wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
283 	mpihelp_add_n(wp, wp, m, wsize);
284 
285 	m[0] = 0;
286 	cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize);
287 	mpih_set_cond(m, ctx->p->d, wsize, (cy != 0UL));
288 	mpihelp_add_n(wp, wp, m, wsize);
289 }
290 
ec_mul2_25519(MPI w,MPI u,struct mpi_ec_ctx * ctx)291 static void ec_mul2_25519(MPI w, MPI u, struct mpi_ec_ctx *ctx)
292 {
293 	ec_addm_25519(w, u, u, ctx);
294 }
295 
ec_pow2_25519(MPI w,const MPI b,struct mpi_ec_ctx * ctx)296 static void ec_pow2_25519(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
297 {
298 	ec_mulm_25519(w, b, b, ctx);
299 }
300 
301 /* Routines for 2^448 - 2^224 - 1.  */
302 
303 #define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
304 #define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2)
305 
ec_addm_448(MPI w,MPI u,MPI v,struct mpi_ec_ctx * ctx)306 static void ec_addm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
307 {
308 	mpi_ptr_t wp, up, vp;
309 	mpi_size_t wsize = LIMB_SIZE_448;
310 	mpi_limb_t n[LIMB_SIZE_448];
311 	mpi_limb_t cy;
312 
313 	if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
314 		log_bug("addm_448: different sizes\n");
315 
316 	memset(n, 0, sizeof(n));
317 	up = u->d;
318 	vp = v->d;
319 	wp = w->d;
320 
321 	cy = mpihelp_add_n(wp, up, vp, wsize);
322 	mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL));
323 	mpihelp_sub_n(wp, wp, n, wsize);
324 }
325 
ec_subm_448(MPI w,MPI u,MPI v,struct mpi_ec_ctx * ctx)326 static void ec_subm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
327 {
328 	mpi_ptr_t wp, up, vp;
329 	mpi_size_t wsize = LIMB_SIZE_448;
330 	mpi_limb_t n[LIMB_SIZE_448];
331 	mpi_limb_t borrow;
332 
333 	if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
334 		log_bug("subm_448: different sizes\n");
335 
336 	memset(n, 0, sizeof(n));
337 	up = u->d;
338 	vp = v->d;
339 	wp = w->d;
340 
341 	borrow = mpihelp_sub_n(wp, up, vp, wsize);
342 	mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL));
343 	mpihelp_add_n(wp, wp, n, wsize);
344 }
345 
ec_mulm_448(MPI w,MPI u,MPI v,struct mpi_ec_ctx * ctx)346 static void ec_mulm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
347 {
348 	mpi_ptr_t wp, up, vp;
349 	mpi_size_t wsize = LIMB_SIZE_448;
350 	mpi_limb_t n[LIMB_SIZE_448*2];
351 	mpi_limb_t a2[LIMB_SIZE_HALF_448];
352 	mpi_limb_t a3[LIMB_SIZE_HALF_448];
353 	mpi_limb_t b0[LIMB_SIZE_HALF_448];
354 	mpi_limb_t b1[LIMB_SIZE_HALF_448];
355 	mpi_limb_t cy;
356 	int i;
357 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
358 	mpi_limb_t b1_rest, a3_rest;
359 #endif
360 
361 	if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
362 		log_bug("mulm_448: different sizes\n");
363 
364 	up = u->d;
365 	vp = v->d;
366 	wp = w->d;
367 
368 	mpihelp_mul_n(n, up, vp, wsize);
369 
370 	for (i = 0; i < (wsize + 1) / 2; i++) {
371 		b0[i] = n[i];
372 		b1[i] = n[i+wsize/2];
373 		a2[i] = n[i+wsize];
374 		a3[i] = n[i+wsize+wsize/2];
375 	}
376 
377 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
378 	b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1;
379 	a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1;
380 
381 	b1_rest = 0;
382 	a3_rest = 0;
383 
384 	for (i = (wsize + 1) / 2 - 1; i >= 0; i--) {
385 		mpi_limb_t b1v, a3v;
386 		b1v = b1[i];
387 		a3v = a3[i];
388 		b1[i] = (b1_rest << 32) | (b1v >> 32);
389 		a3[i] = (a3_rest << 32) | (a3v >> 32);
390 		b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1);
391 		a3_rest = a3v & (((mpi_limb_t)1UL << 32)-1);
392 	}
393 #endif
394 
395 	cy = mpihelp_add_n(b0, b0, a2, LIMB_SIZE_HALF_448);
396 	cy += mpihelp_add_n(b0, b0, a3, LIMB_SIZE_HALF_448);
397 	for (i = 0; i < (wsize + 1) / 2; i++)
398 		wp[i] = b0[i];
399 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
400 	wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL << 32)-1);
401 #endif
402 
403 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
404 	cy = b0[LIMB_SIZE_HALF_448-1] >> 32;
405 #endif
406 
407 	cy = mpihelp_add_1(b1, b1, LIMB_SIZE_HALF_448, cy);
408 	cy += mpihelp_add_n(b1, b1, a2, LIMB_SIZE_HALF_448);
409 	cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448);
410 	cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448);
411 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
412 	b1_rest = 0;
413 	for (i = (wsize + 1) / 2 - 1; i >= 0; i--) {
414 		mpi_limb_t b1v = b1[i];
415 		b1[i] = (b1_rest << 32) | (b1v >> 32);
416 		b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1);
417 	}
418 	wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32);
419 #endif
420 	for (i = 0; i < wsize / 2; i++)
421 		wp[i+(wsize + 1) / 2] = b1[i];
422 
423 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
424 	cy = b1[LIMB_SIZE_HALF_448-1];
425 #endif
426 
427 	memset(n, 0, wsize * BYTES_PER_MPI_LIMB);
428 
429 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
430 	n[LIMB_SIZE_HALF_448-1] = cy << 32;
431 #else
432 	n[LIMB_SIZE_HALF_448] = cy;
433 #endif
434 	n[0] = cy;
435 	mpihelp_add_n(wp, wp, n, wsize);
436 
437 	memset(n, 0, wsize * BYTES_PER_MPI_LIMB);
438 	cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize);
439 	mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL));
440 	mpihelp_add_n(wp, wp, n, wsize);
441 }
442 
ec_mul2_448(MPI w,MPI u,struct mpi_ec_ctx * ctx)443 static void ec_mul2_448(MPI w, MPI u, struct mpi_ec_ctx *ctx)
444 {
445 	ec_addm_448(w, u, u, ctx);
446 }
447 
ec_pow2_448(MPI w,const MPI b,struct mpi_ec_ctx * ctx)448 static void ec_pow2_448(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
449 {
450 	ec_mulm_448(w, b, b, ctx);
451 }
452 
453 struct field_table {
454 	const char *p;
455 
456 	/* computation routines for the field.  */
457 	void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx);
458 	void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx);
459 	void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx);
460 	void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx);
461 	void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx);
462 };
463 
464 static const struct field_table field_table[] = {
465 	{
466 		"0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",
467 		ec_addm_25519,
468 		ec_subm_25519,
469 		ec_mulm_25519,
470 		ec_mul2_25519,
471 		ec_pow2_25519
472 	},
473 	{
474 		"0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE"
475 		"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
476 		ec_addm_448,
477 		ec_subm_448,
478 		ec_mulm_448,
479 		ec_mul2_448,
480 		ec_pow2_448
481 	},
482 	{ NULL, NULL, NULL, NULL, NULL, NULL },
483 };
484 
485 /* Force recomputation of all helper variables.  */
mpi_ec_get_reset(struct mpi_ec_ctx * ec)486 static void mpi_ec_get_reset(struct mpi_ec_ctx *ec)
487 {
488 	ec->t.valid.a_is_pminus3 = 0;
489 	ec->t.valid.two_inv_p = 0;
490 }
491 
492 /* Accessor for helper variable.  */
ec_get_a_is_pminus3(struct mpi_ec_ctx * ec)493 static int ec_get_a_is_pminus3(struct mpi_ec_ctx *ec)
494 {
495 	MPI tmp;
496 
497 	if (!ec->t.valid.a_is_pminus3) {
498 		ec->t.valid.a_is_pminus3 = 1;
499 		tmp = mpi_alloc_like(ec->p);
500 		mpi_sub_ui(tmp, ec->p, 3);
501 		ec->t.a_is_pminus3 = !mpi_cmp(ec->a, tmp);
502 		mpi_free(tmp);
503 	}
504 
505 	return ec->t.a_is_pminus3;
506 }
507 
508 /* Accessor for helper variable.  */
ec_get_two_inv_p(struct mpi_ec_ctx * ec)509 static MPI ec_get_two_inv_p(struct mpi_ec_ctx *ec)
510 {
511 	if (!ec->t.valid.two_inv_p) {
512 		ec->t.valid.two_inv_p = 1;
513 		if (!ec->t.two_inv_p)
514 			ec->t.two_inv_p = mpi_alloc(0);
515 		ec_invm(ec->t.two_inv_p, mpi_const(MPI_C_TWO), ec);
516 	}
517 	return ec->t.two_inv_p;
518 }
519 
520 static const char *const curve25519_bad_points[] = {
521 	"0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed",
522 	"0x0000000000000000000000000000000000000000000000000000000000000000",
523 	"0x0000000000000000000000000000000000000000000000000000000000000001",
524 	"0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0",
525 	"0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f",
526 	"0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec",
527 	"0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee",
528 	NULL
529 };
530 
531 static const char *const curve448_bad_points[] = {
532 	"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
533 	"ffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
534 	"0x00000000000000000000000000000000000000000000000000000000"
535 	"00000000000000000000000000000000000000000000000000000000",
536 	"0x00000000000000000000000000000000000000000000000000000000"
537 	"00000000000000000000000000000000000000000000000000000001",
538 	"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
539 	"fffffffffffffffffffffffffffffffffffffffffffffffffffffffe",
540 	"0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
541 	"00000000000000000000000000000000000000000000000000000000",
542 	NULL
543 };
544 
545 static const char *const *bad_points_table[] = {
546 	curve25519_bad_points,
547 	curve448_bad_points,
548 };
549 
mpi_ec_coefficient_normalize(MPI a,MPI p)550 static void mpi_ec_coefficient_normalize(MPI a, MPI p)
551 {
552 	if (a->sign) {
553 		mpi_resize(a, p->nlimbs);
554 		mpihelp_sub_n(a->d, p->d, a->d, p->nlimbs);
555 		a->nlimbs = p->nlimbs;
556 		a->sign = 0;
557 	}
558 }
559 
560 /* This function initialized a context for elliptic curve based on the
561  * field GF(p).  P is the prime specifying this field, A is the first
562  * coefficient.  CTX is expected to be zeroized.
563  */
mpi_ec_init(struct mpi_ec_ctx * ctx,enum gcry_mpi_ec_models model,enum ecc_dialects dialect,int flags,MPI p,MPI a,MPI b)564 void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model,
565 			enum ecc_dialects dialect,
566 			int flags, MPI p, MPI a, MPI b)
567 {
568 	int i;
569 	static int use_barrett = -1 /* TODO: 1 or -1 */;
570 
571 	mpi_ec_coefficient_normalize(a, p);
572 	mpi_ec_coefficient_normalize(b, p);
573 
574 	/* Fixme: Do we want to check some constraints? e.g.  a < p  */
575 
576 	ctx->model = model;
577 	ctx->dialect = dialect;
578 	ctx->flags = flags;
579 	if (dialect == ECC_DIALECT_ED25519)
580 		ctx->nbits = 256;
581 	else
582 		ctx->nbits = mpi_get_nbits(p);
583 	ctx->p = mpi_copy(p);
584 	ctx->a = mpi_copy(a);
585 	ctx->b = mpi_copy(b);
586 
587 	ctx->d = NULL;
588 	ctx->t.two_inv_p = NULL;
589 
590 	ctx->t.p_barrett = use_barrett > 0 ? mpi_barrett_init(ctx->p, 0) : NULL;
591 
592 	mpi_ec_get_reset(ctx);
593 
594 	if (model == MPI_EC_MONTGOMERY) {
595 		for (i = 0; i < DIM(bad_points_table); i++) {
596 			MPI p_candidate = mpi_scanval(bad_points_table[i][0]);
597 			int match_p = !mpi_cmp(ctx->p, p_candidate);
598 			int j;
599 
600 			mpi_free(p_candidate);
601 			if (!match_p)
602 				continue;
603 
604 			for (j = 0; i < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++)
605 				ctx->t.scratch[j] = mpi_scanval(bad_points_table[i][j]);
606 		}
607 	} else {
608 		/* Allocate scratch variables.  */
609 		for (i = 0; i < DIM(ctx->t.scratch); i++)
610 			ctx->t.scratch[i] = mpi_alloc_like(ctx->p);
611 	}
612 
613 	ctx->addm = ec_addm;
614 	ctx->subm = ec_subm;
615 	ctx->mulm = ec_mulm;
616 	ctx->mul2 = ec_mul2;
617 	ctx->pow2 = ec_pow2;
618 
619 	for (i = 0; field_table[i].p; i++) {
620 		MPI f_p;
621 
622 		f_p = mpi_scanval(field_table[i].p);
623 		if (!f_p)
624 			break;
625 
626 		if (!mpi_cmp(p, f_p)) {
627 			ctx->addm = field_table[i].addm;
628 			ctx->subm = field_table[i].subm;
629 			ctx->mulm = field_table[i].mulm;
630 			ctx->mul2 = field_table[i].mul2;
631 			ctx->pow2 = field_table[i].pow2;
632 			mpi_free(f_p);
633 
634 			mpi_resize(ctx->a, ctx->p->nlimbs);
635 			ctx->a->nlimbs = ctx->p->nlimbs;
636 
637 			mpi_resize(ctx->b, ctx->p->nlimbs);
638 			ctx->b->nlimbs = ctx->p->nlimbs;
639 
640 			for (i = 0; i < DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++)
641 				ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs;
642 
643 			break;
644 		}
645 
646 		mpi_free(f_p);
647 	}
648 }
649 EXPORT_SYMBOL_GPL(mpi_ec_init);
650 
mpi_ec_deinit(struct mpi_ec_ctx * ctx)651 void mpi_ec_deinit(struct mpi_ec_ctx *ctx)
652 {
653 	int i;
654 
655 	mpi_barrett_free(ctx->t.p_barrett);
656 
657 	/* Domain parameter.  */
658 	mpi_free(ctx->p);
659 	mpi_free(ctx->a);
660 	mpi_free(ctx->b);
661 	mpi_point_release(ctx->G);
662 	mpi_free(ctx->n);
663 
664 	/* The key.  */
665 	mpi_point_release(ctx->Q);
666 	mpi_free(ctx->d);
667 
668 	/* Private data of ec.c.  */
669 	mpi_free(ctx->t.two_inv_p);
670 
671 	for (i = 0; i < DIM(ctx->t.scratch); i++)
672 		mpi_free(ctx->t.scratch[i]);
673 }
674 EXPORT_SYMBOL_GPL(mpi_ec_deinit);
675 
676 /* Compute the affine coordinates from the projective coordinates in
677  * POINT.  Set them into X and Y.  If one coordinate is not required,
678  * X or Y may be passed as NULL.  CTX is the usual context. Returns: 0
679  * on success or !0 if POINT is at infinity.
680  */
mpi_ec_get_affine(MPI x,MPI y,MPI_POINT point,struct mpi_ec_ctx * ctx)681 int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx)
682 {
683 	if (!mpi_cmp_ui(point->z, 0))
684 		return -1;
685 
686 	switch (ctx->model) {
687 	case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates.  */
688 		{
689 			MPI z1, z2, z3;
690 
691 			z1 = mpi_new(0);
692 			z2 = mpi_new(0);
693 			ec_invm(z1, point->z, ctx);  /* z1 = z^(-1) mod p  */
694 			ec_mulm(z2, z1, z1, ctx);    /* z2 = z^(-2) mod p  */
695 
696 			if (x)
697 				ec_mulm(x, point->x, z2, ctx);
698 
699 			if (y) {
700 				z3 = mpi_new(0);
701 				ec_mulm(z3, z2, z1, ctx);      /* z3 = z^(-3) mod p */
702 				ec_mulm(y, point->y, z3, ctx);
703 				mpi_free(z3);
704 			}
705 
706 			mpi_free(z2);
707 			mpi_free(z1);
708 		}
709 		return 0;
710 
711 	case MPI_EC_MONTGOMERY:
712 		{
713 			if (x)
714 				mpi_set(x, point->x);
715 
716 			if (y) {
717 				log_fatal("%s: Getting Y-coordinate on %s is not supported\n",
718 						"mpi_ec_get_affine", "Montgomery");
719 				return -1;
720 			}
721 		}
722 		return 0;
723 
724 	case MPI_EC_EDWARDS:
725 		{
726 			MPI z;
727 
728 			z = mpi_new(0);
729 			ec_invm(z, point->z, ctx);
730 
731 			mpi_resize(z, ctx->p->nlimbs);
732 			z->nlimbs = ctx->p->nlimbs;
733 
734 			if (x) {
735 				mpi_resize(x, ctx->p->nlimbs);
736 				x->nlimbs = ctx->p->nlimbs;
737 				ctx->mulm(x, point->x, z, ctx);
738 			}
739 			if (y) {
740 				mpi_resize(y, ctx->p->nlimbs);
741 				y->nlimbs = ctx->p->nlimbs;
742 				ctx->mulm(y, point->y, z, ctx);
743 			}
744 
745 			mpi_free(z);
746 		}
747 		return 0;
748 
749 	default:
750 		return -1;
751 	}
752 }
753 EXPORT_SYMBOL_GPL(mpi_ec_get_affine);
754 
755 /*  RESULT = 2 * POINT  (Weierstrass version). */
dup_point_weierstrass(MPI_POINT result,MPI_POINT point,struct mpi_ec_ctx * ctx)756 static void dup_point_weierstrass(MPI_POINT result,
757 		MPI_POINT point, struct mpi_ec_ctx *ctx)
758 {
759 #define x3 (result->x)
760 #define y3 (result->y)
761 #define z3 (result->z)
762 #define t1 (ctx->t.scratch[0])
763 #define t2 (ctx->t.scratch[1])
764 #define t3 (ctx->t.scratch[2])
765 #define l1 (ctx->t.scratch[3])
766 #define l2 (ctx->t.scratch[4])
767 #define l3 (ctx->t.scratch[5])
768 
769 	if (!mpi_cmp_ui(point->y, 0) || !mpi_cmp_ui(point->z, 0)) {
770 		/* P_y == 0 || P_z == 0 => [1:1:0] */
771 		mpi_set_ui(x3, 1);
772 		mpi_set_ui(y3, 1);
773 		mpi_set_ui(z3, 0);
774 	} else {
775 		if (ec_get_a_is_pminus3(ctx)) {
776 			/* Use the faster case.  */
777 			/* L1 = 3(X - Z^2)(X + Z^2) */
778 			/*                          T1: used for Z^2. */
779 			/*                          T2: used for the right term. */
780 			ec_pow2(t1, point->z, ctx);
781 			ec_subm(l1, point->x, t1, ctx);
782 			ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx);
783 			ec_addm(t2, point->x, t1, ctx);
784 			ec_mulm(l1, l1, t2, ctx);
785 		} else {
786 			/* Standard case. */
787 			/* L1 = 3X^2 + aZ^4 */
788 			/*                          T1: used for aZ^4. */
789 			ec_pow2(l1, point->x, ctx);
790 			ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx);
791 			ec_powm(t1, point->z, mpi_const(MPI_C_FOUR), ctx);
792 			ec_mulm(t1, t1, ctx->a, ctx);
793 			ec_addm(l1, l1, t1, ctx);
794 		}
795 		/* Z3 = 2YZ */
796 		ec_mulm(z3, point->y, point->z, ctx);
797 		ec_mul2(z3, z3, ctx);
798 
799 		/* L2 = 4XY^2 */
800 		/*                              T2: used for Y2; required later. */
801 		ec_pow2(t2, point->y, ctx);
802 		ec_mulm(l2, t2, point->x, ctx);
803 		ec_mulm(l2, l2, mpi_const(MPI_C_FOUR), ctx);
804 
805 		/* X3 = L1^2 - 2L2 */
806 		/*                              T1: used for L2^2. */
807 		ec_pow2(x3, l1, ctx);
808 		ec_mul2(t1, l2, ctx);
809 		ec_subm(x3, x3, t1, ctx);
810 
811 		/* L3 = 8Y^4 */
812 		/*                              T2: taken from above. */
813 		ec_pow2(t2, t2, ctx);
814 		ec_mulm(l3, t2, mpi_const(MPI_C_EIGHT), ctx);
815 
816 		/* Y3 = L1(L2 - X3) - L3 */
817 		ec_subm(y3, l2, x3, ctx);
818 		ec_mulm(y3, y3, l1, ctx);
819 		ec_subm(y3, y3, l3, ctx);
820 	}
821 
822 #undef x3
823 #undef y3
824 #undef z3
825 #undef t1
826 #undef t2
827 #undef t3
828 #undef l1
829 #undef l2
830 #undef l3
831 }
832 
833 /*  RESULT = 2 * POINT  (Montgomery version). */
dup_point_montgomery(MPI_POINT result,MPI_POINT point,struct mpi_ec_ctx * ctx)834 static void dup_point_montgomery(MPI_POINT result,
835 				MPI_POINT point, struct mpi_ec_ctx *ctx)
836 {
837 	(void)result;
838 	(void)point;
839 	(void)ctx;
840 	log_fatal("%s: %s not yet supported\n",
841 			"mpi_ec_dup_point", "Montgomery");
842 }
843 
844 /*  RESULT = 2 * POINT  (Twisted Edwards version). */
dup_point_edwards(MPI_POINT result,MPI_POINT point,struct mpi_ec_ctx * ctx)845 static void dup_point_edwards(MPI_POINT result,
846 		MPI_POINT point, struct mpi_ec_ctx *ctx)
847 {
848 #define X1 (point->x)
849 #define Y1 (point->y)
850 #define Z1 (point->z)
851 #define X3 (result->x)
852 #define Y3 (result->y)
853 #define Z3 (result->z)
854 #define B (ctx->t.scratch[0])
855 #define C (ctx->t.scratch[1])
856 #define D (ctx->t.scratch[2])
857 #define E (ctx->t.scratch[3])
858 #define F (ctx->t.scratch[4])
859 #define H (ctx->t.scratch[5])
860 #define J (ctx->t.scratch[6])
861 
862 	/* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */
863 
864 	/* B = (X_1 + Y_1)^2  */
865 	ctx->addm(B, X1, Y1, ctx);
866 	ctx->pow2(B, B, ctx);
867 
868 	/* C = X_1^2 */
869 	/* D = Y_1^2 */
870 	ctx->pow2(C, X1, ctx);
871 	ctx->pow2(D, Y1, ctx);
872 
873 	/* E = aC */
874 	if (ctx->dialect == ECC_DIALECT_ED25519)
875 		ctx->subm(E, ctx->p, C, ctx);
876 	else
877 		ctx->mulm(E, ctx->a, C, ctx);
878 
879 	/* F = E + D */
880 	ctx->addm(F, E, D, ctx);
881 
882 	/* H = Z_1^2 */
883 	ctx->pow2(H, Z1, ctx);
884 
885 	/* J = F - 2H */
886 	ctx->mul2(J, H, ctx);
887 	ctx->subm(J, F, J, ctx);
888 
889 	/* X_3 = (B - C - D) · J */
890 	ctx->subm(X3, B, C, ctx);
891 	ctx->subm(X3, X3, D, ctx);
892 	ctx->mulm(X3, X3, J, ctx);
893 
894 	/* Y_3 = F · (E - D) */
895 	ctx->subm(Y3, E, D, ctx);
896 	ctx->mulm(Y3, Y3, F, ctx);
897 
898 	/* Z_3 = F · J */
899 	ctx->mulm(Z3, F, J, ctx);
900 
901 #undef X1
902 #undef Y1
903 #undef Z1
904 #undef X3
905 #undef Y3
906 #undef Z3
907 #undef B
908 #undef C
909 #undef D
910 #undef E
911 #undef F
912 #undef H
913 #undef J
914 }
915 
916 /*  RESULT = 2 * POINT  */
917 static void
mpi_ec_dup_point(MPI_POINT result,MPI_POINT point,struct mpi_ec_ctx * ctx)918 mpi_ec_dup_point(MPI_POINT result, MPI_POINT point, struct mpi_ec_ctx *ctx)
919 {
920 	switch (ctx->model) {
921 	case MPI_EC_WEIERSTRASS:
922 		dup_point_weierstrass(result, point, ctx);
923 		break;
924 	case MPI_EC_MONTGOMERY:
925 		dup_point_montgomery(result, point, ctx);
926 		break;
927 	case MPI_EC_EDWARDS:
928 		dup_point_edwards(result, point, ctx);
929 		break;
930 	}
931 }
932 
933 /* RESULT = P1 + P2  (Weierstrass version).*/
add_points_weierstrass(MPI_POINT result,MPI_POINT p1,MPI_POINT p2,struct mpi_ec_ctx * ctx)934 static void add_points_weierstrass(MPI_POINT result,
935 		MPI_POINT p1, MPI_POINT p2,
936 		struct mpi_ec_ctx *ctx)
937 {
938 #define x1 (p1->x)
939 #define y1 (p1->y)
940 #define z1 (p1->z)
941 #define x2 (p2->x)
942 #define y2 (p2->y)
943 #define z2 (p2->z)
944 #define x3 (result->x)
945 #define y3 (result->y)
946 #define z3 (result->z)
947 #define l1 (ctx->t.scratch[0])
948 #define l2 (ctx->t.scratch[1])
949 #define l3 (ctx->t.scratch[2])
950 #define l4 (ctx->t.scratch[3])
951 #define l5 (ctx->t.scratch[4])
952 #define l6 (ctx->t.scratch[5])
953 #define l7 (ctx->t.scratch[6])
954 #define l8 (ctx->t.scratch[7])
955 #define l9 (ctx->t.scratch[8])
956 #define t1 (ctx->t.scratch[9])
957 #define t2 (ctx->t.scratch[10])
958 
959 	if ((!mpi_cmp(x1, x2)) && (!mpi_cmp(y1, y2)) && (!mpi_cmp(z1, z2))) {
960 		/* Same point; need to call the duplicate function.  */
961 		mpi_ec_dup_point(result, p1, ctx);
962 	} else if (!mpi_cmp_ui(z1, 0)) {
963 		/* P1 is at infinity.  */
964 		mpi_set(x3, p2->x);
965 		mpi_set(y3, p2->y);
966 		mpi_set(z3, p2->z);
967 	} else if (!mpi_cmp_ui(z2, 0)) {
968 		/* P2 is at infinity.  */
969 		mpi_set(x3, p1->x);
970 		mpi_set(y3, p1->y);
971 		mpi_set(z3, p1->z);
972 	} else {
973 		int z1_is_one = !mpi_cmp_ui(z1, 1);
974 		int z2_is_one = !mpi_cmp_ui(z2, 1);
975 
976 		/* l1 = x1 z2^2  */
977 		/* l2 = x2 z1^2  */
978 		if (z2_is_one)
979 			mpi_set(l1, x1);
980 		else {
981 			ec_pow2(l1, z2, ctx);
982 			ec_mulm(l1, l1, x1, ctx);
983 		}
984 		if (z1_is_one)
985 			mpi_set(l2, x2);
986 		else {
987 			ec_pow2(l2, z1, ctx);
988 			ec_mulm(l2, l2, x2, ctx);
989 		}
990 		/* l3 = l1 - l2 */
991 		ec_subm(l3, l1, l2, ctx);
992 		/* l4 = y1 z2^3  */
993 		ec_powm(l4, z2, mpi_const(MPI_C_THREE), ctx);
994 		ec_mulm(l4, l4, y1, ctx);
995 		/* l5 = y2 z1^3  */
996 		ec_powm(l5, z1, mpi_const(MPI_C_THREE), ctx);
997 		ec_mulm(l5, l5, y2, ctx);
998 		/* l6 = l4 - l5  */
999 		ec_subm(l6, l4, l5, ctx);
1000 
1001 		if (!mpi_cmp_ui(l3, 0)) {
1002 			if (!mpi_cmp_ui(l6, 0)) {
1003 				/* P1 and P2 are the same - use duplicate function. */
1004 				mpi_ec_dup_point(result, p1, ctx);
1005 			} else {
1006 				/* P1 is the inverse of P2.  */
1007 				mpi_set_ui(x3, 1);
1008 				mpi_set_ui(y3, 1);
1009 				mpi_set_ui(z3, 0);
1010 			}
1011 		} else {
1012 			/* l7 = l1 + l2  */
1013 			ec_addm(l7, l1, l2, ctx);
1014 			/* l8 = l4 + l5  */
1015 			ec_addm(l8, l4, l5, ctx);
1016 			/* z3 = z1 z2 l3  */
1017 			ec_mulm(z3, z1, z2, ctx);
1018 			ec_mulm(z3, z3, l3, ctx);
1019 			/* x3 = l6^2 - l7 l3^2  */
1020 			ec_pow2(t1, l6, ctx);
1021 			ec_pow2(t2, l3, ctx);
1022 			ec_mulm(t2, t2, l7, ctx);
1023 			ec_subm(x3, t1, t2, ctx);
1024 			/* l9 = l7 l3^2 - 2 x3  */
1025 			ec_mul2(t1, x3, ctx);
1026 			ec_subm(l9, t2, t1, ctx);
1027 			/* y3 = (l9 l6 - l8 l3^3)/2  */
1028 			ec_mulm(l9, l9, l6, ctx);
1029 			ec_powm(t1, l3, mpi_const(MPI_C_THREE), ctx); /* fixme: Use saved value*/
1030 			ec_mulm(t1, t1, l8, ctx);
1031 			ec_subm(y3, l9, t1, ctx);
1032 			ec_mulm(y3, y3, ec_get_two_inv_p(ctx), ctx);
1033 		}
1034 	}
1035 
1036 #undef x1
1037 #undef y1
1038 #undef z1
1039 #undef x2
1040 #undef y2
1041 #undef z2
1042 #undef x3
1043 #undef y3
1044 #undef z3
1045 #undef l1
1046 #undef l2
1047 #undef l3
1048 #undef l4
1049 #undef l5
1050 #undef l6
1051 #undef l7
1052 #undef l8
1053 #undef l9
1054 #undef t1
1055 #undef t2
1056 }
1057 
1058 /* RESULT = P1 + P2  (Montgomery version).*/
add_points_montgomery(MPI_POINT result,MPI_POINT p1,MPI_POINT p2,struct mpi_ec_ctx * ctx)1059 static void add_points_montgomery(MPI_POINT result,
1060 		MPI_POINT p1, MPI_POINT p2,
1061 		struct mpi_ec_ctx *ctx)
1062 {
1063 	(void)result;
1064 	(void)p1;
1065 	(void)p2;
1066 	(void)ctx;
1067 	log_fatal("%s: %s not yet supported\n",
1068 			"mpi_ec_add_points", "Montgomery");
1069 }
1070 
1071 /* RESULT = P1 + P2  (Twisted Edwards version).*/
add_points_edwards(MPI_POINT result,MPI_POINT p1,MPI_POINT p2,struct mpi_ec_ctx * ctx)1072 static void add_points_edwards(MPI_POINT result,
1073 		MPI_POINT p1, MPI_POINT p2,
1074 		struct mpi_ec_ctx *ctx)
1075 {
1076 #define X1 (p1->x)
1077 #define Y1 (p1->y)
1078 #define Z1 (p1->z)
1079 #define X2 (p2->x)
1080 #define Y2 (p2->y)
1081 #define Z2 (p2->z)
1082 #define X3 (result->x)
1083 #define Y3 (result->y)
1084 #define Z3 (result->z)
1085 #define A (ctx->t.scratch[0])
1086 #define B (ctx->t.scratch[1])
1087 #define C (ctx->t.scratch[2])
1088 #define D (ctx->t.scratch[3])
1089 #define E (ctx->t.scratch[4])
1090 #define F (ctx->t.scratch[5])
1091 #define G (ctx->t.scratch[6])
1092 #define tmp (ctx->t.scratch[7])
1093 
1094 	point_resize(result, ctx);
1095 
1096 	/* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */
1097 
1098 	/* A = Z1 · Z2 */
1099 	ctx->mulm(A, Z1, Z2, ctx);
1100 
1101 	/* B = A^2 */
1102 	ctx->pow2(B, A, ctx);
1103 
1104 	/* C = X1 · X2 */
1105 	ctx->mulm(C, X1, X2, ctx);
1106 
1107 	/* D = Y1 · Y2 */
1108 	ctx->mulm(D, Y1, Y2, ctx);
1109 
1110 	/* E = d · C · D */
1111 	ctx->mulm(E, ctx->b, C, ctx);
1112 	ctx->mulm(E, E, D, ctx);
1113 
1114 	/* F = B - E */
1115 	ctx->subm(F, B, E, ctx);
1116 
1117 	/* G = B + E */
1118 	ctx->addm(G, B, E, ctx);
1119 
1120 	/* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */
1121 	ctx->addm(tmp, X1, Y1, ctx);
1122 	ctx->addm(X3, X2, Y2, ctx);
1123 	ctx->mulm(X3, X3, tmp, ctx);
1124 	ctx->subm(X3, X3, C, ctx);
1125 	ctx->subm(X3, X3, D, ctx);
1126 	ctx->mulm(X3, X3, F, ctx);
1127 	ctx->mulm(X3, X3, A, ctx);
1128 
1129 	/* Y_3 = A · G · (D - aC) */
1130 	if (ctx->dialect == ECC_DIALECT_ED25519) {
1131 		ctx->addm(Y3, D, C, ctx);
1132 	} else {
1133 		ctx->mulm(Y3, ctx->a, C, ctx);
1134 		ctx->subm(Y3, D, Y3, ctx);
1135 	}
1136 	ctx->mulm(Y3, Y3, G, ctx);
1137 	ctx->mulm(Y3, Y3, A, ctx);
1138 
1139 	/* Z_3 = F · G */
1140 	ctx->mulm(Z3, F, G, ctx);
1141 
1142 
1143 #undef X1
1144 #undef Y1
1145 #undef Z1
1146 #undef X2
1147 #undef Y2
1148 #undef Z2
1149 #undef X3
1150 #undef Y3
1151 #undef Z3
1152 #undef A
1153 #undef B
1154 #undef C
1155 #undef D
1156 #undef E
1157 #undef F
1158 #undef G
1159 #undef tmp
1160 }
1161 
1162 /* Compute a step of Montgomery Ladder (only use X and Z in the point).
1163  * Inputs:  P1, P2, and x-coordinate of DIF = P1 - P1.
1164  * Outputs: PRD = 2 * P1 and  SUM = P1 + P2.
1165  */
montgomery_ladder(MPI_POINT prd,MPI_POINT sum,MPI_POINT p1,MPI_POINT p2,MPI dif_x,struct mpi_ec_ctx * ctx)1166 static void montgomery_ladder(MPI_POINT prd, MPI_POINT sum,
1167 		MPI_POINT p1, MPI_POINT p2, MPI dif_x,
1168 		struct mpi_ec_ctx *ctx)
1169 {
1170 	ctx->addm(sum->x, p2->x, p2->z, ctx);
1171 	ctx->subm(p2->z, p2->x, p2->z, ctx);
1172 	ctx->addm(prd->x, p1->x, p1->z, ctx);
1173 	ctx->subm(p1->z, p1->x, p1->z, ctx);
1174 	ctx->mulm(p2->x, p1->z, sum->x, ctx);
1175 	ctx->mulm(p2->z, prd->x, p2->z, ctx);
1176 	ctx->pow2(p1->x, prd->x, ctx);
1177 	ctx->pow2(p1->z, p1->z, ctx);
1178 	ctx->addm(sum->x, p2->x, p2->z, ctx);
1179 	ctx->subm(p2->z, p2->x, p2->z, ctx);
1180 	ctx->mulm(prd->x, p1->x, p1->z, ctx);
1181 	ctx->subm(p1->z, p1->x, p1->z, ctx);
1182 	ctx->pow2(sum->x, sum->x, ctx);
1183 	ctx->pow2(sum->z, p2->z, ctx);
1184 	ctx->mulm(prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */
1185 	ctx->mulm(sum->z, sum->z, dif_x, ctx);
1186 	ctx->addm(prd->z, p1->x, prd->z, ctx);
1187 	ctx->mulm(prd->z, prd->z, p1->z, ctx);
1188 }
1189 
1190 /* RESULT = P1 + P2 */
mpi_ec_add_points(MPI_POINT result,MPI_POINT p1,MPI_POINT p2,struct mpi_ec_ctx * ctx)1191 void mpi_ec_add_points(MPI_POINT result,
1192 		MPI_POINT p1, MPI_POINT p2,
1193 		struct mpi_ec_ctx *ctx)
1194 {
1195 	switch (ctx->model) {
1196 	case MPI_EC_WEIERSTRASS:
1197 		add_points_weierstrass(result, p1, p2, ctx);
1198 		break;
1199 	case MPI_EC_MONTGOMERY:
1200 		add_points_montgomery(result, p1, p2, ctx);
1201 		break;
1202 	case MPI_EC_EDWARDS:
1203 		add_points_edwards(result, p1, p2, ctx);
1204 		break;
1205 	}
1206 }
1207 EXPORT_SYMBOL_GPL(mpi_ec_add_points);
1208 
1209 /* Scalar point multiplication - the main function for ECC.  If takes
1210  * an integer SCALAR and a POINT as well as the usual context CTX.
1211  * RESULT will be set to the resulting point.
1212  */
mpi_ec_mul_point(MPI_POINT result,MPI scalar,MPI_POINT point,struct mpi_ec_ctx * ctx)1213 void mpi_ec_mul_point(MPI_POINT result,
1214 			MPI scalar, MPI_POINT point,
1215 			struct mpi_ec_ctx *ctx)
1216 {
1217 	MPI x1, y1, z1, k, h, yy;
1218 	unsigned int i, loops;
1219 	struct gcry_mpi_point p1, p2, p1inv;
1220 
1221 	if (ctx->model == MPI_EC_EDWARDS) {
1222 		/* Simple left to right binary method.  Algorithm 3.27 from
1223 		 * {author={Hankerson, Darrel and Menezes, Alfred J. and Vanstone, Scott},
1224 		 *  title = {Guide to Elliptic Curve Cryptography},
1225 		 *  year = {2003}, isbn = {038795273X},
1226 		 *  url = {http://www.cacr.math.uwaterloo.ca/ecc/},
1227 		 *  publisher = {Springer-Verlag New York, Inc.}}
1228 		 */
1229 		unsigned int nbits;
1230 		int j;
1231 
1232 		if (mpi_cmp(scalar, ctx->p) >= 0)
1233 			nbits = mpi_get_nbits(scalar);
1234 		else
1235 			nbits = mpi_get_nbits(ctx->p);
1236 
1237 		mpi_set_ui(result->x, 0);
1238 		mpi_set_ui(result->y, 1);
1239 		mpi_set_ui(result->z, 1);
1240 		point_resize(point, ctx);
1241 
1242 		point_resize(result, ctx);
1243 		point_resize(point, ctx);
1244 
1245 		for (j = nbits-1; j >= 0; j--) {
1246 			mpi_ec_dup_point(result, result, ctx);
1247 			if (mpi_test_bit(scalar, j))
1248 				mpi_ec_add_points(result, result, point, ctx);
1249 		}
1250 		return;
1251 	} else if (ctx->model == MPI_EC_MONTGOMERY) {
1252 		unsigned int nbits;
1253 		int j;
1254 		struct gcry_mpi_point p1_, p2_;
1255 		MPI_POINT q1, q2, prd, sum;
1256 		unsigned long sw;
1257 		mpi_size_t rsize;
1258 
1259 		/* Compute scalar point multiplication with Montgomery Ladder.
1260 		 * Note that we don't use Y-coordinate in the points at all.
1261 		 * RESULT->Y will be filled by zero.
1262 		 */
1263 
1264 		nbits = mpi_get_nbits(scalar);
1265 		point_init(&p1);
1266 		point_init(&p2);
1267 		point_init(&p1_);
1268 		point_init(&p2_);
1269 		mpi_set_ui(p1.x, 1);
1270 		mpi_free(p2.x);
1271 		p2.x = mpi_copy(point->x);
1272 		mpi_set_ui(p2.z, 1);
1273 
1274 		point_resize(&p1, ctx);
1275 		point_resize(&p2, ctx);
1276 		point_resize(&p1_, ctx);
1277 		point_resize(&p2_, ctx);
1278 
1279 		mpi_resize(point->x, ctx->p->nlimbs);
1280 		point->x->nlimbs = ctx->p->nlimbs;
1281 
1282 		q1 = &p1;
1283 		q2 = &p2;
1284 		prd = &p1_;
1285 		sum = &p2_;
1286 
1287 		for (j = nbits-1; j >= 0; j--) {
1288 			MPI_POINT t;
1289 
1290 			sw = mpi_test_bit(scalar, j);
1291 			point_swap_cond(q1, q2, sw, ctx);
1292 			montgomery_ladder(prd, sum, q1, q2, point->x, ctx);
1293 			point_swap_cond(prd, sum, sw, ctx);
1294 			t = q1;  q1 = prd;  prd = t;
1295 			t = q2;  q2 = sum;  sum = t;
1296 		}
1297 
1298 		mpi_clear(result->y);
1299 		sw = (nbits & 1);
1300 		point_swap_cond(&p1, &p1_, sw, ctx);
1301 
1302 		rsize = p1.z->nlimbs;
1303 		MPN_NORMALIZE(p1.z->d, rsize);
1304 		if (rsize == 0) {
1305 			mpi_set_ui(result->x, 1);
1306 			mpi_set_ui(result->z, 0);
1307 		} else {
1308 			z1 = mpi_new(0);
1309 			ec_invm(z1, p1.z, ctx);
1310 			ec_mulm(result->x, p1.x, z1, ctx);
1311 			mpi_set_ui(result->z, 1);
1312 			mpi_free(z1);
1313 		}
1314 
1315 		point_free(&p1);
1316 		point_free(&p2);
1317 		point_free(&p1_);
1318 		point_free(&p2_);
1319 		return;
1320 	}
1321 
1322 	x1 = mpi_alloc_like(ctx->p);
1323 	y1 = mpi_alloc_like(ctx->p);
1324 	h  = mpi_alloc_like(ctx->p);
1325 	k  = mpi_copy(scalar);
1326 	yy = mpi_copy(point->y);
1327 
1328 	if (mpi_has_sign(k)) {
1329 		k->sign = 0;
1330 		ec_invm(yy, yy, ctx);
1331 	}
1332 
1333 	if (!mpi_cmp_ui(point->z, 1)) {
1334 		mpi_set(x1, point->x);
1335 		mpi_set(y1, yy);
1336 	} else {
1337 		MPI z2, z3;
1338 
1339 		z2 = mpi_alloc_like(ctx->p);
1340 		z3 = mpi_alloc_like(ctx->p);
1341 		ec_mulm(z2, point->z, point->z, ctx);
1342 		ec_mulm(z3, point->z, z2, ctx);
1343 		ec_invm(z2, z2, ctx);
1344 		ec_mulm(x1, point->x, z2, ctx);
1345 		ec_invm(z3, z3, ctx);
1346 		ec_mulm(y1, yy, z3, ctx);
1347 		mpi_free(z2);
1348 		mpi_free(z3);
1349 	}
1350 	z1 = mpi_copy(mpi_const(MPI_C_ONE));
1351 
1352 	mpi_mul(h, k, mpi_const(MPI_C_THREE)); /* h = 3k */
1353 	loops = mpi_get_nbits(h);
1354 	if (loops < 2) {
1355 		/* If SCALAR is zero, the above mpi_mul sets H to zero and thus
1356 		 * LOOPs will be zero.  To avoid an underflow of I in the main
1357 		 * loop we set LOOP to 2 and the result to (0,0,0).
1358 		 */
1359 		loops = 2;
1360 		mpi_clear(result->x);
1361 		mpi_clear(result->y);
1362 		mpi_clear(result->z);
1363 	} else {
1364 		mpi_set(result->x, point->x);
1365 		mpi_set(result->y, yy);
1366 		mpi_set(result->z, point->z);
1367 	}
1368 	mpi_free(yy); yy = NULL;
1369 
1370 	p1.x = x1; x1 = NULL;
1371 	p1.y = y1; y1 = NULL;
1372 	p1.z = z1; z1 = NULL;
1373 	point_init(&p2);
1374 	point_init(&p1inv);
1375 
1376 	/* Invert point: y = p - y mod p  */
1377 	point_set(&p1inv, &p1);
1378 	ec_subm(p1inv.y, ctx->p, p1inv.y, ctx);
1379 
1380 	for (i = loops-2; i > 0; i--) {
1381 		mpi_ec_dup_point(result, result, ctx);
1382 		if (mpi_test_bit(h, i) == 1 && mpi_test_bit(k, i) == 0) {
1383 			point_set(&p2, result);
1384 			mpi_ec_add_points(result, &p2, &p1, ctx);
1385 		}
1386 		if (mpi_test_bit(h, i) == 0 && mpi_test_bit(k, i) == 1) {
1387 			point_set(&p2, result);
1388 			mpi_ec_add_points(result, &p2, &p1inv, ctx);
1389 		}
1390 	}
1391 
1392 	point_free(&p1);
1393 	point_free(&p2);
1394 	point_free(&p1inv);
1395 	mpi_free(h);
1396 	mpi_free(k);
1397 }
1398 EXPORT_SYMBOL_GPL(mpi_ec_mul_point);
1399 
1400 /* Return true if POINT is on the curve described by CTX.  */
mpi_ec_curve_point(MPI_POINT point,struct mpi_ec_ctx * ctx)1401 int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx)
1402 {
1403 	int res = 0;
1404 	MPI x, y, w;
1405 
1406 	x = mpi_new(0);
1407 	y = mpi_new(0);
1408 	w = mpi_new(0);
1409 
1410 	/* Check that the point is in range.  This needs to be done here and
1411 	 * not after conversion to affine coordinates.
1412 	 */
1413 	if (mpi_cmpabs(point->x, ctx->p) >= 0)
1414 		goto leave;
1415 	if (mpi_cmpabs(point->y, ctx->p) >= 0)
1416 		goto leave;
1417 	if (mpi_cmpabs(point->z, ctx->p) >= 0)
1418 		goto leave;
1419 
1420 	switch (ctx->model) {
1421 	case MPI_EC_WEIERSTRASS:
1422 		{
1423 			MPI xxx;
1424 
1425 			if (mpi_ec_get_affine(x, y, point, ctx))
1426 				goto leave;
1427 
1428 			xxx = mpi_new(0);
1429 
1430 			/* y^2 == x^3 + a·x + b */
1431 			ec_pow2(y, y, ctx);
1432 
1433 			ec_pow3(xxx, x, ctx);
1434 			ec_mulm(w, ctx->a, x, ctx);
1435 			ec_addm(w, w, ctx->b, ctx);
1436 			ec_addm(w, w, xxx, ctx);
1437 
1438 			if (!mpi_cmp(y, w))
1439 				res = 1;
1440 
1441 			mpi_free(xxx);
1442 		}
1443 		break;
1444 
1445 	case MPI_EC_MONTGOMERY:
1446 		{
1447 #define xx y
1448 			/* With Montgomery curve, only X-coordinate is valid. */
1449 			if (mpi_ec_get_affine(x, NULL, point, ctx))
1450 				goto leave;
1451 
1452 			/* The equation is: b * y^2 == x^3 + a · x^2 + x */
1453 			/* We check if right hand is quadratic residue or not by
1454 			 * Euler's criterion.
1455 			 */
1456 			/* CTX->A has (a-2)/4 and CTX->B has b^-1 */
1457 			ec_mulm(w, ctx->a, mpi_const(MPI_C_FOUR), ctx);
1458 			ec_addm(w, w, mpi_const(MPI_C_TWO), ctx);
1459 			ec_mulm(w, w, x, ctx);
1460 			ec_pow2(xx, x, ctx);
1461 			ec_addm(w, w, xx, ctx);
1462 			ec_addm(w, w, mpi_const(MPI_C_ONE), ctx);
1463 			ec_mulm(w, w, x, ctx);
1464 			ec_mulm(w, w, ctx->b, ctx);
1465 #undef xx
1466 			/* Compute Euler's criterion: w^(p-1)/2 */
1467 #define p_minus1 y
1468 			ec_subm(p_minus1, ctx->p, mpi_const(MPI_C_ONE), ctx);
1469 			mpi_rshift(p_minus1, p_minus1, 1);
1470 			ec_powm(w, w, p_minus1, ctx);
1471 
1472 			res = !mpi_cmp_ui(w, 1);
1473 #undef p_minus1
1474 		}
1475 		break;
1476 
1477 	case MPI_EC_EDWARDS:
1478 		{
1479 			if (mpi_ec_get_affine(x, y, point, ctx))
1480 				goto leave;
1481 
1482 			mpi_resize(w, ctx->p->nlimbs);
1483 			w->nlimbs = ctx->p->nlimbs;
1484 
1485 			/* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */
1486 			ctx->pow2(x, x, ctx);
1487 			ctx->pow2(y, y, ctx);
1488 			if (ctx->dialect == ECC_DIALECT_ED25519)
1489 				ctx->subm(w, ctx->p, x, ctx);
1490 			else
1491 				ctx->mulm(w, ctx->a, x, ctx);
1492 			ctx->addm(w, w, y, ctx);
1493 			ctx->mulm(x, x, y, ctx);
1494 			ctx->mulm(x, x, ctx->b, ctx);
1495 			ctx->subm(w, w, x, ctx);
1496 			if (!mpi_cmp_ui(w, 1))
1497 				res = 1;
1498 		}
1499 		break;
1500 	}
1501 
1502 leave:
1503 	mpi_free(w);
1504 	mpi_free(x);
1505 	mpi_free(y);
1506 
1507 	return res;
1508 }
1509 EXPORT_SYMBOL_GPL(mpi_ec_curve_point);
1510