Botan  2.11.0
Crypto and TLS for C++11
primality.cpp
Go to the documentation of this file.
1 /*
2 * (C) 2016,2018 Jack Lloyd
3 *
4 * Botan is released under the Simplified BSD License (see license.txt)
5 */
6 
7 #include <botan/internal/primality.h>
8 #include <botan/internal/monty_exp.h>
9 #include <botan/bigint.h>
10 #include <botan/monty.h>
11 #include <botan/reducer.h>
12 #include <botan/rng.h>
13 #include <algorithm>
14 
15 namespace Botan {
16 
17 bool is_lucas_probable_prime(const BigInt& C, const Modular_Reducer& mod_C)
18  {
19  if(C <= 1)
20  return false;
21  else if(C == 2)
22  return true;
23  else if(C.is_even())
24  return false;
25  else if(C == 3 || C == 5 || C == 7 || C == 11 || C == 13)
26  return true;
27 
28  BigInt D = 5;
29 
30  for(;;)
31  {
32  int32_t j = jacobi(D, C);
33  if(j == 0)
34  return false;
35 
36  if(j == -1)
37  break;
38 
39  // Check 5, -7, 9, -11, 13, -15, 17, ...
40  if(D.is_negative())
41  {
42  D.flip_sign();
43  D += 2;
44  }
45  else
46  {
47  D += 2;
48  D.flip_sign();
49  }
50 
51  if(D == 17 && is_perfect_square(C).is_nonzero())
52  return false;
53  }
54 
55  const BigInt K = C + 1;
56  const size_t K_bits = K.bits() - 1;
57 
58  BigInt U = 1;
59  BigInt V = 1;
60 
61  BigInt Ut, Vt, U2, V2;
62 
63  for(size_t i = 0; i != K_bits; ++i)
64  {
65  const uint8_t k_bit = K.get_bit(K_bits - 1 - i);
66 
67  Ut = mod_C.multiply(U, V);
68 
69  Vt = mod_C.reduce(mod_C.square(V) + mod_C.multiply(D, mod_C.square(U)));
70  if(Vt.is_odd())
71  Vt += C;
72  Vt >>= 1;
73  Vt = mod_C.reduce(Vt);
74 
75  U = Ut;
76  V = Vt;
77 
78  U2 = mod_C.reduce(Ut + Vt);
79  if(U2.is_odd())
80  U2 += C;
81  U2 >>= 1;
82 
83  V2 = mod_C.reduce(Vt + Ut*D);
84  if(V2.is_odd())
85  V2 += C;
86  V2 >>= 1;
87 
88  U.ct_cond_assign(k_bit, U2);
89  V.ct_cond_assign(k_bit, V2);
90  }
91 
92  return (U == 0);
93  }
94 
95 bool is_bailie_psw_probable_prime(const BigInt& n, const Modular_Reducer& mod_n)
96  {
97  auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
98  return passes_miller_rabin_test(n, mod_n, monty_n, 2) && is_lucas_probable_prime(n, mod_n);
99  }
100 
101 bool is_bailie_psw_probable_prime(const BigInt& n)
102  {
103  Modular_Reducer mod_n(n);
104  return is_bailie_psw_probable_prime(n, mod_n);
105  }
106 
107 bool passes_miller_rabin_test(const BigInt& n,
108  const Modular_Reducer& mod_n,
109  const std::shared_ptr<Montgomery_Params>& monty_n,
110  const BigInt& a)
111  {
112  BOTAN_ASSERT_NOMSG(n > 1);
113 
114  const BigInt n_minus_1 = n - 1;
115  const size_t s = low_zero_bits(n_minus_1);
116  const BigInt nm1_s = n_minus_1 >> s;
117  const size_t n_bits = n.bits();
118 
119  const size_t powm_window = 4;
120 
121  auto powm_a_n = monty_precompute(monty_n, a, powm_window);
122 
123  BigInt y = monty_execute(*powm_a_n, nm1_s, n_bits);
124 
125  if(y == 1 || y == n_minus_1)
126  return true;
127 
128  for(size_t i = 1; i != s; ++i)
129  {
130  y = mod_n.square(y);
131 
132  if(y == 1) // found a non-trivial square root
133  return false;
134 
135  /*
136  -1 is the trivial square root of unity, so ``a`` is not a
137  witness for this number - give up
138  */
139  if(y == n_minus_1)
140  return true;
141  }
142 
143  return false;
144  }
145 
147  const Modular_Reducer& mod_n,
148  RandomNumberGenerator& rng,
149  size_t test_iterations)
150  {
151  BOTAN_ASSERT_NOMSG(n > 1);
152 
153  auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
154 
155  for(size_t i = 0; i != test_iterations; ++i)
156  {
157  const BigInt a = BigInt::random_integer(rng, 2, n);
158 
159  if(!passes_miller_rabin_test(n, mod_n, monty_n, a))
160  return false;
161  }
162 
163  // Failed to find a counterexample
164  return true;
165  }
166 
167 
168 size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
169  {
170  const size_t base = (prob + 2) / 2; // worst case 4^-t error rate
171 
172  /*
173  * If the candidate prime was maliciously constructed, we can't rely
174  * on arguments based on p being random.
175  */
176  if(random == false)
177  return base;
178 
179  /*
180  * For randomly chosen numbers we can use the estimates from
181  * http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf
182  *
183  * These values are derived from the inequality for p(k,t) given on
184  * the second page.
185  */
186  if(prob <= 128)
187  {
188  if(n_bits >= 1536)
189  return 4; // < 2^-133
190  if(n_bits >= 1024)
191  return 6; // < 2^-133
192  if(n_bits >= 512)
193  return 12; // < 2^-129
194  if(n_bits >= 256)
195  return 29; // < 2^-128
196  }
197 
198  /*
199  If the user desires a smaller error probability than we have
200  precomputed error estimates for, just fall back to using the worst
201  case error rate.
202  */
203  return base;
204  }
205 
206 }
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)
Definition: primality.cpp:17
bool RandomNumberGenerator & rng
Definition: numthry.h:176
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:26
BigInt size_t n
Definition: bigint.h:1096
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
Definition: primality.cpp:168
botan_rng_t size_t n_bits
Definition: ffi.h:949
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
bool is_bailie_psw_probable_prime(const BigInt &n, const Modular_Reducer &mod_n)
Definition: primality.cpp:95
bool RandomNumberGenerator size_t prob
Definition: numthry.h:177
size_t const BigInt & a
Definition: numthry.h:111
BigInt is_perfect_square(const BigInt &C)
Definition: numthry.cpp:456
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(std::shared_ptr< const Montgomery_Params > params, const BigInt &g, size_t window_bits, bool const_time)
Definition: monty_exp.cpp:159
Definition: alg_id.cpp:13
bool passes_miller_rabin_test(const BigInt &n, const Modular_Reducer &mod_n, const std::shared_ptr< Montgomery_Params > &monty_n, const BigInt &a)
Definition: primality.cpp:107
uint8_t base
Definition: ffi.h:749
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
Definition: primality.cpp:146
const OctetString & y
Definition: symkey.h:126
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
Definition: monty_exp.cpp:167
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15