From 66b5d1ec81433d4cbc218ed18f2e4ee04d51aa38 Mon Sep 17 00:00:00 2001 From: Michael Brown Date: Wed, 22 Jan 2025 12:54:52 +0000 Subject: [crypto] Add a generic implementation of a Montgomery ladder The Montgomery ladder may be used to perform any operation that is isomorphic to exponentiation, i.e. to compute the result r = g^e = g * g * g * g * .... * g for an arbitrary commutative operation "*", base or generator "g", and exponent "e". Implement a generic Montgomery ladder for use by both modular exponentiation and elliptic curve point multiplication (both of which are isomorphic to exponentiation). Signed-off-by: Michael Brown --- src/include/ipxe/bigint.h | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) (limited to 'src/include') diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h index 1cc606b89..410d0fd90 100644 --- a/src/include/ipxe/bigint.h +++ b/src/include/ipxe/bigint.h @@ -304,6 +304,24 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); (result)->element, size ); \ } while ( 0 ) +/** + * Perform generalised exponentiation via a Montgomery ladder + * + * @v result Big integer result (initialised to identity element) + * @v multiple Big integer multiple (initialised to generator) + * @v exponent Big integer exponent + * @v op Montgomery ladder commutative operation + * @v ctx Operation context (if needed) + * @v tmp Temporary working space (if needed) + */ +#define bigint_ladder( result, multiple, exponent, op, ctx, tmp ) do { \ + unsigned int size = bigint_size (result); \ + unsigned int exponent_size = bigint_size (exponent); \ + bigint_ladder_raw ( (result)->element, (multiple)->element, \ + size, (exponent)->element, exponent_size, \ + (op), (ctx), (tmp) ); \ + } while ( 0 ) + /** * Perform modular exponentiation of big integers * @@ -335,6 +353,20 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); #include +/** + * A big integer Montgomery ladder commutative operation + * + * @v operand Element 0 of first input operand (may overlap result) + * @v result Element 0 of second input operand and result + * @v size Number of elements in operands and result + * @v ctx Operation context (if needed) + * @v tmp Temporary working space (if needed) + */ +typedef void ( bigint_ladder_op_t ) ( const bigint_element_t *operand0, + bigint_element_t *result0, + unsigned int size, const void *ctx, + void *tmp ); + /** * Test if bit is set in big integer * @@ -422,6 +454,14 @@ int bigint_montgomery_relaxed_raw ( const bigint_element_t *modulus0, void bigint_montgomery_raw ( const bigint_element_t *modulus0, bigint_element_t *value0, bigint_element_t *result0, unsigned int size ); +void bigint_ladder_raw ( bigint_element_t *result0, + bigint_element_t *multiple0, unsigned int size, + const bigint_element_t *exponent0, + unsigned int exponent_size, bigint_ladder_op_t *op, + const void *ctx, void *tmp ); +void bigint_mod_exp_ladder ( const bigint_element_t *multiplier0, + bigint_element_t *result0, unsigned int size, + const void *ctx, void *tmp ); void bigint_mod_exp_raw ( const bigint_element_t *base0, const bigint_element_t *modulus0, const bigint_element_t *exponent0, -- cgit v1.2.3-55-g7522