Botan 2.19.1
Crypto and TLS for C&
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
14namespace Botan {
15
16namespace {
17
18/*
19* Handle signed operands, if necessary
20*/
21void 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
32inline 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
52void 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
82void 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
118BigInt 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*/
159void vartime_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}
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
size_t sig_words() const
Definition: bigint.h:586
void conditionally_set_bit(size_t n, bool set_it)
Definition: bigint.cpp:260
word * mutable_data()
Definition: bigint.h:614
size_t size() const
Definition: bigint.h:580
void grow_to(size_t n) const
Definition: bigint.h:636
void flip_sign()
Definition: bigint.h:554
size_t top_bits_free() const
Definition: bigint.cpp:286
const word * data() const
Definition: bigint.h:620
word word_at(size_t n) const
Definition: bigint.h:508
size_t bits() const
Definition: bigint.cpp:296
void ct_cond_swap(bool predicate, BigInt &other)
Definition: bigint.cpp:466
bool is_zero() const
Definition: bigint.h:421
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:336
bool is_negative() const
Definition: bigint.h:527
bool is_nonzero() const
Definition: bigint.h:415
bool get_bit(size_t n) const
Definition: bigint.h:465
void set_sign(Sign sign)
Definition: bigint.h:563
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
static Mask< T > is_gte(T x, T y)
Definition: ct_utils.h:181
Definition: alg_id.cpp:13
word bigint_divop(word n1, word n0, word d)
Definition: mp_core.h:721
const word MP_WORD_MAX
Definition: mp_core.h:22
void ct_divide_u8(const BigInt &x, uint8_t y, BigInt &q_out, uint8_t &r_out)
Definition: divide.cpp:82
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:52
word word_madd2(word a, word b, word *c)
Definition: mp_madd.h:46
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:159
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
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition: divide.cpp:118