Implement EC field element operations.

Provide EC_FIELD_ELEMENT and EC_FIELD_MODULUS, which allow for operations
on fixed width fields in constant time. These can in turn be used to
implement Elliptic Curve cryptography for prime fields, without needing
to use BN. This will improve the code, reduces timing leaks and enable
further optimisation.

ok beck@ tb@

5 files changed, 299 insertions, 31 deletions

diff --git a/src/lib/libcrypto/Makefile b/src/lib/libcrypto/Makefile
index dd64f07f48..7564001961 100644
--- a/src/lib/libcrypto/Makefile
+++ b/src/lib/libcrypto/Makefile
@@ -1,4 +1,4 @@
-# $OpenBSD: Makefile,v 1.233 2025/05/25 04:58:32 jsing Exp $
+# $OpenBSD: Makefile,v 1.234 2025/05/25 05:12:05 jsing Exp $
 
 LIB=    crypto
 LIBREBUILD=y
@@ -283,6 +283,7 @@ SRCS+= ec_asn1.c
 SRCS+= ec_convert.c
 SRCS+= ec_curve.c
 SRCS+= ec_err.c
+SRCS+= ec_field.c
 SRCS+= ec_key.c
 SRCS+= ec_lib.c
 SRCS+= ec_mult.c
diff --git a/src/lib/libcrypto/bn/bn_internal.h b/src/lib/libcrypto/bn/bn_internal.h
index b6e903553f..a1f1515b57 100644
--- a/src/lib/libcrypto/bn/bn_internal.h
+++ b/src/lib/libcrypto/bn/bn_internal.h
@@ -1,4 +1,4 @@
-/*      $OpenBSD: bn_internal.h,v 1.18 2025/05/25 04:58:32 jsing Exp $ */
+/*      $OpenBSD: bn_internal.h,v 1.19 2025/05/25 05:12:05 jsing Exp $ */
 /*
  * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
  *
@@ -45,6 +45,8 @@ void bn_mod_mul_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
 void bn_montgomery_multiply_words(BN_ULONG *rp, const BN_ULONG *ap,
     const BN_ULONG *bp, const BN_ULONG *np, BN_ULONG *tp, BN_ULONG n0,
     int n_len);
+void bn_montgomery_reduce_words(BN_ULONG *r, BN_ULONG *a, const BN_ULONG *n,
+    BN_ULONG n0, int n_len);
 
 #ifndef HAVE_BN_CT_NE_ZERO
 static inline int
diff --git a/src/lib/libcrypto/bn/bn_mont.c b/src/lib/libcrypto/bn/bn_mont.c
index ce88b23ca9..950846fa5b 100644
--- a/src/lib/libcrypto/bn/bn_mont.c
+++ b/src/lib/libcrypto/bn/bn_mont.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_mont.c,v 1.67 2025/05/25 04:58:32 jsing Exp $ */
+/* $OpenBSD: bn_mont.c,v 1.68 2025/05/25 05:12:05 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -316,6 +316,44 @@ BN_MONT_CTX_set_locked(BN_MONT_CTX **pmctx, int lock, const BIGNUM *mod,
 LCRYPTO_ALIAS(BN_MONT_CTX_set_locked);
 
 /*
+ * bn_montgomery_reduce_words() performs Montgomery reduction, reducing the input
+ * from its Montgomery form aR to a, returning the result in r. a must be twice
+ * the length of the modulus. Note that the input is mutated in the process of
+ * performing the reduction.
+ */
+void
+bn_montgomery_reduce_words(BN_ULONG *r, BN_ULONG *a, const BN_ULONG *n,
+    BN_ULONG n0, int n_len)
+{
+        BN_ULONG v, mask;
+        BN_ULONG carry = 0;
+        int i;
+
+        /* Add multiples of the modulus, so that it becomes divisible by R. */
+        for (i = 0; i < n_len; i++) {
+                v = bn_mul_add_words(&a[i], n, n_len, a[i] * n0);
+                bn_addw_addw(v, a[i + n_len], carry, &carry, &a[i + n_len]);
+        }
+
+        /* Divide by R (this is the equivalent of right shifting by n_len). */
+        a = &a[n_len];
+
+        /*
+         * The output is now in the range of [0, 2N). Attempt to reduce once by
+         * subtracting the modulus. If the reduction was necessary then the
+         * result is already in r, otherwise copy the value prior to reduction
+         * from the top half of a.
+         */
+        mask = carry - bn_sub_words(r, a, n, n_len);
+
+        for (i = 0; i < n_len; i++) {
+                *r = (*r & ~mask) | (*a & mask);
+                r++;
+                a++;
+        }
+}
+
+/*
  * bn_montgomery_reduce() performs Montgomery reduction, reducing the input
  * from its Montgomery form aR to a, returning the result in r. Note that the
  * input is mutated in the process of performing the reduction, destroying its
@@ -325,7 +363,6 @@ static int
 bn_montgomery_reduce(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mctx)
 {
         BIGNUM *n;
-        BN_ULONG *ap, *rp, n0, v, carry, mask;
         int i, max, n_len;
 
         n = &mctx->N;
@@ -341,7 +378,8 @@ bn_montgomery_reduce(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mctx)
 
         /*
          * Expand a to twice the length of the modulus, zero if necessary.
-         * XXX - make this a requirement of the caller.
+         * XXX - make this a requirement of the caller or use a temporary
+         * allocation.
          */
         if ((max = 2 * n_len) < n_len)
                 return 0;
@@ -350,33 +388,8 @@ bn_montgomery_reduce(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mctx)
         for (i = a->top; i < max; i++)
                 a->d[i] = 0;
 
-        carry = 0;
-        n0 = mctx->n0[0];
-
-        /* Add multiples of the modulus, so that it becomes divisible by R. */
-        for (i = 0; i < n_len; i++) {
-                v = bn_mul_add_words(&a->d[i], n->d, n_len, a->d[i] * n0);
-                bn_addw_addw(v, a->d[i + n_len], carry, &carry,
-                    &a->d[i + n_len]);
-        }
-
-        /* Divide by R (this is the equivalent of right shifting by n_len). */
-        ap = &a->d[n_len];
-
-        /*
-         * The output is now in the range of [0, 2N). Attempt to reduce once by
-         * subtracting the modulus. If the reduction was necessary then the
-         * result is already in r, otherwise copy the value prior to reduction
-         * from the top half of a.
-         */
-        mask = carry - bn_sub_words(r->d, ap, n->d, n_len);
+        bn_montgomery_reduce_words(r->d, a->d, n->d, mctx->n0[0], n_len);
 
-        rp = r->d;
-        for (i = 0; i < n_len; i++) {
-                *rp = (*rp & ~mask) | (*ap & mask);
-                rp++;
-                ap++;
-        }
         r->top = n_len;
 
         bn_correct_top(r);
diff --git a/src/lib/libcrypto/ec/ec_field.c b/src/lib/libcrypto/ec/ec_field.c
new file mode 100644
index 0000000000..ec1c7d11e0
--- /dev/null
+++ b/src/lib/libcrypto/ec/ec_field.c
@@ -0,0 +1,189 @@
+/*      $OpenBSD: ec_field.c,v 1.1 2025/05/25 05:12:05 jsing Exp $      */
+/*
+ * Copyright (c) 2024 Joel Sing <jsing@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <string.h>
+
+#include <openssl/ec.h>
+
+#include "bn_local.h"
+#include "bn_internal.h"
+#include "ec_local.h"
+#include "ec_internal.h"
+
+int
+ec_field_modulus_from_bn(EC_FIELD_MODULUS *fm, const BIGNUM *bn, BN_CTX *ctx)
+{
+        BN_MONT_CTX *mctx = NULL;
+        size_t i;
+        int ret = 0;
+
+        if (BN_is_negative(bn))
+                goto err;
+        if (BN_num_bits(bn) > EC_FIELD_ELEMENT_MAX_BITS)
+                goto err;
+
+        memset(fm, 0, sizeof(*fm));
+
+        fm->n = (BN_num_bits(bn) + BN_BITS2 - 1) / BN_BITS2;
+
+        for (i = 0; i < bn->top; i++)
+                fm->m.w[i] = bn->d[i];
+
+        /* XXX - implement this without BN_MONT_CTX. */
+        if ((mctx = BN_MONT_CTX_new()) == NULL)
+                goto err;
+        if (!BN_MONT_CTX_set(mctx, bn, ctx))
+                goto err;
+
+        for (i = 0; i < mctx->RR.top; i++)
+                fm->rr.w[i] = mctx->RR.d[i];
+
+        fm->minv0 = mctx->n0[0];
+
+        ret = 1;
+
+ err:
+        BN_MONT_CTX_free(mctx);
+
+        return ret;
+}
+
+int
+ec_field_element_from_bn(const EC_FIELD_MODULUS *fm, const EC_GROUP *group,
+    EC_FIELD_ELEMENT *fe, const BIGNUM *bn, BN_CTX *ctx)
+{
+        BN_ULONG t[EC_FIELD_ELEMENT_MAX_WORDS * 2 + 2];
+        BIGNUM *tmp;
+        size_t i;
+        int ret = 0;
+
+        BN_CTX_start(ctx);
+
+        if ((tmp = BN_CTX_get(ctx)) == NULL)
+                goto err;
+
+        /* XXX - enforce 0 <= n < p. */
+
+        if (BN_num_bits(bn) > EC_FIELD_ELEMENT_MAX_BITS)
+                goto err;
+
+        /* XXX - do this without BN. */
+        if (!BN_nnmod(tmp, bn, group->p, ctx))
+                goto err;
+
+        if (BN_num_bits(tmp) > EC_FIELD_ELEMENT_MAX_BITS)
+                abort();
+
+        memset(fe->w, 0, sizeof(fe->w));
+
+        for (i = 0; i < tmp->top; i++)
+                fe->w[i] = tmp->d[i];
+
+        bn_mod_mul_words(fe->w, fe->w, fm->rr.w, fm->m.w, t, fm->minv0, fm->n);
+
+        ret = 1;
+
+ err:
+        BN_CTX_end(ctx);
+
+        return ret;
+}
+
+int
+ec_field_element_to_bn(const EC_FIELD_MODULUS *fm, const EC_FIELD_ELEMENT *fe,
+    BIGNUM *bn, BN_CTX *ctx)
+{
+        BN_ULONG t[EC_FIELD_ELEMENT_MAX_WORDS * 2 + 2];
+        size_t i;
+
+        if (!bn_wexpand(bn, fm->n))
+                return 0;
+
+        memset(t, 0, sizeof(t));
+        for (i = 0; i < fm->n; i++)
+                t[i] = fe->w[i];
+
+        bn_montgomery_reduce_words(bn->d, t, fm->m.w, fm->minv0, fm->n);
+
+        bn->top = fm->n;
+        bn_correct_top(bn);
+
+        return 1;
+}
+
+void
+ec_field_element_copy(EC_FIELD_ELEMENT *dst, const EC_FIELD_ELEMENT *src)
+{
+        memcpy(dst, src, sizeof(EC_FIELD_ELEMENT));
+}
+
+int
+ec_field_element_equal(const EC_FIELD_MODULUS *fm, const EC_FIELD_ELEMENT *a,
+    const EC_FIELD_ELEMENT *b)
+{
+        BN_ULONG v = 0;
+        int i;
+
+        for (i = 0; i < fm->n; i++)
+                v |= a->w[i] ^ b->w[i];
+
+        return bn_ct_eq_zero(v);
+}
+
+int
+ec_field_element_is_zero(const EC_FIELD_MODULUS *fm, const EC_FIELD_ELEMENT *fe)
+{
+        BN_ULONG v = 0;
+        int i;
+
+        for (i = 0; i < fm->n; i++)
+                v |= fe->w[i];
+
+        return bn_ct_eq_zero(v);
+}
+
+void
+ec_field_element_add(const EC_FIELD_MODULUS *m, EC_FIELD_ELEMENT *r,
+    const EC_FIELD_ELEMENT *a, const EC_FIELD_ELEMENT *b)
+{
+        bn_mod_add_words(r->w, a->w, b->w, m->m.w, m->n);
+}
+
+void
+ec_field_element_sub(const EC_FIELD_MODULUS *m, EC_FIELD_ELEMENT *r,
+    const EC_FIELD_ELEMENT *a, const EC_FIELD_ELEMENT *b)
+{
+        bn_mod_sub_words(r->w, a->w, b->w, m->m.w, m->n);
+}
+
+void
+ec_field_element_mul(const EC_FIELD_MODULUS *m, EC_FIELD_ELEMENT *r,
+    const EC_FIELD_ELEMENT *a, const EC_FIELD_ELEMENT *b)
+{
+        BN_ULONG t[EC_FIELD_ELEMENT_MAX_WORDS * 2 + 2];
+
+        bn_mod_mul_words(r->w, a->w, b->w, m->m.w, t, m->minv0, m->n);
+}
+
+void
+ec_field_element_sqr(const EC_FIELD_MODULUS *m, EC_FIELD_ELEMENT *r,
+    const EC_FIELD_ELEMENT *a)
+{
+        BN_ULONG t[EC_FIELD_ELEMENT_MAX_WORDS * 2 + 2];
+
+        bn_mod_mul_words(r->w, a->w, a->w, m->m.w, t, m->minv0, m->n);
+}
diff --git a/src/lib/libcrypto/ec/ec_internal.h b/src/lib/libcrypto/ec/ec_internal.h
new file mode 100644
index 0000000000..29b447e8c9
--- /dev/null
+++ b/src/lib/libcrypto/ec/ec_internal.h
@@ -0,0 +1,63 @@
+/*      $OpenBSD: ec_internal.h,v 1.1 2025/05/25 05:12:05 jsing Exp $   */
+/*
+ * Copyright (c) 2024 Joel Sing <jsing@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <openssl/bn.h>
+
+#ifndef HEADER_EC_INTERNAL_H
+#define HEADER_EC_INTERNAL_H
+
+#define EC_FIELD_ELEMENT_MAX_BITS 521
+#define EC_FIELD_ELEMENT_MAX_BYTES \
+    (EC_FIELD_ELEMENT_MAX_BITS + 7) / 8
+#define EC_FIELD_ELEMENT_MAX_WORDS \
+    ((EC_FIELD_ELEMENT_MAX_BYTES + BN_BYTES - 1) / BN_BYTES)
+
+typedef struct {
+        BN_ULONG w[EC_FIELD_ELEMENT_MAX_WORDS];
+} EC_FIELD_ELEMENT;
+
+typedef struct {
+        size_t n;
+        EC_FIELD_ELEMENT m;
+        EC_FIELD_ELEMENT rr;
+        BN_ULONG minv0;
+} EC_FIELD_MODULUS;
+
+int ec_field_modulus_from_bn(EC_FIELD_MODULUS *fm, const BIGNUM *bn,
+    BN_CTX *ctx);
+
+int ec_field_element_from_bn(const EC_FIELD_MODULUS *fm, const EC_GROUP *group,
+    EC_FIELD_ELEMENT *fe, const BIGNUM *bn, BN_CTX *ctx);
+int ec_field_element_to_bn(const EC_FIELD_MODULUS *fm, const EC_FIELD_ELEMENT *fe,
+    BIGNUM *bn, BN_CTX *ctx);
+
+void ec_field_element_copy(EC_FIELD_ELEMENT *dst, const EC_FIELD_ELEMENT *src);
+
+int ec_field_element_equal(const EC_FIELD_MODULUS *fm, const EC_FIELD_ELEMENT *a,
+    const EC_FIELD_ELEMENT *b);
+int ec_field_element_is_zero(const EC_FIELD_MODULUS *fm, const EC_FIELD_ELEMENT *fe);
+
+void ec_field_element_add(const EC_FIELD_MODULUS *m, EC_FIELD_ELEMENT *r,
+    const EC_FIELD_ELEMENT *a, const EC_FIELD_ELEMENT *b);
+void ec_field_element_sub(const EC_FIELD_MODULUS *m, EC_FIELD_ELEMENT *r,
+    const EC_FIELD_ELEMENT *a, const EC_FIELD_ELEMENT *b);
+void ec_field_element_mul(const EC_FIELD_MODULUS *m, EC_FIELD_ELEMENT *r,
+    const EC_FIELD_ELEMENT *a, const EC_FIELD_ELEMENT *b);
+void ec_field_element_sqr(const EC_FIELD_MODULUS *m, EC_FIELD_ELEMENT *r,
+    const EC_FIELD_ELEMENT *a);
+
+#endif