src/crypto/bigint.c

   1 /*
   2  * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301, USA.
  18  *
  19  * You can also choose to distribute this program under the terms of
  20  * the Unmodified Binary Distribution Licence (as given in the file
  21  * COPYING.UBDL), provided that you have satisfied its requirements.
  22  */
  23
  24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  25
  26 #include <stdint.h>
  27 #include <string.h>
  28 #include <assert.h>
  29 #include <ipxe/bigint.h>
  30
  31 /** @file
  32  *
  33  * Big integer support
  34  */
  35
  36 /**
  37  * Perform modular multiplication of big integers
  38  *
  39  * @v multiplicand0     Element 0 of big integer to be multiplied
  40  * @v multiplier0       Element 0 of big integer to be multiplied
  41  * @v modulus0          Element 0 of big integer modulus
  42  * @v result0           Element 0 of big integer to hold result
  43  * @v size              Number of elements in base, modulus, and result
  44  * @v tmp               Temporary working space
  45  */
  46 void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0,
  47                                const bigint_element_t *multiplier0,
  48                                const bigint_element_t *modulus0,
  49                                bigint_element_t *result0,
  50                                unsigned int size, void *tmp ) {
  51         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
  52                 ( ( const void * ) multiplicand0 );
  53         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
  54                 ( ( const void * ) multiplier0 );
  55         const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
  56                 ( ( const void * ) modulus0 );
  57         bigint_t ( size ) __attribute__ (( may_alias )) *result =
  58                 ( ( void * ) result0 );
  59         struct {
  60                 bigint_t ( size * 2 ) result;
  61                 bigint_t ( size * 2 ) modulus;
  62         } *temp = tmp;
  63         int rotation;
  64         int i;
  65
  66         /* Sanity check */
  67         assert ( sizeof ( *temp ) == bigint_mod_multiply_tmp_len ( modulus ) );
  68
  69         /* Perform multiplication */
  70         bigint_multiply ( multiplicand, multiplier, &temp->result );
  71
  72         /* Rescale modulus to match result */
  73         bigint_grow ( modulus, &temp->modulus );
  74         rotation = ( bigint_max_set_bit ( &temp->result ) -
  75                      bigint_max_set_bit ( &temp->modulus ) );
  76         for ( i = 0 ; i < rotation ; i++ )
  77                 bigint_rol ( &temp->modulus );
  78
  79         /* Subtract multiples of modulus */
  80         for ( i = 0 ; i <= rotation ; i++ ) {
  81                 if ( bigint_is_geq ( &temp->result, &temp->modulus ) )
  82                         bigint_subtract ( &temp->modulus, &temp->result );
  83                 bigint_ror ( &temp->modulus );
  84         }
  85
  86         /* Resize result */
  87         bigint_shrink ( &temp->result, result );
  88
  89         /* Sanity check */
  90         assert ( bigint_is_geq ( modulus, result ) );
  91 }
  92
  93 /**
  94  * Perform modular exponentiation of big integers
  95  *
  96  * @v base0             Element 0 of big integer base
  97  * @v modulus0          Element 0 of big integer modulus
  98  * @v exponent0         Element 0 of big integer exponent
  99  * @v result0           Element 0 of big integer to hold result
 100  * @v size              Number of elements in base, modulus, and result
 101  * @v exponent_size     Number of elements in exponent
 102  * @v tmp               Temporary working space
 103  */
 104 void bigint_mod_exp_raw ( const bigint_element_t *base0,
 105                           const bigint_element_t *modulus0,
 106                           const bigint_element_t *exponent0,
 107                           bigint_element_t *result0,
 108                           unsigned int size, unsigned int exponent_size,
 109                           void *tmp ) {
 110         const bigint_t ( size ) __attribute__ (( may_alias )) *base =
 111                 ( ( const void * ) base0 );
 112         const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
 113                 ( ( const void * ) modulus0 );
 114         const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
 115                 *exponent = ( ( const void * ) exponent0 );
 116         bigint_t ( size ) __attribute__ (( may_alias )) *result =
 117                 ( ( void * ) result0 );
 118         size_t mod_multiply_len = bigint_mod_multiply_tmp_len ( modulus );
 119         struct {
 120                 bigint_t ( size ) base;
 121                 bigint_t ( exponent_size ) exponent;
 122                 uint8_t mod_multiply[mod_multiply_len];
 123         } *temp = tmp;
 124         static const uint8_t start[1] = { 0x01 };
 125
 126         memcpy ( &temp->base, base, sizeof ( temp->base ) );
 127         memcpy ( &temp->exponent, exponent, sizeof ( temp->exponent ) );
 128         bigint_init ( result, start, sizeof ( start ) );
 129
 130         while ( ! bigint_is_zero ( &temp->exponent ) ) {
 131                 if ( bigint_bit_is_set ( &temp->exponent, 0 ) ) {
 132                         bigint_mod_multiply ( result, &temp->base, modulus,
 133                                               result, temp->mod_multiply );
 134                 }
 135                 bigint_ror ( &temp->exponent );
 136                 bigint_mod_multiply ( &temp->base, &temp->base, modulus,
 137                                       &temp->base, temp->mod_multiply );
 138         }
 139 }