aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/crypto/bigint.c71
-rw-r--r--src/include/ipxe/bigint.h34
-rw-r--r--src/tests/bigint_test.c84
3 files changed, 72 insertions, 117 deletions
diff --git a/src/crypto/bigint.c b/src/crypto/bigint.c
index 35701a1d0..4b37c062b 100644
--- a/src/crypto/bigint.c
+++ b/src/crypto/bigint.c
@@ -139,32 +139,20 @@ void bigint_multiply_raw ( const bigint_element_t *multiplicand0,
/**
* Reduce big integer
*
- * @v minuend0 Element 0 of big integer to be reduced
- * @v minuend_size Number of elements in minuend
* @v modulus0 Element 0 of big integer modulus
- * @v modulus_size Number of elements in modulus and result
- * @v result0 Element 0 of big integer to hold result
- * @v tmp Temporary working space
+ * @v value0 Element 0 of big integer to be reduced
+ * @v size Number of elements in modulus and value
*/
-void bigint_reduce_raw ( const bigint_element_t *minuend0,
- unsigned int minuend_size,
- const bigint_element_t *modulus0,
- unsigned int modulus_size,
- bigint_element_t *result0, void *tmp ) {
- const bigint_t ( minuend_size ) __attribute__ (( may_alias ))
- *minuend = ( ( const void * ) minuend0 );
- const bigint_t ( modulus_size ) __attribute__ (( may_alias ))
- *modulus = ( ( const void * ) modulus0 );
- bigint_t ( modulus_size ) __attribute__ (( may_alias ))
- *result = ( ( void * ) result0 );
- struct {
- bigint_t ( minuend_size ) minuend;
- bigint_t ( minuend_size ) modulus;
- } *temp = tmp;
+void bigint_reduce_raw ( bigint_element_t *modulus0, bigint_element_t *value0,
+ unsigned int size ) {
+ bigint_t ( size ) __attribute__ (( may_alias ))
+ *modulus = ( ( void * ) modulus0 );
+ bigint_t ( size ) __attribute__ (( may_alias ))
+ *value = ( ( void * ) value0 );
const unsigned int width = ( 8 * sizeof ( bigint_element_t ) );
bigint_element_t *element;
- unsigned int minuend_max;
unsigned int modulus_max;
+ unsigned int value_max;
unsigned int subshift;
int offset;
int shift;
@@ -174,31 +162,23 @@ void bigint_reduce_raw ( const bigint_element_t *minuend0,
/* Start profiling */
profile_start ( &bigint_mod_profiler );
- /* Sanity check */
- assert ( minuend_size >= modulus_size );
- assert ( sizeof ( *temp ) == bigint_reduce_tmp_len ( minuend ) );
-
- /* Copy minuend and modulus to temporary working space */
- bigint_shrink ( minuend, &temp->minuend );
- bigint_grow ( modulus, &temp->modulus );
-
/* Normalise the modulus
*
* Scale the modulus by shifting left such that both modulus
- * "m" and minuend "x" have the same most significant set bit.
- * (If this is not possible, then the minuend is already less
+ * "m" and value "x" have the same most significant set bit.
+ * (If this is not possible, then the value is already less
* than the modulus, and we may therefore skip reduction
* completely.)
*/
- minuend_max = bigint_max_set_bit ( minuend );
+ value_max = bigint_max_set_bit ( value );
modulus_max = bigint_max_set_bit ( modulus );
- shift = ( minuend_max - modulus_max );
+ shift = ( value_max - modulus_max );
if ( shift < 0 )
goto skip;
subshift = ( shift & ( width - 1 ) );
offset = ( shift / width );
- element = temp->modulus.element;
- for ( i = ( ( minuend_max - 1 ) / width ) ; ; i-- ) {
+ element = modulus->element;
+ for ( i = ( ( value_max - 1 ) / width ) ; ; i-- ) {
element[i] = ( element[ i - offset ] << subshift );
if ( i <= offset )
break;
@@ -210,14 +190,14 @@ void bigint_reduce_raw ( const bigint_element_t *minuend0,
for ( i-- ; i >= 0 ; i-- )
element[i] = 0;
- /* Reduce the minuend "x" by iteratively adding or subtracting
+ /* Reduce the value "x" by iteratively adding or subtracting
* the scaled modulus "m".
*
* On each loop iteration, we maintain the invariant:
*
* -2m <= x < 2m
*
- * If x is positive, we obtain the new minuend x' by
+ * If x is positive, we obtain the new value x' by
* subtracting m, otherwise we add m:
*
* 0 <= x < 2m => x' := x - m => -m <= x' < m
@@ -284,21 +264,18 @@ void bigint_reduce_raw ( const bigint_element_t *minuend0,
*/
for ( msb = 0 ; ( msb || ( shift >= 0 ) ) ; shift-- ) {
if ( msb ) {
- bigint_add ( &temp->modulus, &temp->minuend );
+ bigint_add ( modulus, value );
} else {
- bigint_subtract ( &temp->modulus, &temp->minuend );
+ bigint_subtract ( modulus, value );
}
- msb = bigint_msb_is_set ( &temp->minuend );
+ msb = bigint_msb_is_set ( value );
if ( shift > 0 )
- bigint_shr ( &temp->modulus );
+ bigint_shr ( modulus );
}
skip:
/* Sanity check */
- assert ( ! bigint_is_geq ( &temp->minuend, &temp->modulus ) );
-
- /* Copy result */
- bigint_shrink ( &temp->minuend, result );
+ assert ( ! bigint_is_geq ( value, modulus ) );
/* Stop profiling */
profile_stop ( &bigint_mod_profiler );
@@ -396,7 +373,9 @@ void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0,
bigint_multiply ( multiplicand, multiplier, &temp->result );
/* Reduce result */
- bigint_reduce ( &temp->result, modulus, result, temp );
+ bigint_grow ( modulus, &temp->modulus );
+ bigint_reduce ( &temp->modulus, &temp->result );
+ bigint_shrink ( &temp->result, result );
/* Sanity check */
assert ( ! bigint_is_geq ( result, modulus ) );
diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h
index 2a0a200c5..330d7deec 100644
--- a/src/include/ipxe/bigint.h
+++ b/src/include/ipxe/bigint.h
@@ -232,33 +232,16 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
/**
* Reduce big integer
*
- * @v minuend Big integer to be reduced
* @v modulus Big integer modulus
- * @v result Big integer to hold result
- * @v tmp Temporary working space
+ * @v value Big integer to be reduced
*/
-#define bigint_reduce( minuend, modulus, result, tmp ) do { \
- unsigned int minuend_size = bigint_size (minuend); \
- unsigned int modulus_size = bigint_size (modulus); \
- bigint_reduce_raw ( (minuend)->element, minuend_size, \
- (modulus)->element, modulus_size, \
- (result)->element, tmp ); \
+#define bigint_reduce( modulus, value ) do { \
+ unsigned int size = bigint_size (modulus); \
+ bigint_reduce_raw ( (modulus)->element, \
+ (value)->element, size ); \
} while ( 0 )
/**
- * Calculate temporary working space required for reduction
- *
- * @v minuend Big integer to be reduced
- * @ret len Length of temporary working space
- */
-#define bigint_reduce_tmp_len( minuend ) ( { \
- unsigned int size = bigint_size (minuend); \
- sizeof ( struct { \
- bigint_t ( size ) temp_minuend; \
- bigint_t ( size ) temp_modulus; \
- } ); } )
-
-/**
* Compute inverse of odd big integer modulo its own size
*
* @v invertend Odd big integer to be inverted
@@ -422,11 +405,8 @@ void bigint_multiply_raw ( const bigint_element_t *multiplicand0,
const bigint_element_t *multiplier0,
unsigned int multiplier_size,
bigint_element_t *result0 );
-void bigint_reduce_raw ( const bigint_element_t *minuend0,
- unsigned int minuend_size,
- const bigint_element_t *modulus0,
- unsigned int modulus_size,
- bigint_element_t *result0, void *tmp );
+void bigint_reduce_raw ( bigint_element_t *modulus0, bigint_element_t *value0,
+ unsigned int size );
void bigint_mod_invert_raw ( const bigint_element_t *invertend0,
bigint_element_t *inverse0,
unsigned int size, void *tmp );
diff --git a/src/tests/bigint_test.c b/src/tests/bigint_test.c
index 271d76723..61f78fff9 100644
--- a/src/tests/bigint_test.c
+++ b/src/tests/bigint_test.c
@@ -185,19 +185,14 @@ void bigint_multiply_sample ( const bigint_element_t *multiplicand0,
bigint_multiply ( multiplicand, multiplier, result );
}
-void bigint_reduce_sample ( const bigint_element_t *minuend0,
- unsigned int minuend_size,
- const bigint_element_t *modulus0,
- unsigned int modulus_size,
- bigint_element_t *result0, void *tmp ) {
- const bigint_t ( minuend_size ) __attribute__ (( may_alias ))
- *minuend = ( ( const void * ) minuend0 );
- const bigint_t ( modulus_size ) __attribute__ (( may_alias ))
- *modulus = ( ( const void * ) modulus0 );
- bigint_t ( modulus_size ) __attribute__ (( may_alias ))
- *result = ( ( void * ) result0 );
+void bigint_reduce_sample ( bigint_element_t *modulus0,
+ bigint_element_t *value0, unsigned int size ) {
+ bigint_t ( size ) __attribute__ (( may_alias ))
+ *modulus = ( ( void * ) modulus0 );
+ bigint_t ( size ) __attribute__ (( may_alias ))
+ *value = ( ( void * ) value0 );
- bigint_reduce ( minuend, modulus, result, tmp );
+ bigint_reduce ( modulus, value );
}
void bigint_mod_invert_sample ( const bigint_element_t *invertend0,
@@ -555,43 +550,40 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0,
/**
* Report result of big integer modular direct reduction test
*
- * @v minuend Big integer to be reduced
* @v modulus Big integer modulus
+ * @v value Big integer to be reduced
* @v expected Big integer expected result
*/
-#define bigint_reduce_ok( minuend, modulus, expected ) do { \
- static const uint8_t minuend_raw[] = minuend; \
+#define bigint_reduce_ok( modulus, value, expected ) do { \
static const uint8_t modulus_raw[] = modulus; \
+ static const uint8_t value_raw[] = value; \
static const uint8_t expected_raw[] = expected; \
uint8_t result_raw[ sizeof ( expected_raw ) ]; \
- unsigned int minuend_size = \
- bigint_required_size ( sizeof ( minuend_raw ) ); \
- unsigned int modulus_size = \
+ unsigned int size = \
bigint_required_size ( sizeof ( modulus_raw ) ); \
- bigint_t ( minuend_size ) minuend_temp; \
- bigint_t ( modulus_size ) modulus_temp; \
- bigint_t ( modulus_size ) result_temp; \
- size_t tmp_len = bigint_reduce_tmp_len ( &minuend_temp ); \
- uint8_t tmp[tmp_len]; \
+ bigint_t ( size ) modulus_temp; \
+ bigint_t ( size ) value_temp; \
{} /* Fix emacs alignment */ \
\
- assert ( bigint_size ( &result_temp ) == \
- bigint_size ( &modulus_temp ) ); \
- bigint_init ( &minuend_temp, minuend_raw, \
- sizeof ( minuend_raw ) ); \
+ assert ( bigint_size ( &modulus_temp ) == \
+ bigint_size ( &value_temp ) ); \
bigint_init ( &modulus_temp, modulus_raw, \
sizeof ( modulus_raw ) ); \
+ bigint_init ( &value_temp, value_raw, sizeof ( value_raw ) ); \
DBG ( "Modular reduce:\n" ); \
- DBG_HDA ( 0, &minuend_temp, sizeof ( minuend_temp ) ); \
DBG_HDA ( 0, &modulus_temp, sizeof ( modulus_temp ) ); \
- bigint_reduce ( &minuend_temp, &modulus_temp, &result_temp, \
- tmp ); \
- DBG_HDA ( 0, &result_temp, sizeof ( result_temp ) ); \
- bigint_done ( &result_temp, result_raw, \
- sizeof ( result_raw ) ); \
+ DBG_HDA ( 0, &value_temp, sizeof ( value_temp ) ); \
+ bigint_reduce ( &modulus_temp, &value_temp ); \
+ DBG_HDA ( 0, &value_temp, sizeof ( value_temp ) ); \
+ bigint_done ( &value_temp, result_raw, sizeof ( result_raw ) ); \
\
ok ( memcmp ( result_raw, expected_raw, \
sizeof ( result_raw ) ) == 0 ); \
+ \
+ bigint_init ( &value_temp, modulus_raw, \
+ sizeof ( modulus_raw ) ); \
+ ok ( memcmp ( &modulus_temp, &value_temp, \
+ sizeof ( modulus_temp ) ) == 0 ); \
} while ( 0 )
/**
@@ -1797,17 +1789,17 @@ static void bigint_test_exec ( void ) {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x01 ) );
- bigint_reduce_ok ( BIGINT ( 0x00 ),
- BIGINT ( 0xaf ),
+ bigint_reduce_ok ( BIGINT ( 0xaf ),
+ BIGINT ( 0x00 ),
BIGINT ( 0x00 ) );
bigint_reduce_ok ( BIGINT ( 0xab ),
BIGINT ( 0xab ),
BIGINT ( 0x00 ) );
- bigint_reduce_ok ( BIGINT ( 0x1d, 0x97, 0x63, 0xc9, 0x97, 0xcd, 0x43,
- 0xcb, 0x8e, 0x71, 0xac, 0x41, 0xdd ),
- BIGINT ( 0xcc, 0x9d, 0xa0, 0x79, 0x96, 0x6a, 0x46,
+ bigint_reduce_ok ( BIGINT ( 0xcc, 0x9d, 0xa0, 0x79, 0x96, 0x6a, 0x46,
0xd5, 0xb4, 0x30, 0xd2, 0x2b, 0xbf ),
BIGINT ( 0x1d, 0x97, 0x63, 0xc9, 0x97, 0xcd, 0x43,
+ 0xcb, 0x8e, 0x71, 0xac, 0x41, 0xdd ),
+ BIGINT ( 0x1d, 0x97, 0x63, 0xc9, 0x97, 0xcd, 0x43,
0xcb, 0x8e, 0x71, 0xac, 0x41, 0xdd ) );
bigint_reduce_ok ( BIGINT ( 0x21, 0xfa, 0x4f, 0xce, 0x0f, 0x0f, 0x4d,
0x43, 0xaa, 0xad, 0x21, 0x30, 0xe5 ),
@@ -1815,15 +1807,19 @@ static void bigint_test_exec ( void ) {
0x43, 0xaa, 0xad, 0x21, 0x30, 0xe5 ),
BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00 ) );
- bigint_reduce_ok ( BIGINT ( 0xf9, 0x78, 0x96, 0x39, 0xee, 0x98, 0x42,
+ bigint_reduce_ok ( BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0xf3, 0x65, 0x35, 0x41,
+ 0x66, 0x65 ),
+ BIGINT ( 0xf9, 0x78, 0x96, 0x39, 0xee, 0x98, 0x42,
0x6a, 0xb8, 0x74, 0x0b, 0xe8, 0x5c, 0x76,
0x34, 0xaf ),
- BIGINT ( 0xf3, 0x65, 0x35, 0x41, 0x66, 0x65 ),
- BIGINT ( 0xb3, 0x07, 0xe8, 0xb7, 0x01, 0xf6 ) );
- bigint_reduce_ok ( BIGINT ( 0xfe, 0x30, 0xe1, 0xc6, 0x65, 0x97, 0x48,
- 0x2e, 0x94, 0xd4 ),
- BIGINT ( 0x47, 0xaa, 0x88, 0x00, 0xd0, 0x30, 0x62,
+ BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0xb3, 0x07, 0xe8, 0xb7,
+ 0x01, 0xf6 ) );
+ bigint_reduce_ok ( BIGINT ( 0x47, 0xaa, 0x88, 0x00, 0xd0, 0x30, 0x62,
0xfb, 0x5d, 0x55 ),
+ BIGINT ( 0xfe, 0x30, 0xe1, 0xc6, 0x65, 0x97, 0x48,
+ 0x2e, 0x94, 0xd4 ),
BIGINT ( 0x27, 0x31, 0x49, 0xc3, 0xf5, 0x06, 0x1f,
0x3c, 0x7c, 0xd5 ) );
bigint_mod_invert_ok ( BIGINT ( 0x01 ), BIGINT ( 0x01 ) );
generated by cgit (git 2.34.1) at 2025-02-22 22:58:14 +0000