## Coverage Report

#### Created: 2021-02-21 07:20

/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 9 #include 10 #include 11 #include 12 #include 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.22M { 23 2.22M q.cond_flip_sign(x.sign() != y.sign()); 24 25 2.22M if(x.is_negative() && r.is_nonzero()) 26 1.18k { 27 1.18k q -= 1; 28 1.18k r = y.abs() - r; 29 1.18k } 30 2.22M } 31 32 inline bool division_check(word q, word y2, word y1, 33 word x3, word x2, word x1) 34 5.08M { 35 /* 36 Compute (y3,y2,y1) = (y2,y1) * q 37 and return true if (y3,y2,y1) > (x3,x2,x1) 38 */ 39 40 5.08M word y3 = 0; 41 5.08M y1 = word_madd2(q, y1, &y3); 42 5.08M y2 = word_madd2(q, y2, &y3); 43 44 5.08M const word x[3] = { x1, x2, x3 }; 45 5.08M const word y[3] = { y1, y2, y3 }; 46 47 5.08M return bigint_ct_is_lt(x, 3, y, 3).is_set(); 48 5.08M } 49 50 } 51 52 void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) 53 29.2k { 54 29.2k const size_t x_words = x.sig_words(); 55 29.2k const size_t y_words = y.sig_words(); 56 57 29.2k const size_t x_bits = x.bits(); 58 59 29.2k BigInt q(BigInt::Positive, x_words); 60 29.2k BigInt r(BigInt::Positive, y_words); 61 29.2k BigInt t(BigInt::Positive, y_words); // a temporary 62 63 44.1M for(size_t i = 0; i != x_bits; ++i) 64 44.1M { 65 44.1M const size_t b = x_bits - 1 - i; 66 44.1M const bool x_b = x.get_bit(b); 67 68 44.1M r *= 2; 69 44.1M r.conditionally_set_bit(0, x_b); 70 71 44.1M const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0; 72 73 44.1M q.conditionally_set_bit(b, r_gte_y); 74 44.1M r.ct_cond_swap(r_gte_y, t); 75 44.1M } 76 77 29.2k sign_fixup(x, y, q, r); 78 29.2k r_out = r; 79 29.2k q_out = q; 80 29.2k } 81 82 void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out) 83 819 { 84 819 const size_t x_words = x.sig_words(); 85 819 const size_t x_bits = x.bits(); 86 87 819 BigInt q(BigInt::Positive, x_words); 88 819 uint32_t r = 0; 89 90 690k for(size_t i = 0; i != x_bits; ++i) 91 689k { 92 689k const size_t b = x_bits - 1 - i; 93 689k const bool x_b = x.get_bit(b); 94 95 689k r *= 2; 96 689k r += x_b; 97 98 689k const auto r_gte_y = CT::Mask::is_gte(r, y); 99 100 689k q.conditionally_set_bit(b, r_gte_y.is_set()); 101 689k r = r_gte_y.select(r - y, r); 102 689k } 103 104 819 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 114 819 r_out = static_cast(r); 115 819 q_out = q; 116 819 } 117 118 BigInt ct_modulo(const BigInt& x, const BigInt& y) 119 2.18k { 120 2.18k if(y.is_negative() || y.is_zero()) 121 0 throw Invalid_Argument("ct_modulo requires y > 0"); 122 123 2.18k const size_t y_words = y.sig_words(); 124 125 2.18k const size_t x_bits = x.bits(); 126 127 2.18k BigInt r(BigInt::Positive, y_words); 128 2.18k BigInt t(BigInt::Positive, y_words); 129 130 2.11M for(size_t i = 0; i != x_bits; ++i) 131 2.11M { 132 2.11M const size_t b = x_bits - 1 - i; 133 2.11M const bool x_b = x.get_bit(b); 134 135 2.11M r *= 2; 136 2.11M r.conditionally_set_bit(0, x_b); 137 138 2.11M const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0; 139 140 2.11M r.ct_cond_swap(r_gte_y, t); 141 2.11M } 142 143 2.18k if(x.is_negative()) 144 654 { 145 654 if(r.is_nonzero()) 146 606 { 147 606 r = y - r; 148 606 } 149 654 } 150 151 2.18k return r; 152 2.18k } 153 154 /* 155 * Solve x = q * y + r 156 * 157 * See Handbook of Applied Cryptography section 14.2.5 158 */ 159 void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) 160 2.19M { 161 2.19M if(y_arg.is_zero()) 162 0 throw Invalid_Argument("vartime_divide: cannot divide by zero"); 163 164 2.19M const size_t y_words = y_arg.sig_words(); 165 166 2.19M BOTAN_ASSERT_NOMSG(y_words > 0); 167 168 2.19M BigInt y = y_arg; 169 170 2.19M BigInt r = x; 171 2.19M BigInt q = 0; 172 2.19M secure_vector ws; 173 174 2.19M r.set_sign(BigInt::Positive); 175 2.19M y.set_sign(BigInt::Positive); 176 177 // Calculate shifts needed to normalize y with high bit set 178 2.19M const size_t shifts = y.top_bits_free(); 179 180 2.19M y <<= shifts; 181 2.19M r <<= shifts; 182 183 // we know y has not changed size, since we only shifted up to set high bit 184 2.19M const size_t t = y_words - 1; 185 2.19M const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however 186 187 2.19M BOTAN_ASSERT_NOMSG(n >= t); 188 189 2.19M q.grow_to(n - t + 1); 190 191 2.19M word* q_words = q.mutable_data(); 192 193 2.19M BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n-t)); 194 195 // Set q_{n-t} to number of times r > shifted_y 196 2.19M q_words[n-t] = r.reduce_below(shifted_y, ws); 197 198 2.19M const word y_t0 = y.word_at(t); 199 2.19M const word y_t1 = y.word_at(t-1); 200 2.19M BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS-1)) == 1); 201 202 4.73M for(size_t j = n; j != t; --j) 203 2.54M { 204 2.54M const word x_j0 = r.word_at(j); 205 2.54M const word x_j1 = r.word_at(j-1); 206 2.54M const word x_j2 = r.word_at(j-2); 207 208 2.54M word qjt = bigint_divop(x_j0, x_j1, y_t0); 209 210 2.54M qjt = CT::Mask::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 2.54M qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2); 214 2.54M qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2); 215 2.54M BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false); 216 217 2.54M 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 2.54M r -= qjt * shifted_y; 222 2.54M qjt -= r.is_negative(); 223 2.54M r += static_cast(r.is_negative()) * shifted_y; 224 225 2.54M q_words[j-t-1] = qjt; 226 2.54M } 227 228 2.19M r >>= shifts; 229 230 2.19M sign_fixup(x, y_arg, q, r); 231 232 2.19M r_out = r; 233 2.19M q_out = q; 234 2.19M } 235 236 }