iPXE
Defines | Functions
bigint.h File Reference

Big integer support. More...

#include <bits/bigint.h>

Go to the source code of this file.

Defines

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

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

Detailed Description

Big integer support.

Definition in file bigint.h.


Define Documentation

#define bigint_t (   size)
#define bigint_required_size (   len)
Value:
( ( (len) + sizeof ( bigint_element_t ) - 1 ) /                 \
          sizeof ( bigint_element_t ) )

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.

Referenced by rsa_alloc().

#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.

#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 )

Initialise big integer.

Parameters:
valueBig integer to initialise
dataRaw data
lenLength of raw data

Definition at line 48 of file bigint.h.

Referenced by bigint_init_sample(), bigint_mod_exp_raw(), rsa_cipher(), and rsa_init().

#define bigint_done (   value,
  out,
  len 
)
Value:
do {                            \
        unsigned int size = bigint_size (value);                        \
        bigint_done_raw ( (value)->element, size, (out), (len) );       \
        } while ( 0 )

Finalise big integer.

Parameters:
valueBig integer to finalise
outOutput buffer
lenLength of output buffer

Definition at line 61 of file bigint.h.

Referenced by bigint_done_sample(), and rsa_cipher().

#define bigint_add (   addend,
  value 
)
Value:
do {                            \
        unsigned int size = bigint_size (addend);                       \
        bigint_add_raw ( (addend)->element, (value)->element, size );   \
        } while ( 0 )

Add big integers.

Parameters:
addendBig integer to add
valueBig integer to be added to

Definition at line 72 of file bigint.h.

Referenced by bigint_add_sample().

#define bigint_subtract (   subtrahend,
  value 
)
Value:
do {                    \
        unsigned int size = bigint_size (subtrahend);                   \
        bigint_subtract_raw ( (subtrahend)->element, (value)->element,  \
                              size );                                   \
        } while ( 0 )

Subtract big integers.

Parameters:
subtrahendBig integer to subtract
valueBig integer to be subtracted from

Definition at line 83 of file bigint.h.

Referenced by bigint_mod_multiply_raw(), and bigint_subtract_sample().

#define bigint_rol (   value)
Value:
do {                                    \
        unsigned int size = bigint_size (value);                        \
        bigint_rol_raw ( (value)->element, size );                      \
        } while ( 0 )

Rotate big integer left.

Parameters:
valueBig integer

Definition at line 94 of file bigint.h.

Referenced by bigint_mod_multiply_raw(), and bigint_rol_sample().

#define bigint_ror (   value)
Value:
do {                                    \
        unsigned int size = bigint_size (value);                        \
        bigint_ror_raw ( (value)->element, size );                      \
        } while ( 0 )

Rotate big integer right.

Parameters:
valueBig integer

Definition at line 104 of file bigint.h.

Referenced by bigint_mod_exp_raw(), bigint_mod_multiply_raw(), and bigint_ror_sample().

#define bigint_is_zero (   value)
Value:
( {                                     \
        unsigned int size = bigint_size (value);                        \
        bigint_is_zero_raw ( (value)->element, size ); } )

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.

Referenced by bigint_is_zero_sample(), and bigint_mod_exp_raw().

#define bigint_is_geq (   value,
  reference 
)
Value:
( {                             \
        unsigned int size = bigint_size (value);                        \
        bigint_is_geq_raw ( (value)->element, (reference)->element,     \
                            size ); } )

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.

Referenced by bigint_is_geq_sample(), and bigint_mod_multiply_raw().

#define bigint_bit_is_set (   value,
  bit 
)
Value:
( {                             \
        unsigned int size = bigint_size (value);                        \
        bigint_bit_is_set_raw ( (value)->element, size, bit ); } )

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.

Referenced by bigint_bit_is_set_sample(), and bigint_mod_exp_raw().

#define bigint_max_set_bit (   value)
Value:
( {                                     \
        unsigned int size = bigint_size (value);                        \
        bigint_max_set_bit_raw ( (value)->element, size ); } )

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.

Referenced by bigint_max_set_bit_sample(), and bigint_mod_multiply_raw().

#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 )

Grow big integer.

Parameters:
sourceSource big integer
destDestination big integer

Definition at line 159 of file bigint.h.

Referenced by bigint_grow_sample(), and bigint_mod_multiply_raw().

#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 )

Shrink big integer.

Parameters:
sourceSource big integer
destDestination big integer

Definition at line 172 of file bigint.h.

Referenced by bigint_mod_multiply_raw(), and bigint_shrink_sample().

#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 )

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.

Referenced by bigint_mod_multiply_raw(), and bigint_multiply_sample().

#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 )

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.

Referenced by bigint_mod_exp_raw(), and bigint_mod_multiply_sample().

#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;                     \
        } ); } )

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.

Referenced by bigint_mod_exp_raw(), and bigint_mod_multiply_raw().

#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 )

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.

Referenced by bigint_mod_exp_sample(), and rsa_cipher().

#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];                 \
        } ); } )

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.

Referenced by rsa_alloc().


Function Documentation

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

References __asm__(), __attribute__, bigint_t, index, memset(), multiplier, and size.

                                                                  {
        const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
                ( ( const void * ) multiplicand0 );
        const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
                ( ( const void * ) multiplier0 );
        bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
                ( ( void * ) result0 );
        unsigned int i;
        unsigned int j;
        uint32_t multiplicand_element;
        uint32_t multiplier_element;
        uint32_t *result_elements;
        uint32_t discard_a;
        uint32_t discard_d;
        long index;

        /* Zero result */
        memset ( result, 0, sizeof ( *result ) );

        /* Multiply integers one element at a time */
        for ( i = 0 ; i < size ; i++ ) {
                multiplicand_element = multiplicand->element[i];
                for ( j = 0 ; j < size ; j++ ) {
                        multiplier_element = multiplier->element[j];
                        result_elements = &result->element[ i + j ];
                        /* Perform a single multiply, and add the
                         * resulting double-element into the result,
                         * carrying as necessary.  The carry can
                         * never overflow beyond the end of the
                         * result, since:
                         *
                         *     a < 2^{n}, b < 2^{n} => ab < 2^{2n}
                         */
                        __asm__ __volatile__ ( "mull %4\n\t"
                                               "addl %%eax, (%5,%2,4)\n\t"
                                               "adcl %%edx, 4(%5,%2,4)\n\t"
                                               "\n1:\n\t"
                                               "adcl $0, 8(%5,%2,4)\n\t"
                                               "inc %2\n\t"
                                                       /* Does not affect CF */
                                               "jc 1b\n\t"
                                               : "=&a" ( discard_a ),
                                                 "=&d" ( discard_d ),
                                                 "=&r" ( index )
                                               : "0" ( multiplicand_element ),
                                                 "g" ( multiplier_element ),
                                                 "r" ( result_elements ),
                                                 "2" ( 0 ) );
                }
        }
}
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 46 of file bigint.c.

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, and multiplier.

                                                              {
        const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
                ( ( const void * ) multiplicand0 );
        const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
                ( ( const void * ) multiplier0 );
        const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
                ( ( const void * ) modulus0 );
        bigint_t ( size ) __attribute__ (( may_alias )) *result =
                ( ( void * ) result0 );
        struct {
                bigint_t ( size * 2 ) result;
                bigint_t ( size * 2 ) modulus;
        } *temp = tmp;
        int rotation;
        int i;

        /* Sanity check */
        assert ( sizeof ( *temp ) == bigint_mod_multiply_tmp_len ( modulus ) );

        /* Perform multiplication */
        bigint_multiply ( multiplicand, multiplier, &temp->result );

        /* Rescale modulus to match result */
        bigint_grow ( modulus, &temp->modulus );
        rotation = ( bigint_max_set_bit ( &temp->result ) -
                     bigint_max_set_bit ( &temp->modulus ) );
        for ( i = 0 ; i < rotation ; i++ )
                bigint_rol ( &temp->modulus );

        /* Subtract multiples of modulus */
        for ( i = 0 ; i <= rotation ; i++ ) {
                if ( bigint_is_geq ( &temp->result, &temp->modulus ) )
                        bigint_subtract ( &temp->modulus, &temp->result );
                bigint_ror ( &temp->modulus );
        }

        /* Resize result */
        bigint_shrink ( &temp->result, result );

        /* Sanity check */
        assert ( bigint_is_geq ( modulus, result ) );
}
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 104 of file bigint.c.

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(), and start.

                                      {
        const bigint_t ( size ) __attribute__ (( may_alias )) *base =
                ( ( const void * ) base0 );
        const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
                ( ( const void * ) modulus0 );
        const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
                *exponent = ( ( const void * ) exponent0 );
        bigint_t ( size ) __attribute__ (( may_alias )) *result =
                ( ( void * ) result0 );
        size_t mod_multiply_len = bigint_mod_multiply_tmp_len ( modulus );
        struct {
                bigint_t ( size ) base;
                bigint_t ( exponent_size ) exponent;
                uint8_t mod_multiply[mod_multiply_len];
        } *temp = tmp;
        static const uint8_t start[1] = { 0x01 };

        memcpy ( &temp->base, base, sizeof ( temp->base ) );
        memcpy ( &temp->exponent, exponent, sizeof ( temp->exponent ) );
        bigint_init ( result, start, sizeof ( start ) );

        while ( ! bigint_is_zero ( &temp->exponent ) ) {
                if ( bigint_bit_is_set ( &temp->exponent, 0 ) ) {
                        bigint_mod_multiply ( result, &temp->base, modulus,
                                              result, temp->mod_multiply );
                }
                bigint_ror ( &temp->exponent );
                bigint_mod_multiply ( &temp->base, &temp->base, modulus,
                                      &temp->base, temp->mod_multiply );
        }
}