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