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

1 files changed, 28 insertions, 49 deletions

diff --git a/src/lib/libcrypto/bn/bn_gcd.c b/src/lib/libcrypto/bn/bn_gcd.c
index 905178913c..e741ef37dc 100644
--- a/src/lib/libcrypto/bn/bn_gcd.c
+++ b/src/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