iPXE
bigint.c
Go to the documentation of this file.
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/profile.h>
30 #include <ipxe/bigint.h>
31 
32 /** @file
33  *
34  * Big integer support
35  */
36 
37 /** Modular multiplication overall profiler */
38 static struct profiler bigint_mod_multiply_profiler __profiler =
39  { .name = "bigint_mod_multiply" };
40 
41 /** Modular multiplication multiply step profiler */
42 static struct profiler bigint_mod_multiply_multiply_profiler __profiler =
43  { .name = "bigint_mod_multiply.multiply" };
44 
45 /** Modular multiplication rescale step profiler */
46 static struct profiler bigint_mod_multiply_rescale_profiler __profiler =
47  { .name = "bigint_mod_multiply.rescale" };
48 
49 /** Modular multiplication subtract step profiler */
50 static struct profiler bigint_mod_multiply_subtract_profiler __profiler =
51  { .name = "bigint_mod_multiply.subtract" };
52 
53 /**
54  * Perform modular multiplication of big integers
55  *
56  * @v multiplicand0 Element 0 of big integer to be multiplied
57  * @v multiplier0 Element 0 of big integer to be multiplied
58  * @v modulus0 Element 0 of big integer modulus
59  * @v result0 Element 0 of big integer to hold result
60  * @v size Number of elements in base, modulus, and result
61  * @v tmp Temporary working space
62  */
63 void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0,
64  const bigint_element_t *multiplier0,
65  const bigint_element_t *modulus0,
66  bigint_element_t *result0,
67  unsigned int size, void *tmp ) {
68  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
69  ( ( const void * ) multiplicand0 );
70  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
71  ( ( const void * ) multiplier0 );
72  const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
73  ( ( const void * ) modulus0 );
74  bigint_t ( size ) __attribute__ (( may_alias )) *result =
75  ( ( void * ) result0 );
76  struct {
77  bigint_t ( size * 2 ) result;
78  bigint_t ( size * 2 ) modulus;
79  } *temp = tmp;
80  int rotation;
81  int i;
82 
83  /* Start profiling */
84  profile_start ( &bigint_mod_multiply_profiler );
85 
86  /* Sanity check */
87  assert ( sizeof ( *temp ) == bigint_mod_multiply_tmp_len ( modulus ) );
88 
89  /* Perform multiplication */
90  profile_start ( &bigint_mod_multiply_multiply_profiler );
91  bigint_multiply ( multiplicand, multiplier, &temp->result );
92  profile_stop ( &bigint_mod_multiply_multiply_profiler );
93 
94  /* Rescale modulus to match result */
95  profile_start ( &bigint_mod_multiply_rescale_profiler );
96  bigint_grow ( modulus, &temp->modulus );
97  rotation = ( bigint_max_set_bit ( &temp->result ) -
98  bigint_max_set_bit ( &temp->modulus ) );
99  for ( i = 0 ; i < rotation ; i++ )
100  bigint_rol ( &temp->modulus );
101  profile_stop ( &bigint_mod_multiply_rescale_profiler );
102 
103  /* Subtract multiples of modulus */
104  profile_start ( &bigint_mod_multiply_subtract_profiler );
105  for ( i = 0 ; i <= rotation ; i++ ) {
106  if ( bigint_is_geq ( &temp->result, &temp->modulus ) )
107  bigint_subtract ( &temp->modulus, &temp->result );
108  bigint_ror ( &temp->modulus );
109  }
110  profile_stop ( &bigint_mod_multiply_subtract_profiler );
111 
112  /* Resize result */
113  bigint_shrink ( &temp->result, result );
114 
115  /* Sanity check */
116  assert ( bigint_is_geq ( modulus, result ) );
117 
118  /* Stop profiling */
119  profile_stop ( &bigint_mod_multiply_profiler );
120 }
121 
122 /**
123  * Perform modular exponentiation of big integers
124  *
125  * @v base0 Element 0 of big integer base
126  * @v modulus0 Element 0 of big integer modulus
127  * @v exponent0 Element 0 of big integer exponent
128  * @v result0 Element 0 of big integer to hold result
129  * @v size Number of elements in base, modulus, and result
130  * @v exponent_size Number of elements in exponent
131  * @v tmp Temporary working space
132  */
134  const bigint_element_t *modulus0,
135  const bigint_element_t *exponent0,
136  bigint_element_t *result0,
137  unsigned int size, unsigned int exponent_size,
138  void *tmp ) {
139  const bigint_t ( size ) __attribute__ (( may_alias )) *base =
140  ( ( const void * ) base0 );
141  const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
142  ( ( const void * ) modulus0 );
143  const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
144  *exponent = ( ( const void * ) exponent0 );
145  bigint_t ( size ) __attribute__ (( may_alias )) *result =
146  ( ( void * ) result0 );
147  size_t mod_multiply_len = bigint_mod_multiply_tmp_len ( modulus );
148  struct {
149  bigint_t ( size ) base;
150  bigint_t ( exponent_size ) exponent;
151  uint8_t mod_multiply[mod_multiply_len];
152  } *temp = tmp;
153  static const uint8_t start[1] = { 0x01 };
154 
155  memcpy ( &temp->base, base, sizeof ( temp->base ) );
156  memcpy ( &temp->exponent, exponent, sizeof ( temp->exponent ) );
157  bigint_init ( result, start, sizeof ( start ) );
158 
159  while ( ! bigint_is_zero ( &temp->exponent ) ) {
160  if ( bigint_bit_is_set ( &temp->exponent, 0 ) ) {
161  bigint_mod_multiply ( result, &temp->base, modulus,
162  result, temp->mod_multiply );
163  }
164  bigint_ror ( &temp->exponent );
165  bigint_mod_multiply ( &temp->base, &temp->base, modulus,
166  &temp->base, temp->mod_multiply );
167  }
168 }
#define __attribute__(x)
Definition: compiler.h:10
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)
Perform modular exponentiation of big integers.
Definition: bigint.c:133
#define bigint_max_set_bit(value)
Find highest bit set in big integer.
Definition: bigint.h:149
#define bigint_ror(value)
Rotate big integer right.
Definition: bigint.h:104
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)
Perform modular multiplication of big integers.
Definition: bigint.c:63
#define bigint_grow(source, dest)
Grow big integer.
Definition: bigint.h:159
#define bigint_init(value, data, len)
Initialise big integer.
Definition: bigint.h:48
A data structure for storing profiling information.
Definition: profile.h:26
#define bigint_is_zero(value)
Test if big integer is equal to zero.
Definition: bigint.h:116
static void profile_stop(struct profiler *profiler)
Stop profiling.
Definition: profile.h:171
uint8_t multiplier
Port multiplier number.
Definition: edd.h:32
Big integer support.
static struct profiler bigint_mod_multiply_profiler __profiler
Modular multiplication overall profiler.
Definition: bigint.c:38
uint32_t start
Starting offset.
Definition: netvsc.h:12
#define bigint_is_geq(value, reference)
Compare big integers.
Definition: bigint.h:127
void * memcpy(void *dest, const void *src, size_t len) __nonnull
int result
Definition: bigint.h:148
const char * name
Name.
Definition: profile.h:28
Assertions.
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
#define bigint_shrink(source, dest)
Shrink big integer.
Definition: bigint.h:172
uint32_t bigint_element_t
Element of a big integer.
Definition: bigint.h:15
static void profile_start(struct profiler *profiler)
Start profiling.
Definition: profile.h:158
Profiling.
const bigint_t(size) __attribute__((may_alias)) *reference
#define bigint_rol(value)
Rotate big integer left.
Definition: bigint.h:94
uint8_t * tmp
Definition: entropy.h:156
unsigned char uint8_t
Definition: stdint.h:10
static unsigned int rotation
Definition: rotate.h:14
uint16_t base
Base address.
Definition: edd.h:14
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
#define bigint_mod_multiply(multiplicand, multiplier, modulus, result, tmp)
Perform modular multiplication of big integers.
Definition: bigint.h:202
#define bigint_mod_multiply_tmp_len(modulus)
Calculate temporary working space required for moduluar multiplication.
Definition: bigint.h:217
#define bigint_multiply(multiplicand, multiplier, result)
Multiply big integers.
Definition: bigint.h:186
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
#define bigint_bit_is_set(value, bit)
Test if bit is set in big integer.
Definition: bigint.h:139
#define bigint_subtract(subtrahend, value)
Subtract big integers.
Definition: bigint.h:83
String functions.