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/profile.h>
00030 #include <ipxe/bigint.h>
00031 
00032 /** @file
00033  *
00034  * Big integer support
00035  */
00036 
00037 /** Modular multiplication overall profiler */
00038 static struct profiler bigint_mod_multiply_profiler __profiler =
00039         { .name = "bigint_mod_multiply" };
00040 
00041 /** Modular multiplication multiply step profiler */
00042 static struct profiler bigint_mod_multiply_multiply_profiler __profiler =
00043         { .name = "bigint_mod_multiply.multiply" };
00044 
00045 /** Modular multiplication rescale step profiler */
00046 static struct profiler bigint_mod_multiply_rescale_profiler __profiler =
00047         { .name = "bigint_mod_multiply.rescale" };
00048 
00049 /** Modular multiplication subtract step profiler */
00050 static struct profiler bigint_mod_multiply_subtract_profiler __profiler =
00051         { .name = "bigint_mod_multiply.subtract" };
00052 
00053 /**
00054  * Perform modular multiplication of big integers
00055  *
00056  * @v multiplicand0     Element 0 of big integer to be multiplied
00057  * @v multiplier0       Element 0 of big integer to be multiplied
00058  * @v modulus0          Element 0 of big integer modulus
00059  * @v result0           Element 0 of big integer to hold result
00060  * @v size              Number of elements in base, modulus, and result
00061  * @v tmp               Temporary working space
00062  */
00063 void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0,
00064                                const bigint_element_t *multiplier0,
00065                                const bigint_element_t *modulus0,
00066                                bigint_element_t *result0,
00067                                unsigned int size, void *tmp ) {
00068         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
00069                 ( ( const void * ) multiplicand0 );
00070         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
00071                 ( ( const void * ) multiplier0 );
00072         const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
00073                 ( ( const void * ) modulus0 );
00074         bigint_t ( size ) __attribute__ (( may_alias )) *result =
00075                 ( ( void * ) result0 );
00076         struct {
00077                 bigint_t ( size * 2 ) result;
00078                 bigint_t ( size * 2 ) modulus;
00079         } *temp = tmp;
00080         int rotation;
00081         int i;
00082 
00083         /* Start profiling */
00084         profile_start ( &bigint_mod_multiply_profiler );
00085 
00086         /* Sanity check */
00087         assert ( sizeof ( *temp ) == bigint_mod_multiply_tmp_len ( modulus ) );
00088 
00089         /* Perform multiplication */
00090         profile_start ( &bigint_mod_multiply_multiply_profiler );
00091         bigint_multiply ( multiplicand, multiplier, &temp->result );
00092         profile_stop ( &bigint_mod_multiply_multiply_profiler );
00093 
00094         /* Rescale modulus to match result */
00095         profile_start ( &bigint_mod_multiply_rescale_profiler );
00096         bigint_grow ( modulus, &temp->modulus );
00097         rotation = ( bigint_max_set_bit ( &temp->result ) -
00098                      bigint_max_set_bit ( &temp->modulus ) );
00099         for ( i = 0 ; i < rotation ; i++ )
00100                 bigint_rol ( &temp->modulus );
00101         profile_stop ( &bigint_mod_multiply_rescale_profiler );
00102 
00103         /* Subtract multiples of modulus */
00104         profile_start ( &bigint_mod_multiply_subtract_profiler );
00105         for ( i = 0 ; i <= rotation ; i++ ) {
00106                 if ( bigint_is_geq ( &temp->result, &temp->modulus ) )
00107                         bigint_subtract ( &temp->modulus, &temp->result );
00108                 bigint_ror ( &temp->modulus );
00109         }
00110         profile_stop ( &bigint_mod_multiply_subtract_profiler );
00111 
00112         /* Resize result */
00113         bigint_shrink ( &temp->result, result );
00114 
00115         /* Sanity check */
00116         assert ( bigint_is_geq ( modulus, result ) );
00117 
00118         /* Stop profiling */
00119         profile_stop ( &bigint_mod_multiply_profiler );
00120 }
00121 
00122 /**
00123  * Perform modular exponentiation of big integers
00124  *
00125  * @v base0             Element 0 of big integer base
00126  * @v modulus0          Element 0 of big integer modulus
00127  * @v exponent0         Element 0 of big integer exponent
00128  * @v result0           Element 0 of big integer to hold result
00129  * @v size              Number of elements in base, modulus, and result
00130  * @v exponent_size     Number of elements in exponent
00131  * @v tmp               Temporary working space
00132  */
00133 void bigint_mod_exp_raw ( const bigint_element_t *base0,
00134                           const bigint_element_t *modulus0,
00135                           const bigint_element_t *exponent0,
00136                           bigint_element_t *result0,
00137                           unsigned int size, unsigned int exponent_size,
00138                           void *tmp ) {
00139         const bigint_t ( size ) __attribute__ (( may_alias )) *base =
00140                 ( ( const void * ) base0 );
00141         const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
00142                 ( ( const void * ) modulus0 );
00143         const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
00144                 *exponent = ( ( const void * ) exponent0 );
00145         bigint_t ( size ) __attribute__ (( may_alias )) *result =
00146                 ( ( void * ) result0 );
00147         size_t mod_multiply_len = bigint_mod_multiply_tmp_len ( modulus );
00148         struct {
00149                 bigint_t ( size ) base;
00150                 bigint_t ( exponent_size ) exponent;
00151                 uint8_t mod_multiply[mod_multiply_len];
00152         } *temp = tmp;
00153         static const uint8_t start[1] = { 0x01 };
00154 
00155         memcpy ( &temp->base, base, sizeof ( temp->base ) );
00156         memcpy ( &temp->exponent, exponent, sizeof ( temp->exponent ) );
00157         bigint_init ( result, start, sizeof ( start ) );
00158 
00159         while ( ! bigint_is_zero ( &temp->exponent ) ) {
00160                 if ( bigint_bit_is_set ( &temp->exponent, 0 ) ) {
00161                         bigint_mod_multiply ( result, &temp->base, modulus,
00162                                               result, temp->mod_multiply );
00163                 }
00164                 bigint_ror ( &temp->exponent );
00165                 bigint_mod_multiply ( &temp->base, &temp->base, modulus,
00166                                       &temp->base, temp->mod_multiply );
00167         }
00168 }