summaryrefslogtreecommitdiff
path: root/src/lib
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib')
-rw-r--r--src/lib/libcrypto/bn/bn_local.h12
-rw-r--r--src/lib/libcrypto/bn/bn_mul.c396
-rw-r--r--src/lib/libcrypto/man/bn_dump.374
3 files changed, 15 insertions, 467 deletions
diff --git a/src/lib/libcrypto/bn/bn_local.h b/src/lib/libcrypto/bn/bn_local.h
index 48d24c5a27..08e7064c5b 100644
--- a/src/lib/libcrypto/bn/bn_local.h
+++ b/src/lib/libcrypto/bn/bn_local.h
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_local.h,v 1.3 2022/11/30 03:08:39 jsing Exp $ */ 1/* $OpenBSD: bn_local.h,v 1.4 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 *
@@ -498,16 +498,10 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
498void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, 498void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
499 int n, int tna, int tnb, BN_ULONG *t); 499 int n, int tna, int tnb, BN_ULONG *t);
500void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t); 500void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t);
501void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n);
502void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
503 BN_ULONG *t);
504void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
505 BN_ULONG *t);
506BN_ULONG bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
507 int cl, int dl);
508BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, 501BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
509 int cl, int dl); 502 int cl, int dl);
510int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, const BN_ULONG *np, const BN_ULONG *n0, int num); 503int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
504 const BN_ULONG *np, const BN_ULONG *n0, int num);
511 505
512void bn_correct_top(BIGNUM *a); 506void bn_correct_top(BIGNUM *a);
513int bn_expand(BIGNUM *a, int bits); 507int bn_expand(BIGNUM *a, int bits);
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
diff --git a/src/lib/libcrypto/man/bn_dump.3 b/src/lib/libcrypto/man/bn_dump.3
index 36ae660785..cfe707b775 100644
--- a/src/lib/libcrypto/man/bn_dump.3
+++ b/src/lib/libcrypto/man/bn_dump.3
@@ -1,4 +1,4 @@
1.\" $OpenBSD: bn_dump.3,v 1.7 2022/11/22 19:00:15 schwarze Exp $ 1.\" $OpenBSD: bn_dump.3,v 1.8 2023/01/20 12:16:46 jsing Exp $
2.\" full merge up to: 2.\" full merge up to:
3.\" OpenSSL crypto/bn/README.pod aebb9aac Jul 19 09:27:53 2016 -0400 3.\" OpenSSL crypto/bn/README.pod aebb9aac Jul 19 09:27:53 2016 -0400
4.\" 4.\"
@@ -50,7 +50,7 @@
50.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
51.\" OF THE POSSIBILITY OF SUCH DAMAGE. 51.\" OF THE POSSIBILITY OF SUCH DAMAGE.
52.\" 52.\"
53.Dd $Mdocdate: November 22 2022 $ 53.Dd $Mdocdate: January 20 2023 $
54.Dt BN_DUMP 3 54.Dt BN_DUMP 3
55.Os 55.Os
56.Sh NAME 56.Sh NAME
@@ -66,11 +66,8 @@
66.Nm bn_sqr_comba8 , 66.Nm bn_sqr_comba8 ,
67.Nm bn_cmp_words , 67.Nm bn_cmp_words ,
68.Nm bn_mul_normal , 68.Nm bn_mul_normal ,
69.Nm bn_mul_low_normal ,
70.Nm bn_mul_recursive , 69.Nm bn_mul_recursive ,
71.Nm bn_mul_part_recursive , 70.Nm bn_mul_part_recursive ,
72.Nm bn_mul_low_recursive ,
73.Nm bn_mul_high ,
74.Nm bn_sqr_normal , 71.Nm bn_sqr_normal ,
75.Nm bn_sqr_recursive , 72.Nm bn_sqr_recursive ,
76.Nm bn_expand , 73.Nm bn_expand ,
@@ -166,13 +163,6 @@
166.Fa "int nb" 163.Fa "int nb"
167.Fc 164.Fc
168.Ft void 165.Ft void
169.Fo bn_mul_low_normal
170.Fa "BN_ULONG *r"
171.Fa "BN_ULONG *a"
172.Fa "BN_ULONG *b"
173.Fa "int n"
174.Fc
175.Ft void
176.Fo bn_mul_recursive 166.Fo bn_mul_recursive
177.Fa "BN_ULONG *r" 167.Fa "BN_ULONG *r"
178.Fa "BN_ULONG *a" 168.Fa "BN_ULONG *a"
@@ -193,23 +183,6 @@
193.Fa "BN_ULONG *tmp" 183.Fa "BN_ULONG *tmp"
194.Fc 184.Fc
195.Ft void 185.Ft void
196.Fo bn_mul_low_recursive
197.Fa "BN_ULONG *r"
198.Fa "BN_ULONG *a"
199.Fa "BN_ULONG *b"
200.Fa "int n2"
201.Fa "BN_ULONG *tmp"
202.Fc
203.Ft void
204.Fo bn_mul_high
205.Fa "BN_ULONG *r"
206.Fa "BN_ULONG *a"
207.Fa "BN_ULONG *b"
208.Fa "BN_ULONG *l"
209.Fa "int n2"
210.Fa "BN_ULONG *tmp"
211.Fc
212.Ft void
213.Fo bn_sqr_normal 186.Fo bn_sqr_normal
214.Fa "BN_ULONG *r" 187.Fa "BN_ULONG *r"
215.Fa "BN_ULONG *a" 188.Fa "BN_ULONG *a"
@@ -545,21 +518,6 @@ It computes
545and places the result in 518and places the result in
546.Fa r . 519.Fa r .
547.Pp 520.Pp
548.Fn bn_mul_low_normal r a b n
549operates on the
550.Fa n
551word arrays
552.Fa r ,
553.Fa a
554and
555.Fa b .
556It computes the
557.Fa n
558low words of
559.Fa a Ns * Ns Fa b
560and places the result in
561.Fa r .
562.Pp
563.Fn bn_mul_recursive r a b n2 dna dnb t 521.Fn bn_mul_recursive r a b n2 dna dnb t
564operates on the word arrays 522operates on the word arrays
565.Fa a 523.Fa a
@@ -601,34 +559,6 @@ word arrays
601and 559and
602.Fa tmp . 560.Fa tmp .
603.Pp 561.Pp
604.Fn bn_mul_low_recursive r a b n2 tmp
605operates on the
606.Fa n2
607word arrays
608.Fa r
609and
610.Fa tmp
611and the
612.Fa n2 Ns /2
613word arrays
614.Fa a
615and
616.Fa b .
617.Pp
618.Fn bn_mul_high r a b l n2 tmp
619operates on the
620.Fa n2
621word arrays
622.Fa r ,
623.Fa a ,
624.Fa b
625and
626.Fa l
627(?) and the
628.Pf 3* Fa n2
629word array
630.Fa tmp .
631.Pp
632.Xr BN_mul 3 562.Xr BN_mul 3
633calls 563calls
634.Fn bn_mul_normal , 564.Fn bn_mul_normal ,
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-22 20:16:23 +0000