Botan  2.4.0
Crypto and TLS for C++11
mp_monty.cpp
Go to the documentation of this file.
1 /*
2 * Montgomery Reduction
3 * (C) 1999-2011 Jack Lloyd
4 * 2006 Luca Piccarreta
5 * 2016 Matthias Gierlings
6 *
7 * Botan is released under the Simplified BSD License (see license.txt)
8 */
9 
10 #include <botan/bigint.h>
11 #include <botan/internal/mp_core.h>
12 #include <botan/internal/mp_madd.h>
13 #include <botan/internal/mp_asmi.h>
14 #include <botan/internal/ct_utils.h>
15 #include <botan/mem_ops.h>
16 
17 namespace Botan {
18 
19 /*
20 * Montgomery Reduction Algorithm
21 */
22 void bigint_monty_redc(word z[],
23  const word p[], size_t p_size,
24  word p_dash, word ws[])
25  {
26  const size_t z_size = 2*(p_size+1);
27 
28  CT::poison(z, z_size);
29  CT::poison(p, p_size);
30  CT::poison(ws, 2*(p_size+1));
31 
32  const size_t blocks_of_8 = p_size - (p_size % 8);
33 
34  for(size_t i = 0; i != p_size; ++i)
35  {
36  word* z_i = z + i;
37 
38  const word y = z_i[0] * p_dash;
39 
40  /*
41  bigint_linmul3(ws, p, p_size, y);
42  bigint_add2(z_i, z_size - i, ws, p_size+1);
43  */
44 
45  word carry = 0;
46 
47  for(size_t j = 0; j != blocks_of_8; j += 8)
48  carry = word8_madd3(z_i + j, p + j, y, carry);
49 
50  for(size_t j = blocks_of_8; j != p_size; ++j)
51  z_i[j] = word_madd3(p[j], y, z_i[j], &carry);
52 
53  word z_sum = z_i[p_size] + carry;
54  carry = (z_sum < z_i[p_size]);
55  z_i[p_size] = z_sum;
56 
57  for(size_t j = p_size + 1; j < z_size - i; ++j)
58  {
59  z_i[j] += carry;
60  carry = carry & !z_i[j];
61  }
62  }
63 
64  /*
65  * The result might need to be reduced mod p. To avoid a timing
66  * channel, always perform the subtraction. If in the compution
67  * of x - p a borrow is required then x was already < p.
68  *
69  * x - p starts at ws[0] and is p_size+1 bytes long
70  * x starts at ws[p_size+1] and is also p_size+1 bytes log
71  * (that's the copy_mem)
72  *
73  * Select which address to copy from indexing off of the final
74  * borrow.
75  */
76 
77  word borrow = 0;
78  for(size_t i = 0; i != p_size; ++i)
79  ws[i] = word_sub(z[p_size + i], p[i], &borrow);
80 
81  ws[p_size] = word_sub(z[p_size+p_size], 0, &borrow);
82 
83  copy_mem(ws + p_size + 1, z + p_size, p_size + 1);
84 
85  CT::conditional_copy_mem(borrow, z, ws + (p_size + 1), ws, (p_size + 1));
86  clear_mem(z + p_size + 1, z_size - p_size - 1);
87 
88  CT::unpoison(z, z_size);
89  CT::unpoison(p, p_size);
90  CT::unpoison(ws, 2*(p_size+1));
91 
92  // This check comes after we've used it but that's ok here
93  CT::unpoison(&borrow, 1);
94  BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow");
95  }
96 
97 void bigint_monty_mul(BigInt& z, const BigInt& x, const BigInt& y,
98  const word p[], size_t p_size, word p_dash,
99  word ws[])
100  {
101  bigint_mul(z, x, y, &ws[0]);
102 
104  p, p_size, p_dash,
105  ws);
106  }
107 
108 void bigint_monty_sqr(BigInt& z, const BigInt& x, const word p[],
109  size_t p_size, word p_dash, word ws[])
110  {
111  bigint_sqr(z.mutable_data(), z.size(), &ws[0],
112  x.data(), x.size(), x.sig_words());
113 
115  p, p_size, p_dash,
116  ws);
117  }
118 
119 }
void conditional_copy_mem(T value, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:142
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:86
word word_madd3(word a, word b, word c, word *d)
Definition: mp_madd.h:105
word * mutable_data()
Definition: bigint.h:424
void poison(const T *p, size_t n)
Definition: ct_utils.h:46
const word * data() const
Definition: bigint.h:430
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:29
void bigint_monty_sqr(BigInt &z, const BigInt &x, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:108
word word8_madd3(word z[8], const word x[8], word y, word carry)
Definition: mp_asmi.h:681
void bigint_sqr(word z[], size_t z_size, word workspace[], const word x[], size_t x_size, size_t x_sw)
Definition: mp_karat.cpp:321
void bigint_monty_mul(BigInt &z, const BigInt &x, const BigInt &y, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:97
size_t size() const
Definition: bigint.h:392
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:97
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:398
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:280
void bigint_mul(BigInt &z, const BigInt &x, const BigInt &y, word workspace[])
Definition: mp_karat.cpp:253
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:57
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:22