summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_mul.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_mul.c')
-rw-r--r--src/lib/libcrypto/bn/bn_mul.c396
1 files changed, 10 insertions, 386 deletions
diff --git a/src/lib/libcrypto/bn/bn_mul.c b/src/lib/libcrypto/bn/bn_mul.c
index 5437e7e883..b7a7f8bcef 100644
--- a/src/lib/libcrypto/bn/bn_mul.c
+++ b/src/lib/libcrypto/bn/bn_mul.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_mul.c,v 1.26 2023/01/20 10:00:51 jsing Exp $ */ 1/* $OpenBSD: bn_mul.c,v 1.27 2023/01/20 12:16:46 jsing Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -64,177 +64,16 @@
64 64
65#include "bn_local.h" 65#include "bn_local.h"
66 66
67/* Here follows specialised variants of bn_add_words() and
68 bn_sub_words(). They have the property performing operations on
69 arrays of different sizes. The sizes of those arrays is expressed through
70 cl, which is the common length ( basicall, min(len(a),len(b)) ), and dl,
71 which is the delta between the two lengths, calculated as len(a)-len(b).
72 All lengths are the number of BN_ULONGs... For the operations that require
73 a result array as parameter, it must have the length cl+abs(dl).
74 These functions should probably end up in bn_asm.c as soon as there are
75 assembler counterparts for the systems that use assembler files. */
76
77BN_ULONG
78bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl,
79 int dl)
80{
81 BN_ULONG c, l, t;
82
83 assert(cl >= 0);
84 c = bn_add_words(r, a, b, cl);
85
86 if (dl == 0)
87 return c;
88
89 r += cl;
90 a += cl;
91 b += cl;
92
93 if (dl < 0) {
94 int save_dl = dl;
95 while (c) {
96 l = (c + b[0]) & BN_MASK2;
97 c = (l < c);
98 r[0] = l;
99 if (++dl >= 0)
100 break;
101
102 l = (c + b[1]) & BN_MASK2;
103 c = (l < c);
104 r[1] = l;
105 if (++dl >= 0)
106 break;
107
108 l = (c + b[2]) & BN_MASK2;
109 c = (l < c);
110 r[2] = l;
111 if (++dl >= 0)
112 break;
113
114 l = (c + b[3]) & BN_MASK2;
115 c = (l < c);
116 r[3] = l;
117 if (++dl >= 0)
118 break;
119
120 save_dl = dl;
121 b += 4;
122 r += 4;
123 }
124 if (dl < 0) {
125 if (save_dl < dl) {
126 switch (dl - save_dl) {
127 case 1:
128 r[1] = b[1];
129 if (++dl >= 0)
130 break;
131 case 2:
132 r[2] = b[2];
133 if (++dl >= 0)
134 break;
135 case 3:
136 r[3] = b[3];
137 if (++dl >= 0)
138 break;
139 }
140 b += 4;
141 r += 4;
142 }
143 }
144 if (dl < 0) {
145 for (;;) {
146 r[0] = b[0];
147 if (++dl >= 0)
148 break;
149 r[1] = b[1];
150 if (++dl >= 0)
151 break;
152 r[2] = b[2];
153 if (++dl >= 0)
154 break;
155 r[3] = b[3];
156 if (++dl >= 0)
157 break;
158
159 b += 4;
160 r += 4;
161 }
162 }
163 } else {
164 int save_dl = dl;
165 while (c) {
166 t = (a[0] + c) & BN_MASK2;
167 c = (t < c);
168 r[0] = t;
169 if (--dl <= 0)
170 break;
171
172 t = (a[1] + c) & BN_MASK2;
173 c = (t < c);
174 r[1] = t;
175 if (--dl <= 0)
176 break;
177
178 t = (a[2] + c) & BN_MASK2;
179 c = (t < c);
180 r[2] = t;
181 if (--dl <= 0)
182 break;
183
184 t = (a[3] + c) & BN_MASK2;
185 c = (t < c);
186 r[3] = t;
187 if (--dl <= 0)
188 break;
189
190 save_dl = dl;
191 a += 4;
192 r += 4;
193 }
194 if (dl > 0) {
195 if (save_dl > dl) {
196 switch (save_dl - dl) {
197 case 1:
198 r[1] = a[1];
199 if (--dl <= 0)
200 break;
201 case 2:
202 r[2] = a[2];
203 if (--dl <= 0)
204 break;
205 case 3:
206 r[3] = a[3];
207 if (--dl <= 0)
208 break;
209 }
210 a += 4;
211 r += 4;
212 }
213 }
214 if (dl > 0) {
215 for (;;) {
216 r[0] = a[0];
217 if (--dl <= 0)
218 break;
219 r[1] = a[1];
220 if (--dl <= 0)
221 break;
222 r[2] = a[2];
223 if (--dl <= 0)
224 break;
225 r[3] = a[3];
226 if (--dl <= 0)
227 break;
228
229 a += 4;
230 r += 4;
231 }
232 }
233 }
234 return c;
235}
236
237#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS) 67#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS)
68/*
69 * Here follows a specialised variant of bn_sub_words(), which has the property
70 * performing operations on arrays of different sizes. The sizes of those arrays
71 * is expressed through cl, which is the common length (basically,
72 * min(len(a),len(b))), and dl, which is the delta between the two lengths,
73 * calculated as len(a)-len(b). All lengths are the number of BN_ULONGs. For the
74 * operations that require a result array as parameter, it must have the length
75 * cl+abs(dl).
76 */
238BN_ULONG 77BN_ULONG
239bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, 78bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl,
240 int dl) 79 int dl)
@@ -407,199 +246,7 @@ bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
407 } 246 }
408} 247}
409 248
410void
411bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
412{
413 bn_mul_words(r, a, n, b[0]);
414
415 for (;;) {
416 if (--n <= 0)
417 return;
418 bn_mul_add_words(&(r[1]), a, n, b[1]);
419 if (--n <= 0)
420 return;
421 bn_mul_add_words(&(r[2]), a, n, b[2]);
422 if (--n <= 0)
423 return;
424 bn_mul_add_words(&(r[3]), a, n, b[3]);
425 if (--n <= 0)
426 return;
427 bn_mul_add_words(&(r[4]), a, n, b[4]);
428 r += 4;
429 b += 4;
430 }
431}
432
433#ifdef BN_RECURSION 249#ifdef BN_RECURSION
434/* a and b must be the same size, which is n2.
435 * r needs to be n2 words and t needs to be n2*2
436 * l is the low words of the output.
437 * t needs to be n2*3
438 */
439void
440bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
441 BN_ULONG *t)
442{
443 int i, n;
444 int c1, c2;
445 int neg, oneg, zero;
446 BN_ULONG ll, lc, *lp, *mp;
447
448 n = n2 / 2;
449
450 /* Calculate (al-ah)*(bh-bl) */
451 neg = zero = 0;
452 c1 = bn_cmp_words(&(a[0]), &(a[n]), n);
453 c2 = bn_cmp_words(&(b[n]), &(b[0]), n);
454 switch (c1 * 3 + c2) {
455 case -4:
456 bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
457 bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
458 break;
459 case -3:
460 zero = 1;
461 break;
462 case -2:
463 bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
464 bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
465 neg = 1;
466 break;
467 case -1:
468 case 0:
469 case 1:
470 zero = 1;
471 break;
472 case 2:
473 bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
474 bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
475 neg = 1;
476 break;
477 case 3:
478 zero = 1;
479 break;
480 case 4:
481 bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
482 bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
483 break;
484 }
485
486 oneg = neg;
487 /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
488 /* r[10] = (a[1]*b[1]) */
489# ifdef BN_MUL_COMBA
490 if (n == 8) {
491 bn_mul_comba8(&(t[0]), &(r[0]), &(r[n]));
492 bn_mul_comba8(r, &(a[n]), &(b[n]));
493 } else
494# endif
495 {
496 bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, 0, 0, &(t[n2]));
497 bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2]));
498 }
499
500 /* s0 == low(al*bl)
501 * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
502 * We know s0 and s1 so the only unknown is high(al*bl)
503 * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
504 * high(al*bl) == s1 - (r[0]+l[0]+t[0])
505 */
506 if (l != NULL) {
507 lp = &(t[n2 + n]);
508 c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n));
509 } else {
510 c1 = 0;
511 lp = &(r[0]);
512 }
513
514 if (neg)
515 neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n));
516 else {
517 bn_add_words(&(t[n2]), lp, &(t[0]), n);
518 neg = 0;
519 }
520
521 if (l != NULL) {
522 bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n);
523 } else {
524 lp = &(t[n2 + n]);
525 mp = &(t[n2]);
526 for (i = 0; i < n; i++)
527 lp[i] = ((~mp[i]) + 1) & BN_MASK2;
528 }
529
530 /* s[0] = low(al*bl)
531 * t[3] = high(al*bl)
532 * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
533 * r[10] = (a[1]*b[1])
534 */
535 /* R[10] = al*bl
536 * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
537 * R[32] = ah*bh
538 */
539 /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
540 * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
541 * R[3]=r[1]+(carry/borrow)
542 */
543 if (l != NULL) {
544 lp = &(t[n2]);
545 c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n));
546 } else {
547 lp = &(t[n2 + n]);
548 c1 = 0;
549 }
550 c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n));
551 if (oneg)
552 c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n));
553 else
554 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n));
555
556 c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n));
557 c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n));
558 if (oneg)
559 c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n));
560 else
561 c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n));
562
563 if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
564 {
565 i = 0;
566 if (c1 > 0) {
567 lc = c1;
568 do {
569 ll = (r[i] + lc) & BN_MASK2;
570 r[i++] = ll;
571 lc = (lc > ll);
572 } while (lc);
573 } else {
574 lc = -c1;
575 do {
576 ll = r[i];
577 r[i++] = (ll - lc) & BN_MASK2;
578 lc = (lc > ll);
579 } while (lc);
580 }
581 }
582 if (c2 != 0) /* Add starting at r[1] */
583 {
584 i = n;
585 if (c2 > 0) {
586 lc = c2;
587 do {
588 ll = (r[i] + lc) & BN_MASK2;
589 r[i++] = ll;
590 lc = (lc > ll);
591 } while (lc);
592 } else {
593 lc = -c2;
594 do {
595 ll = r[i];
596 r[i++] = (ll - lc) & BN_MASK2;
597 lc = (lc > ll);
598 } while (lc);
599 }
600 }
601}
602
603/* Karatsuba recursive multiplication algorithm 250/* Karatsuba recursive multiplication algorithm
604 * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ 251 * (cf. Knuth, The Art of Computer Programming, Vol. 2) */
605 252
@@ -912,29 +559,6 @@ bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, int tna,
912 } 559 }
913 } 560 }
914} 561}
915
916/* a and b must be the same size, which is n2.
917 * r needs to be n2 words and t needs to be n2*2
918 */
919void
920bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, BN_ULONG *t)
921{
922 int n = n2 / 2;
923
924
925 bn_mul_recursive(r, a, b, n, 0, 0, &(t[0]));
926 if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) {
927 bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2]));
928 bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
929 bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2]));
930 bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
931 } else {
932 bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n);
933 bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n);
934 bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
935 bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
936 }
937}
938#endif /* BN_RECURSION */ 562#endif /* BN_RECURSION */
939 563
940int 564int
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-23 10:42:04 +0000