38 #define BIGINT_NTOA_LSB_MIN 16 62 if (
count >= ( (
sizeof ( buf ) - 1 ) / 2 ) ) {
63 threshold -= ( (
sizeof ( buf ) - 3
69 for (
tmp = buf, i = (
count - 1 ) ; i >= 0 ; i-- ) {
73 if ( i == threshold ) {
78 assert (
tmp < ( buf +
sizeof ( buf ) ) );
92 unsigned int size,
int swap ) {
101 for ( i = 0 ; i <
size ; i++ ) {
102 xor = ( mask & ( first0[i] ^ second0[i] ) );
118 unsigned int multiplicand_size,
120 unsigned int multiplier_size,
122 unsigned int result_size = ( multiplicand_size + multiplier_size );
124 *multiplicand = ( (
const void * ) multiplicand0 );
126 *
multiplier = ( (
const void * ) multiplier0 );
128 *
result = ( (
void * ) result0 );
162 for ( i = 0 ; i < multiplicand_size ; i++ ) {
163 multiplicand_element = multiplicand->element[i];
165 result_element = &
result->element[i];
167 for ( j = 0 ; j < multiplier_size ; j++ ) {
169 *(multiplier_element++),
173 *result_element = carry_element;
191 *modulus = ( (
const void * ) modulus0 );
193 *
result = ( (
void * ) result0 );
273 shift = ( ( 2 *
size * width ) -
max );
299 sign = ( msb ^
carry );
320 *invertend = ( (
const void * ) invertend0 );
322 *inverse = ( (
void * ) inverse0 );
331 memset ( inverse, 0xff,
sizeof ( *inverse ) );
356 for ( i =
size ; i > 0 ; i-- ) {
358 *addend = ( (
const void * ) invertend );
360 *residue = ( (
void * ) inverse );
363 for ( accum = 0,
bit = 1 ;
bit ;
bit <<= 1 ) {
372 inverse->element[ i - 1 ] = accum;
376 for ( i = 0 ; i < (
size / 2 ) ; i++ ) {
377 accum = inverse->element[i];
378 inverse->element[i] = inverse->element[
size - 1 - i ];
379 inverse->element[
size - 1 - i ] = accum;
490 unsigned int size ) {
492 *modulus = ( (
const void * ) modulus0 );
501 *
result = ( (
void * ) result0 );
514 if ( cached.element[0] != modulus->element[0] ) {
516 negmodinv.element[0] = -negmodinv.element[0];
517 cached.element[0] = modulus->element[0];
521 for ( i = 0 ; i <
size ; i++ ) {
524 multiple = (
value->low.element[i] * negmodinv.element[0] );
528 for ( j = 0 ; j <
size ; j++ ) {
530 &
value->full.element[ i + j ],
567 unsigned int size ) {
569 *modulus = ( (
const void * ) modulus0 );
578 *
result = ( (
void * ) result0 );
635 const void *
ctx,
void *
tmp ) {
637 *
result = ( (
void * ) result0 );
639 *multiple = ( (
void * ) multiple0 );
641 *exponent = ( (
const void * ) exponent0 );
643 unsigned int bit = ( exponent_size * width );
721 const void *
ctx,
void *
tmp ) {
723 *
multiplier = ( (
const void * ) multiplier0 );
725 *
result = ( (
void * ) result0 );
727 *modulus = ( (
const void * )
ctx );
755 unsigned int size,
unsigned int exponent_size,
758 ( (
const void * ) base0 );
760 ( (
const void * ) modulus0 );
762 *exponent = ( (
const void * ) exponent0 );
764 ( (
void * ) result0 );
778 unsigned int subsize;
797 subsize = ( ( scale + width - 1 ) / width );
798 submask = ( ( 1UL << ( scale % width ) ) - 1 );
816 &temp->modulus, &temp->product );
826 *subbase = ( (
const void * )
base );
828 *submodulus = ( (
void * ) &temp->modulus );
830 *substash = ( (
void * ) &temp->stash );
832 *subresult = ( (
void * )
result );
837 *subproduct = ( (
void * ) &temp->product.full );
847 for ( i = 0 ; i < scale ; i++ )
857 subproduct->low.element[ subsize - 1 ] &= submask;
866 &temp->product.full );
void bigint_multiply_raw(const bigint_element_t *multiplicand0, unsigned int multiplicand_size, const bigint_element_t *multiplier0, unsigned int multiplier_size, bigint_element_t *result0)
Multiply big integers.
uint32_t low
Low 16 bits of address.
void bigint_mod_exp_raw(const bigint_element_t *base0, const bigint_element_t *modulus0, const bigint_element_t *exponent0, bigint_element_t *result0, unsigned int size, unsigned int exponent_size, void *tmp)
Perform modular exponentiation of big integers.
#define bigint_max_set_bit(value)
Find highest bit set in big integer.
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)
Perform generalised exponentiation via a Montgomery ladder.
#define sprintf(buf, fmt,...)
Write a formatted string to a buffer.
uint8_t size
Entry size (in 32-bit words)
#define bigint_grow(source, dest)
Grow big integer.
#define bigint_init(value, data, len)
Initialise big integer.
static unsigned int unsigned int bit
void bigint_multiply_one(const bigint_element_t multiplicand, const bigint_element_t multiplier, bigint_element_t *result, bigint_element_t *carry)
struct golan_eq_context ctx
#define bigint_montgomery_relaxed(modulus, value, result)
Perform relaxed Montgomery reduction (REDC) of a big integer.
static u32 xor(u32 a, u32 b)
int bigint_montgomery_relaxed_raw(const bigint_element_t *modulus0, bigint_element_t *value0, bigint_element_t *result0, unsigned int size)
Perform relaxed Montgomery reduction (REDC) of a big integer.
#define bigint_is_geq(value, reference)
Compare big integers.
#define bigint_mod_invert(invertend, inverse)
Compute inverse of odd big integer modulo any power of two.
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
#define bigint_shr(value)
Shift big integer right.
#define bigint_shrink(source, dest)
Shrink big integer.
pseudo_bit_t value[0x00020]
#define bigint_copy(source, dest)
Copy big integer.
uint32_t bigint_element_t
Element of a big integer.
uint16_t count
Number of entries.
uint32_t high
High 32 bits of address.
#define bigint_swap(first, second, swap)
Conditionally swap big integers (in constant time)
void bigint_montgomery_raw(const bigint_element_t *modulus0, bigint_element_t *value0, bigint_element_t *result0, unsigned int size)
Perform classic Montgomery reduction (REDC) of a big integer.
#define bigint_shl(value)
Shift big integer left.
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
static uint16_t struct vmbus_xfer_pages_operations * op
#define bigint_montgomery(modulus, value, result)
Perform classic Montgomery reduction (REDC) of a big integer.
static const uint32_t multiplier
Port multiplier number.
void bigint_swap_raw(bigint_element_t *first0, bigint_element_t *second0, unsigned int size, int swap)
Conditionally swap big integers (in constant time)
#define bigint_multiply(multiplicand, multiplier, result)
Multiply big integers.
#define bigint_reduce(modulus, result)
Reduce big integer R^2 modulo N.
uint8_t product
Product string.
#define bigint_ladder(result, multiple, exponent, op, ctx, tmp)
Perform generalised exponentiation via a Montgomery ladder.
void() bigint_ladder_op_t(const bigint_element_t *operand0, bigint_element_t *result0, unsigned int size, const void *ctx, void *tmp)
A big integer Montgomery ladder commutative operation.
const char * bigint_ntoa_raw(const bigint_element_t *value0, unsigned int size)
Transcribe big integer (for debugging)
#define bigint_bit_is_set(value, bit)
Test if bit is set in big integer.
#define bigint_subtract(subtrahend, value)
Subtract big integers.
void bigint_mod_invert_raw(const bigint_element_t *invertend0, bigint_element_t *inverse0, unsigned int size)
Compute inverse of odd big integer modulo any power of two.
#define bigint_mod_exp_tmp_len(modulus)
Calculate temporary working space required for moduluar exponentiation.
#define bigint_add(addend, value)
Add big integers.
#define NULL
NULL pointer (VOID *)
#define bigint_set_bit(value, bit)
Set bit in big integer.
void bigint_reduce_raw(const bigint_element_t *modulus0, bigint_element_t *result0, unsigned int size)
Reduce big integer R^2 modulo N.
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.
#define BIGINT_NTOA_LSB_MIN
Minimum number of least significant bytes included in transcription.
void * memset(void *dest, int character, size_t len) __nonnull
void bigint_mod_exp_ladder(const bigint_element_t *multiplier0, bigint_element_t *result0, unsigned int size, const void *ctx, void *tmp)
Perform modular multiplication as part of a Montgomery ladder.