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