qemu/roms/ipxe/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
  20 FILE_LICENCE ( GPL2_OR_LATER );
  21
  22 #include <stdint.h>
  23 #include <string.h>
  24 #include <assert.h>
  25 #include <ipxe/bigint.h>
  26
  27 /** @file
  28  *
  29  * Big integer support
  30  */
  31
  32 /**
  33  * Perform modular multiplication of big integers
  34  *
  35  * @v multiplicand0     Element 0 of big integer to be multiplied
  36  * @v multiplier0       Element 0 of big integer to be multiplied
  37  * @v modulus0          Element 0 of big integer modulus
  38  * @v result0           Element 0 of big integer to hold result
  39  * @v size              Number of elements in base, modulus, and result
  40  * @v tmp               Temporary working space
  41  */
  42 void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0,
  43                                const bigint_element_t *multiplier0,
  44                                const bigint_element_t *modulus0,
  45                                bigint_element_t *result0,
  46                                unsigned int size, void *tmp ) {
  47         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
  48                 ( ( const void * ) multiplicand0 );
  49         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
  50                 ( ( const void * ) multiplier0 );
  51         const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
  52                 ( ( const void * ) modulus0 );
  53         bigint_t ( size ) __attribute__ (( may_alias )) *result =
  54                 ( ( void * ) result0 );
  55         struct {
  56                 bigint_t ( size * 2 ) result;
  57                 bigint_t ( size * 2 ) modulus;
  58         } *temp = tmp;
  59         int rotation;
  60         int i;
  61
  62         /* Sanity check */
  63         assert ( sizeof ( *temp ) == bigint_mod_multiply_tmp_len ( modulus ) );
  64
  65         /* Perform multiplication */
  66         bigint_multiply ( multiplicand, multiplier, &temp->result );
  67
  68         /* Rescale modulus to match result */
  69         bigint_grow ( modulus, &temp->modulus );
  70         rotation = ( bigint_max_set_bit ( &temp->result ) -
  71                      bigint_max_set_bit ( &temp->modulus ) );
  72         for ( i = 0 ; i < rotation ; i++ )
  73                 bigint_rol ( &temp->modulus );
  74
  75         /* Subtract multiples of modulus */
  76         for ( i = 0 ; i <= rotation ; i++ ) {
  77                 if ( bigint_is_geq ( &temp->result, &temp->modulus ) )
  78                         bigint_subtract ( &temp->modulus, &temp->result );
  79                 bigint_ror ( &temp->modulus );
  80         }
  81
  82         /* Resize result */
  83         bigint_shrink ( &temp->result, result );
  84
  85         /* Sanity check */
  86         assert ( bigint_is_geq ( modulus, result ) );
  87 }
  88
  89 /**
  90  * Perform modular exponentiation of big integers
  91  *
  92  * @v base0             Element 0 of big integer base
  93  * @v modulus0          Element 0 of big integer modulus
  94  * @v exponent0         Element 0 of big integer exponent
  95  * @v result0           Element 0 of big integer to hold result
  96  * @v size              Number of elements in base, modulus, and result
  97  * @v exponent_size     Number of elements in exponent
  98  * @v tmp               Temporary working space
  99  */
 100 void bigint_mod_exp_raw ( const bigint_element_t *base0,
 101                           const bigint_element_t *modulus0,
 102                           const bigint_element_t *exponent0,
 103                           bigint_element_t *result0,
 104                           unsigned int size, unsigned int exponent_size,
 105                           void *tmp ) {
 106         const bigint_t ( size ) __attribute__ (( may_alias )) *base =
 107                 ( ( const void * ) base0 );
 108         const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
 109                 ( ( const void * ) modulus0 );
 110         const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
 111                 *exponent = ( ( const void * ) exponent0 );
 112         bigint_t ( size ) __attribute__ (( may_alias )) *result =
 113                 ( ( void * ) result0 );
 114         size_t mod_multiply_len = bigint_mod_multiply_tmp_len ( modulus );
 115         struct {
 116                 bigint_t ( size ) base;
 117                 bigint_t ( exponent_size ) exponent;
 118                 uint8_t mod_multiply[mod_multiply_len];
 119         } *temp = tmp;
 120         static const uint8_t start[1] = { 0x01 };
 121
 122         memcpy ( &temp->base, base, sizeof ( temp->base ) );
 123         memcpy ( &temp->exponent, exponent, sizeof ( temp->exponent ) );
 124         bigint_init ( result, start, sizeof ( start ) );
 125
 126         while ( ! bigint_is_zero ( &temp->exponent ) ) {
 127                 if ( bigint_bit_is_set ( &temp->exponent, 0 ) ) {
 128                         bigint_mod_multiply ( result, &temp->base, modulus,
 129                                               result, temp->mod_multiply );
 130                 }
 131                 bigint_ror ( &temp->exponent );
 132                 bigint_mod_multiply ( &temp->base, &temp->base, modulus,
 133                                       &temp->base, temp->mod_multiply );
 134         }
 135 }