From 1f279c5e8c7d20419cf0d309f20c1a9bef82881f Mon Sep 17 00:00:00 2001
From: tb <tb@openbsd.org>
Date: Mon, 3 Apr 2023 21:43:43 +0000
Subject: [PATCH] Compress euclid() a little

This function is spread out over way too many lines and has too much
repetition. Once this is made a little more compact, it becomes clearer
that this is a somewhat obfuscated version of binary gcd (it is not
constant time therefore cryptographically unsound. It is not used
internally). This will likely go away later.

ok jsing
---
 lib/libcrypto/bn/bn_gcd.c | 77 ++++++++++++++-------------------------
 1 file changed, 28 insertions(+), 49 deletions(-)

diff --git a/lib/libcrypto/bn/bn_gcd.c b/lib/libcrypto/bn/bn_gcd.c
index 905178913c6..e741ef37dc3 100644
--- a/lib/libcrypto/bn/bn_gcd.c
+++ b/lib/libcrypto/bn/bn_gcd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_gcd.c,v 1.25 2023/04/01 11:10:55 tb Exp $ */
+/* $OpenBSD: bn_gcd.c,v 1.26 2023/04/03 21:43:43 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -119,65 +119,44 @@ euclid(BIGNUM *a, BIGNUM *b)
 	BIGNUM *t;
 	int shifts = 0;
 
-
-	/* 0 <= b <= a */
+	/* Loop invariant: 0 <= b <= a. */
 	while (!BN_is_zero(b)) {
-		/* 0 < b <= a */
-
-		if (BN_is_odd(a)) {
-			if (BN_is_odd(b)) {
-				if (!BN_sub(a, a, b))
-					goto err;
-				if (!BN_rshift1(a, a))
-					goto err;
-				if (BN_cmp(a, b) < 0) {
-					t = a;
-					a = b;
-					b = t;
-				}
-			}
-			else		/* a odd - b even */
-			{
-				if (!BN_rshift1(b, b))
-					goto err;
-				if (BN_cmp(a, b) < 0) {
-					t = a;
-					a = b;
-					b = t;
-				}
-			}
+		if (BN_is_odd(a) && BN_is_odd(b)) {
+			if (!BN_sub(a, a, b))
+				goto err;
+			if (!BN_rshift1(a, a))
+				goto err;
+		} else if (BN_is_odd(a) && !BN_is_odd(b)) {
+			if (!BN_rshift1(b, b))
+				goto err;
+		} else if (!BN_is_odd(a) && BN_is_odd(b)) {
+			if (!BN_rshift1(a, a))
+				goto err;
+		} else {
+			if (!BN_rshift1(a, a))
+				goto err;
+			if (!BN_rshift1(b, b))
+				goto err;
+			shifts++;
+			continue;
 		}
-		else			/* a is even */
-		{
-			if (BN_is_odd(b)) {
-				if (!BN_rshift1(a, a))
-					goto err;
-				if (BN_cmp(a, b) < 0) {
-					t = a;
-					a = b;
-					b = t;
-				}
-			}
-			else		/* a even - b even */
-			{
-				if (!BN_rshift1(a, a))
-					goto err;
-				if (!BN_rshift1(b, b))
-					goto err;
-				shifts++;
-			}
+
+		if (BN_cmp(a, b) < 0) {
+			t = a;
+			a = b;
+			b = t;
 		}
-		/* 0 <= b <= a */
 	}
 
 	if (shifts) {
 		if (!BN_lshift(a, a, shifts))
 			goto err;
 	}
-	return (a);
+
+	return a;
 
  err:
-	return (NULL);
+	return NULL;
 }
 
 int
-- 
2.20.1