1/*
2 * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10#include <assert.h>
11#include "internal/cryptlib.h"
12#include "bn_local.h"
13
14#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS)
15/*
16 * Here follows specialised variants of bn_add_words() and bn_sub_words().
17 * They have the property performing operations on arrays of different sizes.
18 * The sizes of those arrays is expressed through cl, which is the common
19 * length ( basically, min(len(a),len(b)) ), and dl, which is the delta
20 * between the two lengths, calculated as len(a)-len(b). All lengths are the
21 * number of BN_ULONGs... For the operations that require a result array as
22 * parameter, it must have the length cl+abs(dl). These functions should
23 * probably end up in bn_asm.c as soon as there are assembler counterparts
24 * for the systems that use assembler files.
25 */
26
27BN_ULONG bn_sub_part_words(BN_ULONG *r,
28 const BN_ULONG *a, const BN_ULONG *b,
29 int cl, int dl)
30{
31 BN_ULONG c, t;
32
33 assert(cl >= 0);
34 c = bn_sub_words(r, a, b, cl);
35
36 if (dl == 0)
37 return c;
38
39 r += cl;
40 a += cl;
41 b += cl;
42
43 if (dl < 0) {
44 for (;;) {
45 t = b[0];
46 r[0] = (0 - t - c) & BN_MASK2;
47 if (t != 0)
48 c = 1;
49 if (++dl >= 0)
50 break;
51
52 t = b[1];
53 r[1] = (0 - t - c) & BN_MASK2;
54 if (t != 0)
55 c = 1;
56 if (++dl >= 0)
57 break;
58
59 t = b[2];
60 r[2] = (0 - t - c) & BN_MASK2;
61 if (t != 0)
62 c = 1;
63 if (++dl >= 0)
64 break;
65
66 t = b[3];
67 r[3] = (0 - t - c) & BN_MASK2;
68 if (t != 0)
69 c = 1;
70 if (++dl >= 0)
71 break;
72
73 b += 4;
74 r += 4;
75 }
76 } else {
77 int save_dl = dl;
78 while (c) {
79 t = a[0];
80 r[0] = (t - c) & BN_MASK2;
81 if (t != 0)
82 c = 0;
83 if (--dl <= 0)
84 break;
85
86 t = a[1];
87 r[1] = (t - c) & BN_MASK2;
88 if (t != 0)
89 c = 0;
90 if (--dl <= 0)
91 break;
92
93 t = a[2];
94 r[2] = (t - c) & BN_MASK2;
95 if (t != 0)
96 c = 0;
97 if (--dl <= 0)
98 break;
99
100 t = a[3];
101 r[3] = (t - c) & BN_MASK2;
102 if (t != 0)
103 c = 0;
104 if (--dl <= 0)
105 break;
106
107 save_dl = dl;
108 a += 4;
109 r += 4;
110 }
111 if (dl > 0) {
112 if (save_dl > dl) {
113 switch (save_dl - dl) {
114 case 1:
115 r[1] = a[1];
116 if (--dl <= 0)
117 break;
118 /* fall thru */
119 case 2:
120 r[2] = a[2];
121 if (--dl <= 0)
122 break;
123 /* fall thru */
124 case 3:
125 r[3] = a[3];
126 if (--dl <= 0)
127 break;
128 }
129 a += 4;
130 r += 4;
131 }
132 }
133 if (dl > 0) {
134 for (;;) {
135 r[0] = a[0];
136 if (--dl <= 0)
137 break;
138 r[1] = a[1];
139 if (--dl <= 0)
140 break;
141 r[2] = a[2];
142 if (--dl <= 0)
143 break;
144 r[3] = a[3];
145 if (--dl <= 0)
146 break;
147
148 a += 4;
149 r += 4;
150 }
151 }
152 }
153 return c;
154}
155#endif
156
157#ifdef BN_RECURSION
158/*
159 * Karatsuba recursive multiplication algorithm (cf. Knuth, The Art of
160 * Computer Programming, Vol. 2)
161 */
162
163/*-
164 * r is 2*n2 words in size,
165 * a and b are both n2 words in size.
166 * n2 must be a power of 2.
167 * We multiply and return the result.
168 * t must be 2*n2 words in size
169 * We calculate
170 * a[0]*b[0]
171 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
172 * a[1]*b[1]
173 */
174/* dnX may not be positive, but n2/2+dnX has to be */
175void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
176 int dna, int dnb, BN_ULONG *t)
177{
178 int n = n2 / 2, c1, c2;
179 int tna = n + dna, tnb = n + dnb;
180 unsigned int neg, zero;
181 BN_ULONG ln, lo, *p;
182
183# ifdef BN_MUL_COMBA
184# if 0
185 if (n2 == 4) {
186 bn_mul_comba4(r, a, b);
187 return;
188 }
189# endif
190 /*
191 * Only call bn_mul_comba 8 if n2 == 8 and the two arrays are complete
192 * [steve]
193 */
194 if (n2 == 8 && dna == 0 && dnb == 0) {
195 bn_mul_comba8(r, a, b);
196 return;
197 }
198# endif /* BN_MUL_COMBA */
199 /* Else do normal multiply */
200 if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
201 bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
202 if ((dna + dnb) < 0)
203 memset(&r[2 * n2 + dna + dnb], 0,
204 sizeof(BN_ULONG) * -(dna + dnb));
205 return;
206 }
207 /* r=(a[0]-a[1])*(b[1]-b[0]) */
208 c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
209 c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
210 zero = neg = 0;
211 switch (c1 * 3 + c2) {
212 case -4:
213 bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
214 bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
215 break;
216 case -3:
217 zero = 1;
218 break;
219 case -2:
220 bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
221 bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
222 neg = 1;
223 break;
224 case -1:
225 case 0:
226 case 1:
227 zero = 1;
228 break;
229 case 2:
230 bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
231 bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
232 neg = 1;
233 break;
234 case 3:
235 zero = 1;
236 break;
237 case 4:
238 bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
239 bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
240 break;
241 }
242
243# ifdef BN_MUL_COMBA
244 if (n == 4 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba4 could take
245 * extra args to do this well */
246 if (!zero)
247 bn_mul_comba4(&(t[n2]), t, &(t[n]));
248 else
249 memset(&t[n2], 0, sizeof(*t) * 8);
250
251 bn_mul_comba4(r, a, b);
252 bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
253 } else if (n == 8 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba8 could
254 * take extra args to do
255 * this well */
256 if (!zero)
257 bn_mul_comba8(&(t[n2]), t, &(t[n]));
258 else
259 memset(&t[n2], 0, sizeof(*t) * 16);
260
261 bn_mul_comba8(r, a, b);
262 bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
263 } else
264# endif /* BN_MUL_COMBA */
265 {
266 p = &(t[n2 * 2]);
267 if (!zero)
268 bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
269 else
270 memset(&t[n2], 0, sizeof(*t) * n2);
271 bn_mul_recursive(r, a, b, n, 0, 0, p);
272 bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
273 }
274
275 /*-
276 * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
277 * r[10] holds (a[0]*b[0])
278 * r[32] holds (b[1]*b[1])
279 */
280
281 c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
282
283 if (neg) { /* if t[32] is negative */
284 c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
285 } else {
286 /* Might have a carry */
287 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
288 }
289
290 /*-
291 * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
292 * r[10] holds (a[0]*b[0])
293 * r[32] holds (b[1]*b[1])
294 * c1 holds the carry bits
295 */
296 c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
297 if (c1) {
298 p = &(r[n + n2]);
299 lo = *p;
300 ln = (lo + c1) & BN_MASK2;
301 *p = ln;
302
303 /*
304 * The overflow will stop before we over write words we should not
305 * overwrite
306 */
307 if (ln < (BN_ULONG)c1) {
308 do {
309 p++;
310 lo = *p;
311 ln = (lo + 1) & BN_MASK2;
312 *p = ln;
313 } while (ln == 0);
314 }
315 }
316}
317
318/*
319 * n+tn is the word length t needs to be n*4 is size, as does r
320 */
321/* tnX may not be negative but less than n */
322void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
323 int tna, int tnb, BN_ULONG *t)
324{
325 int i, j, n2 = n * 2;
326 int c1, c2, neg;
327 BN_ULONG ln, lo, *p;
328
329 if (n < 8) {
330 bn_mul_normal(r, a, n + tna, b, n + tnb);
331 return;
332 }
333
334 /* r=(a[0]-a[1])*(b[1]-b[0]) */
335 c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
336 c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
337 neg = 0;
338 switch (c1 * 3 + c2) {
339 case -4:
340 bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
341 bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
342 break;
343 case -3:
344 case -2:
345 bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
346 bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
347 neg = 1;
348 break;
349 case -1:
350 case 0:
351 case 1:
352 case 2:
353 bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
354 bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
355 neg = 1;
356 break;
357 case 3:
358 case 4:
359 bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
360 bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
361 break;
362 }
363 /*
364 * The zero case isn't yet implemented here. The speedup would probably
365 * be negligible.
366 */
367# if 0
368 if (n == 4) {
369 bn_mul_comba4(&(t[n2]), t, &(t[n]));
370 bn_mul_comba4(r, a, b);
371 bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
372 memset(&r[n2 + tn * 2], 0, sizeof(*r) * (n2 - tn * 2));
373 } else
374# endif
375 if (n == 8) {
376 bn_mul_comba8(&(t[n2]), t, &(t[n]));
377 bn_mul_comba8(r, a, b);
378 bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
379 memset(&r[n2 + tna + tnb], 0, sizeof(*r) * (n2 - tna - tnb));
380 } else {
381 p = &(t[n2 * 2]);
382 bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
383 bn_mul_recursive(r, a, b, n, 0, 0, p);
384 i = n / 2;
385 /*
386 * If there is only a bottom half to the number, just do it
387 */
388 if (tna > tnb)
389 j = tna - i;
390 else
391 j = tnb - i;
392 if (j == 0) {
393 bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),
394 i, tna - i, tnb - i, p);
395 memset(&r[n2 + i * 2], 0, sizeof(*r) * (n2 - i * 2));
396 } else if (j > 0) { /* eg, n == 16, i == 8 and tn == 11 */
397 bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),
398 i, tna - i, tnb - i, p);
399 memset(&(r[n2 + tna + tnb]), 0,
400 sizeof(BN_ULONG) * (n2 - tna - tnb));
401 } else { /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
402
403 memset(&r[n2], 0, sizeof(*r) * n2);
404 if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL
405 && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
406 bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
407 } else {
408 for (;;) {
409 i /= 2;
410 /*
411 * these simplified conditions work exclusively because
412 * difference between tna and tnb is 1 or 0
413 */
414 if (i < tna || i < tnb) {
415 bn_mul_part_recursive(&(r[n2]),
416 &(a[n]), &(b[n]),
417 i, tna - i, tnb - i, p);
418 break;
419 } else if (i == tna || i == tnb) {
420 bn_mul_recursive(&(r[n2]),
421 &(a[n]), &(b[n]),
422 i, tna - i, tnb - i, p);
423 break;
424 }
425 }
426 }
427 }
428 }
429
430 /*-
431 * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
432 * r[10] holds (a[0]*b[0])
433 * r[32] holds (b[1]*b[1])
434 */
435
436 c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
437
438 if (neg) { /* if t[32] is negative */
439 c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
440 } else {
441 /* Might have a carry */
442 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
443 }
444
445 /*-
446 * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
447 * r[10] holds (a[0]*b[0])
448 * r[32] holds (b[1]*b[1])
449 * c1 holds the carry bits
450 */
451 c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
452 if (c1) {
453 p = &(r[n + n2]);
454 lo = *p;
455 ln = (lo + c1) & BN_MASK2;
456 *p = ln;
457
458 /*
459 * The overflow will stop before we over write words we should not
460 * overwrite
461 */
462 if (ln < (BN_ULONG)c1) {
463 do {
464 p++;
465 lo = *p;
466 ln = (lo + 1) & BN_MASK2;
467 *p = ln;
468 } while (ln == 0);
469 }
470 }
471}
472
473/*-
474 * a and b must be the same size, which is n2.
475 * r needs to be n2 words and t needs to be n2*2
476 */
477void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
478 BN_ULONG *t)
479{
480 int n = n2 / 2;
481
482 bn_mul_recursive(r, a, b, n, 0, 0, &(t[0]));
483 if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) {
484 bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2]));
485 bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
486 bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2]));
487 bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
488 } else {
489 bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n);
490 bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n);
491 bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
492 bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
493 }
494}
495#endif /* BN_RECURSION */
496
497int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
498{
499 int ret = bn_mul_fixed_top(r, a, b, ctx);
500
501 bn_correct_top(r);
502 bn_check_top(r);
503
504 return ret;
505}
506
507int bn_mul_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
508{
509 int ret = 0;
510 int top, al, bl;
511 BIGNUM *rr;
512#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
513 int i;
514#endif
515#ifdef BN_RECURSION
516 BIGNUM *t = NULL;
517 int j = 0, k;
518#endif
519
520 bn_check_top(a);
521 bn_check_top(b);
522 bn_check_top(r);
523
524 al = a->top;
525 bl = b->top;
526
527 if ((al == 0) || (bl == 0)) {
528 BN_zero(r);
529 return 1;
530 }
531 top = al + bl;
532
533 BN_CTX_start(ctx);
534 if ((r == a) || (r == b)) {
535 if ((rr = BN_CTX_get(ctx)) == NULL)
536 goto err;
537 } else
538 rr = r;
539
540#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
541 i = al - bl;
542#endif
543#ifdef BN_MUL_COMBA
544 if (i == 0) {
545# if 0
546 if (al == 4) {
547 if (bn_wexpand(rr, 8) == NULL)
548 goto err;
549 rr->top = 8;
550 bn_mul_comba4(rr->d, a->d, b->d);
551 goto end;
552 }
553# endif
554 if (al == 8) {
555 if (bn_wexpand(rr, 16) == NULL)
556 goto err;
557 rr->top = 16;
558 bn_mul_comba8(rr->d, a->d, b->d);
559 goto end;
560 }
561 }
562#endif /* BN_MUL_COMBA */
563#ifdef BN_RECURSION
564 if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
565 if (i >= -1 && i <= 1) {
566 /*
567 * Find out the power of two lower or equal to the longest of the
568 * two numbers
569 */
570 if (i >= 0) {
571 j = BN_num_bits_word((BN_ULONG)al);
572 }
573 if (i == -1) {
574 j = BN_num_bits_word((BN_ULONG)bl);
575 }
576 j = 1 << (j - 1);
577 assert(j <= al || j <= bl);
578 k = j + j;
579 t = BN_CTX_get(ctx);
580 if (t == NULL)
581 goto err;
582 if (al > j || bl > j) {
583 if (bn_wexpand(t, k * 4) == NULL)
584 goto err;
585 if (bn_wexpand(rr, k * 4) == NULL)
586 goto err;
587 bn_mul_part_recursive(rr->d, a->d, b->d,
588 j, al - j, bl - j, t->d);
589 } else { /* al <= j || bl <= j */
590
591 if (bn_wexpand(t, k * 2) == NULL)
592 goto err;
593 if (bn_wexpand(rr, k * 2) == NULL)
594 goto err;
595 bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d);
596 }
597 rr->top = top;
598 goto end;
599 }
600 }
601#endif /* BN_RECURSION */
602 if (bn_wexpand(rr, top) == NULL)
603 goto err;
604 rr->top = top;
605 bn_mul_normal(rr->d, a->d, al, b->d, bl);
606
607#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
608 end:
609#endif
610 rr->neg = a->neg ^ b->neg;
611 rr->flags |= BN_FLG_FIXED_TOP;
612 if (r != rr && BN_copy(r, rr) == NULL)
613 goto err;
614
615 ret = 1;
616 err:
617 bn_check_top(r);
618 BN_CTX_end(ctx);
619 return ret;
620}
621
622void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
623{
624 BN_ULONG *rr;
625
626 if (na < nb) {
627 int itmp;
628 BN_ULONG *ltmp;
629
630 itmp = na;
631 na = nb;
632 nb = itmp;
633 ltmp = a;
634 a = b;
635 b = ltmp;
636
637 }
638 rr = &(r[na]);
639 if (nb <= 0) {
640 (void)bn_mul_words(r, a, na, 0);
641 return;
642 } else
643 rr[0] = bn_mul_words(r, a, na, b[0]);
644
645 for (;;) {
646 if (--nb <= 0)
647 return;
648 rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
649 if (--nb <= 0)
650 return;
651 rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
652 if (--nb <= 0)
653 return;
654 rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
655 if (--nb <= 0)
656 return;
657 rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
658 rr += 4;
659 r += 4;
660 b += 4;
661 }
662}
663
664void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
665{
666 bn_mul_words(r, a, n, b[0]);
667
668 for (;;) {
669 if (--n <= 0)
670 return;
671 bn_mul_add_words(&(r[1]), a, n, b[1]);
672 if (--n <= 0)
673 return;
674 bn_mul_add_words(&(r[2]), a, n, b[2]);
675 if (--n <= 0)
676 return;
677 bn_mul_add_words(&(r[3]), a, n, b[3]);
678 if (--n <= 0)
679 return;
680 bn_mul_add_words(&(r[4]), a, n, b[4]);
681 r += 4;
682 b += 4;
683 }
684}
685