Coverage Report

Created: 2020-06-30 13:58

/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/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
2.69M
   {
23
2.69M
   q.cond_flip_sign(x.sign() != y.sign());
24
2.69M
25
2.69M
   if(x.is_negative() && r.is_nonzero())
26
1.24k
      {
27
1.24k
      q -= 1;
28
1.24k
      r = y.abs() - r;
29
1.24k
      }
30
2.69M
   }
31
32
inline bool division_check(word q, word y2, word y1,
33
                           word x3, word x2, word x1)
34
5.97M
   {
35
5.97M
   /*
36
5.97M
   Compute (y3,y2,y1) = (y2,y1) * q
37
5.97M
   and return true if (y3,y2,y1) > (x3,x2,x1)
38
5.97M
   */
39
5.97M
40
5.97M
   word y3 = 0;
41
5.97M
   y1 = word_madd2(q, y1, &y3);
42
5.97M
   y2 = word_madd2(q, y2, &y3);
43
5.97M
44
5.97M
   const word x[3] = { x1, x2, x3 };
45
5.97M
   const word y[3] = { y1, y2, y3 };
46
5.97M
47
5.97M
   return bigint_ct_is_lt(x, 3, y, 3).is_set();
48
5.97M
   }
49
50
}
51
52
void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
53
99.7k
   {
54
99.7k
   const size_t x_words = x.sig_words();
55
99.7k
   const size_t y_words = y.sig_words();
56
99.7k
57
99.7k
   const size_t x_bits = x.bits();
58
99.7k
59
99.7k
   BigInt q(BigInt::Positive, x_words);
60
99.7k
   BigInt r(BigInt::Positive, y_words);
61
99.7k
   BigInt t(BigInt::Positive, y_words); // a temporary
62
99.7k
63
149M
   for(size_t i = 0; i != x_bits; ++i)
64
149M
      {
65
149M
      const size_t b = x_bits - 1 - i;
66
149M
      const bool x_b = x.get_bit(b);
67
149M
68
149M
      r *= 2;
69
149M
      r.conditionally_set_bit(0, x_b);
70
149M
71
149M
      const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;
72
149M
73
149M
      q.conditionally_set_bit(b, r_gte_y);
74
149M
      r.ct_cond_swap(r_gte_y, t);
75
149M
      }
76
99.7k
77
99.7k
   sign_fixup(x, y, q, r);
78
99.7k
   r_out = r;
79
99.7k
   q_out = q;
80
99.7k
   }
81
82
void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
83
802
   {
84
802
   const size_t x_words = x.sig_words();
85
802
   const size_t x_bits = x.bits();
86
802
87
802
   BigInt q(BigInt::Positive, x_words);
88
802
   uint32_t r = 0;
89
802
90
698k
   for(size_t i = 0; i != x_bits; ++i)
91
697k
      {
92
697k
      const size_t b = x_bits - 1 - i;
93
697k
      const bool x_b = x.get_bit(b);
94
697k
95
697k
      r *= 2;
96
697k
      r += x_b;
97
697k
98
697k
      const auto r_gte_y = CT::Mask<uint32_t>::is_gte(r, y);
99
697k
100
697k
      q.conditionally_set_bit(b, r_gte_y.is_set());
101
697k
      r = r_gte_y.select(r - y, r);
102
697k
      }
103
802
104
802
   if(x.is_negative())
105
0
      {
106
0
      q.flip_sign();
107
0
      if(r != 0)
108
0
         {
109
0
         --q;
110
0
         r = y - r;
111
0
         }
112
0
      }
113
802
114
802
   r_out = static_cast<uint8_t>(r);
115
802
   q_out = q;
116
802
   }
117
118
BigInt ct_modulo(const BigInt& x, const BigInt& y)
119
1.89k
   {
120
1.89k
   if(y.is_negative() || y.is_zero())
121
0
      throw Invalid_Argument("ct_modulo requires y > 0");
122
1.89k
123
1.89k
   const size_t y_words = y.sig_words();
124
1.89k
125
1.89k
   const size_t x_bits = x.bits();
126
1.89k
127
1.89k
   BigInt r(BigInt::Positive, y_words);
128
1.89k
   BigInt t(BigInt::Positive, y_words);
129
1.89k
130
2.02M
   for(size_t i = 0; i != x_bits; ++i)
131
2.02M
      {
132
2.02M
      const size_t b = x_bits - 1 - i;
133
2.02M
      const bool x_b = x.get_bit(b);
134
2.02M
135
2.02M
      r *= 2;
136
2.02M
      r.conditionally_set_bit(0, x_b);
137
2.02M
138
2.02M
      const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;
139
2.02M
140
2.02M
      r.ct_cond_swap(r_gte_y, t);
141
2.02M
      }
142
1.89k
143
1.89k
   if(x.is_negative())
144
509
      {
145
509
      if(r.is_nonzero())
146
396
         {
147
396
         r = y - r;
148
396
         }
149
509
      }
150
1.89k
151
1.89k
   return r;
152
1.89k
   }
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
2.59M
   {
161
2.59M
   if(y_arg.is_zero())
162
0
      throw BigInt::DivideByZero();
163
2.59M
164
2.59M
   const size_t y_words = y_arg.sig_words();
165
2.59M
166
2.59M
   BOTAN_ASSERT_NOMSG(y_words > 0);
167
2.59M
168
2.59M
   BigInt y = y_arg;
169
2.59M
170
2.59M
   BigInt r = x;
171
2.59M
   BigInt q = 0;
172
2.59M
   secure_vector<word> ws;
173
2.59M
174
2.59M
   r.set_sign(BigInt::Positive);
175
2.59M
   y.set_sign(BigInt::Positive);
176
2.59M
177
2.59M
   // Calculate shifts needed to normalize y with high bit set
178
2.59M
   const size_t shifts = y.top_bits_free();
179
2.59M
180
2.59M
   y <<= shifts;
181
2.59M
   r <<= shifts;
182
2.59M
183
2.59M
   // we know y has not changed size, since we only shifted up to set high bit
184
2.59M
   const size_t t = y_words - 1;
185
2.59M
   const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however
186
2.59M
187
2.59M
   BOTAN_ASSERT_NOMSG(n >= t);
188
2.59M
189
2.59M
   q.grow_to(n - t + 1);
190
2.59M
191
2.59M
   word* q_words = q.mutable_data();
192
2.59M
193
2.59M
   BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n-t));
194
2.59M
195
2.59M
   // Set q_{n-t} to number of times r > shifted_y
196
2.59M
   q_words[n-t] = r.reduce_below(shifted_y, ws);
197
2.59M
198
2.59M
   const word y_t0  = y.word_at(t);
199
2.59M
   const word y_t1  = y.word_at(t-1);
200
2.59M
   BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS-1)) == 1);
201
2.59M
202
5.57M
   for(size_t j = n; j != t; --j)
203
2.98M
      {
204
2.98M
      const word x_j0  = r.word_at(j);
205
2.98M
      const word x_j1 = r.word_at(j-1);
206
2.98M
      const word x_j2 = r.word_at(j-2);
207
2.98M
208
2.98M
      word qjt = bigint_divop(x_j0, x_j1, y_t0);
209
2.98M
210
2.98M
      qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(MP_WORD_MAX, qjt);
211
2.98M
212
2.98M
      // Per HAC 14.23, this operation is required at most twice
213
2.98M
      qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
214
2.98M
      qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
215
2.98M
      BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);
216
2.98M
217
2.98M
      shifted_y >>= BOTAN_MP_WORD_BITS;
218
2.98M
      // Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1))
219
2.98M
220
2.98M
      // TODO this sequence could be better
221
2.98M
      r -= qjt * shifted_y;
222
2.98M
      qjt -= r.is_negative();
223
2.98M
      r += static_cast<word>(r.is_negative()) * shifted_y;
224
2.98M
225
2.98M
      q_words[j-t-1] = qjt;
226
2.98M
      }
227
2.59M
228
2.59M
   r >>= shifts;
229
2.59M
230
2.59M
   sign_fixup(x, y_arg, q, r);
231
2.59M
232
2.59M
   r_out = r;
233
2.59M
   q_out = q;
234
2.59M
   }
235
236
}