iPXE
Functions | Variables
bigint.c File Reference

Big integer support. More...

#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <ipxe/profile.h>
#include <ipxe/bigint.h>

Go to the source code of this file.

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
 
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_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...
 

Variables

static struct profiler bigint_mod_multiply_profiler __profiler
 Modular multiplication overall profiler. More...
 

Detailed Description

Big integer support.

Definition in file bigint.c.

Function Documentation

◆ FILE_LICENCE()

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )

◆ 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_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.

Variable Documentation

◆ __profiler

struct profiler bigint_mod_multiply_subtract_profiler __profiler
static
Initial value:
=
{ .name = "bigint_mod_multiply" }

Modular multiplication overall profiler.

Modular multiplication subtract step profiler.

Modular multiplication rescale step profiler.

Modular multiplication multiply step profiler.

Definition at line 38 of file bigint.c.