[crypto] Add support for Weierstrass elliptic curve point multiplication

The NIST elliptic curves are Weierstrass curves and have the form

  y^2 = x^3 + ax + b

with each curve defined by its field prime, the constants "a" and "b",
and a generator base point.

Implement a constant-time algorithm for point addition, based upon
Algorithm 1 from "Complete addition formulas for prime order elliptic
curves" (Joost Renes, Craig Costello, and Lejla Batina), and use this
as a Montgomery ladder commutative operation to perform constant-time
point multiplication.

The code for point addition is implemented using a custom bytecode
interpreter with 16-bit instructions, since this results in
substantially smaller code than compiling the somewhat lengthy
sequence of arithmetic operations directly.  Values are calculated
modulo small multiples of the field prime in order to allow for the
use of relaxed Montgomery reduction.

Signed-off-by: Michael Brown <mcb30@ipxe.org>

2 files changed, 167 insertions, 0 deletions

diff --git a/src/include/ipxe/errfile.h b/src/include/ipxe/errfile.h
index 48b35c537..b826a4a6f 100644
--- a/src/include/ipxe/errfile.h
+++ b/src/include/ipxe/errfile.h
@@ -426,6 +426,7 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
 #define ERRFILE_form_ui		      ( ERRFILE_OTHER | 0x00630000 )
 #define ERRFILE_usb_cmd		      ( ERRFILE_OTHER | 0x00640000 )
 #define ERRFILE_usb_settings	      ( ERRFILE_OTHER | 0x00650000 )
+#define ERRFILE_weierstrass	      ( ERRFILE_OTHER | 0x00660000 )
 
 /** @} */
 
diff --git a/src/include/ipxe/weierstrass.h b/src/include/ipxe/weierstrass.h
new file mode 100644
index 000000000..fb09fa6fa
--- /dev/null
+++ b/src/include/ipxe/weierstrass.h
@@ -0,0 +1,166 @@
+#ifndef _IPXE_WEIERSTRASS_H
+#define _IPXE_WEIERSTRASS_H
+
+/** @file
+ *
+ * Weierstrass elliptic curves
+ *
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
+
+#include <ipxe/bigint.h>
+#include <ipxe/crypto.h>
+
+/** Number of axes in Weierstrass curve point representation */
+#define WEIERSTRASS_AXES 2
+
+/**
+ * Maximum multiple of field prime encountered during calculations
+ *
+ * Calculations are performed using values modulo a small multiple of
+ * the field prime, rather than modulo the field prime itself.  This
+ * allows explicit reductions after additions, subtractions, and
+ * relaxed Montgomery multiplications to be omitted entirely, provided
+ * that we keep careful track of the field prime multiple for each
+ * intermediate value.
+ *
+ * Relaxed Montgomery multiplication will produce a result in the
+ * range t < (1+m/k)N, where m is this maximum multiple of the field
+ * prime, and k is the constant in R > kN representing the leading
+ * zero padding in the big integer representation of the field prime.
+ * We choose to set k=m so that multiplications will always produce a
+ * result in the range t < 2N.
+ *
+ * This is expressed as the base-two logarithm of the multiple
+ * (rounded up), to simplify compile-time calculations.
+ */
+#define WEIERSTRASS_MAX_MULTIPLE_LOG2 5 /* maximum reached is mod 20N */
+
+/**
+ * Determine number of elements in scalar values for a Weierstrass curve
+ *
+ * @v len		Length of field prime, in bytes
+ * @ret size		Number of elements
+ */
+#define weierstrass_size( len )						\
+	bigint_required_size ( (len) +					\
+			       ( ( WEIERSTRASS_MAX_MULTIPLE_LOG2 + 7 )	\
+				 / 8 ) )
+
+/**
+ * Define a Weierstrass projective co-ordinate type
+ *
+ * @v size		Number of elements in scalar values
+ * @ret weierstrass_t	Projective co-ordinate type
+ */
+#define weierstrass_t( size )						\
+	union {								\
+		bigint_t ( size ) axis[3];				\
+		struct {						\
+			bigint_t ( size ) x;				\
+			bigint_t ( size ) y;				\
+			bigint_t ( size ) z;				\
+		};							\
+		bigint_t ( size * 3 ) all;				\
+	}
+
+/** Indexes for stored multiples of the field prime */
+enum weierstrass_multiple {
+	WEIERSTRASS_N = 0,
+	WEIERSTRASS_2N,
+	WEIERSTRASS_4N,
+	WEIERSTRASS_NUM_MULTIPLES
+};
+
+/** Number of cached in Montgomery form for each Weierstrass curve */
+#define WEIERSTRASS_NUM_MONT 3
+
+/** Number of cached big integers for each Weierstrass curve */
+#define WEIERSTRASS_NUM_CACHED						\
+	( WEIERSTRASS_NUM_MULTIPLES +					\
+	  1 /* fermat */ + 1 /* mont */ +				\
+	  WEIERSTRASS_NUM_MONT )
+
+/**
+ * A Weierstrass elliptic curve
+ *
+ * This is an elliptic curve y^2 = x^3 + ax + b
+ */
+struct weierstrass_curve {
+	/** Number of elements in scalar values */
+	const unsigned int size;
+	/** Curve name */
+	const char *name;
+	/** Length of raw scalar values */
+	size_t len;
+	/** Field prime */
+	const uint8_t *prime_raw;
+	/** Constant "a" */
+	const uint8_t *a_raw;
+	/** Constant "b" */
+	const uint8_t *b_raw;
+	/** Base point */
+	const uint8_t *base;
+
+	/** Cached field prime "N" (and multiples thereof) */
+	bigint_element_t *prime[WEIERSTRASS_NUM_CACHED];
+	/** Cached constant "N-2" (for Fermat's little theorem) */
+	bigint_element_t *fermat;
+	/** Cached Montgomery constant (R^2 mod N) */
+	bigint_element_t *square;
+	/** Cached constants in Montgomery form */
+	union {
+		struct {
+			/** Cached constant "1", in Montgomery form */
+			bigint_element_t *one;
+			/** Cached constant "a", in Montgomery form */
+			bigint_element_t *a;
+			/** Cached constant "3b", in Montgomery form */
+			bigint_element_t *b3;
+		};
+		bigint_element_t *mont[WEIERSTRASS_NUM_MONT];
+	};
+};
+
+extern int weierstrass_multiply ( struct weierstrass_curve *curve,
+				  const void *base, const void *scalar,
+				  void *result );
+
+/** Define a Weierstrass curve */
+#define WEIERSTRASS_CURVE( _name, _curve, _len, _prime, _a, _b, _base )	\
+	static bigint_t ( weierstrass_size(_len) )			\
+		_name ## _cache[WEIERSTRASS_NUM_CACHED];		\
+	static struct weierstrass_curve _name ## _weierstrass = {	\
+		.size = weierstrass_size(_len),				\
+		.name = #_name,						\
+		.len = (_len),						\
+		.prime_raw = (_prime),					\
+		.a_raw = (_a),						\
+		.b_raw = (_b),						\
+		.base = (_base),					\
+		.prime = {						\
+			(_name ## _cache)[0].element,			\
+			(_name ## _cache)[1].element,			\
+			(_name ## _cache)[2].element,			\
+		},							\
+		.fermat = (_name ## _cache)[3].element,			\
+		.square = (_name ## _cache)[4].element,			\
+		.one = (_name ## _cache)[5].element,			\
+		.a = (_name ## _cache)[6].element,			\
+		.b3 = (_name ## _cache)[7].element,			\
+	};								\
+	static int _name ## _multiply ( const void *base,		\
+					const void *scalar,		\
+					void *result ) {		\
+		return weierstrass_multiply ( &_name ## _weierstrass,	\
+					      base, scalar, result );	\
+	}								\
+	struct elliptic_curve _curve = {				\
+		.name = #_name,						\
+		.pointsize = ( WEIERSTRASS_AXES * (_len) ),		\
+		.keysize = (_len),					\
+		.multiply = _name ## _multiply,				\
+	}
+
+#endif /* _IPXE_WEIERSTRASS_H */