2 * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
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.
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.
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
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.
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL
);
29 #include <ipxe/bigint.h>
37 * Perform modular multiplication of big integers
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
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
);
60 bigint_t ( size
* 2 ) result
;
61 bigint_t ( size
* 2 ) modulus
;
67 assert ( sizeof ( *temp
) == bigint_mod_multiply_tmp_len ( modulus
) );
69 /* Perform multiplication */
70 bigint_multiply ( multiplicand
, multiplier
, &temp
->result
);
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
);
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
);
87 bigint_shrink ( &temp
->result
, result
);
90 assert ( bigint_is_geq ( modulus
, result
) );
94 * Perform modular exponentiation of big integers
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
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
,
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
);
120 bigint_t ( size
) base
;
121 bigint_t ( exponent_size
) exponent
;
122 uint8_t mod_multiply
[mod_multiply_len
];
124 static const uint8_t start
[1] = { 0x01 };
126 memcpy ( &temp
->base
, base
, sizeof ( temp
->base
) );
127 memcpy ( &temp
->exponent
, exponent
, sizeof ( temp
->exponent
) );
128 bigint_init ( result
, start
, sizeof ( start
) );
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
);
135 bigint_ror ( &temp
->exponent
);
136 bigint_mod_multiply ( &temp
->base
, &temp
->base
, modulus
,
137 &temp
->base
, temp
->mod_multiply
);