From 0954bbaddbf74f6f184f313822c63bf1b56695bd Mon Sep 17 00:00:00 2001
From: jsing <>
Date: Wed, 19 Apr 2023 10:51:22 +0000
Subject: unifdef BN_RECURSION
This removes a bunch of incomplete and scary code, which potentially leaks
secrets and is not constant time. A performance gain is achieved on arm64
for sizes that we care about, while a minimal decrease in performance is
noted for larger sizes on some other platforms.
While we will potentially reimplement Karatsuba (or Toom-Cook) at a later
date, it will be easier and safer to do it from a clean slate.
ok tb@
---
src/lib/libcrypto/bn/bn.h | 8 +-
src/lib/libcrypto/bn/bn_lib.c | 50 +----
src/lib/libcrypto/bn/bn_local.h | 10 +-
src/lib/libcrypto/bn/bn_mul.c | 423 +---------------------------------------
src/lib/libcrypto/bn/bn_sqr.c | 108 +---------
5 files changed, 5 insertions(+), 594 deletions(-)
(limited to 'src/lib')
diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h
index bb85ea442c..53b109bd8a 100644
--- a/src/lib/libcrypto/bn/bn.h
+++ b/src/lib/libcrypto/bn/bn.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn.h,v 1.61 2023/04/16 09:13:46 tb Exp $ */
+/* $OpenBSD: bn.h,v 1.62 2023/04/19 10:51:22 jsing Exp $ */
/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com)
* All rights reserved.
*
@@ -138,12 +138,6 @@
extern "C" {
#endif
-#ifndef OPENSSL_SMALL_FOOTPRINT
-#define BN_MUL_COMBA
-#define BN_SQR_COMBA
-#define BN_RECURSION
-#endif
-
/* This next option uses the C libraries (2 word)/(1 word) function.
* If it is not defined, I use my C version (which is slower).
* The reason for this flag is that when the particular C compiler
diff --git a/src/lib/libcrypto/bn/bn_lib.c b/src/lib/libcrypto/bn/bn_lib.c
index f25caa04af..89664fbb97 100644
--- a/src/lib/libcrypto/bn/bn_lib.c
+++ b/src/lib/libcrypto/bn/bn_lib.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_lib.c,v 1.81 2023/04/14 11:04:24 jsing Exp $ */
+/* $OpenBSD: bn_lib.c,v 1.82 2023/04/19 10:51:22 jsing Exp $ */
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
* All rights reserved.
*
@@ -735,54 +735,6 @@ BN_set_negative(BIGNUM *bn, int neg)
bn->neg = ~BN_is_zero(bn) & bn_ct_ne_zero(neg);
}
-int
-bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
-{
- int i;
- BN_ULONG aa, bb;
-
- aa = a[n - 1];
- bb = b[n - 1];
- if (aa != bb)
- return ((aa > bb) ? 1 : -1);
- for (i = n - 2; i >= 0; i--) {
- aa = a[i];
- bb = b[i];
- if (aa != bb)
- return ((aa > bb) ? 1 : -1);
- }
- return (0);
-}
-
-/* Here follows a specialised variants of bn_cmp_words(). It has the
- property of performing the operation on arrays of different sizes.
- The sizes of those arrays is expressed through cl, which is the
- common length ( basicall, min(len(a),len(b)) ), and dl, which is the
- delta between the two lengths, calculated as len(a)-len(b).
- All lengths are the number of BN_ULONGs... */
-
-int
-bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
-{
- int n, i;
-
- n = cl - 1;
-
- if (dl < 0) {
- for (i = dl; i < 0; i++) {
- if (b[n - i] != 0)
- return -1; /* a < b */
- }
- }
- if (dl > 0) {
- for (i = dl; i > 0; i--) {
- if (a[n + i] != 0)
- return 1; /* a > b */
- }
- }
- return bn_cmp_words(a, b, cl);
-}
-
/*
* Constant-time conditional swap of a and b.
* a and b are swapped if condition is not 0.
diff --git a/src/lib/libcrypto/bn/bn_local.h b/src/lib/libcrypto/bn/bn_local.h
index 4912ae96f3..5e85dfc3de 100644
--- a/src/lib/libcrypto/bn/bn_local.h
+++ b/src/lib/libcrypto/bn/bn_local.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_local.h,v 1.18 2023/03/27 08:37:33 tb Exp $ */
+/* $OpenBSD: bn_local.h,v 1.19 2023/04/19 10:51:22 jsing Exp $ */
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
* All rights reserved.
*
@@ -256,14 +256,6 @@ void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp);
void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a);
void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a);
-int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n);
-int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b,
- int cl, int dl);
-void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
- int dna, int dnb, BN_ULONG *t);
-void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
- int n, int tna, int tnb, BN_ULONG *t);
-void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t);
int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
const BN_ULONG *np, const BN_ULONG *n0, int num);
diff --git a/src/lib/libcrypto/bn/bn_mul.c b/src/lib/libcrypto/bn/bn_mul.c
index fe3f29617f..118e8cddc5 100644
--- a/src/lib/libcrypto/bn/bn_mul.c
+++ b/src/lib/libcrypto/bn/bn_mul.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_mul.c,v 1.36 2023/03/30 14:28:56 tb Exp $ */
+/* $OpenBSD: bn_mul.c,v 1.37 2023/04/19 10:51:22 jsing Exp $ */
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
* All rights reserved.
*
@@ -313,323 +313,8 @@ bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
}
}
-#ifdef BN_RECURSION
-/* Karatsuba recursive multiplication algorithm
- * (cf. Knuth, The Art of Computer Programming, Vol. 2) */
-
-/* r is 2*n2 words in size,
- * a and b are both n2 words in size.
- * n2 must be a power of 2.
- * We multiply and return the result.
- * t must be 2*n2 words in size
- * We calculate
- * a[0]*b[0]
- * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
- * a[1]*b[1]
- */
-/* dnX may not be positive, but n2/2+dnX has to be */
-void
-bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, int dna,
- int dnb, BN_ULONG *t)
-{
- int n = n2 / 2, c1, c2;
- int tna = n + dna, tnb = n + dnb;
- unsigned int neg, zero;
- BN_ULONG ln, lo, *p;
-
-# ifdef BN_MUL_COMBA
-# if 0
- if (n2 == 4) {
- bn_mul_comba4(r, a, b);
- return;
- }
-# endif
- /* Only call bn_mul_comba 8 if n2 == 8 and the
- * two arrays are complete [steve]
- */
- if (n2 == 8 && dna == 0 && dnb == 0) {
- bn_mul_comba8(r, a, b);
- return;
- }
-# endif /* BN_MUL_COMBA */
- /* Else do normal multiply */
- if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
- bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
- if ((dna + dnb) < 0)
- memset(&r[2*n2 + dna + dnb], 0,
- sizeof(BN_ULONG) * -(dna + dnb));
- return;
- }
- /* r=(a[0]-a[1])*(b[1]-b[0]) */
- c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
- c2 = bn_cmp_part_words(&(b[n]), b,tnb, tnb - n);
- zero = neg = 0;
- switch (c1 * 3 + c2) {
- case -4:
- bn_sub(t, n, &a[n], tna, a, n); /* - */
- bn_sub(&t[n], n, b, n, &b[n], tnb); /* - */
- break;
- case -3:
- zero = 1;
- break;
- case -2:
- bn_sub(t, n, &a[n], tna, a, n); /* - */
- bn_sub(&t[n], n, &b[n], tnb, b, n); /* + */
- neg = 1;
- break;
- case -1:
- case 0:
- case 1:
- zero = 1;
- break;
- case 2:
- bn_sub(t, n, a, n, &a[n], tna); /* + */
- bn_sub(&t[n], n, b, n, &b[n], tnb); /* - */
- neg = 1;
- break;
- case 3:
- zero = 1;
- break;
- case 4:
- bn_sub(t, n, a, n, &a[n], tna);
- bn_sub(&t[n], n, &b[n], tnb, b, n);
- break;
- }
-
-# ifdef BN_MUL_COMBA
- if (n == 4 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba4 could take
- extra args to do this well */
- {
- if (!zero)
- bn_mul_comba4(&(t[n2]), t, &(t[n]));
- else
- memset(&(t[n2]), 0, 8 * sizeof(BN_ULONG));
-
- bn_mul_comba4(r, a, b);
- bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
- } else if (n == 8 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba8 could
- take extra args to do this
- well */
- {
- if (!zero)
- bn_mul_comba8(&(t[n2]), t, &(t[n]));
- else
- memset(&(t[n2]), 0, 16 * sizeof(BN_ULONG));
-
- bn_mul_comba8(r, a, b);
- bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
- } else
-# endif /* BN_MUL_COMBA */
- {
- p = &(t[n2 * 2]);
- if (!zero)
- bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
- else
- memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG));
- bn_mul_recursive(r, a, b, n, 0, 0, p);
- bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
- }
-
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- */
-
- c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
-
- if (neg) /* if t[32] is negative */
- {
- c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
- } else {
- /* Might have a carry */
- c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
- }
-
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- * c1 holds the carry bits
- */
- c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
- if (c1) {
- p = &(r[n + n2]);
- lo= *p;
- ln = (lo + c1) & BN_MASK2;
- *p = ln;
-
- /* The overflow will stop before we over write
- * words we should not overwrite */
- if (ln < (BN_ULONG)c1) {
- do {
- p++;
- lo= *p;
- ln = (lo + 1) & BN_MASK2;
- *p = ln;
- } while (ln == 0);
- }
- }
-}
-
-/* n+tn is the word length
- * t needs to be n*4 is size, as does r */
-/* tnX may not be negative but less than n */
-void
-bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, int tna,
- int tnb, BN_ULONG *t)
-{
- int i, j, n2 = n * 2;
- int c1, c2, neg;
- BN_ULONG ln, lo, *p;
-
- if (n < 8) {
- bn_mul_normal(r, a, n + tna, b, n + tnb);
- return;
- }
-
- /* r=(a[0]-a[1])*(b[1]-b[0]) */
- c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
- c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
- neg = 0;
- switch (c1 * 3 + c2) {
- case -4:
- bn_sub(t, n, &a[n], tna, a, n); /* - */
- bn_sub(&t[n], n, b, n, &b[n], tnb); /* - */
- break;
- case -3:
- /* break; */
- case -2:
- bn_sub(t, n, &a[n], tna, a, n); /* - */
- bn_sub(&t[n], n, &b[n], tnb, b, n); /* + */
- neg = 1;
- break;
- case -1:
- case 0:
- case 1:
- /* break; */
- case 2:
- bn_sub(t, n, a, n, &a[n], tna); /* + */
- bn_sub(&t[n], n, b, n, &b[n], tnb); /* - */
- neg = 1;
- break;
- case 3:
- /* break; */
- case 4:
- bn_sub(t, n, a, n, &a[n], tna);
- bn_sub(&t[n], n, &b[n], tnb, b, n);
- break;
- }
- /* The zero case isn't yet implemented here. The speedup
- would probably be negligible. */
-# if 0
- if (n == 4) {
- bn_mul_comba4(&(t[n2]), t, &(t[n]));
- bn_mul_comba4(r, a, b);
- bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
- memset(&(r[n2 + tn * 2]), 0, sizeof(BN_ULONG) * (n2 - tn * 2));
- } else
-# endif
- if (n == 8) {
- bn_mul_comba8(&(t[n2]), t, &(t[n]));
- bn_mul_comba8(r, a, b);
- bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
- memset(&(r[n2 + tna + tnb]), 0,
- sizeof(BN_ULONG) * (n2 - tna - tnb));
- } else {
- p = &(t[n2*2]);
- bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
- bn_mul_recursive(r, a, b, n, 0, 0, p);
- i = n / 2;
- /* If there is only a bottom half to the number,
- * just do it */
- if (tna > tnb)
- j = tna - i;
- else
- j = tnb - i;
- if (j == 0) {
- bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),
- i, tna - i, tnb - i, p);
- memset(&(r[n2 + i * 2]), 0,
- sizeof(BN_ULONG) * (n2 - i * 2));
- }
- else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
- {
- bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),
- i, tna - i, tnb - i, p);
- memset(&(r[n2 + tna + tnb]), 0,
- sizeof(BN_ULONG) * (n2 - tna - tnb));
- }
- else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
- {
- memset(&(r[n2]), 0, sizeof(BN_ULONG) * n2);
- if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL &&
- tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
- bn_mul_normal(&(r[n2]), &(a[n]), tna,
- &(b[n]), tnb);
- } else {
- for (;;) {
- i /= 2;
- /* these simplified conditions work
- * exclusively because difference
- * between tna and tnb is 1 or 0 */
- if (i < tna || i < tnb) {
- bn_mul_part_recursive(&(r[n2]),
- &(a[n]), &(b[n]), i,
- tna - i, tnb - i, p);
- break;
- } else if (i == tna || i == tnb) {
- bn_mul_recursive(&(r[n2]),
- &(a[n]), &(b[n]), i,
- tna - i, tnb - i, p);
- break;
- }
- }
- }
- }
- }
-
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- */
-
- c1 = (int)(bn_add_words(t, r,&(r[n2]), n2));
-
- if (neg) /* if t[32] is negative */
- {
- c1 -= (int)(bn_sub_words(&(t[n2]), t,&(t[n2]), n2));
- } else {
- /* Might have a carry */
- c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
- }
-
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- * c1 holds the carry bits
- */
- c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
- if (c1) {
- p = &(r[n + n2]);
- lo= *p;
- ln = (lo + c1)&BN_MASK2;
- *p = ln;
-
- /* The overflow will stop before we over write
- * words we should not overwrite */
- if (ln < (BN_ULONG)c1) {
- do {
- p++;
- lo= *p;
- ln = (lo + 1) & BN_MASK2;
- *p = ln;
- } while (ln == 0);
- }
- }
-}
-#endif /* BN_RECURSION */
#ifndef HAVE_BN_MUL
-#ifndef BN_RECURSION
int
bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx)
{
@@ -638,112 +323,6 @@ bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx)
return 1;
}
-#else /* BN_RECURSION */
-int
-bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx)
-{
- BIGNUM *t = NULL;
- int al, bl, i, k;
- int j = 0;
- int ret = 0;
-
- BN_CTX_start(ctx);
-
- al = a->top;
- bl = b->top;
-
- i = al - bl;
-
- if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
- if (i >= -1 && i <= 1) {
- /* Find out the power of two lower or equal
- to the longest of the two numbers */
- if (i >= 0) {
- j = BN_num_bits_word((BN_ULONG)al);
- }
- if (i == -1) {
- j = BN_num_bits_word((BN_ULONG)bl);
- }
- j = 1 << (j - 1);
- assert(j <= al || j <= bl);
- k = j + j;
- if ((t = BN_CTX_get(ctx)) == NULL)
- goto err;
- if (al > j || bl > j) {
- if (!bn_wexpand(t, k * 4))
- goto err;
- if (!bn_wexpand(r, k * 4))
- goto err;
- bn_mul_part_recursive(r->d, a->d, b->d,
- j, al - j, bl - j, t->d);
- }
- else /* al <= j || bl <= j */
- {
- if (!bn_wexpand(t, k * 2))
- goto err;
- if (!bn_wexpand(r, k * 2))
- goto err;
- bn_mul_recursive(r->d, a->d, b->d,
- j, al - j, bl - j, t->d);
- }
- r->top = rn;
- goto end;
- }
-#if 0
- if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) {
- BIGNUM *tmp_bn = (BIGNUM *)b;
- if (!bn_wexpand(tmp_bn, al))
- goto err;
- tmp_bn->d[bl] = 0;
- bl++;
- i--;
- } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) {
- BIGNUM *tmp_bn = (BIGNUM *)a;
- if (!bn_wexpand(tmp_bn, bl))
- goto err;
- tmp_bn->d[al] = 0;
- al++;
- i++;
- }
- if (i == 0) {
- /* symmetric and > 4 */
- /* 16 or larger */
- j = BN_num_bits_word((BN_ULONG)al);
- j = 1 << (j - 1);
- k = j + j;
- if ((t = BN_CTX_get(ctx)) == NULL)
- goto err;
- if (al == j) /* exact multiple */
- {
- if (!bn_wexpand(t, k * 2))
- goto err;
- if (!bn_wexpand(r, k * 2))
- goto err;
- bn_mul_recursive(r->d, a->d, b->d, al, t->d);
- } else {
- if (!bn_wexpand(t, k * 4))
- goto err;
- if (!bn_wexpand(r, k * 4))
- goto err;
- bn_mul_part_recursive(r->d, a->d, b->d,
- al - j, j, t->d);
- }
- r->top = top;
- goto end;
- }
-#endif
- }
-
- bn_mul_normal(r->d, a->d, al, b->d, bl);
-
- end:
- ret = 1;
- err:
- BN_CTX_end(ctx);
-
- return ret;
-}
-#endif /* BN_RECURSION */
#endif /* HAVE_BN_MUL */
int
diff --git a/src/lib/libcrypto/bn/bn_sqr.c b/src/lib/libcrypto/bn/bn_sqr.c
index d5da775200..d414800feb 100644
--- a/src/lib/libcrypto/bn/bn_sqr.c
+++ b/src/lib/libcrypto/bn/bn_sqr.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_sqr.c,v 1.29 2023/03/30 14:28:56 tb Exp $ */
+/* $OpenBSD: bn_sqr.c,v 1.30 2023/04/19 10:51:22 jsing Exp $ */
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
* All rights reserved.
*
@@ -228,90 +228,6 @@ bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp)
bn_add_words(r, r, tmp, max);
}
-#ifdef BN_RECURSION
-/* r is 2*n words in size,
- * a and b are both n words in size. (There's not actually a 'b' here ...)
- * n must be a power of 2.
- * We multiply and return the result.
- * t must be 2*n words in size
- * We calculate
- * a[0]*b[0]
- * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
- * a[1]*b[1]
- */
-void
-bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t)
-{
- int n = n2 / 2;
- int zero, c1;
- BN_ULONG ln, lo, *p;
-
- if (n2 == 4) {
- bn_sqr_comba4(r, a);
- return;
- } else if (n2 == 8) {
- bn_sqr_comba8(r, a);
- return;
- }
- if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL) {
- bn_sqr_normal(r, a, n2, t);
- return;
- }
- /* r=(a[0]-a[1])*(a[1]-a[0]) */
- c1 = bn_cmp_words(a, &(a[n]), n);
- zero = 0;
- if (c1 > 0)
- bn_sub_words(t, a, &(a[n]), n);
- else if (c1 < 0)
- bn_sub_words(t, &(a[n]), a, n);
- else
- zero = 1;
-
- /* The result will always be negative unless it is zero */
- p = &(t[n2*2]);
-
- if (!zero)
- bn_sqr_recursive(&(t[n2]), t, n, p);
- else
- memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG));
- bn_sqr_recursive(r, a, n, p);
- bn_sqr_recursive(&(r[n2]), &(a[n]), n, p);
-
- /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- */
-
- c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
-
- /* t[32] is negative */
- c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
-
- /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
- * r[10] holds (a[0]*a[0])
- * r[32] holds (a[1]*a[1])
- * c1 holds the carry bits
- */
- c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
- if (c1) {
- p = &(r[n + n2]);
- lo= *p;
- ln = (lo + c1) & BN_MASK2;
- *p = ln;
-
- /* The overflow will stop before we over write
- * words we should not overwrite */
- if (ln < (BN_ULONG)c1) {
- do {
- p++;
- lo= *p;
- ln = (lo + 1) & BN_MASK2;
- *p = ln;
- } while (ln == 0);
- }
- }
-}
-#endif
/*
* bn_sqr() computes a * a, storing the result in r. The caller must ensure that
@@ -330,31 +246,9 @@ bn_sqr(BIGNUM *r, const BIGNUM *a, int rn, BN_CTX *ctx)
if ((tmp = BN_CTX_get(ctx)) == NULL)
goto err;
-#if defined(BN_RECURSION)
- if (a->top < BN_SQR_RECURSIVE_SIZE_NORMAL) {
- BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL*2];
- bn_sqr_normal(r->d, a->d, a->top, t);
- } else {
- int j, k;
-
- j = BN_num_bits_word((BN_ULONG)a->top);
- j = 1 << (j - 1);
- k = j + j;
- if (a->top == j) {
- if (!bn_wexpand(tmp, k * 2))
- goto err;
- bn_sqr_recursive(r->d, a->d, a->top, tmp->d);
- } else {
- if (!bn_wexpand(tmp, rn))
- goto err;
- bn_sqr_normal(r->d, a->d, a->top, tmp->d);
- }
- }
-#else
if (!bn_wexpand(tmp, rn))
goto err;
bn_sqr_normal(r->d, a->d, a->top, tmp->d);
-#endif
ret = 1;
--
cgit v1.2.3-55-g6feb