iPXE
Functions
bigint.c File Reference

Big integer support. More...

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

Go to the source code of this file.

Functions

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


Function Documentation

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )
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 );
        }
}