Coverage Report

Created: 2020-05-23 13:54

/src/botan/src/lib/math/numbertheory/numthry.cpp
Line
Count
Source (jump to first uncovered line)
1
/*
2
* Number Theory Functions
3
* (C) 1999-2011,2016,2018,2019 Jack Lloyd
4
*
5
* Botan is released under the Simplified BSD License (see license.txt)
6
*/
7
8
#include <botan/numthry.h>
9
#include <botan/reducer.h>
10
#include <botan/monty.h>
11
#include <botan/divide.h>
12
#include <botan/rng.h>
13
#include <botan/internal/ct_utils.h>
14
#include <botan/internal/mp_core.h>
15
#include <botan/internal/monty_exp.h>
16
#include <botan/internal/primality.h>
17
#include <algorithm>
18
19
namespace Botan {
20
21
namespace {
22
23
void sub_abs(BigInt& z, const BigInt& x, const BigInt& y)
24
0
   {
25
0
   const size_t x_sw = x.sig_words();
26
0
   const size_t y_sw = y.sig_words();
27
0
   z.resize(std::max(x_sw, y_sw));
28
0
29
0
   bigint_sub_abs(z.mutable_data(),
30
0
                  x.data(), x_sw,
31
0
                  y.data(), y_sw);
32
0
   }
33
34
}
35
36
/*
37
* Return the number of 0 bits at the end of n
38
*/
39
size_t low_zero_bits(const BigInt& n)
40
3.03M
   {
41
3.03M
   size_t low_zero = 0;
42
3.03M
43
3.03M
   auto seen_nonempty_word = CT::Mask<word>::cleared();
44
3.03M
45
55.2M
   for(size_t i = 0; i != n.size(); ++i)
46
52.1M
      {
47
52.1M
      const word x = n.word_at(i);
48
52.1M
49
52.1M
      // ctz(0) will return sizeof(word)
50
52.1M
      const size_t tz_x = ctz(x);
51
52.1M
52
52.1M
      // if x > 0 we want to count tz_x in total but not any
53
52.1M
      // further words, so set the mask after the addition
54
52.1M
      low_zero += seen_nonempty_word.if_not_set_return(tz_x);
55
52.1M
56
52.1M
      seen_nonempty_word |= CT::Mask<word>::expand(x);
57
52.1M
      }
58
3.03M
59
3.03M
   // if we saw no words with x > 0 then n == 0 and the value we have
60
3.03M
   // computed is meaningless. Instead return 0 in that case.
61
3.03M
   return seen_nonempty_word.if_set_return(low_zero);
62
3.03M
   }
63
64
/*
65
* Calculate the GCD
66
*/
67
BigInt gcd(const BigInt& a, const BigInt& b)
68
0
   {
69
0
   if(a.is_zero() || b.is_zero())
70
0
      return 0;
71
0
   if(a == 1 || b == 1)
72
0
      return 1;
73
0
74
0
   // See https://gcd.cr.yp.to/safegcd-20190413.pdf fig 1.2
75
0
76
0
   BigInt f = a;
77
0
   BigInt g = b;
78
0
   f.const_time_poison();
79
0
   g.const_time_poison();
80
0
81
0
   f.set_sign(BigInt::Positive);
82
0
   g.set_sign(BigInt::Positive);
83
0
84
0
   const size_t common2s = std::min(low_zero_bits(f), low_zero_bits(g));
85
0
   CT::unpoison(common2s);
86
0
87
0
   f >>= common2s;
88
0
   g >>= common2s;
89
0
90
0
   f.ct_cond_swap(f.is_even(), g);
91
0
92
0
   int32_t delta = 1;
93
0
94
0
   const size_t loop_cnt = 4 + 3*std::max(f.bits(), g.bits());
95
0
96
0
   BigInt newg, t;
97
0
   for(size_t i = 0; i != loop_cnt; ++i)
98
0
      {
99
0
      sub_abs(newg, f, g);
100
0
101
0
      const bool need_swap = (g.is_odd() && delta > 0);
102
0
103
0
      // if(need_swap) delta *= -1
104
0
      delta *= CT::Mask<uint8_t>::expand(need_swap).select(0, 2) - 1;
105
0
      f.ct_cond_swap(need_swap, g);
106
0
      g.ct_cond_swap(need_swap, newg);
107
0
108
0
      delta += 1;
109
0
110
0
      g.ct_cond_add(g.is_odd(), f);
111
0
      g >>= 1;
112
0
      }
113
0
114
0
   f <<= common2s;
115
0
116
0
   f.const_time_unpoison();
117
0
   g.const_time_unpoison();
118
0
119
0
   return f;
120
0
   }
121
122
/*
123
* Calculate the LCM
124
*/
125
BigInt lcm(const BigInt& a, const BigInt& b)
126
0
   {
127
0
   return ct_divide(a * b, gcd(a, b));
128
0
   }
129
130
/*
131
* Modular Exponentiation
132
*/
133
BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod)
134
63.9k
   {
135
63.9k
   if(mod.is_negative() || mod == 1)
136
18
      {
137
18
      return 0;
138
18
      }
139
63.9k
140
63.9k
   if(base.is_zero() || mod.is_zero())
141
13
      {
142
13
      if(exp.is_zero())
143
1
         return 1;
144
12
      return 0;
145
12
      }
146
63.9k
147
63.9k
   Modular_Reducer reduce_mod(mod);
148
63.9k
149
63.9k
   const size_t exp_bits = exp.bits();
150
63.9k
151
63.9k
   if(mod.is_odd())
152
63.3k
      {
153
63.3k
      const size_t powm_window = 4;
154
63.3k
155
63.3k
      auto monty_mod = std::make_shared<Montgomery_Params>(mod, reduce_mod);
156
63.3k
      auto powm_base_mod = monty_precompute(monty_mod, reduce_mod.reduce(base), powm_window);
157
63.3k
      return monty_execute(*powm_base_mod, exp, exp_bits);
158
63.3k
      }
159
556
160
556
   /*
161
556
   Support for even modulus is just a convenience and not considered
162
556
   cryptographically important, so this implementation is slow ...
163
556
   */
164
556
   BigInt accum = 1;
165
556
   BigInt g = reduce_mod.reduce(base);
166
556
   BigInt t;
167
556
168
253k
   for(size_t i = 0; i != exp_bits; ++i)
169
252k
      {
170
252k
      t = reduce_mod.multiply(g, accum);
171
252k
      g = reduce_mod.square(g);
172
252k
      accum.ct_cond_assign(exp.get_bit(i), t);
173
252k
      }
174
556
   return accum;
175
556
   }
176
177
178
BigInt is_perfect_square(const BigInt& C)
179
94
   {
180
94
   if(C < 1)
181
0
      throw Invalid_Argument("is_perfect_square requires C >= 1");
182
94
   if(C == 1)
183
0
      return 1;
184
94
185
94
   const size_t n = C.bits();
186
94
   const size_t m = (n + 1) / 2;
187
94
   const BigInt B = C + BigInt::power_of_2(m);
188
94
189
94
   BigInt X = BigInt::power_of_2(m) - 1;
190
94
   BigInt X2 = (X*X);
191
94
192
94
   for(;;)
193
453
      {
194
453
      X = (X2 + C) / (2*X);
195
453
      X2 = (X*X);
196
453
197
453
      if(X2 < B)
198
94
         break;
199
453
      }
200
94
201
94
   if(X2 == C)
202
0
      return X;
203
94
   else
204
94
      return 0;
205
94
   }
206
207
/*
208
* Test for primality using Miller-Rabin
209
*/
210
bool is_prime(const BigInt& n,
211
              RandomNumberGenerator& rng,
212
              size_t prob,
213
              bool is_random)
214
149
   {
215
149
   if(n == 2)
216
0
      return true;
217
149
   if(n <= 1 || n.is_even())
218
0
      return false;
219
149
220
149
   const size_t n_bits = n.bits();
221
149
222
149
   // Fast path testing for small numbers (<= 65521)
223
149
   if(n_bits <= 16)
224
0
      {
225
0
      const uint16_t num = static_cast<uint16_t>(n.word_at(0));
226
0
227
0
      return std::binary_search(PRIMES, PRIMES + PRIME_TABLE_SIZE, num);
228
0
      }
229
149
230
149
   Modular_Reducer mod_n(n);
231
149
232
149
   if(rng.is_seeded())
233
149
      {
234
149
      const size_t t = miller_rabin_test_iterations(n_bits, prob, is_random);
235
149
236
149
      if(is_miller_rabin_probable_prime(n, mod_n, rng, t) == false)
237
69
         return false;
238
80
239
80
      return is_lucas_probable_prime(n, mod_n);
240
80
      }
241
0
   else
242
0
      {
243
0
      return is_bailie_psw_probable_prime(n, mod_n);
244
0
      }
245
149
   }
246
247
}