1 /* ===================================================================
2 *
3 * Copyright (c) 2018, Helder Eijs <helderijs@gmail.com>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
20 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
21 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
23 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
25 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
27 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
29 * ===================================================================
30 */
31
32 #include <assert.h>
33
34 #include "common.h"
35 #include "endianess.h"
36 #include "multiply.h"
37 #include "mont.h"
38 #include "ec.h"
39
40 #include "p256_table.h"
41 #include "p384_table.h"
42 #include "p521_table.h"
43
FAKE_INIT(ec_ws)44 FAKE_INIT(ec_ws)
45
46 #ifdef MAIN
47 STATIC void print_x(const char *s, const uint64_t *number, const MontContext *ctx)
48 {
49 unsigned i;
50 size_t size;
51 uint8_t *encoded;
52 int res;
53
54 size = mont_bytes(ctx);
55 encoded = calloc(1, size);
56 res = mont_to_bytes(encoded, size, number, ctx);
57 assert(res == 0);
58
59 printf("%s: ", s);
60 for (i=0; i<size; i++)
61 printf("%02X", encoded[i]);
62 printf("\n");
63
64 free(encoded);
65 }
66 #endif
67
new_workplace(const MontContext * ctx)68 STATIC Workplace *new_workplace(const MontContext *ctx)
69 {
70 Workplace *wp;
71 int res;
72
73 wp = calloc(1, sizeof(Workplace));
74 if (NULL == wp)
75 return NULL;
76
77 res = mont_number(&wp->a, 1, ctx);
78 if (res) goto cleanup;
79 res = mont_number(&wp->b, 1, ctx);
80 if (res) goto cleanup;
81 res = mont_number(&wp->c, 1, ctx);
82 if (res) goto cleanup;
83 res = mont_number(&wp->d, 1, ctx);
84 if (res) goto cleanup;
85 res = mont_number(&wp->e, 1, ctx);
86 if (res) goto cleanup;
87 res = mont_number(&wp->f, 1, ctx);
88 if (res) goto cleanup;
89 res = mont_number(&wp->g, 1, ctx);
90 if (res) goto cleanup;
91 res = mont_number(&wp->h, 1, ctx);
92 if (res) goto cleanup;
93 res = mont_number(&wp->i, 1, ctx);
94 if (res) goto cleanup;
95 res = mont_number(&wp->j, 1, ctx);
96 if (res) goto cleanup;
97 res = mont_number(&wp->k, 1, ctx);
98 if (res) goto cleanup;
99 res = mont_number(&wp->scratch, SCRATCHPAD_NR, ctx);
100 if (res) goto cleanup;
101 return wp;
102
103 cleanup:
104 free(wp->a);
105 free(wp->b);
106 free(wp->c);
107 free(wp->d);
108 free(wp->e);
109 free(wp->f);
110 free(wp->g);
111 free(wp->h);
112 free(wp->i);
113 free(wp->j);
114 free(wp->k);
115 free(wp->scratch);
116 return NULL;
117 }
118
free_workplace(Workplace * wp)119 STATIC void free_workplace(Workplace *wp)
120 {
121 if (NULL == wp)
122 return;
123 free(wp->a);
124 free(wp->b);
125 free(wp->c);
126 free(wp->d);
127 free(wp->e);
128 free(wp->f);
129 free(wp->g);
130 free(wp->h);
131 free(wp->i);
132 free(wp->j);
133 free(wp->k);
134 free(wp->scratch);
135 free(wp);
136 }
137
138 /*
139 * Convert projective coordinates of an EC point to affine
140 */
ec_projective_to_affine(uint64_t * x3,uint64_t * y3,const uint64_t * x1,uint64_t * y1,uint64_t * z1,Workplace * tmp,const MontContext * ctx)141 STATIC void ec_projective_to_affine(uint64_t *x3, uint64_t *y3,
142 const uint64_t *x1, uint64_t *y1, uint64_t *z1,
143 Workplace *tmp,
144 const MontContext *ctx)
145 {
146 uint64_t *a = tmp->a;
147 uint64_t *s = tmp->scratch;
148
149 if (mont_is_zero(z1, ctx)) {
150 mont_set(x3, 0, ctx);
151 mont_set(y3, 0, ctx);
152 return;
153 }
154
155 mont_inv_prime(a, z1, ctx);
156 mont_mult(x3, x1, a, s, ctx); /* X/Z */
157 mont_mult(y3, y1, a, s, ctx); /* Y/Z */
158 }
159
160 /*
161 * Double an EC point on a short Weierstrass curve of equation y²=x³-3x+b.
162 *
163 * @param x3 Projective X coordinate of the output point, in Montgomery form
164 * @param y3 Projective Y coordinate of the output point, in Montgomery form
165 * @param z3 Projective Z coordinate of the output point, in Montgomery form
166 * @param x1 Projective X coordinate of the input point, in Montgomery form
167 * @param y1 Projective Y coordinate of the input point, in Montgomery form
168 * @param z1 Projective Z coordinate of the input point, in Montgomery form
169 * @param b Parameter b in the equation, in Montgomery form
170 * @param tmp Workplace for temporary variables
171 * @param ctx The Montgomery context
172 *
173 * Input and output points can match. The input can be the point-at-infinity.
174 */
ec_full_double(uint64_t * x3,uint64_t * y3,uint64_t * z3,const uint64_t * x1,const uint64_t * y1,const uint64_t * z1,const uint64_t * b,Workplace * tmp,const MontContext * ctx)175 STATIC void ec_full_double(uint64_t *x3, uint64_t *y3, uint64_t *z3,
176 const uint64_t *x1, const uint64_t *y1, const uint64_t *z1,
177 const uint64_t *b,
178 Workplace *tmp, const MontContext *ctx)
179 {
180 uint64_t *t0 = tmp->a;
181 uint64_t *t1 = tmp->b;
182 uint64_t *t2 = tmp->c;
183 uint64_t *t3 = tmp->d;
184 uint64_t *x = tmp->e;
185 uint64_t *y = tmp->f;
186 uint64_t *z = tmp->g;
187 uint64_t *s = tmp->scratch;
188
189 /*
190 * Algorithm 6 in "Complete addition formulas for prime order elliptic curves", Renes et al.
191 */
192
193 memcpy(x, x1, ctx->bytes);
194 memcpy(y, y1, ctx->bytes);
195 memcpy(z, z1, ctx->bytes);
196
197 mont_mult(t0, x, x, s, ctx); /* 1 */
198 mont_mult(t1, y, y, s, ctx);
199 mont_mult(t2, z, z, s, ctx);
200
201 mont_mult(t3, x, y, s, ctx); /* 4 */
202 mont_add(t3, t3, t3, s, ctx);
203 mont_mult(z3, x, z, s, ctx);
204
205 mont_add(z3, z3, z3, s, ctx); /* 7 */
206 mont_mult(y3, b, t2, s, ctx);
207 mont_sub(y3, y3, z3, s, ctx);
208
209 mont_add(x3, y3, y3, s, ctx); /* 10 */
210 mont_add(y3, x3, y3, s, ctx);
211 mont_sub(x3, t1, y3, s, ctx);
212
213 mont_add(y3, t1, y3, s, ctx); /* 13 */
214 mont_mult(y3, x3, y3, s, ctx);
215 mont_mult(x3, x3, t3, s, ctx);
216
217 mont_add(t3, t2, t2, s, ctx); /* 16 */
218 mont_add(t2, t2, t3, s, ctx);
219 mont_mult(z3, b, z3, s, ctx);
220
221 mont_sub(z3, z3, t2, s, ctx); /* 19 */
222 mont_sub(z3, z3, t0, s, ctx);
223 mont_add(t3, z3, z3, s, ctx);
224
225 mont_add(z3, z3, t3, s, ctx); /* 22 */
226 mont_add(t3, t0, t0, s, ctx);
227 mont_add(t0, t3, t0, s, ctx);
228
229 mont_sub(t0, t0, t2, s, ctx); /* 25 */
230 mont_mult(t0, t0, z3, s, ctx);
231 mont_add(y3, y3, t0, s, ctx);
232
233 mont_mult(t0, y, z, s, ctx); /* 28 */
234 mont_add(t0, t0, t0, s, ctx);
235 mont_mult(z3, t0, z3, s, ctx);
236
237 mont_sub(x3, x3, z3, s, ctx); /* 31 */
238 mont_mult(z3, t0, t1, s, ctx);
239 mont_add(z3, z3, z3, s, ctx);
240
241 mont_add(z3, z3, z3, s, ctx); /* 34 */
242 }
243
244 /*
245 * Add two EC points on a short Weierstrass curve of equation y²=x³-3x+b.
246 *
247 * @param x3 Projective X coordinate of the output point, in Montgomery form
248 * @param y3 Projective Y coordinate of the output point, in Montgomery form
249 * @param z3 Projective Z coordinate of the output point, in Montgomery form
250 * @param x1 Projective X coordinate of the first input point, in Montgomery form
251 * @param y1 Projective Y coordinate of the first input point, in Montgomery form
252 * @param z1 Projective Z coordinate of the first input point, in Montgomery form
253 * @param x2 Affine X coordinate of the second input point, in Montgomery form
254 * @param y2 Affine Y coordinate of the second input point, in Montgomery form
255 * @param b Parameter b in the equation, in Montgomery form
256 * @param tmp Workplace for temporary variables
257 * @param ctx The Montgomery context
258 *
259 * Input and output points can match. The correct is produced if both or either
260 * input points are at infinity.
261 *
262 * @warning The function is regular (constant-time) only if the second point (affine)
263 * is NOT the point-at-infinity.
264 */
ec_mix_add(uint64_t * x3,uint64_t * y3,uint64_t * z3,const uint64_t * x13,const uint64_t * y13,const uint64_t * z13,const uint64_t * x2,const uint64_t * y2,const uint64_t * b,Workplace * tmp,const MontContext * ctx)265 STATIC void ec_mix_add(uint64_t *x3, uint64_t *y3, uint64_t *z3,
266 const uint64_t *x13, const uint64_t *y13, const uint64_t *z13,
267 const uint64_t *x2, const uint64_t *y2,
268 const uint64_t *b,
269 Workplace *tmp,
270 const MontContext *ctx)
271 {
272 uint64_t *t0 = tmp->a;
273 uint64_t *t1 = tmp->b;
274 uint64_t *t2 = tmp->c;
275 uint64_t *t3 = tmp->d;
276 uint64_t *t4 = tmp->e;
277 uint64_t *x1 = tmp->f;
278 uint64_t *y1 = tmp->g;
279 uint64_t *z1 = tmp->h;
280 uint64_t *s = tmp->scratch;
281
282 /*
283 * Algorithm 5 in "Complete addition formulas for prime order elliptic curves", Renes et al.
284 */
285
286 if (mont_is_zero(x2, ctx) & mont_is_zero(y2, ctx)) {
287 mont_copy(x3, x13, ctx);
288 mont_copy(y3, y13, ctx);
289 mont_copy(z3, z13, ctx);
290 return;
291 }
292
293 memcpy(x1, x13, ctx->bytes);
294 memcpy(y1, y13, ctx->bytes);
295 memcpy(z1, z13, ctx->bytes);
296
297 mont_mult(t0, x1, x2, s, ctx); /* 1 */
298 mont_mult(t1, y1, y2, s, ctx);
299 mont_add(t3, x2, y2, s, ctx);
300
301 mont_add(t4, x1, y1, s, ctx); /* 4 */
302 mont_mult(t3, t3, t4, s, ctx);
303 mont_add(t4, t0, t1, s, ctx);
304
305 mont_sub(t3, t3, t4, s, ctx); /* 7 */
306 mont_mult(t4, y2, z1, s, ctx);
307 mont_add(t4, t4, y1, s, ctx);
308
309 mont_mult(y3, x2, z1, s, ctx); /* 10 */
310 mont_add(y3, y3, x1, s, ctx);
311 mont_mult(z3, b, z1, s, ctx);
312
313 mont_sub(x3, y3, z3, s, ctx); /* 13 */
314 mont_add(z3, x3, x3, s, ctx);
315 mont_add(x3, x3, z3, s, ctx);
316
317 mont_sub(z3, t1, x3, s, ctx); /* 16 */
318 mont_add(x3, t1, x3, s, ctx);
319 mont_mult(y3, b, y3, s, ctx);
320
321 mont_add(t1, z1, z1, s, ctx); /* 19 */
322 mont_add(t2, t1, z1, s, ctx);
323 mont_sub(y3, y3, t2, s, ctx);
324
325 mont_sub(y3, y3, t0, s, ctx); /* 22 */
326 mont_add(t1, y3, y3, s, ctx);
327 mont_add(y3, t1, y3, s, ctx);
328
329 mont_add(t1, t0, t0, s, ctx); /* 25 */
330 mont_add(t0, t1, t0, s, ctx);
331 mont_sub(t0, t0, t2, s, ctx);
332
333 mont_mult(t1, t4, y3, s, ctx); /* 28 */
334 mont_mult(t2, t0, y3, s, ctx);
335 mont_mult(y3, x3, z3, s, ctx);
336
337 mont_add(y3, y3, t2, s, ctx); /* 31 */
338 mont_mult(x3, t3, x3, s, ctx);
339 mont_sub(x3, x3, t1, s, ctx);
340
341 mont_mult(z3, t4, z3, s, ctx); /* 34 */
342 mont_mult(t1, t3, t0, s, ctx);
343 mont_add(z3, z3, t1, s, ctx);
344 }
345
346 /*
347 * Add two EC points on a short Weierstrass curve of equation y²=x³-3x+b.
348 *
349 * @param x3 Projective X coordinate of the output point, in Montgomery form
350 * @param y3 Projective Y coordinate of the output point, in Montgomery form
351 * @param z3 Projective Z coordinate of the output point, in Montgomery form
352 * @param x1 Projective X coordinate of the first input point, in Montgomery form
353 * @param y1 Projective Y coordinate of the first input point, in Montgomery form
354 * @param z1 Projective Z coordinate of the first input point, in Montgomery form
355 * @param x2 Projective X coordinate of the second input point, in Montgomery form
356 * @param y2 Projective Y coordinate of the second input point, in Montgomery form
357 * @param z2 Projective Z coordinate of the second input point, in Montgomery form
358 * @param b Parameter b in the equation, in Montgomery form
359 * @param tmp Workplace for temporary variables
360 * @param ctx The Montgomery context
361 */
ec_full_add(uint64_t * x3,uint64_t * y3,uint64_t * z3,const uint64_t * x13,const uint64_t * y13,const uint64_t * z13,const uint64_t * x12,const uint64_t * y12,const uint64_t * z12,const uint64_t * b,Workplace * tmp,const MontContext * ctx)362 STATIC void ec_full_add(uint64_t *x3, uint64_t *y3, uint64_t *z3,
363 const uint64_t *x13, const uint64_t *y13, const uint64_t *z13,
364 const uint64_t *x12, const uint64_t *y12, const uint64_t *z12,
365 const uint64_t *b,
366 Workplace *tmp,
367 const MontContext *ctx)
368 {
369 uint64_t *t0 = tmp->a;
370 uint64_t *t1 = tmp->b;
371 uint64_t *t2 = tmp->c;
372 uint64_t *t3 = tmp->d;
373 uint64_t *t4 = tmp->e;
374 uint64_t *x1 = tmp->f;
375 uint64_t *y1 = tmp->g;
376 uint64_t *z1 = tmp->h;
377 uint64_t *x2 = tmp->i;
378 uint64_t *y2 = tmp->j;
379 uint64_t *z2 = tmp->k;
380 uint64_t *s = tmp->scratch;
381
382 /*
383 * Algorithm 4 in "Complete addition formulas for prime order elliptic curves", Renes et al.
384 */
385
386 memcpy(x1, x13, ctx->bytes);
387 memcpy(y1, y13, ctx->bytes);
388 memcpy(z1, z13, ctx->bytes);
389
390 memcpy(x2, x12, ctx->bytes);
391 memcpy(y2, y12, ctx->bytes);
392 memcpy(z2, z12, ctx->bytes);
393
394 mont_mult(t0, x1, x2, s, ctx); /* 1 */
395 mont_mult(t1, y1, y2, s, ctx);
396 mont_mult(t2, z1, z2, s, ctx);
397
398 mont_add(t3, x1, y1, s, ctx); /* 4 */
399 mont_add(t4, x2, y2, s, ctx);
400 mont_mult(t3, t3, t4, s, ctx);
401
402 mont_add(t4, t0, t1, s, ctx); /* 7 */
403 mont_sub(t3, t3, t4, s, ctx);
404 mont_add(t4, y1, z1, s, ctx);
405
406 mont_add(x3, y2, z2, s, ctx); /* 10 */
407 mont_mult(t4, t4, x3, s, ctx);
408 mont_add(x3, t1, t2, s, ctx);
409
410 mont_sub(t4, t4, x3, s, ctx); /* 13 */
411 mont_add(x3, x1, z1, s, ctx);
412 mont_add(y3, x2, z2, s, ctx);
413
414 mont_mult(x3, x3, y3, s, ctx); /* 16 */
415 mont_add(y3, t0, t2, s, ctx);
416 mont_sub(y3, x3, y3, s, ctx);
417
418 mont_mult(z3, b, t2, s, ctx); /* 19 */
419 mont_sub(x3, y3, z3, s, ctx);
420 mont_add(z3, x3, x3, s, ctx);
421
422 mont_add(x3, x3, z3, s, ctx); /* 22 */
423 mont_sub(z3, t1, x3, s, ctx);
424 mont_add(x3, t1, x3, s, ctx);
425
426 mont_mult(y3, b, y3, s, ctx); /* 25 */
427 mont_add(t1, t2, t2, s, ctx);
428 mont_add(t2, t1, t2, s, ctx);
429
430 mont_sub(y3, y3, t2, s, ctx); /* 28 */
431 mont_sub(y3, y3, t0, s, ctx);
432 mont_add(t1, y3, y3, s, ctx);
433
434 mont_add(y3, t1, y3, s, ctx); /* 31 */
435 mont_add(t1, t0, t0, s, ctx);
436 mont_add(t0, t1, t0, s, ctx);
437
438 mont_sub(t0, t0, t2, s, ctx); /* 34 */
439 mont_mult(t1, t4, y3, s, ctx);
440 mont_mult(t2, t0, y3, s, ctx);
441
442 mont_mult(y3, x3, z3, s, ctx); /* 37 */
443 mont_add(y3, y3, t2, s, ctx);
444 mont_mult(x3, t3, x3, s, ctx);
445
446 mont_sub(x3, x3, t1, s, ctx); /* 40 */
447 mont_mult(z3, t4, z3, s, ctx);
448 mont_mult(t1, t3, t0, s, ctx);
449
450 mont_add(z3, z3, t1, s, ctx); /* 43 */
451 }
452
453 #define WINDOW_SIZE_BITS 4
454 #define WINDOW_SIZE_ITEMS (1<<WINDOW_SIZE_BITS)
455
456 /*
457 * Compute the scalar multiplication of an EC point.
458 * Projective coordinates as output and input.
459 */
ec_scalar(uint64_t * x3,uint64_t * y3,uint64_t * z3,const uint64_t * x1,const uint64_t * y1,const uint64_t * z1,const uint64_t * b,const uint8_t * exp,size_t exp_size,uint64_t seed,Workplace * wp1,Workplace * wp2,const MontContext * ctx)460 STATIC int ec_scalar(uint64_t *x3, uint64_t *y3, uint64_t *z3,
461 const uint64_t *x1, const uint64_t *y1, const uint64_t *z1,
462 const uint64_t *b,
463 const uint8_t *exp, size_t exp_size,
464 uint64_t seed,
465 Workplace *wp1,
466 Workplace *wp2,
467 const MontContext *ctx)
468 {
469 unsigned z1_is_one;
470 unsigned i;
471 int res;
472 uint64_t *window_x[WINDOW_SIZE_ITEMS],
473 *window_y[WINDOW_SIZE_ITEMS],
474 *window_z[WINDOW_SIZE_ITEMS];
475 uint64_t *xw=NULL, *yw=NULL, *zw=NULL;
476 ProtMemory *prot_x=NULL, *prot_y=NULL, *prot_z=NULL;
477
478 struct BitWindow_LR bw;
479
480 z1_is_one = (unsigned)mont_is_one(z1, ctx);
481 res = ERR_MEMORY;
482
483 #define alloc(n) n=calloc(ctx->words, 8); if (NULL == n) goto cleanup;
484
485 alloc(xw);
486 alloc(yw);
487 alloc(zw);
488
489 /** Create window O, P, P² .. P¹⁵ **/
490 memset(window_x, 0, sizeof window_x);
491 memset(window_y, 0, sizeof window_y);
492 memset(window_z, 0, sizeof window_z);
493
494 for (i=0; i<WINDOW_SIZE_ITEMS; i++) {
495 alloc(window_x[i]);
496 alloc(window_y[i]);
497 alloc(window_z[i]);
498 }
499
500 #undef alloc
501
502 mont_set(window_x[0], 0, ctx);
503 mont_set(window_y[0], 1, ctx);
504 mont_set(window_z[0], 0, ctx);
505
506 mont_copy(window_x[1], x1, ctx);
507 mont_copy(window_y[1], y1, ctx);
508 mont_copy(window_z[1], z1, ctx);
509
510 for (i=2; i<WINDOW_SIZE_ITEMS; i++) {
511 if (z1_is_one)
512 ec_mix_add(window_x[i], window_y[i], window_z[i],
513 window_x[i-1], window_y[i-1], window_z[i-1],
514 x1, y1,
515 b,
516 wp1, ctx);
517 else
518 ec_full_add(window_x[i], window_y[i], window_z[i],
519 window_x[i-1], window_y[i-1], window_z[i-1],
520 x1, y1, z1,
521 b,
522 wp1, ctx);
523 }
524
525 res = scatter(&prot_x, (const void**)window_x, WINDOW_SIZE_ITEMS, mont_bytes(ctx), seed);
526 if (res) goto cleanup;
527 res = scatter(&prot_y, (const void**)window_y, WINDOW_SIZE_ITEMS, mont_bytes(ctx), seed);
528 if (res) goto cleanup;
529 res = scatter(&prot_z, (const void**)window_z, WINDOW_SIZE_ITEMS, mont_bytes(ctx), seed);
530 if (res) goto cleanup;
531
532 /** Start from PAI **/
533 mont_set(x3, 0, ctx);
534 mont_set(y3, 1, ctx);
535 mont_set(z3, 0, ctx);
536
537 /** Find first non-zero byte in exponent **/
538 for (; exp_size && *exp==0; exp++, exp_size--);
539 bw = init_bit_window_lr(WINDOW_SIZE_BITS, exp, exp_size);
540
541 /** For every nibble, double 16 times and add window value **/
542 for (i=0; i < bw.nr_windows; i++) {
543 unsigned index;
544 int j;
545
546 index = get_next_digit_lr(&bw);
547 gather(xw, prot_x, index);
548 gather(yw, prot_y, index);
549 gather(zw, prot_z, index);
550 for (j=0; j<WINDOW_SIZE_BITS; j++)
551 ec_full_double(x3, y3, z3, x3, y3, z3, b, wp1, ctx);
552 ec_full_add(x3, y3, z3, x3, y3, z3, xw, yw, zw, b, wp1, ctx);
553 }
554
555 res = 0;
556
557 cleanup:
558 free(xw);
559 free(yw);
560 free(zw);
561 for (i=0; i<WINDOW_SIZE_ITEMS; i++) {
562 free(window_x[i]);
563 free(window_y[i]);
564 free(window_z[i]);
565 }
566 free_scattered(prot_x);
567 free_scattered(prot_y);
568 free_scattered(prot_z);
569
570 return res;
571 }
572
free_g_p256(ProtMemory ** prot_g)573 STATIC void free_g_p256(ProtMemory **prot_g)
574 {
575 unsigned i;
576
577 if (prot_g) {
578 for (i=0; i<p256_n_tables; i++)
579 free_scattered(prot_g[i]);
580 free(prot_g);
581 }
582 }
583
free_g_p384(ProtMemory ** prot_g)584 STATIC void free_g_p384(ProtMemory **prot_g)
585 {
586 unsigned i;
587
588 if (prot_g) {
589 for (i=0; i<p384_n_tables; i++)
590 free_scattered(prot_g[i]);
591 free(prot_g);
592 }
593 }
594
free_g_p521(ProtMemory ** prot_g)595 STATIC void free_g_p521(ProtMemory **prot_g)
596 {
597 unsigned i;
598
599 if (prot_g) {
600 for (i=0; i<p521_n_tables; i++)
601 free_scattered(prot_g[i]);
602 free(prot_g);
603 }
604 }
605
606 /*
607 * Fill the pre-computed table for the generator point in the P-256 EC context.
608 */
ec_scramble_g_p256(const MontContext * ctx,uint64_t seed)609 STATIC ProtMemory** ec_scramble_g_p256(const MontContext *ctx, uint64_t seed)
610 {
611 const void **tables_ptrs;
612 ProtMemory **prot_g;
613 unsigned i;
614 int res;
615
616 tables_ptrs = (const void**)calloc(p256_points_per_table, sizeof(void*));
617 if (NULL == tables_ptrs)
618 return NULL;
619
620 prot_g = (ProtMemory**)calloc(p256_n_tables, sizeof(ProtMemory*));
621 if (NULL == prot_g) {
622 free((void*)tables_ptrs);
623 return NULL;
624 }
625
626 res = 0;
627 for (i=0; res==0 && i<p256_n_tables; i++) {
628 unsigned j;
629
630 for (j=0; j<p256_points_per_table; j++) {
631 tables_ptrs[j] = &p256_tables[i][j];
632 }
633 res = scatter(&prot_g[i], tables_ptrs, (uint8_t)p256_points_per_table, 2*mont_bytes(ctx), seed);
634 }
635
636 if (res) {
637 free_g_p256(prot_g);
638 prot_g = NULL;
639 }
640
641 free((void*)tables_ptrs);
642 return prot_g;
643 }
644
645 /*
646 * Fill the pre-computed table for the generator point in the P-384 EC context.
647 */
ec_scramble_g_p384(const MontContext * ctx,uint64_t seed)648 STATIC ProtMemory** ec_scramble_g_p384(const MontContext *ctx, uint64_t seed)
649 {
650 const void **tables_ptrs;
651 ProtMemory **prot_g;
652 unsigned i;
653 int res;
654
655 tables_ptrs = (const void**)calloc(p384_points_per_table, sizeof(void*));
656 if (NULL == tables_ptrs)
657 return NULL;
658
659 prot_g = (ProtMemory**)calloc(p384_n_tables, sizeof(ProtMemory*));
660 if (NULL == prot_g) {
661 free((void*)tables_ptrs);
662 return NULL;
663 }
664
665 res = 0;
666 for (i=0; res==0 && i<p384_n_tables; i++) {
667 unsigned j;
668
669 for (j=0; j<p384_points_per_table; j++) {
670 tables_ptrs[j] = &p384_tables[i][j];
671 }
672 res = scatter(&prot_g[i], tables_ptrs, (uint8_t)p384_points_per_table, 2*mont_bytes(ctx), seed);
673 }
674
675 if (res) {
676 free_g_p384(prot_g);
677 prot_g = NULL;
678 }
679
680 free((void*)tables_ptrs);
681 return prot_g;
682 }
683
684 /*
685 * Fill the pre-computed table for the generator point in the P-521 EC context.
686 */
ec_scramble_g_p521(const MontContext * ctx,uint64_t seed)687 STATIC ProtMemory** ec_scramble_g_p521(const MontContext *ctx, uint64_t seed)
688 {
689 const void **tables_ptrs;
690 ProtMemory **prot_g;
691 unsigned i;
692 int res;
693
694 tables_ptrs = (const void**)calloc(p521_points_per_table, sizeof(void*));
695 if (NULL == tables_ptrs)
696 return NULL;
697
698 prot_g = (ProtMemory**)calloc(p521_n_tables, sizeof(ProtMemory*));
699 if (NULL == prot_g) {
700 free((void*)tables_ptrs);
701 return NULL;
702 }
703
704 res = 0;
705 for (i=0; res==0 && i<p521_n_tables; i++) {
706 unsigned j;
707
708 for (j=0; j<p521_points_per_table; j++) {
709 tables_ptrs[j] = &p521_tables[i][j];
710 }
711 res = scatter(&prot_g[i], tables_ptrs, (uint8_t)p521_points_per_table, 2*mont_bytes(ctx), seed);
712 }
713
714 if (res) {
715 free_g_p521(prot_g);
716 prot_g = NULL;
717 }
718
719 free((void*)tables_ptrs);
720 return prot_g;
721 }
722
ec_scalar_g_p256(uint64_t * x3,uint64_t * y3,uint64_t * z3,const uint64_t * b,const uint8_t * exp,size_t exp_size,uint64_t seed,Workplace * wp1,Workplace * wp2,ProtMemory ** prot_g,const MontContext * ctx)723 STATIC int ec_scalar_g_p256(uint64_t *x3, uint64_t *y3, uint64_t *z3,
724 const uint64_t *b,
725 const uint8_t *exp, size_t exp_size,
726 uint64_t seed,
727 Workplace *wp1,
728 Workplace *wp2,
729 ProtMemory **prot_g,
730 const MontContext *ctx)
731 {
732 unsigned i;
733 struct BitWindow_RL bw;
734
735 /** Start from PAI **/
736 mont_set(x3, 0, ctx);
737 mont_set(y3, 1, ctx);
738 mont_set(z3, 0, ctx);
739
740 /** Find first non-zero byte in exponent **/
741 for (; exp_size && *exp==0; exp++, exp_size--);
742 bw = init_bit_window_rl(p256_window_size, exp, exp_size);
743
744 if (bw.nr_windows > p256_n_tables)
745 return ERR_VALUE;
746
747 for (i=0; i < bw.nr_windows; i++) {
748 unsigned index;
749 uint64_t buffer[4*2]; /* X and Y affine coordinates **/
750 uint64_t *xw, *yw;
751
752 index = get_next_digit_rl(&bw);
753 gather(buffer, prot_g[i], index);
754 xw = &buffer[0];
755 yw = &buffer[4];
756 ec_mix_add(x3, y3, z3,
757 x3, y3, z3,
758 xw, yw,
759 b,
760 wp1, ctx);
761 }
762
763 return 0;
764 }
765
ec_scalar_g_p384(uint64_t * x3,uint64_t * y3,uint64_t * z3,const uint64_t * b,const uint8_t * exp,size_t exp_size,uint64_t seed,Workplace * wp1,Workplace * wp2,ProtMemory ** prot_g,const MontContext * ctx)766 STATIC int ec_scalar_g_p384(uint64_t *x3, uint64_t *y3, uint64_t *z3,
767 const uint64_t *b,
768 const uint8_t *exp, size_t exp_size,
769 uint64_t seed,
770 Workplace *wp1,
771 Workplace *wp2,
772 ProtMemory **prot_g,
773 const MontContext *ctx)
774 {
775 unsigned i;
776 struct BitWindow_RL bw;
777
778 /** Start from PAI **/
779 mont_set(x3, 0, ctx);
780 mont_set(y3, 1, ctx);
781 mont_set(z3, 0, ctx);
782
783 /** Find first non-zero byte in exponent **/
784 for (; exp_size && *exp==0; exp++, exp_size--);
785 bw = init_bit_window_rl(p384_window_size, exp, exp_size);
786
787 if (bw.nr_windows > p384_n_tables)
788 return ERR_VALUE;
789
790 for (i=0; i < bw.nr_windows; i++) {
791 unsigned index;
792 uint64_t buffer[6*2]; /* X and Y affine coordinates **/
793 uint64_t *xw, *yw;
794
795 index = get_next_digit_rl(&bw);
796 gather(buffer, prot_g[i], index);
797 xw = &buffer[0];
798 yw = &buffer[6];
799
800 ec_mix_add(x3, y3, z3,
801 x3, y3, z3,
802 xw, yw,
803 b,
804 wp1, ctx);
805 }
806
807 return 0;
808 }
809
ec_scalar_g_p521(uint64_t * x3,uint64_t * y3,uint64_t * z3,const uint64_t * b,const uint8_t * exp,size_t exp_size,uint64_t seed,Workplace * wp1,Workplace * wp2,ProtMemory ** prot_g,const MontContext * ctx)810 STATIC int ec_scalar_g_p521(uint64_t *x3, uint64_t *y3, uint64_t *z3,
811 const uint64_t *b,
812 const uint8_t *exp, size_t exp_size,
813 uint64_t seed,
814 Workplace *wp1,
815 Workplace *wp2,
816 ProtMemory **prot_g,
817 const MontContext *ctx)
818 {
819 unsigned i;
820 struct BitWindow_RL bw;
821
822 /** Start from PAI **/
823 mont_set(x3, 0, ctx);
824 mont_set(y3, 1, ctx);
825 mont_set(z3, 0, ctx);
826
827 /** Find first non-zero byte in exponent **/
828 for (; exp_size && *exp==0; exp++, exp_size--);
829 bw = init_bit_window_rl(p521_window_size, exp, exp_size);
830
831 if (exp_size == 66) {
832 if (exp[0] >> 1) {
833 return ERR_VALUE;
834 }
835 switch (p521_window_size) {
836 case 1: bw.nr_windows -= 7; break;
837 case 2: bw.nr_windows -= 3; break;
838 case 3: bw.nr_windows -= 2; break;
839 case 4:
840 case 5:
841 case 6:
842 case 7: bw.nr_windows -= 1; break;
843 }
844 }
845
846 if (exp_size > 66)
847 return ERR_VALUE;
848
849 if (bw.nr_windows > p521_n_tables)
850 return ERR_VALUE;
851
852 for (i=0; i < bw.nr_windows; i++) {
853 unsigned index;
854 uint64_t buffer[9*2]; /* X and Y affine coordinates **/
855 uint64_t *xw, *yw;
856
857 index = get_next_digit_rl(&bw);
858 gather(buffer, prot_g[i], index);
859 xw = &buffer[0];
860 yw = &buffer[9];
861
862 ec_mix_add(x3, y3, z3,
863 x3, y3, z3,
864 xw, yw,
865 b,
866 wp1, ctx);
867 }
868
869 return 0;
870 }
871
872 /*
873 * Create an Elliptic Curve context for Weierstress curves y²=x³+ax+b with a=-3
874 *
875 * @param pec_ctx The memory area where the pointer to the newly allocated
876 * EC context will be stored.
877 * @param modulus The prime modulus for the curve, big-endian encoded
878 * @param b The constant b, big-endian encoded
879 * @param order The order of the EC curve
880 * @param len The length in bytes of modulus, b, and order
881 * @return 0 for success, the appopriate error code otherwise
882 */
ec_ws_new_context(EcContext ** pec_ctx,const uint8_t * modulus,const uint8_t * b,const uint8_t * order,size_t len,uint64_t seed)883 EXPORT_SYM int ec_ws_new_context(EcContext **pec_ctx,
884 const uint8_t *modulus,
885 const uint8_t *b,
886 const uint8_t *order,
887 size_t len,
888 uint64_t seed)
889 {
890 EcContext *ec_ctx = NULL;
891 unsigned order_words;
892 int res;
893 MontContext *ctx;
894
895 if (NULL == pec_ctx || NULL == modulus || NULL == b)
896 return ERR_NULL;
897
898 *pec_ctx = NULL;
899
900 if (len == 0)
901 return ERR_NOT_ENOUGH_DATA;
902
903 *pec_ctx = ec_ctx = (EcContext*)calloc(1, sizeof(EcContext));
904 if (NULL == ec_ctx)
905 return ERR_MEMORY;
906
907 res = mont_context_init(&ec_ctx->mont_ctx, modulus, len);
908 if (res) goto cleanup;
909 ctx = ec_ctx->mont_ctx;
910
911 res = mont_from_bytes(&ec_ctx->b, b, len, ctx);
912 if (res) goto cleanup;
913
914 order_words = ((unsigned)len+7)/8;
915 ec_ctx->order = (uint64_t*)calloc(order_words, sizeof(uint64_t));
916 if (NULL == ec_ctx->order) {
917 res = ERR_MEMORY;
918 goto cleanup;
919 }
920 bytes_to_words(ec_ctx->order, order_words, order, len);
921
922 /* Scramble lookup table for special generators */
923 switch (ctx->modulus_type) {
924 case ModulusP256: {
925 ec_ctx->prot_g = ec_scramble_g_p256(ec_ctx->mont_ctx, seed);
926 if (NULL == ec_ctx->prot_g) {
927 res = ERR_MEMORY;
928 goto cleanup;
929 }
930 break;
931 }
932 case ModulusP384: {
933 ec_ctx->prot_g = ec_scramble_g_p384(ec_ctx->mont_ctx, seed);
934 if (NULL == ec_ctx->prot_g) {
935 res = ERR_MEMORY;
936 goto cleanup;
937 }
938 break;
939 }
940 case ModulusP521: {
941 ec_ctx->prot_g = ec_scramble_g_p521(ec_ctx->mont_ctx, seed);
942 if (NULL == ec_ctx->prot_g) {
943 res = ERR_MEMORY;
944 goto cleanup;
945 }
946 break;
947 }
948 case ModulusGeneric:
949 break;
950 }
951
952 return 0;
953
954 cleanup:
955 free(ec_ctx->b);
956 free(ec_ctx->order);
957 mont_context_free(ec_ctx->mont_ctx);
958 free(ec_ctx);
959 return res;
960 }
961
ec_free_context(EcContext * ec_ctx)962 EXPORT_SYM void ec_free_context(EcContext *ec_ctx)
963 {
964 if (NULL == ec_ctx)
965 return;
966 switch (ec_ctx->mont_ctx->modulus_type) {
967 case ModulusP256:
968 free_g_p256(ec_ctx->prot_g);
969 break;
970 case ModulusP384:
971 free_g_p384(ec_ctx->prot_g);
972 break;
973 case ModulusP521:
974 free_g_p521(ec_ctx->prot_g);
975 break;
976 case ModulusGeneric:
977 break;
978 }
979 free(ec_ctx->b);
980 free(ec_ctx->order);
981 mont_context_free(ec_ctx->mont_ctx);
982 free(ec_ctx);
983 }
984
985 /*
986 * Create a new EC point on the given EC curve.
987 *
988 * @param pecp The memory area where the pointer to the newly allocated EC
989 * point will be stored. Use ec_free_point() for deallocating it.
990 * @param x The X-coordinate (affine, big-endian)
991 * @param y The Y-coordinate (affine, big-endian)
992 * @param len The length of x and y in bytes
993 * @param ec_ctx The EC context
994 * @return 0 for success, the appopriate error code otherwise
995 */
ec_ws_new_point(EcPoint ** pecp,const uint8_t * x,const uint8_t * y,size_t len,const EcContext * ec_ctx)996 EXPORT_SYM int ec_ws_new_point(EcPoint **pecp,
997 const uint8_t *x,
998 const uint8_t *y,
999 size_t len,
1000 const EcContext *ec_ctx)
1001 {
1002 int res;
1003 Workplace *wp = NULL;
1004 EcPoint *ecp;
1005 MontContext *ctx;
1006
1007 if (NULL == pecp || NULL == x || NULL == y || NULL == ec_ctx)
1008 return ERR_NULL;
1009 ctx = ec_ctx->mont_ctx;
1010
1011 if (len == 0)
1012 return ERR_NOT_ENOUGH_DATA;
1013
1014 if (len > ctx->bytes)
1015 return ERR_VALUE;
1016
1017 *pecp = ecp = (EcPoint*)calloc(1, sizeof(EcPoint));
1018 if (NULL == ecp)
1019 return ERR_MEMORY;
1020
1021 ecp->ec_ctx = ec_ctx;
1022
1023 res = mont_from_bytes(&ecp->x, x, len, ctx);
1024 if (res) goto cleanup;
1025 res = mont_from_bytes(&ecp->y, y, len, ctx);
1026 if (res) goto cleanup;
1027 res = mont_number(&ecp->z, 1, ctx);
1028 if (res) goto cleanup;
1029 mont_set(ecp->z, 1, ctx);
1030
1031 /** Convert PAI: (0, 0) to (0, 1, 0) */
1032 /** Verify the point is on the curve, if not point-at-infinity */
1033 if (mont_is_zero(ecp->x, ctx) && mont_is_zero(ecp->y, ctx)) {
1034 mont_set(ecp->x, 0, ctx);
1035 mont_set(ecp->y, 1, ctx);
1036 mont_set(ecp->z, 0, ctx);
1037 } else {
1038 wp = new_workplace(ctx);
1039 mont_mult(wp->a, ecp->y, ecp->y, wp->scratch, ctx);
1040 mont_mult(wp->c, ecp->x, ecp->x, wp->scratch, ctx);
1041 mont_mult(wp->c, wp->c, ecp->x, wp->scratch, ctx);
1042 mont_sub(wp->c, wp->c, ecp->x, wp->scratch, ctx);
1043 mont_sub(wp->c, wp->c, ecp->x, wp->scratch, ctx);
1044 mont_sub(wp->c, wp->c, ecp->x, wp->scratch, ctx);
1045 mont_add(wp->c, wp->c, ec_ctx->b, wp->scratch, ctx);
1046 res = !mont_is_equal(wp->a, wp->c, ctx);
1047 free_workplace(wp);
1048
1049 if (res) {
1050 res = ERR_EC_POINT;
1051 goto cleanup;
1052 }
1053 }
1054 return 0;
1055
1056 cleanup:
1057 free(ecp->x);
1058 free(ecp->y);
1059 free(ecp->z);
1060 free(ecp);
1061 *pecp = NULL;
1062 return res;
1063 }
1064
ec_free_point(EcPoint * ecp)1065 EXPORT_SYM void ec_free_point(EcPoint *ecp)
1066 {
1067 if (NULL == ecp)
1068 return;
1069
1070 /* It is not up to us to deallocate the EC context */
1071 free(ecp->x);
1072 free(ecp->y);
1073 free(ecp->z);
1074 free(ecp);
1075 }
1076
1077 /*
1078 * Encode the affine coordinates of an EC point.
1079 *
1080 * @param x The location where the affine X-coordinate will be store in big-endian mode
1081 * @param y The location where the affine Y-coordinate will be store in big-endian mode
1082 * @param len The memory available for x and y in bytes.
1083 * It must be as long as the prime modulus of the curve field.
1084 * @param ecp The EC point to encode.
1085 */
ec_ws_get_xy(uint8_t * x,uint8_t * y,size_t len,const EcPoint * ecp)1086 EXPORT_SYM int ec_ws_get_xy(uint8_t *x, uint8_t *y, size_t len, const EcPoint *ecp)
1087 {
1088 uint64_t *xw=NULL, *yw=NULL;
1089 Workplace *wp;
1090 MontContext *ctx;
1091 int res;
1092
1093 if (NULL == x || NULL == y || NULL == ecp)
1094 return ERR_NULL;
1095 ctx = ecp->ec_ctx->mont_ctx;
1096
1097 if (len < ctx->modulus_len)
1098 return ERR_NOT_ENOUGH_DATA;
1099
1100 wp = new_workplace(ctx);
1101 if (NULL == wp)
1102 return ERR_MEMORY;
1103
1104 res = mont_number(&xw, 1, ctx);
1105 if (res) goto cleanup;
1106 res = mont_number(&yw, 1, ctx);
1107 if (res) goto cleanup;
1108
1109 ec_projective_to_affine(xw, yw, ecp->x, ecp->y, ecp->z, wp, ctx);
1110
1111 res = mont_to_bytes(x, len, xw, ctx);
1112 if (res) goto cleanup;
1113 res = mont_to_bytes(y, len, yw, ctx);
1114 if (res) goto cleanup;
1115
1116 res = 0;
1117
1118 cleanup:
1119 free_workplace(wp);
1120 free(xw);
1121 free(yw);
1122 return res;
1123 }
1124
1125 /*
1126 * Double an EC point
1127 */
ec_ws_double(EcPoint * p)1128 EXPORT_SYM int ec_ws_double(EcPoint *p)
1129 {
1130 Workplace *wp;
1131 MontContext *ctx;
1132
1133 if (NULL == p)
1134 return ERR_NULL;
1135 ctx = p->ec_ctx->mont_ctx;
1136
1137 wp = new_workplace(ctx);
1138 if (NULL == wp)
1139 return ERR_MEMORY;
1140
1141 ec_full_double(p->x, p->y, p->z, p->x, p->y, p->z, p->ec_ctx->b, wp, ctx);
1142
1143 free_workplace(wp);
1144 return 0;
1145 }
1146
1147 /*
1148 * Add an EC point to another
1149 */
ec_ws_add(EcPoint * ecpa,EcPoint * ecpb)1150 EXPORT_SYM int ec_ws_add(EcPoint *ecpa, EcPoint *ecpb)
1151 {
1152 Workplace *wp;
1153 MontContext *ctx;
1154
1155 if (NULL == ecpa || NULL == ecpb)
1156 return ERR_NULL;
1157 if (ecpa->ec_ctx != ecpb->ec_ctx)
1158 return ERR_EC_CURVE;
1159 ctx = ecpa->ec_ctx->mont_ctx;
1160
1161 wp = new_workplace(ctx);
1162 if (NULL == wp)
1163 return ERR_MEMORY;
1164
1165 ec_full_add(ecpa->x, ecpa->y, ecpa->z,
1166 ecpa->x, ecpa->y, ecpa->z,
1167 ecpb->x, ecpb->y, ecpb->z,
1168 ecpa->ec_ctx->b,
1169 wp, ctx);
1170
1171 free_workplace(wp);
1172 return 0;
1173 }
1174
1175 /*
1176 * Normalize the projective representation of a point
1177 * so that Z=1 or Z=0.
1178 */
ec_ws_normalize(EcPoint * ecp)1179 EXPORT_SYM int ec_ws_normalize(EcPoint *ecp)
1180 {
1181 MontContext *ctx;
1182 Workplace *wp = NULL;
1183
1184 if (NULL == ecp)
1185 return ERR_NULL;
1186 ctx = ecp->ec_ctx->mont_ctx;
1187
1188 wp = new_workplace(ctx);
1189 if (NULL == wp)
1190 return ERR_MEMORY;
1191
1192 if (!mont_is_zero(ecp->z, ctx)) {
1193 ec_projective_to_affine(ecp->x, ecp->y,
1194 ecp->x, ecp->y, ecp->z,
1195 wp, ctx);
1196 mont_set(ecp->z, 1, ctx);
1197 }
1198
1199 free_workplace(wp);
1200 return 0;
1201 }
1202
ec_ws_is_pai(EcPoint * ecp)1203 EXPORT_SYM int ec_ws_is_pai(EcPoint *ecp)
1204 {
1205 if (NULL == ecp)
1206 return FALSE;
1207
1208 return mont_is_zero(ecp->z, ecp->ec_ctx->mont_ctx);
1209 }
1210
1211 /*
1212 * Blind the scalar factor to be used in an EC multiplication
1213 *
1214 * @param blind_scalar The area of memory where the pointer to a newly
1215 * allocated blind scalar is stored, in big endian mode.
1216 * The caller must deallocate this memory.
1217 * @param blind_scalar_len The area where the length of the blind scalar in bytes will be written to.
1218 * @param scalar The (secret) scalar to blind.
1219 * @param scalar_len The length of the secret scalar in bytes.
1220 * @param R_seed The 32-bit factor to use to blind the scalar.
1221 * @param order The order of the EC curve, big-endian mode, 64 bit words
1222 * @param order_words The number of words making up the order
1223 */
blind_scalar_factor(uint8_t ** blind_scalar,size_t * blind_scalar_len,const uint8_t * scalar,size_t scalar_len,uint32_t R_seed,uint64_t * order,size_t order_words)1224 static int blind_scalar_factor(uint8_t **blind_scalar,
1225 size_t *blind_scalar_len,
1226 const uint8_t *scalar,
1227 size_t scalar_len,
1228 uint32_t R_seed,
1229 uint64_t *order,
1230 size_t order_words)
1231 {
1232 size_t scalar_words;
1233 size_t blind_scalar_words;
1234 uint64_t *output_u64 = NULL;
1235 uint64_t *scratchpad = NULL;
1236 int res = ERR_MEMORY;
1237
1238 scalar_words = (scalar_len+7)/8;
1239 blind_scalar_words = MAX(order_words+2, scalar_words+2);
1240 *blind_scalar_len = blind_scalar_words*sizeof(uint64_t);
1241
1242 *blind_scalar = (uint8_t*)calloc(*blind_scalar_len, 1);
1243 if (NULL == *blind_scalar)
1244 goto cleanup;
1245
1246 output_u64 = (uint64_t*)calloc(blind_scalar_words, sizeof(uint64_t));
1247 if (NULL == output_u64)
1248 goto cleanup;
1249
1250 scratchpad = (uint64_t*)calloc(blind_scalar_words + order_words, sizeof(uint64_t));
1251 if (NULL == scratchpad)
1252 goto cleanup;
1253
1254 bytes_to_words(output_u64, blind_scalar_words, scalar, scalar_len);
1255 addmul128(output_u64, scratchpad, order, R_seed, 0, blind_scalar_words, order_words);
1256 words_to_bytes(*blind_scalar, *blind_scalar_len, output_u64, blind_scalar_words);
1257
1258 res = 0;
1259
1260 cleanup:
1261 free(output_u64);
1262 free(scratchpad);
1263 return res;
1264 }
1265
1266 /*
1267 * Multiply an EC point by a scalar
1268 *
1269 * @param ecp The EC point to multiply
1270 * @param k The scalar, encoded in big endian mode
1271 * @param len The length of the scalar, in bytes
1272 * @param seed The 64-bit to drive the randomizations against SCAs
1273 * @return 0 in case of success, the appropriate error code otherwise
1274 */
ec_ws_scalar(EcPoint * ecp,const uint8_t * k,size_t len,uint64_t seed)1275 EXPORT_SYM int ec_ws_scalar(EcPoint *ecp, const uint8_t *k, size_t len, uint64_t seed)
1276 {
1277 Workplace *wp1=NULL, *wp2=NULL;
1278 MontContext *ctx;
1279 int res;
1280
1281 if (NULL == ecp || NULL == k)
1282 return ERR_NULL;
1283 ctx = ecp->ec_ctx->mont_ctx;
1284
1285 if (len == 0) {
1286 return ERR_NOT_ENOUGH_DATA;
1287 }
1288
1289 wp1 = new_workplace(ctx);
1290 if (NULL == wp1) {
1291 res = ERR_MEMORY;
1292 goto cleanup;
1293 }
1294
1295 wp2 = new_workplace(ctx);
1296 if (NULL == wp2) {
1297 res = ERR_MEMORY;
1298 goto cleanup;
1299 }
1300
1301 switch (ctx->modulus_type) {
1302 case ModulusP256: {
1303 /** Coordinates in Montgomery form **/
1304 const uint64_t mont_Gx[4] = { 0x79E730D418A9143CULL, 0x75BA95FC5FEDB601ULL, 0x79FB732B77622510ULL, 0x18905F76A53755C6ULL };
1305 const uint64_t mont_Gy[4] = { 0xDDF25357CE95560AULL, 0x8B4AB8E4BA19E45CULL, 0xD2E88688DD21F325ULL, 0x8571FF1825885D85ULL };
1306 unsigned is_generator;
1307 unsigned i;
1308
1309 is_generator = 1;
1310 for (i=0; i<4; i++) {
1311 is_generator &= (mont_Gx[i] == ecp->x[i]);
1312 is_generator &= (mont_Gy[i] == ecp->y[i]);
1313 }
1314 is_generator &= (unsigned)mont_is_one(ecp->z, ctx);
1315
1316 if (is_generator) {
1317 res = ec_scalar_g_p256(ecp->x, ecp->y, ecp->z,
1318 ecp->ec_ctx->b,
1319 k, len,
1320 seed + 2,
1321 wp1, wp2,
1322 ecp->ec_ctx->prot_g,
1323 ctx);
1324 goto cleanup;
1325 }
1326 break;
1327 }
1328 case ModulusP384: {
1329 /** Coordinates in Montgomery form **/
1330 const uint64_t mont_Gx[6] = { 0x3DD0756649C0B528ULL, 0x20E378E2A0D6CE38ULL, 0x879C3AFC541B4D6EULL, 0x6454868459A30EFFULL, 0x812FF723614EDE2BULL, 0x4D3AADC2299E1513ULL };
1331 const uint64_t mont_Gy[6] = { 0x23043DAD4B03A4FEULL, 0xA1BFA8BF7BB4A9ACULL, 0x8BADE7562E83B050ULL, 0xC6C3521968F4FFD9ULL, 0xDD8002263969A840ULL, 0x2B78ABC25A15C5E9ULL };
1332 unsigned is_generator;
1333 unsigned i;
1334
1335 is_generator = 1;
1336 for (i=0; i<6; i++) {
1337 is_generator &= (mont_Gx[i] == ecp->x[i]);
1338 is_generator &= (mont_Gy[i] == ecp->y[i]);
1339 }
1340 is_generator &= (unsigned)mont_is_one(ecp->z, ctx);
1341
1342 if (is_generator) {
1343 res = ec_scalar_g_p384(ecp->x, ecp->y, ecp->z,
1344 ecp->ec_ctx->b,
1345 k, len,
1346 seed + 2,
1347 wp1, wp2,
1348 ecp->ec_ctx->prot_g,
1349 ctx);
1350 goto cleanup;
1351 }
1352 break;
1353 }
1354 case ModulusP521: {
1355 /** Coordinates in normal form **/
1356 const uint64_t mont_Gx[9] = { 0xF97E7E31C2E5BD66ULL, 0x3348B3C1856A429BULL, 0xFE1DC127A2FFA8DEULL, 0xA14B5E77EFE75928ULL, 0xF828AF606B4D3DBAULL, 0x9C648139053FB521ULL, 0x9E3ECB662395B442ULL, 0x858E06B70404E9CDULL, 0x00000000000000C6ULL };
1357 const uint64_t mont_Gy[9] = { 0x88BE94769FD16650ULL, 0x353C7086A272C240ULL, 0xC550B9013FAD0761ULL, 0x97EE72995EF42640ULL, 0x17AFBD17273E662CULL, 0x98F54449579B4468ULL, 0x5C8A5FB42C7D1BD9ULL, 0x39296A789A3BC004ULL, 0x0000000000000118ULL };
1358 unsigned is_generator;
1359 unsigned i;
1360
1361 is_generator = 1;
1362 for (i=0; i<9; i++) {
1363 is_generator &= (mont_Gx[i] == ecp->x[i]);
1364 is_generator &= (mont_Gy[i] == ecp->y[i]);
1365 }
1366 is_generator &= (unsigned)mont_is_one(ecp->z, ctx);
1367
1368 if (is_generator) {
1369 res = ec_scalar_g_p521(ecp->x, ecp->y, ecp->z,
1370 ecp->ec_ctx->b,
1371 k, len,
1372 seed + 2,
1373 wp1, wp2,
1374 ecp->ec_ctx->prot_g,
1375 ctx);
1376 goto cleanup;
1377 }
1378 break;
1379 }
1380 case ModulusGeneric:
1381 break;
1382 }
1383
1384 if (seed != 0) {
1385 uint8_t *blind_scalar=NULL;
1386 size_t blind_scalar_len;
1387 uint64_t *factor=NULL;
1388
1389 /* Create the blinding factor for the base point */
1390 res = mont_random_number(&factor, 1, seed, ctx);
1391 if (res)
1392 goto cleanup;
1393
1394 /* Blind the base point */
1395 mont_mult(ecp->x, ecp->x, factor, wp1->scratch, ctx);
1396 mont_mult(ecp->y, ecp->y, factor, wp1->scratch, ctx);
1397 mont_mult(ecp->z, ecp->z, factor, wp1->scratch, ctx);
1398
1399 free(factor);
1400
1401 /* Blind the scalar, by adding R*order where R is at least 32 bits */
1402 res = blind_scalar_factor(&blind_scalar,
1403 &blind_scalar_len,
1404 k, len,
1405 (uint32_t)seed,
1406 ecp->ec_ctx->order,
1407 ctx->words);
1408 if (res) goto cleanup;
1409 res = ec_scalar(ecp->x, ecp->y, ecp->z,
1410 ecp->x, ecp->y, ecp->z,
1411 ecp->ec_ctx->b,
1412 blind_scalar, blind_scalar_len,
1413 seed + 1,
1414 wp1, wp2, ctx);
1415
1416 free(blind_scalar);
1417 if (res) goto cleanup;
1418 } else {
1419 /* No blinding */
1420 res = ec_scalar(ecp->x, ecp->y, ecp->z,
1421 ecp->x, ecp->y, ecp->z,
1422 ecp->ec_ctx->b,
1423 k, len,
1424 seed + 1,
1425 wp1, wp2, ctx);
1426 if (res) goto cleanup;
1427 }
1428
1429 res = 0;
1430
1431 cleanup:
1432 free_workplace(wp1);
1433 free_workplace(wp2);
1434 return res;
1435 }
1436
ec_ws_clone(EcPoint ** pecp2,const EcPoint * ecp)1437 EXPORT_SYM int ec_ws_clone(EcPoint **pecp2, const EcPoint *ecp)
1438 {
1439 int res;
1440 EcPoint *ecp2;
1441 MontContext *ctx;
1442
1443 if (NULL == pecp2 || NULL == ecp)
1444 return ERR_NULL;
1445 ctx = ecp->ec_ctx->mont_ctx;
1446
1447 *pecp2 = ecp2 = (EcPoint*)calloc(1, sizeof(EcPoint));
1448 if (NULL == ecp2)
1449 return ERR_MEMORY;
1450
1451 ecp2->ec_ctx = ecp->ec_ctx;
1452
1453 res = mont_number(&ecp2->x, 1, ctx);
1454 if (res) goto cleanup;
1455 mont_copy(ecp2->x, ecp->x, ctx);
1456
1457 res = mont_number(&ecp2->y, 1, ctx);
1458 if (res) goto cleanup;
1459 mont_copy(ecp2->y, ecp->y, ctx);
1460
1461 res = mont_number(&ecp2->z, 1, ctx);
1462 if (res) goto cleanup;
1463 mont_copy(ecp2->z, ecp->z, ctx);
1464
1465 return 0;
1466
1467 cleanup:
1468 free(ecp2->x);
1469 free(ecp2->y);
1470 free(ecp2->z);
1471 free(ecp2);
1472 *pecp2 = NULL;
1473 return res;
1474 }
1475
ec_ws_copy(EcPoint * ecp1,const EcPoint * ecp2)1476 EXPORT_SYM int ec_ws_copy(EcPoint *ecp1, const EcPoint *ecp2)
1477 {
1478 MontContext *ctx;
1479
1480 if (NULL == ecp1 || NULL == ecp2)
1481 return ERR_NULL;
1482 ctx = ecp2->ec_ctx->mont_ctx;
1483
1484 ecp1->ec_ctx = ecp2->ec_ctx;
1485 mont_copy(ecp1->x, ecp2->x, ctx);
1486 mont_copy(ecp1->y, ecp2->y, ctx);
1487 mont_copy(ecp1->z, ecp2->z, ctx);
1488
1489 return 0;
1490 }
1491
1492 /*
1493 * Compare two EC points and return 0 if they match
1494 */
ec_ws_cmp(const EcPoint * ecp1,const EcPoint * ecp2)1495 EXPORT_SYM int ec_ws_cmp(const EcPoint *ecp1, const EcPoint *ecp2)
1496 {
1497 Workplace *wp;
1498 MontContext *ctx;
1499 int p1_is_pai;
1500 int p2_is_pai;
1501 int result;
1502
1503 if (NULL == ecp1 || NULL == ecp2)
1504 return ERR_NULL;
1505
1506 if (ecp1->ec_ctx != ecp2->ec_ctx)
1507 return ERR_EC_CURVE;
1508 ctx = ecp1->ec_ctx->mont_ctx;
1509
1510 p1_is_pai = mont_is_zero(ecp1->z, ctx);
1511 p2_is_pai = mont_is_zero(ecp2->z, ctx);
1512
1513 /* Check for point-at-infinity */
1514 if (p1_is_pai | p2_is_pai) {
1515 return (p1_is_pai & p2_is_pai) ? 0 : ERR_VALUE;
1516 }
1517
1518 /** Normalize to have the same Z coordinate */
1519 wp = new_workplace(ctx);
1520 if (NULL == wp)
1521 return ERR_MEMORY;
1522
1523 mont_mult(wp->b, ecp1->x, ecp2->z, wp->scratch, ctx); /* B = X1*Z2 */
1524 mont_mult(wp->d, ecp2->x, ecp1->z, wp->scratch, ctx); /* D = X2*Z1 */
1525 mont_mult(wp->e, ecp1->y, ecp2->z, wp->scratch, ctx); /* E = Y1*Z2 */
1526 mont_mult(wp->f, ecp2->y, ecp1->z, wp->scratch, ctx); /* F = Y2*Z1 */
1527 result = (mont_is_equal(wp->b, wp->d, ctx) & mont_is_equal(wp->e, wp->f, ctx)) ? 0 : ERR_VALUE;
1528
1529 free_workplace(wp);
1530
1531 return result;
1532 }
1533
ec_ws_neg(EcPoint * p)1534 EXPORT_SYM int ec_ws_neg(EcPoint *p)
1535 {
1536 MontContext *ctx;
1537 uint64_t *tmp;
1538 int res;
1539
1540 if (NULL == p)
1541 return ERR_NULL;
1542 ctx = p->ec_ctx->mont_ctx;
1543
1544 res = mont_number(&tmp, SCRATCHPAD_NR, ctx);
1545 if (res)
1546 return res;
1547
1548 mont_sub(p->y, ctx->modulus, p->y, tmp, ctx);
1549 free(tmp);
1550 return 0;
1551 }
1552
1553