Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

mp_core.cpp
Go to the documentation of this file.
1 /*
2 * MPI Add, Subtract, Word Multiply
3 * (C) 1999-2010,2016 Jack Lloyd
4 * 2006 Luca Piccarreta
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 */
8
9 #include <botan/internal/mp_core.h>
10 #include <botan/internal/mp_asmi.h>
11 #include <botan/internal/ct_utils.h>
12 #include <botan/exceptn.h>
13 #include <botan/mem_ops.h>
14
15 namespace Botan {
16
17 /*
18 * If cond == 0, does nothing.
19 * If cond > 0, swaps x[0:size] with y[0:size]
20 * Runs in constant time
21 */
22 void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
23 {
24 const word mask = CT::expand_mask(cnd);
25
26 for(size_t i = 0; i != size; ++i)
27 {
28 word a = x[i];
29 word b = y[i];
30 x[i] = CT::select(mask, b, a);
31 y[i] = CT::select(mask, a, b);
32 }
33 }
34
35 /*
36 * If cond > 0 adds x[0:size] to y[0:size] and returns carry
37 * Runs in constant time
38 */
39 word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
40 {
41 const word mask = CT::expand_mask(cnd);
42
43 word carry = 0;
44 for(size_t i = 0; i != size; ++i)
45 {
46 /*
47 Here we are relying on asm version of word_add being
48 a single addcl or equivalent. Fix this.
49 */
50 const word z = word_add(x[i], y[i], &carry);
51 x[i] = CT::select(mask, z, x[i]);
52 }
53
54 return carry & mask;
55 }
56
57 /*
58 * If cond > 0 subs x[0:size] to y[0:size] and returns borrow
59 * Runs in constant time
60 */
61 word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
62 {
63 const word mask = CT::expand_mask(cnd);
64
65 word carry = 0;
66 for(size_t i = 0; i != size; ++i)
67 {
68 const word z = word_sub(x[i], y[i], &carry);
69 x[i] = CT::select(mask, z, x[i]);
70 }
71
72 return carry & mask;
73 }
74
75 void bigint_cnd_abs(word cnd, word x[], size_t size)
76 {
77 const word mask = CT::expand_mask(cnd);
78
79 word carry = mask & 1;
80 for(size_t i = 0; i != size; ++i)
81 {
82 const word z = word_add(~x[i], 0, &carry);
83 x[i] = CT::select(mask, z, x[i]);
84 }
85 }
86
87 /*
88 * Two Operand Addition, No Carry
89 */
90 word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
91 {
92 word carry = 0;
93
94 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
95
96 const size_t blocks = y_size - (y_size % 8);
97
98 for(size_t i = 0; i != blocks; i += 8)
99 carry = word8_add2(x + i, y + i, carry);
100
101 for(size_t i = blocks; i != y_size; ++i)
102 x[i] = word_add(x[i], y[i], &carry);
103
104 for(size_t i = y_size; i != x_size; ++i)
105 x[i] = word_add(x[i], 0, &carry);
106
107 return carry;
108 }
109
110 /*
111 * Three Operand Addition, No Carry
112 */
113 word bigint_add3_nc(word z[], const word x[], size_t x_size,
114 const word y[], size_t y_size)
115 {
116 if(x_size < y_size)
117 { return bigint_add3_nc(z, y, y_size, x, x_size); }
118
119 word carry = 0;
120
121 const size_t blocks = y_size - (y_size % 8);
122
123 for(size_t i = 0; i != blocks; i += 8)
124 carry = word8_add3(z + i, x + i, y + i, carry);
125
126 for(size_t i = blocks; i != y_size; ++i)
127 z[i] = word_add(x[i], y[i], &carry);
128
129 for(size_t i = y_size; i != x_size; ++i)
130 z[i] = word_add(x[i], 0, &carry);
131
132 return carry;
133 }
134
135 /*
136 * Two Operand Addition
137 */
138 void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
139 {
140 if(bigint_add2_nc(x, x_size, y, y_size))
141 x[x_size] += 1;
142 }
143
144 /*
145 * Three Operand Addition
146 */
147 void bigint_add3(word z[], const word x[], size_t x_size,
148 const word y[], size_t y_size)
149 {
150 z[(x_size > y_size ? x_size : y_size)] +=
151 bigint_add3_nc(z, x, x_size, y, y_size);
152 }
153
154 /*
155 * Two Operand Subtraction
156 */
157 word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
158 {
159 word borrow = 0;
160
161 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
162
163 const size_t blocks = y_size - (y_size % 8);
164
165 for(size_t i = 0; i != blocks; i += 8)
166 borrow = word8_sub2(x + i, y + i, borrow);
167
168 for(size_t i = blocks; i != y_size; ++i)
169 x[i] = word_sub(x[i], y[i], &borrow);
170
171 for(size_t i = y_size; i != x_size; ++i)
172 x[i] = word_sub(x[i], 0, &borrow);
173
174 return borrow;
175 }
176
177 /*
178 * Two Operand Subtraction x = y - x
179 */
180 void bigint_sub2_rev(word x[], const word y[], size_t y_size)
181 {
182 word borrow = 0;
183
184 const size_t blocks = y_size - (y_size % 8);
185
186 for(size_t i = 0; i != blocks; i += 8)
187 borrow = word8_sub2_rev(x + i, y + i, borrow);
188
189 for(size_t i = blocks; i != y_size; ++i)
190 x[i] = word_sub(y[i], x[i], &borrow);
191
192 BOTAN_ASSERT(!borrow, "y must be greater than x");
193 }
194
195 /*
196 * Three Operand Subtraction
197 */
198 word bigint_sub3(word z[], const word x[], size_t x_size,
199 const word y[], size_t y_size)
200 {
201 word borrow = 0;
202
203 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
204
205 const size_t blocks = y_size - (y_size % 8);
206
207 for(size_t i = 0; i != blocks; i += 8)
208 borrow = word8_sub3(z + i, x + i, y + i, borrow);
209
210 for(size_t i = blocks; i != y_size; ++i)
211 z[i] = word_sub(x[i], y[i], &borrow);
212
213 for(size_t i = y_size; i != x_size; ++i)
214 z[i] = word_sub(x[i], 0, &borrow);
215
216 return borrow;
217 }
218
219 /*
220 * Two Operand Linear Multiply
221 */
222 void bigint_linmul2(word x[], size_t x_size, word y)
223 {
224 const size_t blocks = x_size - (x_size % 8);
225
226 word carry = 0;
227
228 for(size_t i = 0; i != blocks; i += 8)
229 carry = word8_linmul2(x + i, y, carry);
230
231 for(size_t i = blocks; i != x_size; ++i)
232 x[i] = word_madd2(x[i], y, &carry);
233
234 x[x_size] = carry;
235 }
236
237 /*
238 * Three Operand Linear Multiply
239 */
240 void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
241 {
242 const size_t blocks = x_size - (x_size % 8);
243
244 word carry = 0;
245
246 for(size_t i = 0; i != blocks; i += 8)
247 carry = word8_linmul3(z + i, x + i, y, carry);
248
249 for(size_t i = blocks; i != x_size; ++i)
250 z[i] = word_madd2(x[i], y, &carry);
251
252 z[x_size] = carry;
253 }
254
255 /*
256 * Single Operand Left Shift
257 */
258 void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
259 {
260 if(word_shift)
261 {
262 copy_mem(x + word_shift, x, x_size);
263 clear_mem(x, word_shift);
264 }
265
266 if(bit_shift)
267 {
268 word carry = 0;
269 for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
270 {
271 word temp = x[j];
272 x[j] = (temp << bit_shift) | carry;
273 carry = (temp >> (MP_WORD_BITS - bit_shift));
274 }
275 }
276 }
277
278 /*
279 * Single Operand Right Shift
280 */
281 void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
282 {
283 if(x_size < word_shift)
284 {
285 clear_mem(x, x_size);
286 return;
287 }
288
289 if(word_shift)
290 {
291 copy_mem(x, x + word_shift, x_size - word_shift);
292 clear_mem(x + x_size - word_shift, word_shift);
293 }
294
295 if(bit_shift)
296 {
297 word carry = 0;
298
299 size_t top = x_size - word_shift;
300
301 while(top >= 4)
302 {
303 word w = x[top-1];
304 x[top-1] = (w >> bit_shift) | carry;
305 carry = (w << (MP_WORD_BITS - bit_shift));
306
307 w = x[top-2];
308 x[top-2] = (w >> bit_shift) | carry;
309 carry = (w << (MP_WORD_BITS - bit_shift));
310
311 w = x[top-3];
312 x[top-3] = (w >> bit_shift) | carry;
313 carry = (w << (MP_WORD_BITS - bit_shift));
314
315 w = x[top-4];
316 x[top-4] = (w >> bit_shift) | carry;
317 carry = (w << (MP_WORD_BITS - bit_shift));
318
319 top -= 4;
320 }
321
322 while(top)
323 {
324 word w = x[top-1];
325 x[top-1] = (w >> bit_shift) | carry;
326 carry = (w << (MP_WORD_BITS - bit_shift));
327
328 top--;
329 }
330 }
331 }
332
333 /*
334 * Two Operand Left Shift
335 */
336 void bigint_shl2(word y[], const word x[], size_t x_size,
337 size_t word_shift, size_t bit_shift)
338 {
339 for(size_t j = 0; j != x_size; ++j)
340 y[j + word_shift] = x[j];
341 if(bit_shift)
342 {
343 word carry = 0;
344 for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
345 {
346 word w = y[j];
347 y[j] = (w << bit_shift) | carry;
348 carry = (w >> (MP_WORD_BITS - bit_shift));
349 }
350 }
351 }
352
353 /*
354 * Two Operand Right Shift
355 */
356 void bigint_shr2(word y[], const word x[], size_t x_size,
357 size_t word_shift, size_t bit_shift)
358 {
359 if(x_size < word_shift) return;
360
361 for(size_t j = 0; j != x_size - word_shift; ++j)
362 y[j] = x[j + word_shift];
363 if(bit_shift)
364 {
365 word carry = 0;
366 for(size_t j = x_size - word_shift; j > 0; --j)
367 {
368 word w = y[j-1];
369 y[j-1] = (w >> bit_shift) | carry;
370 carry = (w << (MP_WORD_BITS - bit_shift));
371 }
372 }
373 }
374
375 /*
376 * Compare two MP integers
377 */
378 int32_t bigint_cmp(const word x[], size_t x_size,
379 const word y[], size_t y_size)
380 {
381 if(x_size < y_size) { return (-bigint_cmp(y, y_size, x, x_size)); }
382
383 while(x_size > y_size)
384 {
385 if(x[x_size-1])
386 return 1;
387 x_size--;
388 }
389
390 for(size_t i = x_size; i > 0; --i)
391 {
392 if(x[i-1] > y[i-1])
393 return 1;
394 if(x[i-1] < y[i-1])
395 return -1;
396 }
397
398 return 0;
399 }
400
401 /*
402 * Do a 2-word/1-word Division
403 */
404 word bigint_divop(word n1, word n0, word d)
405 {
406 if(d == 0)
407 throw Invalid_Argument("bigint_divop divide by zero");
408
409 word high = n1 % d, quotient = 0;
410
411 for(size_t i = 0; i != MP_WORD_BITS; ++i)
412 {
413 word high_top_bit = (high & MP_WORD_TOP_BIT);
414
415 high <<= 1;
416 high |= (n0 >> (MP_WORD_BITS-1-i)) & 1;
417 quotient <<= 1;
418
419 if(high_top_bit || high >= d)
420 {
421 high -= d;
422 quotient |= 1;
423 }
424 }
425
426 return quotient;
427 }
428
429 /*
430 * Do a 2-word/1-word Modulo
431 */
432 word bigint_modop(word n1, word n0, word d)
433 {
434 word z = bigint_divop(n1, n0, d);
435 word dummy = 0;
436 z = word_madd2(z, d, &dummy);
437 return (n0-z);
438 }
439
440 }
Botan::bigint_shr1
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:281
Botan::bigint_sub2_rev
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.cpp:180
Botan::Invalid_Argument
Definition: exceptn.h:34
Botan::word8_sub2_rev
word word8_sub2_rev(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:381
Botan::word8_add2
word word8_add2(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:138
Botan::word8_linmul3
word word8_linmul3(word z[8], const word x[8], word y, word carry)
Definition: mp_asmi.h:585
Botan::bigint_shr2
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:356
Botan::bigint_cmp
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:378
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:57
Botan::bigint_sub2
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:157
Botan::bigint_linmul2
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.cpp:222
Botan::bigint_add3_nc
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:113
Botan::word8_sub2
word word8_sub2(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:311
Botan::bigint_sub3
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:198
Botan::bigint_divop
word bigint_divop(word n1, word n0, word d)
Definition: mp_core.cpp:404
Botan::bigint_cnd_sub
word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
Definition: mp_core.cpp:61
Botan::word_madd2
word word_madd2(word a, word b, word *c)
Definition: mp_madd.h:59
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:27
Botan::bigint_linmul3
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.cpp:240
Botan::CT::expand_mask
T expand_mask(T x)
Definition: ct_utils.h:86
Botan::word8_linmul2
word word8_linmul2(word x[8], word y, word carry)
Definition: mp_asmi.h:488
Botan::bigint_cnd_add
word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
Definition: mp_core.cpp:39
Botan::CT::select
T select(T mask, T from0, T from1)
Definition: ct_utils.h:98
Botan::bigint_add2_nc
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:90
Botan::copy_mem
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:68
Botan
Definition: alg_id.cpp:13
Botan::word8_add3
word word8_add3(word z[8], const word x[8], const word y[8], word carry)
Definition: mp_asmi.h:200
Botan::bigint_cnd_abs
void bigint_cnd_abs(word cnd, word x[], size_t size)
Definition: mp_core.cpp:75
Botan::bigint_shl2
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:336
Botan::bigint_shl1
void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:258
Botan::word_sub
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:280
Botan::bigint_add2
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:138
Botan::bigint_cnd_swap
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
Definition: mp_core.cpp:22
Botan::word_add
word word_add(word x, word y, word *carry)
Definition: mp_asmi.h:107
Botan::word8_sub3
word word8_sub3(word z[8], const word x[8], const word y[8], word carry)
Definition: mp_asmi.h:416
Botan::MP_WORD_TOP_BIT
const word MP_WORD_TOP_BIT
Definition: mp_types.h:28
Botan::bigint_add3
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:147
Botan::bigint_modop
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:432
Botan::MP_WORD_BITS
const size_t MP_WORD_BITS
Definition: mp_core.h:21