Botan  2.11.0
Crypto and TLS for C++11
divide.cpp
Go to the documentation of this file.
1 /*
2 * Division Algorithm
3 * (C) 1999-2007,2012,2018 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/divide.h>
9 #include <botan/internal/mp_core.h>
10 #include <botan/internal/mp_madd.h>
11 #include <botan/internal/ct_utils.h>
12 #include <botan/internal/bit_ops.h>
13 
14 namespace Botan {
15 
16 namespace {
17 
18 /*
19 * Handle signed operands, if necessary
20 */
21 void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r)
22  {
23  q.cond_flip_sign(x.sign() != y.sign());
24 
25  if(x.is_negative() && r.is_nonzero())
26  {
27  q -= 1;
28  r = y.abs() - r;
29  }
30  }
31 
32 inline bool division_check(word q, word y2, word y1,
33  word x3, word x2, word x1)
34  {
35  /*
36  Compute (y3,y2,y1) = (y2,y1) * q
37  and return true if (y3,y2,y1) > (x3,x2,x1)
38  */
39 
40  word y3 = 0;
41  y1 = word_madd2(q, y1, &y3);
42  y2 = word_madd2(q, y2, &y3);
43 
44  const word x[3] = { x1, x2, x3 };
45  const word y[3] = { y1, y2, y3 };
46 
47  return bigint_ct_is_lt(x, 3, y, 3).is_set();
48  }
49 
50 }
51 
52 void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
53  {
54  const size_t x_words = x.sig_words();
55  const size_t y_words = y.sig_words();
56 
57  const size_t x_bits = x.bits();
58 
59  BigInt q(BigInt::Positive, x_words);
60  BigInt r(BigInt::Positive, y_words);
61  BigInt t(BigInt::Positive, y_words); // a temporary
62 
63  for(size_t i = 0; i != x_bits; ++i)
64  {
65  const size_t b = x_bits - 1 - i;
66  const bool x_b = x.get_bit(b);
67 
68  r *= 2;
69  r.conditionally_set_bit(0, x_b);
70 
71  const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;
72 
73  q.conditionally_set_bit(b, r_gte_y);
74  r.ct_cond_swap(r_gte_y, t);
75  }
76 
77  sign_fixup(x, y, q, r);
78  r_out = r;
79  q_out = q;
80  }
81 
82 void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
83  {
84  const size_t x_words = x.sig_words();
85  const size_t x_bits = x.bits();
86 
87  BigInt q(BigInt::Positive, x_words);
88  uint32_t r = 0;
89 
90  for(size_t i = 0; i != x_bits; ++i)
91  {
92  const size_t b = x_bits - 1 - i;
93  const bool x_b = x.get_bit(b);
94 
95  r *= 2;
96  r += x_b;
97 
98  const auto r_gte_y = CT::Mask<uint32_t>::is_gte(r, y);
99 
100  q.conditionally_set_bit(b, r_gte_y.is_set());
101  r = r_gte_y.select(r - y, r);
102  }
103 
104  if(x.is_negative())
105  {
106  q.flip_sign();
107  if(r != 0)
108  {
109  --q;
110  r = y - r;
111  }
112  }
113 
114  r_out = static_cast<uint8_t>(r);
115  q_out = q;
116  }
117 
118 BigInt ct_modulo(const BigInt& x, const BigInt& y)
119  {
120  if(y.is_negative() || y.is_zero())
121  throw Invalid_Argument("ct_modulo requires y > 0");
122 
123  const size_t y_words = y.sig_words();
124 
125  const size_t x_bits = x.bits();
126 
127  BigInt r(BigInt::Positive, y_words);
128  BigInt t(BigInt::Positive, y_words);
129 
130  for(size_t i = 0; i != x_bits; ++i)
131  {
132  const size_t b = x_bits - 1 - i;
133  const bool x_b = x.get_bit(b);
134 
135  r *= 2;
136  r.conditionally_set_bit(0, x_b);
137 
138  const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;
139 
140  r.ct_cond_swap(r_gte_y, t);
141  }
142 
143  if(x.is_negative())
144  {
145  if(r.is_nonzero())
146  {
147  r = y - r;
148  }
149  }
150 
151  return r;
152  }
153 
154 /*
155 * Solve x = q * y + r
156 *
157 * See Handbook of Applied Cryptography section 14.2.5
158 */
159 void divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out)
160  {
161  if(y_arg.is_zero())
162  throw BigInt::DivideByZero();
163 
164  const size_t y_words = y_arg.sig_words();
165 
166  BOTAN_ASSERT_NOMSG(y_words > 0);
167 
168  BigInt y = y_arg;
169 
170  BigInt r = x;
171  BigInt q = 0;
173 
176 
177  // Calculate shifts needed to normalize y with high bit set
178  const size_t shifts = y.top_bits_free();
179 
180  y <<= shifts;
181  r <<= shifts;
182 
183  // we know y has not changed size, since we only shifted up to set high bit
184  const size_t t = y_words - 1;
185  const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however
186 
187  BOTAN_ASSERT_NOMSG(n >= t);
188 
189  q.grow_to(n - t + 1);
190 
191  word* q_words = q.mutable_data();
192 
193  BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n-t));
194 
195  // Set q_{n-t} to number of times r > shifted_y
196  q_words[n-t] = r.reduce_below(shifted_y, ws);
197 
198  const word y_t0 = y.word_at(t);
199  const word y_t1 = y.word_at(t-1);
200  BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS-1)) == 1);
201 
202  for(size_t j = n; j != t; --j)
203  {
204  const word x_j0 = r.word_at(j);
205  const word x_j1 = r.word_at(j-1);
206  const word x_j2 = r.word_at(j-2);
207 
208  word qjt = bigint_divop(x_j0, x_j1, y_t0);
209 
210  qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(MP_WORD_MAX, qjt);
211 
212  // Per HAC 14.23, this operation is required at most twice
213  qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
214  qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
215  BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);
216 
217  shifted_y >>= BOTAN_MP_WORD_BITS;
218  // Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1))
219 
220  // TODO this sequence could be better
221  r -= qjt * shifted_y;
222  qjt -= r.is_negative();
223  r += static_cast<word>(r.is_negative()) * shifted_y;
224 
225  q_words[j-t-1] = qjt;
226  }
227 
228  r >>= shifts;
229 
230  sign_fixup(x, y_arg, q, r);
231 
232  r_out = r;
233  q_out = q;
234  }
235 
236 }
bool get_bit(size_t n) const
Definition: bigint.h:464
bool is_negative() const
Definition: bigint.h:530
void divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:159
size_t bits() const
Definition: bigint.cpp:281
bool is_zero() const
Definition: bigint.h:420
word * mutable_data()
Definition: bigint.h:617
static Mask< T > is_gte(T x, T y)
Definition: ct_utils.h:181
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition: divide.cpp:118
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:344
word bigint_divop(word n1, word n0, word d)
Definition: mp_core.h:720
bool is_nonzero() const
Definition: bigint.h:414
word word_at(size_t n) const
Definition: bigint.h:511
const word * data() const
Definition: bigint.h:623
word word_madd2(word a, word b, word *c)
Definition: mp_madd.h:48
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:52
void ct_cond_swap(bool predicate, BigInt &other)
Definition: bigint.cpp:440
size_t size() const
Definition: bigint.h:583
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:589
void conditionally_set_bit(size_t n, bool set_it)
Definition: bigint.cpp:245
void ct_divide_u8(const BigInt &x, uint8_t y, BigInt &q_out, uint8_t &r_out)
Definition: divide.cpp:82
const word MP_WORD_MAX
Definition: mp_core.h:24
CT::Mask< word > bigint_ct_is_lt(const word x[], size_t x_size, const word y[], size_t y_size, bool lt_or_equal=false)
Definition: mp_core.h:576
void grow_to(size_t n) const
Definition: bigint.h:639
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:321
size_t top_bits_free() const
Definition: bigint.cpp:271
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
void flip_sign()
Definition: bigint.h:557
void set_sign(Sign sign)
Definition: bigint.h:566
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149