iPXE
bigint.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 #include <stdint.h>
00027 #include <string.h>
00028 #include <assert.h>
00029 #include <ipxe/bigint.h>
00030 
00031 /** @file
00032  *
00033  * Big integer support
00034  */
00035 
00036 /**
00037  * Perform modular multiplication of big integers
00038  *
00039  * @v multiplicand0     Element 0 of big integer to be multiplied
00040  * @v multiplier0       Element 0 of big integer to be multiplied
00041  * @v modulus0          Element 0 of big integer modulus
00042  * @v result0           Element 0 of big integer to hold result
00043  * @v size              Number of elements in base, modulus, and result
00044  * @v tmp               Temporary working space
00045  */
00046 void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0,
00047                                const bigint_element_t *multiplier0,
00048                                const bigint_element_t *modulus0,
00049                                bigint_element_t *result0,
00050                                unsigned int size, void *tmp ) {
00051         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
00052                 ( ( const void * ) multiplicand0 );
00053         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
00054                 ( ( const void * ) multiplier0 );
00055         const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
00056                 ( ( const void * ) modulus0 );
00057         bigint_t ( size ) __attribute__ (( may_alias )) *result =
00058                 ( ( void * ) result0 );
00059         struct {
00060                 bigint_t ( size * 2 ) result;
00061                 bigint_t ( size * 2 ) modulus;
00062         } *temp = tmp;
00063         int rotation;
00064         int i;
00065 
00066         /* Sanity check */
00067         assert ( sizeof ( *temp ) == bigint_mod_multiply_tmp_len ( modulus ) );
00068 
00069         /* Perform multiplication */
00070         bigint_multiply ( multiplicand, multiplier, &temp->result );
00071 
00072         /* Rescale modulus to match result */
00073         bigint_grow ( modulus, &temp->modulus );
00074         rotation = ( bigint_max_set_bit ( &temp->result ) -
00075                      bigint_max_set_bit ( &temp->modulus ) );
00076         for ( i = 0 ; i < rotation ; i++ )
00077                 bigint_rol ( &temp->modulus );
00078 
00079         /* Subtract multiples of modulus */
00080         for ( i = 0 ; i <= rotation ; i++ ) {
00081                 if ( bigint_is_geq ( &temp->result, &temp->modulus ) )
00082                         bigint_subtract ( &temp->modulus, &temp->result );
00083                 bigint_ror ( &temp->modulus );
00084         }
00085 
00086         /* Resize result */
00087         bigint_shrink ( &temp->result, result );
00088 
00089         /* Sanity check */
00090         assert ( bigint_is_geq ( modulus, result ) );
00091 }
00092 
00093 /**
00094  * Perform modular exponentiation of big integers
00095  *
00096  * @v base0             Element 0 of big integer base
00097  * @v modulus0          Element 0 of big integer modulus
00098  * @v exponent0         Element 0 of big integer exponent
00099  * @v result0           Element 0 of big integer to hold result
00100  * @v size              Number of elements in base, modulus, and result
00101  * @v exponent_size     Number of elements in exponent
00102  * @v tmp               Temporary working space
00103  */
00104 void bigint_mod_exp_raw ( const bigint_element_t *base0,
00105                           const bigint_element_t *modulus0,
00106                           const bigint_element_t *exponent0,
00107                           bigint_element_t *result0,
00108                           unsigned int size, unsigned int exponent_size,
00109                           void *tmp ) {
00110         const bigint_t ( size ) __attribute__ (( may_alias )) *base =
00111                 ( ( const void * ) base0 );
00112         const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
00113                 ( ( const void * ) modulus0 );
00114         const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
00115                 *exponent = ( ( const void * ) exponent0 );
00116         bigint_t ( size ) __attribute__ (( may_alias )) *result =
00117                 ( ( void * ) result0 );
00118         size_t mod_multiply_len = bigint_mod_multiply_tmp_len ( modulus );
00119         struct {
00120                 bigint_t ( size ) base;
00121                 bigint_t ( exponent_size ) exponent;
00122                 uint8_t mod_multiply[mod_multiply_len];
00123         } *temp = tmp;
00124         static const uint8_t start[1] = { 0x01 };
00125 
00126         memcpy ( &temp->base, base, sizeof ( temp->base ) );
00127         memcpy ( &temp->exponent, exponent, sizeof ( temp->exponent ) );
00128         bigint_init ( result, start, sizeof ( start ) );
00129 
00130         while ( ! bigint_is_zero ( &temp->exponent ) ) {
00131                 if ( bigint_bit_is_set ( &temp->exponent, 0 ) ) {
00132                         bigint_mod_multiply ( result, &temp->base, modulus,
00133                                               result, temp->mod_multiply );
00134                 }
00135                 bigint_ror ( &temp->exponent );
00136                 bigint_mod_multiply ( &temp->base, &temp->base, modulus,
00137                                       &temp->base, temp->mod_multiply );
00138         }
00139 }