iPXE
Macros | Functions
bigint.h File Reference

Big integer support. More...

#include <assert.h>
#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_copy(source, dest)
 Copy big integer. More...
 
#define bigint_swap(first, second, swap)
 Conditionally swap big integers (in constant time) 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_swap_raw (bigint_element_t *first0, bigint_element_t *second0, unsigned int size, int swap)
 Conditionally swap big integers (in constant time) More...
 
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. 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 19 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 30 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 40 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:40
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 50 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:40
static unsigned int size void * out
Definition: bigint.h:306
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 63 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:40
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 74 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:40
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 85 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:40
static unsigned int size
Definition: bigint.h:26

Rotate big integer left.

Parameters
valueBig integer

Definition at line 96 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:40
static unsigned int size
Definition: bigint.h:26

Rotate big integer right.

Parameters
valueBig integer

Definition at line 106 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:40
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 118 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:40
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 129 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:208
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:40
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 141 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:40
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 151 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:253
static void * dest
Definition: strings.h:176
static unsigned int source_size
Definition: bigint.h:252
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:40

Grow big integer.

Parameters
sourceSource big integer
destDestination big integer

Definition at line 161 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:253
static void * dest
Definition: strings.h:176
static unsigned int source_size
Definition: bigint.h:252
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:40

Shrink big integer.

Parameters
sourceSource big integer
destDestination big integer

Definition at line 174 of file bigint.h.

◆ bigint_copy

#define bigint_copy (   source,
  dest 
)
Value:
do { \
build_assert ( sizeof ( *(source) ) == sizeof ( *(dest) ) ); \
bigint_shrink ( (source), (dest) ); \
} while ( 0 )
static void * dest
Definition: strings.h:176

Copy big integer.

Parameters
sourceSource big integer
destDestination big integer

Definition at line 187 of file bigint.h.

◆ bigint_swap

#define bigint_swap (   first,
  second,
  swap 
)
Value:
do { \
unsigned int size = bigint_size (first); \
bigint_swap_raw ( (first)->element, (second)->element, size, \
(swap) ); \
} while ( 0 )
static __always_inline int off_t userptr_t second
Definition: efi_uaccess.h:80
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:40
static unsigned int size
Definition: bigint.h:26
uint32_t first
Length to skip in first segment.
Definition: pccrc.h:23

Conditionally swap big integers (in constant time)

Parameters
firstBig integer to be conditionally swapped
secondBig integer to be conditionally swapped
swapSwap first and second big integers

Definition at line 199 of file bigint.h.

◆ bigint_multiply

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

Multiply big integers.

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

Definition at line 212 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
unsigned long tmp
Definition: linux_pci.h:53
int result
Definition: bigint.h:160
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:40
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 229 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:40
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 244 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 )
static const void * base
Base address.
Definition: crypto.h:335
unsigned long tmp
Definition: linux_pci.h:53
int result
Definition: bigint.h:160
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:40
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 260 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:40
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 275 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_swap_raw()

void bigint_swap_raw ( bigint_element_t first0,
bigint_element_t second0,
unsigned int  size,
int  swap 
)

Conditionally swap big integers (in constant time)

Parameters
first0Element 0 of big integer to be conditionally swapped
second0Element 0 of big integer to be conditionally swapped
sizeNumber of elements in big integers
swapSwap first and second big integers

Definition at line 61 of file bigint.c.

62  {
63  bigint_element_t mask;
65  unsigned int i;
66 
67  /* Construct mask */
68  mask = ( ( bigint_element_t ) ( ! swap ) - 1 );
69 
70  /* Conditionally swap elements */
71  for ( i = 0 ; i < size ; i++ ) {
72  xor = ( mask & ( first0[i] ^ second0[i] ) );
73  first0[i] ^= xor;
74  second0[i] ^= xor;
75  }
76 }
static u32 xor(u32 a, u32 b)
Definition: tlan.h:457
uint32_t bigint_element_t
Element of a big integer.
Definition: bigint.h:15
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16

References size, and xor().

◆ bigint_multiply_raw()

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

Multiply big integers.

Parameters
multiplicand0Element 0 of big integer to be multiplied
multiplicand_sizeNumber of elements in multiplicand
multiplier0Element 0 of big integer to be multiplied
multiplier_sizeNumber of elements in multiplier
result0Element 0 of big integer to hold result

Definition at line 44 of file x86_bigint.c.

48  {
49  unsigned int result_size = ( multiplicand_size + multiplier_size );
50  const bigint_t ( multiplicand_size ) __attribute__ (( may_alias ))
51  *multiplicand = ( ( const void * ) multiplicand0 );
52  const bigint_t ( multiplier_size ) __attribute__ (( may_alias ))
53  *multiplier = ( ( const void * ) multiplier0 );
54  bigint_t ( result_size ) __attribute__ (( may_alias ))
55  *result = ( ( void * ) result0 );
56  unsigned int i;
57  unsigned int j;
58  uint32_t multiplicand_element;
59  uint32_t multiplier_element;
60  uint32_t *result_elements;
61  uint32_t discard_a;
62  uint32_t discard_d;
63  long index;
64 
65  /* Zero result */
66  memset ( result, 0, sizeof ( *result ) );
67 
68  /* Multiply integers one element at a time */
69  for ( i = 0 ; i < multiplicand_size ; i++ ) {
70  multiplicand_element = multiplicand->element[i];
71  for ( j = 0 ; j < multiplier_size ; j++ ) {
72  multiplier_element = multiplier->element[j];
73  result_elements = &result->element[ i + j ];
74  /* Perform a single multiply, and add the
75  * resulting double-element into the result,
76  * carrying as necessary. The carry can
77  * never overflow beyond the end of the
78  * result, since:
79  *
80  * a < 2^{n}, b < 2^{m} => ab < 2^{n+m}
81  */
82  __asm__ __volatile__ ( "mull %5\n\t"
83  "addl %%eax, (%6,%2,4)\n\t"
84  "adcl %%edx, 4(%6,%2,4)\n\t"
85  "\n1:\n\t"
86  "adcl $0, 8(%6,%2,4)\n\t"
87  "inc %2\n\t"
88  /* Does not affect CF */
89  "jc 1b\n\t"
90  : "=&a" ( discard_a ),
91  "=&d" ( discard_d ),
92  "=&r" ( index ),
93  "+m" ( *result )
94  : "0" ( multiplicand_element ),
95  "g" ( multiplier_element ),
96  "r" ( result_elements ),
97  "2" ( 0 ) );
98  }
99  }
100 }
#define __attribute__(x)
Definition: compiler.h:10
static const void const void void * result
Definition: crypto.h:335
uint8_t multiplier
Port multiplier number.
Definition: edd.h:32
__asm__ __volatile__("\n1:\n\t" "movb -1(%3,%1), %%al\n\t" "stosb\n\t" "loop 1b\n\t" "xorl %%eax, %%eax\n\t" "mov %4, %1\n\t" "rep stosb\n\t" :"=&D"(discard_D), "=&c"(discard_c), "+m"(*value) :"r"(data), "g"(pad_len), "0"(value0), "1"(len) :"eax")
unsigned int uint32_t
Definition: stdint.h:12
__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")
uint64_t index
Index of the first segment within the content.
Definition: pccrc.h:21
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.
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 88 of file bigint.c.

92  {
93  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
94  ( ( const void * ) multiplicand0 );
95  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
96  ( ( const void * ) multiplier0 );
97  const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
98  ( ( const void * ) modulus0 );
99  bigint_t ( size ) __attribute__ (( may_alias )) *result =
100  ( ( void * ) result0 );
101  struct {
102  bigint_t ( size * 2 ) result;
103  bigint_t ( size * 2 ) modulus;
104  } *temp = tmp;
105  int rotation;
106  int i;
107 
108  /* Start profiling */
109  profile_start ( &bigint_mod_multiply_profiler );
110 
111  /* Sanity check */
112  assert ( sizeof ( *temp ) == bigint_mod_multiply_tmp_len ( modulus ) );
113 
114  /* Perform multiplication */
115  profile_start ( &bigint_mod_multiply_multiply_profiler );
116  bigint_multiply ( multiplicand, multiplier, &temp->result );
117  profile_stop ( &bigint_mod_multiply_multiply_profiler );
118 
119  /* Rescale modulus to match result */
120  profile_start ( &bigint_mod_multiply_rescale_profiler );
121  bigint_grow ( modulus, &temp->modulus );
122  rotation = ( bigint_max_set_bit ( &temp->result ) -
123  bigint_max_set_bit ( &temp->modulus ) );
124  for ( i = 0 ; i < rotation ; i++ )
125  bigint_rol ( &temp->modulus );
126  profile_stop ( &bigint_mod_multiply_rescale_profiler );
127 
128  /* Subtract multiples of modulus */
129  profile_start ( &bigint_mod_multiply_subtract_profiler );
130  for ( i = 0 ; i <= rotation ; i++ ) {
131  if ( bigint_is_geq ( &temp->result, &temp->modulus ) )
132  bigint_subtract ( &temp->modulus, &temp->result );
133  bigint_ror ( &temp->modulus );
134  }
135  profile_stop ( &bigint_mod_multiply_subtract_profiler );
136 
137  /* Resize result */
138  bigint_shrink ( &temp->result, result );
139 
140  /* Sanity check */
141  assert ( bigint_is_geq ( modulus, result ) );
142 
143  /* Stop profiling */
144  profile_stop ( &bigint_mod_multiply_profiler );
145 }
#define __attribute__(x)
Definition: compiler.h:10
static const void const void void * result
Definition: crypto.h:335
#define bigint_max_set_bit(value)
Find highest bit set in big integer.
Definition: bigint.h:151
#define bigint_ror(value)
Rotate big integer right.
Definition: bigint.h:106
#define bigint_grow(source, dest)
Grow big integer.
Definition: bigint.h:161
static void profile_stop(struct profiler *profiler)
Stop profiling.
Definition: profile.h:171
uint8_t multiplier
Port multiplier number.
Definition: edd.h:32
unsigned long tmp
Definition: linux_pci.h:53
#define bigint_is_geq(value, reference)
Compare big integers.
Definition: bigint.h:129
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
#define bigint_shrink(source, dest)
Shrink big integer.
Definition: bigint.h:174
static void profile_start(struct profiler *profiler)
Start profiling.
Definition: profile.h:158
#define bigint_rol(value)
Rotate big integer left.
Definition: bigint.h:96
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:244
#define bigint_multiply(multiplicand, multiplier, result)
Multiply big integers.
Definition: bigint.h:212
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
#define bigint_subtract(subtrahend, value)
Subtract big integers.
Definition: bigint.h:85
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.

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 158 of file bigint.c.

163  {
164  const bigint_t ( size ) __attribute__ (( may_alias )) *base =
165  ( ( const void * ) base0 );
166  const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
167  ( ( const void * ) modulus0 );
168  const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
169  *exponent = ( ( const void * ) exponent0 );
170  bigint_t ( size ) __attribute__ (( may_alias )) *result =
171  ( ( void * ) result0 );
172  size_t mod_multiply_len = bigint_mod_multiply_tmp_len ( modulus );
173  struct {
174  bigint_t ( size ) base;
175  bigint_t ( exponent_size ) exponent;
176  uint8_t mod_multiply[mod_multiply_len];
177  } *temp = tmp;
178  static const uint8_t start[1] = { 0x01 };
179 
180  memcpy ( &temp->base, base, sizeof ( temp->base ) );
181  memcpy ( &temp->exponent, exponent, sizeof ( temp->exponent ) );
182  bigint_init ( result, start, sizeof ( start ) );
183 
184  while ( ! bigint_is_zero ( &temp->exponent ) ) {
185  if ( bigint_bit_is_set ( &temp->exponent, 0 ) ) {
186  bigint_mod_multiply ( result, &temp->base, modulus,
187  result, temp->mod_multiply );
188  }
189  bigint_ror ( &temp->exponent );
190  bigint_mod_multiply ( &temp->base, &temp->base, modulus,
191  &temp->base, temp->mod_multiply );
192  }
193 }
#define __attribute__(x)
Definition: compiler.h:10
static const void const void void * result
Definition: crypto.h:335
#define bigint_ror(value)
Rotate big integer right.
Definition: bigint.h:106
#define bigint_init(value, data, len)
Initialise big integer.
Definition: bigint.h:50
#define bigint_is_zero(value)
Test if big integer is equal to zero.
Definition: bigint.h:118
static const void * base
Base address.
Definition: crypto.h:335
uint32_t start
Starting offset.
Definition: netvsc.h:12
unsigned long tmp
Definition: linux_pci.h:53
void * memcpy(void *dest, const void *src, size_t len) __nonnull
unsigned char uint8_t
Definition: stdint.h:10
#define bigint_mod_multiply(multiplicand, multiplier, modulus, result, tmp)
Perform modular multiplication of big integers.
Definition: bigint.h:229
#define bigint_mod_multiply_tmp_len(modulus)
Calculate temporary working space required for moduluar multiplication.
Definition: bigint.h:244
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:141
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.

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.