/* * Copyright (C) 2012 Michael Brown . * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of the * License, or any later version. * * This program is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA * 02110-1301, USA. * * You can also choose to distribute this program under the terms of * the Unmodified Binary Distribution Licence (as given in the file * COPYING.UBDL), provided that you have satisfied its requirements. */ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); #include #include #include #include /** @file * * Big integer support */ /** * Perform modular multiplication of big integers * * @v multiplicand0 Element 0 of big integer to be multiplied * @v multiplier0 Element 0 of big integer to be multiplied * @v modulus0 Element 0 of big integer modulus * @v result0 Element 0 of big integer to hold result * @v size Number of elements in base, modulus, and result * @v tmp Temporary working space */ 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 ) { 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 ) ); } /** * Perform modular exponentiation of big integers * * @v base0 Element 0 of big integer base * @v modulus0 Element 0 of big integer modulus * @v exponent0 Element 0 of big integer exponent * @v result0 Element 0 of big integer to hold result * @v size Number of elements in base, modulus, and result * @v exponent_size Number of elements in exponent * @v tmp Temporary working space */ 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 ) { 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 ); } }