Coverage Report

Created: 2021-05-04 09:02

/src/botan/src/lib/math/bigint/divide.cpp
Line
Count
Source (jump to first uncovered line)
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/internal/divide.h>
9
#include <botan/internal/mp_core.h>
10
#include <botan/internal/ct_utils.h>
11
#include <botan/internal/bit_ops.h>
12
13
namespace Botan {
14
15
namespace {
16
17
/*
18
* Handle signed operands, if necessary
19
*/
20
void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r)
21
2.36M
   {
22
2.36M
   q.cond_flip_sign(x.sign() != y.sign());
23
24
2.36M
   if(x.is_negative() && r.is_nonzero())
25
1.44k
      {
26
1.44k
      q -= 1;
27
1.44k
      r = y.abs() - r;
28
1.44k
      }
29
2.36M
   }
30
31
inline bool division_check(word q, word y2, word y1,
32
                           word x3, word x2, word x1)
33
5.30M
   {
34
   /*
35
   Compute (y3,y2,y1) = (y2,y1) * q
36
   and return true if (y3,y2,y1) > (x3,x2,x1)
37
   */
38
39
5.30M
   word y3 = 0;
40
5.30M
   y1 = word_madd2(q, y1, &y3);
41
5.30M
   y2 = word_madd2(q, y2, &y3);
42
43
5.30M
   const word x[3] = { x1, x2, x3 };
44
5.30M
   const word y[3] = { y1, y2, y3 };
45
46
5.30M
   return bigint_ct_is_lt(x, 3, y, 3).is_set();
47
5.30M
   }
48
49
}
50
51
void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
52
29.0k
   {
53
29.0k
   const size_t x_words = x.sig_words();
54
29.0k
   const size_t y_words = y.sig_words();
55
56
29.0k
   const size_t x_bits = x.bits();
57
58
29.0k
   BigInt q = BigInt::with_capacity(x_words);
59
29.0k
   BigInt r = BigInt::with_capacity(y_words);
60
29.0k
   BigInt t = BigInt::with_capacity(y_words); // a temporary
61
62
44.6M
   for(size_t i = 0; i != x_bits; ++i)
63
44.6M
      {
64
44.6M
      const size_t b = x_bits - 1 - i;
65
44.6M
      const bool x_b = x.get_bit(b);
66
67
44.6M
      r *= 2;
68
44.6M
      r.conditionally_set_bit(0, x_b);
69
70
44.6M
      const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;
71
72
44.6M
      q.conditionally_set_bit(b, r_gte_y);
73
44.6M
      r.ct_cond_swap(r_gte_y, t);
74
44.6M
      }
75
76
29.0k
   sign_fixup(x, y, q, r);
77
29.0k
   r_out = r;
78
29.0k
   q_out = q;
79
29.0k
   }
80
81
void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
82
834
   {
83
834
   const size_t x_words = x.sig_words();
84
834
   const size_t x_bits = x.bits();
85
86
834
   BigInt q = BigInt::with_capacity(x_words);
87
834
   uint32_t r = 0;
88
89
713k
   for(size_t i = 0; i != x_bits; ++i)
90
712k
      {
91
712k
      const size_t b = x_bits - 1 - i;
92
712k
      const bool x_b = x.get_bit(b);
93
94
712k
      r *= 2;
95
712k
      r += x_b;
96
97
712k
      const auto r_gte_y = CT::Mask<uint32_t>::is_gte(r, y);
98
99
712k
      q.conditionally_set_bit(b, r_gte_y.is_set());
100
712k
      r = r_gte_y.select(r - y, r);
101
712k
      }
102
103
834
   if(x.is_negative())
104
0
      {
105
0
      q.flip_sign();
106
0
      if(r != 0)
107
0
         {
108
0
         --q;
109
0
         r = y - r;
110
0
         }
111
0
      }
112
113
834
   r_out = static_cast<uint8_t>(r);
114
834
   q_out = q;
115
834
   }
116
117
BigInt ct_modulo(const BigInt& x, const BigInt& y)
118
2.25k
   {
119
2.25k
   if(y.is_negative() || y.is_zero())
120
0
      throw Invalid_Argument("ct_modulo requires y > 0");
121
122
2.25k
   const size_t y_words = y.sig_words();
123
124
2.25k
   const size_t x_bits = x.bits();
125
126
2.25k
   BigInt r = BigInt::with_capacity(y_words);
127
2.25k
   BigInt t = BigInt::with_capacity(y_words);
128
129
2.19M
   for(size_t i = 0; i != x_bits; ++i)
130
2.18M
      {
131
2.18M
      const size_t b = x_bits - 1 - i;
132
2.18M
      const bool x_b = x.get_bit(b);
133
134
2.18M
      r *= 2;
135
2.18M
      r.conditionally_set_bit(0, x_b);
136
137
2.18M
      const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;
138
139
2.18M
      r.ct_cond_swap(r_gte_y, t);
140
2.18M
      }
141
142
2.25k
   if(x.is_negative())
143
606
      {
144
606
      if(r.is_nonzero())
145
570
         {
146
570
         r = y - r;
147
570
         }
148
606
      }
149
150
2.25k
   return r;
151
2.25k
   }
152
153
void vartime_divide_word(const BigInt& x, const word y, BigInt& q_out, BigInt& r_out)
154
187
   {
155
187
   if(y == 0)
156
0
      throw Invalid_Argument("vartime_divide_word: cannot divide by zero");
157
158
   // It might be worthwhile to specialize vartime_divide for y with 1 word
159
160
   // until then:
161
187
   vartime_divide(x, BigInt::from_word(y), q_out, r_out);
162
187
   }
163
164
/*
165
* Solve x = q * y + r
166
*
167
* See Handbook of Applied Cryptography section 14.2.5
168
*/
169
void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out)
170
2.33M
   {
171
2.33M
   if(y_arg.is_zero())
172
0
      throw Invalid_Argument("vartime_divide: cannot divide by zero");
173
174
2.33M
   const size_t y_words = y_arg.sig_words();
175
176
2.33M
   BOTAN_ASSERT_NOMSG(y_words > 0);
177
178
2.33M
   BigInt y = y_arg;
179
180
2.33M
   BigInt r = x;
181
2.33M
   BigInt q = BigInt::zero();
182
2.33M
   secure_vector<word> ws;
183
184
2.33M
   r.set_sign(BigInt::Positive);
185
2.33M
   y.set_sign(BigInt::Positive);
186
187
   // Calculate shifts needed to normalize y with high bit set
188
2.33M
   const size_t shifts = y.top_bits_free();
189
190
2.33M
   y <<= shifts;
191
2.33M
   r <<= shifts;
192
193
   // we know y has not changed size, since we only shifted up to set high bit
194
2.33M
   const size_t t = y_words - 1;
195
2.33M
   const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however
196
197
2.33M
   BOTAN_ASSERT_NOMSG(n >= t);
198
199
2.33M
   q.grow_to(n - t + 1);
200
201
2.33M
   word* q_words = q.mutable_data();
202
203
2.33M
   BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n-t));
204
205
   // Set q_{n-t} to number of times r > shifted_y
206
2.33M
   q_words[n-t] = r.reduce_below(shifted_y, ws);
207
208
2.33M
   const word y_t0  = y.word_at(t);
209
2.33M
   const word y_t1  = y.word_at(t-1);
210
2.33M
   BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS-1)) == 1);
211
212
4.98M
   for(size_t j = n; j != t; --j)
213
2.65M
      {
214
2.65M
      const word x_j0  = r.word_at(j);
215
2.65M
      const word x_j1 = r.word_at(j-1);
216
2.65M
      const word x_j2 = r.word_at(j-2);
217
218
2.65M
      word qjt = bigint_divop(x_j0, x_j1, y_t0);
219
220
2.65M
      qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(MP_WORD_MAX, qjt);
221
222
      // Per HAC 14.23, this operation is required at most twice
223
2.65M
      qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
224
2.65M
      qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
225
2.65M
      BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);
226
227
2.65M
      shifted_y >>= BOTAN_MP_WORD_BITS;
228
      // Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1))
229
230
      // TODO this sequence could be better
231
2.65M
      r -= qjt * shifted_y;
232
2.65M
      qjt -= r.is_negative();
233
2.65M
      r += static_cast<word>(r.is_negative()) * shifted_y;
234
235
2.65M
      q_words[j-t-1] = qjt;
236
2.65M
      }
237
238
2.33M
   r >>= shifts;
239
240
2.33M
   sign_fixup(x, y_arg, q, r);
241
242
2.33M
   r_out = r;
243
2.33M
   q_out = q;
244
2.33M
   }
245
246
}