diff options
| -rw-r--r-- | src/crypto/bigint.c | 248 | ||||
| -rw-r--r-- | src/crypto/weierstrass.c | 15 | ||||
| -rw-r--r-- | src/include/ipxe/bigint.h | 85 | ||||
| -rw-r--r-- | src/tests/bigint_test.c | 106 |
4 files changed, 221 insertions, 233 deletions
diff --git a/src/crypto/bigint.c b/src/crypto/bigint.c index ad22af771..9ccd9ff88 100644 --- a/src/crypto/bigint.c +++ b/src/crypto/bigint.c @@ -27,7 +27,6 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); #include <string.h> #include <assert.h> #include <stdio.h> -#include <ipxe/profile.h> #include <ipxe/bigint.h> /** @file @@ -35,10 +34,6 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); * Big integer support */ -/** Modular direct reduction profiler */ -static struct profiler bigint_mod_profiler __profiler = - { .name = "bigint_mod" }; - /** Minimum number of least significant bytes included in transcription */ #define BIGINT_NTOA_LSB_MIN 16 @@ -180,172 +175,136 @@ void bigint_multiply_raw ( const bigint_element_t *multiplicand0, } /** - * Reduce big integer + * Reduce big integer R^2 modulo N * * @v modulus0 Element 0 of big integer modulus - * @v value0 Element 0 of big integer to be reduced - * @v size Number of elements in modulus and value + * @v result0 Element 0 of big integer to hold result + * @v size Number of elements in modulus and result + * + * Reduce the value R^2 modulo N, where R=2^n and n is the number of + * bits in the representation of the modulus N, including any leading + * zero bits. */ -void bigint_reduce_raw ( bigint_element_t *modulus0, bigint_element_t *value0, - unsigned int size ) { - bigint_t ( size ) __attribute__ (( may_alias )) - *modulus = ( ( void * ) modulus0 ); +void bigint_reduce_raw ( const bigint_element_t *modulus0, + bigint_element_t *result0, unsigned int size ) { + const bigint_t ( size ) __attribute__ (( may_alias )) + *modulus = ( ( const void * ) modulus0 ); bigint_t ( size ) __attribute__ (( may_alias )) - *value = ( ( void * ) value0 ); + *result = ( ( void * ) result0 ); const unsigned int width = ( 8 * sizeof ( bigint_element_t ) ); - bigint_element_t *element; - unsigned int modulus_max; - unsigned int value_max; - unsigned int subshift; - int offset; - int shift; + unsigned int shift; + int max; + int sign; int msb; - int i; - - /* Start profiling */ - profile_start ( &bigint_mod_profiler ); + int carry; - /* Normalise the modulus + /* We have the constants: * - * Scale the modulus by shifting left such that both modulus - * "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.) - */ - value_max = bigint_max_set_bit ( value ); - modulus_max = bigint_max_set_bit ( modulus ); - shift = ( value_max - modulus_max ); - if ( shift < 0 ) - goto skip; - subshift = ( shift & ( width - 1 ) ); - offset = ( shift / width ); - element = modulus->element; - for ( i = ( ( value_max - 1 ) / width ) ; ; i-- ) { - element[i] = ( element[ i - offset ] << subshift ); - if ( i <= offset ) - break; - if ( subshift ) { - element[i] |= ( element[ i - offset - 1 ] - >> ( width - subshift ) ); - } - } - for ( i-- ; i >= 0 ; i-- ) - element[i] = 0; - - /* Reduce the value "x" by iteratively adding or subtracting - * the scaled modulus "m". + * N = modulus * - * On each loop iteration, we maintain the invariant: + * n = number of bits in the modulus (including any leading zeros) * - * -2m <= x < 2m + * R = 2^n * - * If x is positive, we obtain the new value x' by - * subtracting m, otherwise we add m: + * Let r be the extension of the n-bit result register by a + * separate two's complement sign bit, such that -R <= r < R, + * and define: * - * 0 <= x < 2m => x' := x - m => -m <= x' < m - * -2m <= x < 0 => x' := x + m => -m <= x' < m + * x = r * 2^k * - * and then halve the modulus (by shifting right): + * as the value being reduced modulo N, where k is a + * non-negative integer bit shift. * - * m' = m/2 + * We want to reduce the initial value R^2=2^(2n), which we + * may trivially represent using r=1 and k=2n. * - * We therefore end up with: + * We then iterate over decrementing k, maintaining the loop + * invariant: * - * -m <= x' < m => -2m' <= x' < 2m' + * -N <= r < N * - * i.e. we have preseved the invariant while reducing the - * bounds on x' by one power of two. + * On each iteration we must first double r, to compensate for + * having decremented k: * - * The issue remains of how to determine on each iteration - * whether or not x is currently positive, given that both - * input values are unsigned big integers that may use all - * available bits (including the MSB). + * k' = k - 1 * - * On the first loop iteration, we may simply assume that x is - * positive, since it is unmodified from the input value and - * so is positive by definition (even if the MSB is set). We - * therefore unconditionally perform a subtraction on the - * first loop iteration. + * r' = 2r * - * Let k be the MSB after normalisation. We then have: + * x = r * 2^k = 2r * 2^(k-1) = r' * 2^k' * - * 2^k <= m < 2^(k+1) - * 2^k <= x < 2^(k+1) + * Note that doubling the n-bit result register will create a + * value of n+1 bits: this extra bit needs to be handled + * separately during the calculation. * - * On the first loop iteration, we therefore have: + * We then subtract N (if r is currently non-negative) or add + * N (if r is currently negative) to restore the loop + * invariant: * - * x' = (x - m) - * < 2^(k+1) - 2^k - * < 2^k + * 0 <= r < N => r" = 2r - N => -N <= r" < N + * -N <= r < 0 => r" = 2r + N => -N <= r" < N * - * Any positive value of x' therefore has its MSB set to zero, - * and so we may validly treat the MSB of x' as a sign bit at - * the end of the first loop iteration. + * Note that since N may use all n bits, the most significant + * bit of the n-bit result register is not a valid two's + * complement sign bit for r: the extra sign bit therefore + * also needs to be handled separately. * - * On all subsequent loop iterations, the starting value m is - * guaranteed to have its MSB set to zero (since it has - * already been shifted right at least once). Since we know - * from above that we preserve the loop invariant: + * Once we reach k=0, we have x=r and therefore: * - * -m <= x' < m + * -N <= x < N * - * we immediately know that any positive value of x' also has - * its MSB set to zero, and so we may validly treat the MSB of - * x' as a sign bit at the end of all subsequent loop - * iterations. + * After this last loop iteration (with k=0), we may need to + * add a single multiple of N to ensure that x is positive, + * i.e. lies within the range 0 <= x < N. * - * After the last loop iteration (when m' has been shifted - * back down to the original value of the modulus), we may - * need to add a single multiple of m' to ensure that x' is - * positive, i.e. lies within the range 0 <= x' < m'. To - * allow for reusing the (inlined) expansion of - * bigint_subtract(), we achieve this via a potential - * additional loop iteration that performs the addition and is - * then guaranteed to terminate (since the result will be - * positive). + * Since neither the modulus nor the value R^2 are secret, we + * may elide approximately half of the total number of + * iterations by constructing the initial representation of + * R^2 as r=2^m and k=2n-m (for some m such that 2^m < N). */ - for ( msb = 0 ; ( msb || ( shift >= 0 ) ) ; shift-- ) { - if ( msb ) { - bigint_add ( modulus, value ); - } else { - bigint_subtract ( modulus, value ); - } - msb = bigint_msb_is_set ( value ); - if ( shift > 0 ) - bigint_shr ( modulus ); + + /* Initialise x=R^2 */ + memset ( result, 0, sizeof ( *result ) ); + max = ( bigint_max_set_bit ( modulus ) - 2 ); + if ( max < 0 ) { + /* Degenerate case of N=0 or N=1: return a zero result */ + return; } + bigint_set_bit ( result, max ); + shift = ( ( 2 * size * width ) - max ); + sign = 0; - skip: - /* Sanity check */ - assert ( ! bigint_is_geq ( value, modulus ) ); + /* Iterate as described above */ + while ( shift-- ) { - /* Stop profiling */ - profile_stop ( &bigint_mod_profiler ); -} + /* Calculate 2r, storing extra bit separately */ + msb = bigint_shl ( result ); -/** - * Reduce supremum of big integer representation - * - * @v modulus0 Element 0 of big integer modulus - * @v result0 Element 0 of big integer to hold result - * @v size Number of elements in modulus and value - * - * Reduce the value 2^k (where k is the bit width of the big integer - * representation) modulo the specified modulus. - */ -void bigint_reduce_supremum_raw ( bigint_element_t *modulus0, - bigint_element_t *result0, - unsigned int size ) { - bigint_t ( size ) __attribute__ (( may_alias )) - *modulus = ( ( void * ) modulus0 ); - bigint_t ( size ) __attribute__ (( may_alias )) - *result = ( ( void * ) result0 ); + /* Add or subtract N according to current sign */ + if ( sign ) { + carry = bigint_add ( modulus, result ); + } else { + carry = bigint_subtract ( modulus, result ); + } - /* Calculate (2^k) mod N via direct reduction of (2^k - N) mod N */ - memset ( result, 0, sizeof ( *result ) ); - bigint_subtract ( modulus, result ); - bigint_reduce ( modulus, result ); + /* Calculate new sign of result + * + * We know the result lies in the range -N <= r < N + * and so the tuple (old sign, msb, carry) cannot ever + * take the values (0, 1, 0) or (1, 0, 0). We can + * therefore treat these as don't-care inputs, which + * allows us to simplify the boolean expression by + * ignoring the old sign completely. + */ + assert ( ( sign == msb ) || carry ); + sign = ( msb ^ carry ); + } + + /* Add N to make result positive if necessary */ + if ( sign ) + bigint_add ( modulus, result ); + + /* Sanity check */ + assert ( ! bigint_is_geq ( result, modulus ) ); } /** @@ -805,12 +764,9 @@ void bigint_mod_exp_raw ( const bigint_element_t *base0, ( ( void * ) result0 ); const unsigned int width = ( 8 * sizeof ( bigint_element_t ) ); struct { - union { - bigint_t ( 2 * size ) padded_modulus; - struct { - bigint_t ( size ) modulus; - bigint_t ( size ) stash; - }; + struct { + bigint_t ( size ) modulus; + bigint_t ( size ) stash; }; union { bigint_t ( 2 * size ) full; @@ -833,7 +789,7 @@ void bigint_mod_exp_raw ( const bigint_element_t *base0, } /* Factor modulus as (N * 2^scale) where N is odd */ - bigint_grow ( modulus, &temp->padded_modulus ); + bigint_copy ( modulus, &temp->modulus ); for ( scale = 0 ; ( ! bigint_bit_is_set ( &temp->modulus, 0 ) ) ; scale++ ) { bigint_shr ( &temp->modulus ); @@ -844,10 +800,10 @@ void bigint_mod_exp_raw ( const bigint_element_t *base0, submask = ~submask; /* Calculate (R^2 mod N) */ - bigint_reduce_supremum ( &temp->padded_modulus, &temp->product.full ); - bigint_copy ( &temp->product.low, &temp->stash ); + bigint_reduce ( &temp->modulus, &temp->stash ); /* Initialise result = Montgomery(1, R^2 mod N) */ + bigint_grow ( &temp->stash, &temp->product.full ); bigint_montgomery ( &temp->modulus, &temp->product.full, result ); /* Convert base into Montgomery form */ diff --git a/src/crypto/weierstrass.c b/src/crypto/weierstrass.c index be3909542..c149c7b21 100644 --- a/src/crypto/weierstrass.c +++ b/src/crypto/weierstrass.c @@ -188,10 +188,6 @@ static void weierstrass_init ( struct weierstrass_curve *curve ) { ( ( void * ) curve->mont[0] ); bigint_t ( size ) __attribute__ (( may_alias )) *temp = ( ( void * ) curve->prime[1] ); - bigint_t ( size * 2 ) __attribute__ (( may_alias )) *prime_double = - ( ( void * ) prime ); - bigint_t ( size * 2 ) __attribute__ (( may_alias )) *square_double = - ( ( void * ) square ); bigint_t ( size * 2 ) __attribute__ (( may_alias )) *product = ( ( void * ) temp ); bigint_t ( size ) __attribute__ (( may_alias )) *two = @@ -206,15 +202,8 @@ static void weierstrass_init ( struct weierstrass_curve *curve ) { DBGC ( curve, "WEIERSTRASS %s N = %s\n", curve->name, bigint_ntoa ( prime ) ); - /* Calculate Montgomery constant R^2 mod N - * - * We rely on the fact that the subsequent big integers in the - * cache (i.e. the first prime multiple, and the constant "1") - * have not yet been written to, and so can be treated as - * being the (zero) upper halves required to hold the - * double-width value R^2. - */ - bigint_reduce_supremum ( prime_double, square_double ); + /* Calculate Montgomery constant R^2 mod N */ + bigint_reduce ( prime, square ); DBGC ( curve, "WEIERSTRASS %s R^2 = %s mod N\n", curve->name, bigint_ntoa ( square ) ); diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h index d8f4571e3..396462f33 100644 --- a/src/include/ipxe/bigint.h +++ b/src/include/ipxe/bigint.h @@ -147,6 +147,28 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); size ); } ) /** + * Set bit in big integer + * + * @v value Big integer + * @v bit Bit to set + */ +#define bigint_set_bit( value, bit ) do { \ + unsigned int size = bigint_size (value); \ + bigint_set_bit_raw ( (value)->element, size, bit ); \ + } while ( 0 ) + +/** + * Clear bit in big integer + * + * @v value Big integer + * @v bit Bit to set + */ +#define bigint_clear_bit( value, bit ) do { \ + unsigned int size = bigint_size (value); \ + bigint_clear_bit_raw ( (value)->element, size, bit ); \ + } while ( 0 ) + +/** * Test if bit is set in big integer * * @v value Big integer @@ -243,30 +265,18 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); } while ( 0 ) /** - * Reduce big integer + * Reduce big integer R^2 modulo N * * @v modulus Big integer modulus - * @v value Big integer to be reduced + * @v result Big integer to hold result */ -#define bigint_reduce( modulus, value ) do { \ +#define bigint_reduce( modulus, result ) do { \ unsigned int size = bigint_size (modulus); \ - bigint_reduce_raw ( (modulus)->element, (value)->element, \ + bigint_reduce_raw ( (modulus)->element, (result)->element, \ size ); \ } while ( 0 ) /** - * Reduce supremum of big integer representation - * - * @v modulus0 Big integer modulus - * @v result0 Big integer to hold result - */ -#define bigint_reduce_supremum( modulus, result ) do { \ - unsigned int size = bigint_size (modulus); \ - bigint_reduce_supremum_raw ( (modulus)->element, \ - (result)->element, size ); \ - } while ( 0 ) - -/** * Compute inverse of odd big integer modulo any power of two * * @v invertend Odd big integer to be inverted @@ -370,6 +380,42 @@ typedef void ( bigint_ladder_op_t ) ( const bigint_element_t *operand0, void *tmp ); /** + * Set bit in big integer + * + * @v value0 Element 0 of big integer + * @v size Number of elements + * @v bit Bit to set + */ +static inline __attribute__ (( always_inline )) void +bigint_set_bit_raw ( bigint_element_t *value0, unsigned int size, + unsigned int bit ) { + bigint_t ( size ) __attribute__ (( may_alias )) *value = + ( ( void * ) value0 ); + unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) ); + unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) ); + + value->element[index] |= ( 1UL << subindex ); +} + +/** + * Clear bit in big integer + * + * @v value0 Element 0 of big integer + * @v size Number of elements + * @v bit Bit to clear + */ +static inline __attribute__ (( always_inline )) void +bigint_clear_bit_raw ( bigint_element_t *value0, unsigned int size, + unsigned int bit ) { + bigint_t ( size ) __attribute__ (( may_alias )) *value = + ( ( void * ) value0 ); + unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) ); + unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) ); + + value->element[index] &= ~( 1UL << subindex ); +} + +/** * Test if bit is set in big integer * * @v value0 Element 0 of big integer @@ -442,11 +488,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 ( bigint_element_t *modulus0, bigint_element_t *value0, - unsigned int size ); -void bigint_reduce_supremum_raw ( bigint_element_t *modulus0, - bigint_element_t *value0, - unsigned int size ); +void bigint_reduce_raw ( const bigint_element_t *modulus0, + bigint_element_t *result0, unsigned int size ); void bigint_mod_invert_raw ( const bigint_element_t *invertend0, bigint_element_t *inverse0, unsigned int size ); int bigint_montgomery_relaxed_raw ( const bigint_element_t *modulus0, diff --git a/src/tests/bigint_test.c b/src/tests/bigint_test.c index a1207fedd..496efdfe2 100644 --- a/src/tests/bigint_test.c +++ b/src/tests/bigint_test.c @@ -185,14 +185,14 @@ void bigint_multiply_sample ( const bigint_element_t *multiplicand0, bigint_multiply ( multiplicand, multiplier, result ); } -void bigint_reduce_sample ( bigint_element_t *modulus0, - bigint_element_t *value0, unsigned int size ) { - bigint_t ( size ) __attribute__ (( may_alias )) - *modulus = ( ( void * ) modulus0 ); +void bigint_reduce_sample ( const bigint_element_t *modulus0, + bigint_element_t *result0, unsigned int size ) { + const bigint_t ( size ) __attribute__ (( may_alias )) + *modulus = ( ( const void * ) modulus0 ); bigint_t ( size ) __attribute__ (( may_alias )) - *value = ( ( void * ) value0 ); + *result = ( ( void * ) result0 ); - bigint_reduce ( modulus, value ); + bigint_reduce ( modulus, result ); } void bigint_mod_invert_sample ( const bigint_element_t *invertend0, @@ -553,42 +553,35 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0, } while ( 0 ) /** - * Report result of big integer modular direct reduction test + * Report result of big integer modular direct reduction of R^2 test * * @v modulus Big integer modulus - * @v value Big integer to be reduced * @v expected Big integer expected result */ -#define bigint_reduce_ok( modulus, value, expected ) do { \ +#define bigint_reduce_ok( modulus, 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 size = \ bigint_required_size ( sizeof ( modulus_raw ) ); \ bigint_t ( size ) modulus_temp; \ - bigint_t ( size ) value_temp; \ + bigint_t ( size ) result_temp; \ {} /* Fix emacs alignment */ \ \ assert ( bigint_size ( &modulus_temp ) == \ - bigint_size ( &value_temp ) ); \ + bigint_size ( &result_temp ) ); \ + assert ( sizeof ( result_temp ) == sizeof ( result_raw ) ); \ bigint_init ( &modulus_temp, modulus_raw, \ sizeof ( modulus_raw ) ); \ - bigint_init ( &value_temp, value_raw, sizeof ( value_raw ) ); \ - DBG ( "Modular reduce:\n" ); \ + DBG ( "Modular reduce R^2:\n" ); \ DBG_HDA ( 0, &modulus_temp, sizeof ( modulus_temp ) ); \ - 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 ) ); \ + bigint_reduce ( &modulus_temp, &result_temp ); \ + DBG_HDA ( 0, &result_temp, sizeof ( result_temp ) ); \ + bigint_done ( &result_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 ) /** @@ -1801,39 +1794,46 @@ 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 ( 0xaf ), - BIGINT ( 0x00 ), - BIGINT ( 0x00 ) ); - bigint_reduce_ok ( BIGINT ( 0xab ), - BIGINT ( 0xab ), - BIGINT ( 0x00 ) ); - 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 ), - BIGINT ( 0x21, 0xfa, 0x4f, 0xce, 0x0f, 0x0f, 0x4d, - 0x43, 0xaa, 0xad, 0x21, 0x30, 0xe5 ), + bigint_reduce_ok ( BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00 ), BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 ) ); + 0x00 ) ); 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 ), + 0x01 ), + BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00 ) ); + bigint_reduce_ok ( BIGINT ( 0x00, 0x00, 0x00, 0x40, 0x00, 0x00, 0x00, + 0x00 ), + BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00 ) ); + bigint_reduce_ok ( BIGINT ( 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00 ), + BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00 ) ); + bigint_reduce_ok ( BIGINT ( 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff ), 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 ) ); + 0x01 ) ); + bigint_reduce_ok ( BIGINT ( 0x39, 0x18, 0x47, 0xc9, 0xa2, 0x1d, 0x4b, + 0xa6 ), + BIGINT ( 0x30, 0x9d, 0xcc, 0xac, 0xd6, 0xf9, 0x2f, + 0xa0 ) ); + bigint_reduce_ok ( BIGINT ( 0x81, 0x96, 0xdb, 0x36, 0xa6, 0xb7, 0x41, + 0x45, 0x92, 0x37, 0x7d, 0x48, 0x1b, 0x2f, + 0x3c, 0xa6 ), + BIGINT ( 0x4a, 0x68, 0x25, 0xf7, 0x2b, 0x72, 0x91, + 0x6e, 0x09, 0x83, 0xca, 0xf1, 0x45, 0x79, + 0x84, 0x18 ) ); + bigint_reduce_ok ( BIGINT ( 0x84, 0x2d, 0xe4, 0x1c, 0xc3, 0x11, 0x4f, + 0xa0, 0x90, 0x4b, 0xa9, 0xa1, 0xdf, 0xed, + 0x4b, 0xe0, 0xb7, 0xfc, 0x5e, 0xd1, 0x91, + 0x59, 0x4d, 0xc2, 0xae, 0x2f, 0x46, 0x9e, + 0x32, 0x6e, 0xf4, 0x67 ), + BIGINT ( 0x46, 0xdd, 0x36, 0x6c, 0x0b, 0xac, 0x3a, + 0x8f, 0x9a, 0x25, 0x90, 0xb2, 0x39, 0xe9, + 0xa4, 0x65, 0xc1, 0xd4, 0xc1, 0x99, 0x61, + 0x95, 0x47, 0xab, 0x4f, 0xd7, 0xad, 0xd4, + 0x3e, 0xe9, 0x9c, 0xfc ) ); bigint_mod_invert_ok ( BIGINT ( 0x01 ), BIGINT ( 0x01 ) ); bigint_mod_invert_ok ( BIGINT ( 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff ), |