iPXE
Macros | Functions
bigint.h File Reference

Big integer support. More...

#include <bits/bigint.h>

Go to the source code of this file.

Macros

#define bigint_t(size)
 Define a big-integer type. More...
 
#define bigint_required_size(len)
 Determine number of elements required for a big-integer type. More...
 
#define bigint_size(bigint)   ( sizeof ( *(bigint) ) / sizeof ( (bigint)->element[0] ) )
 Determine number of elements in big-integer type. More...
 
#define bigint_init(value, data, len)
 Initialise big integer. More...
 
#define bigint_done(value, out, len)
 Finalise big integer. More...
 
#define bigint_add(addend, value)
 Add big integers. More...
 
#define bigint_subtract(subtrahend, value)
 Subtract big integers. More...
 
#define bigint_rol(value)
 Rotate big integer left. More...
 
#define bigint_ror(value)
 Rotate big integer right. More...
 
#define bigint_is_zero(value)
 Test if big integer is equal to zero. More...
 
#define bigint_is_geq(value, reference)
 Compare big integers. More...
 
#define bigint_bit_is_set(value, bit)
 Test if bit is set in big integer. More...
 
#define bigint_max_set_bit(value)
 Find highest bit set in big integer. More...
 
#define bigint_grow(source, dest)
 Grow big integer. More...
 
#define bigint_shrink(source, dest)
 Shrink big integer. More...
 
#define bigint_multiply(multiplicand, multiplier, result)
 Multiply big integers. More...
 
#define bigint_mod_multiply(multiplicand, multiplier, modulus, result, tmp)
 Perform modular multiplication of big integers. More...
 
#define bigint_mod_multiply_tmp_len(modulus)
 Calculate temporary working space required for moduluar multiplication. More...
 
#define bigint_mod_exp(base, modulus, exponent, result, tmp)
 Perform modular exponentiation of big integers. More...
 
#define bigint_mod_exp_tmp_len(modulus, exponent)
 Calculate temporary working space required for moduluar exponentiation. More...
 

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
 
void bigint_init_raw (bigint_element_t *value0, unsigned int size, const void *data, size_t len)
 
void bigint_done_raw (const bigint_element_t *value0, unsigned int size, void *out, size_t len)
 
void bigint_add_raw (const bigint_element_t *addend0, bigint_element_t *value0, unsigned int size)
 
void bigint_subtract_raw (const bigint_element_t *subtrahend0, bigint_element_t *value0, unsigned int size)
 
void bigint_rol_raw (bigint_element_t *value0, unsigned int size)
 
void bigint_ror_raw (bigint_element_t *value0, unsigned int size)
 
int bigint_is_zero_raw (const bigint_element_t *value0, unsigned int size)
 
int bigint_is_geq_raw (const bigint_element_t *value0, const bigint_element_t *reference0, unsigned int size)
 
int bigint_bit_is_set_raw (const bigint_element_t *value0, unsigned int size, unsigned int bit)
 
int bigint_max_set_bit_raw (const bigint_element_t *value0, unsigned int size)
 
void bigint_grow_raw (const bigint_element_t *source0, unsigned int source_size, bigint_element_t *dest0, unsigned int dest_size)
 
void bigint_shrink_raw (const bigint_element_t *source0, unsigned int source_size, bigint_element_t *dest0, unsigned int dest_size)
 
void bigint_multiply_raw (const bigint_element_t *multiplicand0, const bigint_element_t *multiplier0, bigint_element_t *result0, unsigned int size)
 Multiply big integers. More...
 
void bigint_mod_multiply_raw (const bigint_element_t *multiplicand0, const bigint_element_t *multiplier0, const bigint_element_t *modulus0, bigint_element_t *result0, unsigned int size, void *tmp)
 Perform modular multiplication of big integers. More...
 
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. More...
 

Detailed Description

Big integer support.

Definition in file bigint.h.

Macro Definition Documentation

◆ bigint_t

#define bigint_t (   size)
Value:
struct { \
bigint_element_t element[ (size) ]; \
}
static unsigned int size
Definition: bigint.h:26

Define a big-integer type.

Parameters
sizeNumber of elements
Return values
bigint_tBig integer type

Definition at line 17 of file bigint.h.

◆ bigint_required_size

#define bigint_required_size (   len)
Value:
( ( (len) + sizeof ( bigint_element_t ) - 1 ) / \
sizeof ( bigint_element_t ) )
static unsigned int const void size_t len
Definition: bigint.h:27
uint32_t bigint_element_t
Element of a big integer.
Definition: bigint.h:15

Determine number of elements required for a big-integer type.

Parameters
lenMaximum length of big integer, in bytes
Return values
sizeNumber of elements

Definition at line 28 of file bigint.h.

◆ bigint_size

#define bigint_size (   bigint)    ( sizeof ( *(bigint) ) / sizeof ( (bigint)->element[0] ) )

Determine number of elements in big-integer type.

Parameters
bigintBig integer
Return values
sizeNumber of elements

Definition at line 38 of file bigint.h.

◆ bigint_init

#define bigint_init (   value,
  data,
  len 
)
Value:
do { \
unsigned int size = bigint_size (value); \
assert ( (len) <= ( size * sizeof ( (value)->element[0] ) ) ); \
bigint_init_raw ( (value)->element, size, (data), (len) ); \
} while ( 0 )
static unsigned int const void size_t len
Definition: bigint.h:27
static unsigned int const void * data
Definition: bigint.h:26
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Initialise big integer.

Parameters
valueBig integer to initialise
dataRaw data
lenLength of raw data

Definition at line 48 of file bigint.h.

◆ bigint_done

#define bigint_done (   value,
  out,
  len 
)
Value:
do { \
unsigned int size = bigint_size (value); \
bigint_done_raw ( (value)->element, size, (out), (len) ); \
} while ( 0 )
static unsigned int const void size_t len
Definition: bigint.h:27
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size void * out
Definition: bigint.h:290
static unsigned int size
Definition: bigint.h:26

Finalise big integer.

Parameters
valueBig integer to finalise
outOutput buffer
lenLength of output buffer

Definition at line 61 of file bigint.h.

◆ bigint_add

#define bigint_add (   addend,
  value 
)
Value:
do { \
unsigned int size = bigint_size (addend); \
bigint_add_raw ( (addend)->element, (value)->element, size ); \
} while ( 0 )
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Add big integers.

Parameters
addendBig integer to add
valueBig integer to be added to

Definition at line 72 of file bigint.h.

◆ bigint_subtract

#define bigint_subtract (   subtrahend,
  value 
)
Value:
do { \
unsigned int size = bigint_size (subtrahend); \
bigint_subtract_raw ( (subtrahend)->element, (value)->element, \
size ); \
} while ( 0 )
static __always_inline off_t userptr_t subtrahend
Definition: efi_uaccess.h:61
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Subtract big integers.

Parameters
subtrahendBig integer to subtract
valueBig integer to be subtracted from

Definition at line 83 of file bigint.h.

◆ bigint_rol

#define bigint_rol (   value)
Value:
do { \
unsigned int size = bigint_size (value); \
bigint_rol_raw ( (value)->element, size ); \
} while ( 0 )
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Rotate big integer left.

Parameters
valueBig integer

Definition at line 94 of file bigint.h.

◆ bigint_ror

#define bigint_ror (   value)
Value:
do { \
unsigned int size = bigint_size (value); \
bigint_ror_raw ( (value)->element, size ); \
} while ( 0 )
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Rotate big integer right.

Parameters
valueBig integer

Definition at line 104 of file bigint.h.

◆ bigint_is_zero

#define bigint_is_zero (   value)
Value:
( { \
unsigned int size = bigint_size (value); \
bigint_is_zero_raw ( (value)->element, size ); } )
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Test if big integer is equal to zero.

Parameters
valueBig integer
sizeNumber of elements
Return values
is_zeroBig integer is equal to zero

Definition at line 116 of file bigint.h.

◆ bigint_is_geq

#define bigint_is_geq (   value,
  reference 
)
Value:
( { \
unsigned int size = bigint_size (value); \
bigint_is_geq_raw ( (value)->element, (reference)->element, \
size ); } )
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Compare big integers.

Parameters
valueBig integer
referenceReference big integer
Return values
geqBig integer is greater than or equal to the reference

Definition at line 127 of file bigint.h.

◆ bigint_bit_is_set

#define bigint_bit_is_set (   value,
  bit 
)
Value:
( { \
unsigned int size = bigint_size (value); \
bigint_bit_is_set_raw ( (value)->element, size, bit ); } )
static unsigned int unsigned int bit
Definition: bigint.h:196
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Test if bit is set in big integer.

Parameters
valueBig integer
bitBit to test
Return values
is_setBit is set

Definition at line 139 of file bigint.h.

◆ bigint_max_set_bit

#define bigint_max_set_bit (   value)
Value:
( { \
unsigned int size = bigint_size (value); \
bigint_max_set_bit_raw ( (value)->element, size ); } )
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Find highest bit set in big integer.

Parameters
valueBig integer
Return values
max_bitHighest bit set + 1 (or 0 if no bits set)

Definition at line 149 of file bigint.h.

◆ bigint_grow

#define bigint_grow (   source,
  dest 
)
Value:
do { \
unsigned int source_size = bigint_size (source); \
unsigned int dest_size = bigint_size (dest); \
bigint_grow_raw ( (source)->element, source_size, \
(dest)->element, dest_size ); \
} while ( 0 )
static unsigned int uint32_t unsigned int dest_size
Definition: bigint.h:241
static void * dest
Definition: strings.h:176
static unsigned int source_size
Definition: bigint.h:240
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38

Grow big integer.

Parameters
sourceSource big integer
destDestination big integer

Definition at line 159 of file bigint.h.

◆ bigint_shrink

#define bigint_shrink (   source,
  dest 
)
Value:
do { \
unsigned int source_size = bigint_size (source); \
unsigned int dest_size = bigint_size (dest); \
bigint_shrink_raw ( (source)->element, source_size, \
(dest)->element, dest_size ); \
} while ( 0 )
static unsigned int uint32_t unsigned int dest_size
Definition: bigint.h:241
static void * dest
Definition: strings.h:176
static unsigned int source_size
Definition: bigint.h:240
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38

Shrink big integer.

Parameters
sourceSource big integer
destDestination big integer

Definition at line 172 of file bigint.h.

◆ bigint_multiply

#define bigint_multiply (   multiplicand,
  multiplier,
  result 
)
Value:
do { \
unsigned int size = bigint_size (multiplicand); \
bigint_multiply_raw ( (multiplicand)->element, \
(multiplier)->element, (result)->element, \
size ); \
} while ( 0 )
uint8_t multiplier
Port multiplier number.
Definition: edd.h:32
int result
Definition: bigint.h:148
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Multiply big integers.

Parameters
multiplicandBig integer to be multiplied
multiplierBig integer to be multiplied
resultBig integer to hold result

Definition at line 186 of file bigint.h.

◆ bigint_mod_multiply

#define bigint_mod_multiply (   multiplicand,
  multiplier,
  modulus,
  result,
  tmp 
)
Value:
do { \
unsigned int size = bigint_size (multiplicand); \
bigint_mod_multiply_raw ( (multiplicand)->element, \
(multiplier)->element, \
(modulus)->element, \
(result)->element, size, tmp ); \
} while ( 0 )
uint8_t multiplier
Port multiplier number.
Definition: edd.h:32
int result
Definition: bigint.h:148
uint8_t * tmp
Definition: entropy.h:156
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Perform modular multiplication of big integers.

Parameters
multiplicandBig integer to be multiplied
multiplierBig integer to be multiplied
modulusBig integer modulus
resultBig integer to hold result
tmpTemporary working space

Definition at line 202 of file bigint.h.

◆ bigint_mod_multiply_tmp_len

#define bigint_mod_multiply_tmp_len (   modulus)
Value:
( { \
unsigned int size = bigint_size (modulus); \
sizeof ( struct { \
bigint_t ( size * 2 ) temp_result; \
bigint_t ( size * 2 ) temp_modulus; \
} ); } )
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Calculate temporary working space required for moduluar multiplication.

Parameters
modulusBig integer modulus
Return values
lenLength of temporary working space

Definition at line 217 of file bigint.h.

◆ bigint_mod_exp

#define bigint_mod_exp (   base,
  modulus,
  exponent,
  result,
  tmp 
)
Value:
do { \
unsigned int size = bigint_size (base); \
unsigned int exponent_size = bigint_size (exponent); \
bigint_mod_exp_raw ( (base)->element, (modulus)->element, \
(exponent)->element, (result)->element, \
size, exponent_size, tmp ); \
} while ( 0 )
int result
Definition: bigint.h:148
uint8_t * tmp
Definition: entropy.h:156
uint16_t base
Base address.
Definition: edd.h:14
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Perform modular exponentiation of big integers.

Parameters
baseBig integer base
modulusBig integer modulus
exponentBig integer exponent
resultBig integer to hold result
tmpTemporary working space

Definition at line 233 of file bigint.h.

◆ bigint_mod_exp_tmp_len

#define bigint_mod_exp_tmp_len (   modulus,
  exponent 
)
Value:
( { \
unsigned int size = bigint_size (modulus); \
unsigned int exponent_size = bigint_size (exponent); \
size_t mod_multiply_len = \
bigint_mod_multiply_tmp_len (modulus); \
sizeof ( struct { \
bigint_t ( size ) temp_base; \
bigint_t ( exponent_size ) temp_exponent; \
uint8_t mod_multiply[mod_multiply_len]; \
} ); } )
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:38
static unsigned int size
Definition: bigint.h:26

Calculate temporary working space required for moduluar exponentiation.

Parameters
modulusBig integer modulus
exponentBig integer exponent
Return values
lenLength of temporary working space

Definition at line 248 of file bigint.h.

Function Documentation

◆ FILE_LICENCE()

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )

◆ bigint_init_raw()

void bigint_init_raw ( bigint_element_t value0,
unsigned int  size,
const void *  data,
size_t  len 
)

◆ bigint_done_raw()

void bigint_done_raw ( const bigint_element_t value0,
unsigned int  size,
void *  out,
size_t  len 
)

◆ bigint_add_raw()

void bigint_add_raw ( const bigint_element_t addend0,
bigint_element_t value0,
unsigned int  size 
)

◆ bigint_subtract_raw()

void bigint_subtract_raw ( const bigint_element_t subtrahend0,
bigint_element_t value0,
unsigned int  size 
)

◆ bigint_rol_raw()

void bigint_rol_raw ( bigint_element_t value0,
unsigned int  size 
)

◆ bigint_ror_raw()

void bigint_ror_raw ( bigint_element_t value0,
unsigned int  size 
)

◆ bigint_is_zero_raw()

int bigint_is_zero_raw ( const bigint_element_t value0,
unsigned int  size 
)

◆ bigint_is_geq_raw()

int bigint_is_geq_raw ( const bigint_element_t value0,
const bigint_element_t reference0,
unsigned int  size 
)

◆ bigint_bit_is_set_raw()

int bigint_bit_is_set_raw ( const bigint_element_t value0,
unsigned int  size,
unsigned int  bit 
)

◆ bigint_max_set_bit_raw()

int bigint_max_set_bit_raw ( const bigint_element_t value0,
unsigned int  size 
)

◆ bigint_grow_raw()

void bigint_grow_raw ( const bigint_element_t source0,
unsigned int  source_size,
bigint_element_t dest0,
unsigned int  dest_size 
)

◆ bigint_shrink_raw()

void bigint_shrink_raw ( const bigint_element_t source0,
unsigned int  source_size,
bigint_element_t dest0,
unsigned int  dest_size 
)

◆ bigint_multiply_raw()

void bigint_multiply_raw ( const uint32_t multiplicand0,
const uint32_t multiplier0,
uint32_t result0,
unsigned int  size 
)

Multiply big integers.

Parameters
multiplicand0Element 0 of big integer to be multiplied
multiplier0Element 0 of big integer to be multiplied
result0Element 0 of big integer to hold result
sizeNumber of elements

Definition at line 43 of file x86_bigint.c.

45  {
46  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
47  ( ( const void * ) multiplicand0 );
48  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
49  ( ( const void * ) multiplier0 );
50  bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
51  ( ( void * ) result0 );
52  unsigned int i;
53  unsigned int j;
54  uint32_t multiplicand_element;
55  uint32_t multiplier_element;
56  uint32_t *result_elements;
57  uint32_t discard_a;
58  uint32_t discard_d;
59  long index;
60 
61  /* Zero result */
62  memset ( result, 0, sizeof ( *result ) );
63 
64  /* Multiply integers one element at a time */
65  for ( i = 0 ; i < size ; i++ ) {
66  multiplicand_element = multiplicand->element[i];
67  for ( j = 0 ; j < size ; j++ ) {
68  multiplier_element = multiplier->element[j];
69  result_elements = &result->element[ i + j ];
70  /* Perform a single multiply, and add the
71  * resulting double-element into the result,
72  * carrying as necessary. The carry can
73  * never overflow beyond the end of the
74  * result, since:
75  *
76  * a < 2^{n}, b < 2^{n} => ab < 2^{2n}
77  */
78  __asm__ __volatile__ ( "mull %4\n\t"
79  "addl %%eax, (%5,%2,4)\n\t"
80  "adcl %%edx, 4(%5,%2,4)\n\t"
81  "\n1:\n\t"
82  "adcl $0, 8(%5,%2,4)\n\t"
83  "inc %2\n\t"
84  /* Does not affect CF */
85  "jc 1b\n\t"
86  : "=&a" ( discard_a ),
87  "=&d" ( discard_d ),
88  "=&r" ( index )
89  : "0" ( multiplicand_element ),
90  "g" ( multiplier_element ),
91  "r" ( result_elements ),
92  "2" ( 0 ) );
93  }
94  }
95 }
#define __attribute__(x)
Definition: compiler.h:10
uint8_t multiplier
Port multiplier number.
Definition: edd.h:32
int result
Definition: bigint.h:148
#define bigint_t(size)
Define a big-integer type.
Definition: bigint.h:17
unsigned int uint32_t
Definition: stdint.h:12
__asm__ __volatile__("\n1:\n\t" "movb -1(%2,%1), %%al\n\t" "stosb\n\t" "loop 1b\n\t" "xorl %%eax, %%eax\n\t" "mov %3, %1\n\t" "rep stosb\n\t" :"=&D"(discard_D), "=&c"(discard_c) :"r"(data), "g"(pad_len), "0"(value0), "1"(len) :"eax")
__asm__(".section \".rodata\", \"a\", " PROGBITS "\n\t" "\nprivate_key_data:\n\t" ".size private_key_data, ( . - private_key_data )\n\t" ".equ private_key_len, ( . - private_key_data )\n\t" ".previous\n\t")
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
uint64_t index
Index of the first segment within the content.
Definition: pccrc.h:21
void * memset(void *dest, int character, size_t len) __nonnull

◆ bigint_mod_multiply_raw()

void bigint_mod_multiply_raw ( const bigint_element_t multiplicand0,
const bigint_element_t multiplier0,
const bigint_element_t modulus0,
bigint_element_t result0,
unsigned int  size,
void *  tmp 
)

Perform modular multiplication of big integers.

Parameters
multiplicand0Element 0 of big integer to be multiplied
multiplier0Element 0 of big integer to be multiplied
modulus0Element 0 of big integer modulus
result0Element 0 of big integer to hold result
sizeNumber of elements in base, modulus, and result
tmpTemporary working space

Definition at line 63 of file bigint.c.

67  {
68  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
69  ( ( const void * ) multiplicand0 );
70  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
71  ( ( const void * ) multiplier0 );
72  const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
73  ( ( const void * ) modulus0 );
74  bigint_t ( size ) __attribute__ (( may_alias )) *result =
75  ( ( void * ) result0 );
76  struct {
77  bigint_t ( size * 2 ) result;
78  bigint_t ( size * 2 ) modulus;
79  } *temp = tmp;
80  int rotation;
81  int i;
82 
83  /* Start profiling */
84  profile_start ( &bigint_mod_multiply_profiler );
85 
86  /* Sanity check */
87  assert ( sizeof ( *temp ) == bigint_mod_multiply_tmp_len ( modulus ) );
88 
89  /* Perform multiplication */
90  profile_start ( &bigint_mod_multiply_multiply_profiler );
91  bigint_multiply ( multiplicand, multiplier, &temp->result );
92  profile_stop ( &bigint_mod_multiply_multiply_profiler );
93 
94  /* Rescale modulus to match result */
95  profile_start ( &bigint_mod_multiply_rescale_profiler );
96  bigint_grow ( modulus, &temp->modulus );
97  rotation = ( bigint_max_set_bit ( &temp->result ) -
98  bigint_max_set_bit ( &temp->modulus ) );
99  for ( i = 0 ; i < rotation ; i++ )
100  bigint_rol ( &temp->modulus );
101  profile_stop ( &bigint_mod_multiply_rescale_profiler );
102 
103  /* Subtract multiples of modulus */
104  profile_start ( &bigint_mod_multiply_subtract_profiler );
105  for ( i = 0 ; i <= rotation ; i++ ) {
106  if ( bigint_is_geq ( &temp->result, &temp->modulus ) )
107  bigint_subtract ( &temp->modulus, &temp->result );
108  bigint_ror ( &temp->modulus );
109  }
110  profile_stop ( &bigint_mod_multiply_subtract_profiler );
111 
112  /* Resize result */
113  bigint_shrink ( &temp->result, result );
114 
115  /* Sanity check */
116  assert ( bigint_is_geq ( modulus, result ) );
117 
118  /* Stop profiling */
119  profile_stop ( &bigint_mod_multiply_profiler );
120 }
#define __attribute__(x)
Definition: compiler.h:10
#define bigint_max_set_bit(value)
Find highest bit set in big integer.
Definition: bigint.h:149
#define bigint_ror(value)
Rotate big integer right.
Definition: bigint.h:104
#define bigint_grow(source, dest)
Grow big integer.
Definition: bigint.h:159
static void profile_stop(struct profiler *profiler)
Stop profiling.
Definition: profile.h:171
uint8_t multiplier
Port multiplier number.
Definition: edd.h:32
#define bigint_is_geq(value, reference)
Compare big integers.
Definition: bigint.h:127
int result
Definition: bigint.h:148
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
#define bigint_shrink(source, dest)
Shrink big integer.
Definition: bigint.h:172
#define bigint_t(size)
Define a big-integer type.
Definition: bigint.h:17
static void profile_start(struct profiler *profiler)
Start profiling.
Definition: profile.h:158
#define bigint_rol(value)
Rotate big integer left.
Definition: bigint.h:94
uint8_t * tmp
Definition: entropy.h:156
static unsigned int rotation
Definition: rotate.h:22
#define bigint_mod_multiply_tmp_len(modulus)
Calculate temporary working space required for moduluar multiplication.
Definition: bigint.h:217
#define bigint_multiply(multiplicand, multiplier, result)
Multiply big integers.
Definition: bigint.h:186
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
#define bigint_subtract(subtrahend, value)
Subtract big integers.
Definition: bigint.h:83

References __attribute__, assert(), bigint_grow, bigint_is_geq, bigint_max_set_bit, bigint_mod_multiply_tmp_len, bigint_multiply, bigint_rol, bigint_ror, bigint_shrink, bigint_subtract, bigint_t, multiplier, profile_start(), profile_stop(), result, rotation, size, and tmp.

◆ bigint_mod_exp_raw()

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.

Parameters
base0Element 0 of big integer base
modulus0Element 0 of big integer modulus
exponent0Element 0 of big integer exponent
result0Element 0 of big integer to hold result
sizeNumber of elements in base, modulus, and result
exponent_sizeNumber of elements in exponent
tmpTemporary working space

Definition at line 133 of file bigint.c.

138  {
139  const bigint_t ( size ) __attribute__ (( may_alias )) *base =
140  ( ( const void * ) base0 );
141  const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
142  ( ( const void * ) modulus0 );
143  const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
144  *exponent = ( ( const void * ) exponent0 );
145  bigint_t ( size ) __attribute__ (( may_alias )) *result =
146  ( ( void * ) result0 );
147  size_t mod_multiply_len = bigint_mod_multiply_tmp_len ( modulus );
148  struct {
149  bigint_t ( size ) base;
150  bigint_t ( exponent_size ) exponent;
151  uint8_t mod_multiply[mod_multiply_len];
152  } *temp = tmp;
153  static const uint8_t start[1] = { 0x01 };
154 
155  memcpy ( &temp->base, base, sizeof ( temp->base ) );
156  memcpy ( &temp->exponent, exponent, sizeof ( temp->exponent ) );
157  bigint_init ( result, start, sizeof ( start ) );
158 
159  while ( ! bigint_is_zero ( &temp->exponent ) ) {
160  if ( bigint_bit_is_set ( &temp->exponent, 0 ) ) {
161  bigint_mod_multiply ( result, &temp->base, modulus,
162  result, temp->mod_multiply );
163  }
164  bigint_ror ( &temp->exponent );
165  bigint_mod_multiply ( &temp->base, &temp->base, modulus,
166  &temp->base, temp->mod_multiply );
167  }
168 }
#define __attribute__(x)
Definition: compiler.h:10
#define bigint_ror(value)
Rotate big integer right.
Definition: bigint.h:104
#define bigint_init(value, data, len)
Initialise big integer.
Definition: bigint.h:48
#define bigint_is_zero(value)
Test if big integer is equal to zero.
Definition: bigint.h:116
uint32_t start
Starting offset.
Definition: netvsc.h:12
void * memcpy(void *dest, const void *src, size_t len) __nonnull
int result
Definition: bigint.h:148
#define bigint_t(size)
Define a big-integer type.
Definition: bigint.h:17
uint8_t * tmp
Definition: entropy.h:156
unsigned char uint8_t
Definition: stdint.h:10
uint16_t base
Base address.
Definition: edd.h:14
#define bigint_mod_multiply(multiplicand, multiplier, modulus, result, tmp)
Perform modular multiplication of big integers.
Definition: bigint.h:202
#define bigint_mod_multiply_tmp_len(modulus)
Calculate temporary working space required for moduluar multiplication.
Definition: bigint.h:217
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
#define bigint_bit_is_set(value, bit)
Test if bit is set in big integer.
Definition: bigint.h:139

References __attribute__, base, bigint_bit_is_set, bigint_init, bigint_is_zero, bigint_mod_multiply, bigint_mod_multiply_tmp_len, bigint_ror, bigint_t, memcpy(), result, size, start, and tmp.