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 */
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)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 */
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)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 }
140