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  * Conditionally swap big integers (in constant time)
55  *
56  * @v first0 Element 0 of big integer to be conditionally swapped
57  * @v second0 Element 0 of big integer to be conditionally swapped
58  * @v size Number of elements in big integers
59  * @v swap Swap first and second big integers
60  */
62  unsigned int size, int swap ) {
63  bigint_element_t mask;
65  unsigned int i;
66 
67  /* Construct mask */
68  mask = ( ( bigint_element_t ) ( ! swap ) - 1 );
69 
70  /* Conditionally swap elements */
71  for ( i = 0 ; i < size ; i++ ) {
72  xor = ( mask & ( first0[i] ^ second0[i] ) );
73  first0[i] ^= xor;
74  second0[i] ^= xor;
75  }
76 }
77 
78 /**
79  * Perform modular multiplication of big integers
80  *
81  * @v multiplicand0 Element 0 of big integer to be multiplied
82  * @v multiplier0 Element 0 of big integer to be multiplied
83  * @v modulus0 Element 0 of big integer modulus
84  * @v result0 Element 0 of big integer to hold result
85  * @v size Number of elements in base, modulus, and result
86  * @v tmp Temporary working space
87  */
88 void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0,
89  const bigint_element_t *multiplier0,
90  const bigint_element_t *modulus0,
91  bigint_element_t *result0,
92  unsigned int size, void *tmp ) {
93  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
94  ( ( const void * ) multiplicand0 );
95  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
96  ( ( const void * ) multiplier0 );
97  const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
98  ( ( const void * ) modulus0 );
99  bigint_t ( size ) __attribute__ (( may_alias )) *result =
100  ( ( void * ) result0 );
101  struct {
102  bigint_t ( size * 2 ) result;
103  bigint_t ( size * 2 ) modulus;
104  } *temp = tmp;
105  int rotation;
106  int i;
107 
108  /* Start profiling */
109  profile_start ( &bigint_mod_multiply_profiler );
110 
111  /* Sanity check */
112  assert ( sizeof ( *temp ) == bigint_mod_multiply_tmp_len ( modulus ) );
113 
114  /* Perform multiplication */
115  profile_start ( &bigint_mod_multiply_multiply_profiler );
116  bigint_multiply ( multiplicand, multiplier, &temp->result );
117  profile_stop ( &bigint_mod_multiply_multiply_profiler );
118 
119  /* Rescale modulus to match result */
120  profile_start ( &bigint_mod_multiply_rescale_profiler );
121  bigint_grow ( modulus, &temp->modulus );
122  rotation = ( bigint_max_set_bit ( &temp->result ) -
123  bigint_max_set_bit ( &temp->modulus ) );
124  for ( i = 0 ; i < rotation ; i++ )
125  bigint_rol ( &temp->modulus );
126  profile_stop ( &bigint_mod_multiply_rescale_profiler );
127 
128  /* Subtract multiples of modulus */
129  profile_start ( &bigint_mod_multiply_subtract_profiler );
130  for ( i = 0 ; i <= rotation ; i++ ) {
131  if ( bigint_is_geq ( &temp->result, &temp->modulus ) )
132  bigint_subtract ( &temp->modulus, &temp->result );
133  bigint_ror ( &temp->modulus );
134  }
135  profile_stop ( &bigint_mod_multiply_subtract_profiler );
136 
137  /* Resize result */
138  bigint_shrink ( &temp->result, result );
139 
140  /* Sanity check */
141  assert ( bigint_is_geq ( modulus, result ) );
142 
143  /* Stop profiling */
144  profile_stop ( &bigint_mod_multiply_profiler );
145 }
146 
147 /**
148  * Perform modular exponentiation of big integers
149  *
150  * @v base0 Element 0 of big integer base
151  * @v modulus0 Element 0 of big integer modulus
152  * @v exponent0 Element 0 of big integer exponent
153  * @v result0 Element 0 of big integer to hold result
154  * @v size Number of elements in base, modulus, and result
155  * @v exponent_size Number of elements in exponent
156  * @v tmp Temporary working space
157  */
159  const bigint_element_t *modulus0,
160  const bigint_element_t *exponent0,
161  bigint_element_t *result0,
162  unsigned int size, unsigned int exponent_size,
163  void *tmp ) {
164  const bigint_t ( size ) __attribute__ (( may_alias )) *base =
165  ( ( const void * ) base0 );
166  const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
167  ( ( const void * ) modulus0 );
168  const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
169  *exponent = ( ( const void * ) exponent0 );
170  bigint_t ( size ) __attribute__ (( may_alias )) *result =
171  ( ( void * ) result0 );
172  size_t mod_multiply_len = bigint_mod_multiply_tmp_len ( modulus );
173  struct {
174  bigint_t ( size ) base;
175  bigint_t ( exponent_size ) exponent;
176  uint8_t mod_multiply[mod_multiply_len];
177  } *temp = tmp;
178  static const uint8_t start[1] = { 0x01 };
179 
180  memcpy ( &temp->base, base, sizeof ( temp->base ) );
181  memcpy ( &temp->exponent, exponent, sizeof ( temp->exponent ) );
182  bigint_init ( result, start, sizeof ( start ) );
183 
184  while ( ! bigint_is_zero ( &temp->exponent ) ) {
185  if ( bigint_bit_is_set ( &temp->exponent, 0 ) ) {
186  bigint_mod_multiply ( result, &temp->base, modulus,
187  result, temp->mod_multiply );
188  }
189  bigint_ror ( &temp->exponent );
190  bigint_mod_multiply ( &temp->base, &temp->base, modulus,
191  &temp->base, temp->mod_multiply );
192  }
193 }
#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:158
static const void const void void * result
Definition: crypto.h:335
#define bigint_max_set_bit(value)
Find highest bit set in big integer.
Definition: bigint.h:151
#define bigint_ror(value)
Rotate big integer right.
Definition: bigint.h:106
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:88
#define bigint_grow(source, dest)
Grow big integer.
Definition: bigint.h:161
#define bigint_init(value, data, len)
Initialise big integer.
Definition: bigint.h:50
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:118
static void profile_stop(struct profiler *profiler)
Stop profiling.
Definition: profile.h:171
static const void * base
Base address.
Definition: crypto.h:335
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
static u32 xor(u32 a, u32 b)
Definition: tlan.h:457
uint32_t start
Starting offset.
Definition: netvsc.h:12
unsigned long tmp
Definition: linux_pci.h:53
#define bigint_is_geq(value, reference)
Compare big integers.
Definition: bigint.h:129
void * memcpy(void *dest, const void *src, size_t len) __nonnull
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:174
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.
#define bigint_rol(value)
Rotate big integer left.
Definition: bigint.h:96
unsigned char uint8_t
Definition: stdint.h:10
static unsigned int rotation
Definition: rotate.h:22
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
void bigint_swap_raw(bigint_element_t *first0, bigint_element_t *second0, unsigned int size, int swap)
Conditionally swap big integers (in constant time)
Definition: bigint.c:61
#define bigint_mod_multiply(multiplicand, multiplier, modulus, result, tmp)
Perform modular multiplication of big integers.
Definition: bigint.h:229
#define bigint_mod_multiply_tmp_len(modulus)
Calculate temporary working space required for moduluar multiplication.
Definition: bigint.h:244
#define bigint_multiply(multiplicand, multiplier, result)
Multiply big integers.
Definition: bigint.h:212
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:141
#define bigint_subtract(subtrahend, value)
Subtract big integers.
Definition: bigint.h:85
String functions.
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.