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@

5 files changed, 5 insertions, 594 deletions

diff --git a/lib/libcrypto/bn/bn.h b/lib/libcrypto/bn/bn.h
index bb85ea442cf..53b109bd8af 100644
--- a/lib/libcrypto/bn/bn.h
+++ b/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/lib/libcrypto/bn/bn_lib.c b/lib/libcrypto/bn/bn_lib.c
index f25caa04af9..89664fbb97b 100644
--- a/lib/libcrypto/bn/bn_lib.c
+++ b/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/lib/libcrypto/bn/bn_local.h b/lib/libcrypto/bn/bn_local.h
index 4912ae96f32..5e85dfc3de1 100644
--- a/lib/libcrypto/bn/bn_local.h
+++ b/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/lib/libcrypto/bn/bn_mul.c b/lib/libcrypto/bn/bn_mul.c
index fe3f29617fe..118e8cddc5e 100644
--- a/lib/libcrypto/bn/bn_mul.c
+++ b/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/lib/libcrypto/bn/bn_sqr.c b/lib/libcrypto/bn/bn_sqr.c
index d5da7752005..d414800feb3 100644
--- a/lib/libcrypto/bn/bn_sqr.c
+++ b/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;