Botan  2.6.0
Crypto and TLS for C++11
curve_gfp.cpp
Go to the documentation of this file.
1 /*
2 * Elliptic curves over GF(p) Montgomery Representation
3 * (C) 2014,2015,2018 Jack Lloyd
4 * 2016 Matthias Gierlings
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 */
8 
9 #include <botan/curve_gfp.h>
10 #include <botan/curve_nistp.h>
11 #include <botan/numthry.h>
12 #include <botan/reducer.h>
13 #include <botan/internal/mp_core.h>
14 #include <botan/internal/mp_asmi.h>
15 
16 namespace Botan {
17 
18 namespace {
19 
20 class CurveGFp_Montgomery final : public CurveGFp_Repr
21  {
22  public:
23  CurveGFp_Montgomery(const BigInt& p, const BigInt& a, const BigInt& b) :
24  m_p(p), m_a(a), m_b(b),
25  m_p_words(m_p.sig_words()),
26  m_p_dash(monty_inverse(m_p.word_at(0)))
27  {
28  Modular_Reducer mod_p(m_p);
29 
30  m_r.set_bit(m_p_words * BOTAN_MP_WORD_BITS);
31  m_r = mod_p.reduce(m_r);
32 
33  m_r2 = mod_p.square(m_r);
34  m_r3 = mod_p.multiply(m_r, m_r2);
35  m_a_r = mod_p.multiply(m_r, m_a);
36  m_b_r = mod_p.multiply(m_r, m_b);
37  }
38 
39  const BigInt& get_a() const override { return m_a; }
40 
41  const BigInt& get_b() const override { return m_b; }
42 
43  const BigInt& get_p() const override { return m_p; }
44 
45  const BigInt& get_a_rep() const override { return m_a_r; }
46 
47  const BigInt& get_b_rep() const override { return m_b_r; }
48 
49  bool is_one(const BigInt& x) const override { return x == m_r; }
50 
51  size_t get_p_words() const override { return m_p_words; }
52 
53  size_t get_ws_size() const override { return 2*m_p_words + 4; }
54 
55  BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
56 
57  void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
58 
59  void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
60 
61  void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
62  secure_vector<word>& ws) const override;
63 
64  void curve_mul_words(BigInt& z,
65  const word x_words[],
66  const size_t x_size,
67  const BigInt& y,
68  secure_vector<word>& ws) const override;
69 
70  void curve_sqr(BigInt& z, const BigInt& x,
71  secure_vector<word>& ws) const override;
72  private:
73  BigInt m_p;
74  BigInt m_a, m_b;
75  BigInt m_a_r, m_b_r;
76  size_t m_p_words; // cache of m_p.sig_words()
77 
78  // Montgomery parameters
79  BigInt m_r, m_r2, m_r3;
80  word m_p_dash;
81  };
82 
83 BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const
84  {
85  // Should we use Montgomery inverse instead?
86  const BigInt inv = inverse_mod(x, m_p);
87  BigInt res;
88  curve_mul(res, inv, m_r3, ws);
89  return res;
90  }
91 
92 void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const
93  {
94  const BigInt tx = x;
95  curve_mul(x, tx, m_r2, ws);
96  }
97 
98 void CurveGFp_Montgomery::from_curve_rep(BigInt& z, secure_vector<word>& ws) const
99  {
100  if(ws.size() < get_ws_size())
101  ws.resize(get_ws_size());
102 
103  const size_t output_size = 2*m_p_words + 2;
104  if(z.size() < output_size)
105  z.grow_to(output_size);
106 
107  bigint_monty_redc(z.mutable_data(),
108  m_p.data(), m_p_words, m_p_dash,
109  ws.data(), ws.size());
110  }
111 
112 void CurveGFp_Montgomery::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
113  secure_vector<word>& ws) const
114  {
115  if(ws.size() < get_ws_size())
116  ws.resize(get_ws_size());
117 
118  const size_t output_size = 2*m_p_words + 2;
119  if(z.size() < output_size)
120  z.grow_to(output_size);
121 
122  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
123  BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
124 
125  const size_t x_words = (x.size() >= m_p_words) ? m_p_words : x.sig_words();
126  const size_t y_words = (y.size() >= m_p_words) ? m_p_words : y.sig_words();
127 
128  bigint_mul(z.mutable_data(), z.size(),
129  x.data(), x.size(), x_words,
130  y.data(), y.size(), y_words,
131  ws.data(), ws.size());
132 
133  bigint_monty_redc(z.mutable_data(),
134  m_p.data(), m_p_words, m_p_dash,
135  ws.data(), ws.size());
136  }
137 
138 void CurveGFp_Montgomery::curve_mul_words(BigInt& z,
139  const word x_w[],
140  size_t x_size,
141  const BigInt& y,
142  secure_vector<word>& ws) const
143  {
144  if(ws.size() < get_ws_size())
145  ws.resize(get_ws_size());
146 
147  const size_t output_size = 2*m_p_words + 2;
148  if(z.size() < output_size)
149  z.grow_to(output_size);
150 
151  BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
152 
153  const size_t x_words = (x_size >= m_p_words) ? m_p_words : x_size;
154  const size_t y_words = (y.size() >= m_p_words) ? m_p_words : y.sig_words();
155 
156  bigint_mul(z.mutable_data(), z.size(),
157  x_w, x_size, x_words,
158  y.data(), y.size(), y_words,
159  ws.data(), ws.size());
160 
161  bigint_monty_redc(z.mutable_data(),
162  m_p.data(), m_p_words, m_p_dash,
163  ws.data(), ws.size());
164  }
165 
166 void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x,
167  secure_vector<word>& ws) const
168  {
169  if(ws.size() < get_ws_size())
170  ws.resize(get_ws_size());
171 
172  const size_t output_size = 2*m_p_words + 2;
173  if(z.size() < output_size)
174  z.grow_to(output_size);
175 
176  const size_t x_words = (x.size() >= m_p_words) ? m_p_words : x.sig_words();
177 
178  bigint_sqr(z.mutable_data(), z.size(),
179  x.data(), x.size(), x_words,
180  ws.data(), ws.size());
181 
182  bigint_monty_redc(z.mutable_data(),
183  m_p.data(), m_p_words, m_p_dash,
184  ws.data(), ws.size());
185  }
186 
187 class CurveGFp_NIST : public CurveGFp_Repr
188  {
189  public:
190  CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) :
191  m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS)
192  {
193  }
194 
195  const BigInt& get_a() const override { return m_a; }
196 
197  const BigInt& get_b() const override { return m_b; }
198 
199  size_t get_p_words() const override { return m_p_words; }
200 
201  size_t get_ws_size() const override { return 2*m_p_words + 4; }
202 
203  const BigInt& get_a_rep() const override { return m_a; }
204 
205  const BigInt& get_b_rep() const override { return m_b; }
206 
207  bool is_one(const BigInt& x) const override { return x == 1; }
208 
209  void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override
210  { redc(x, ws); }
211 
212  void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override
213  { redc(x, ws); }
214 
215  BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
216 
217  void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
218  secure_vector<word>& ws) const override;
219 
220  void curve_mul_words(BigInt& z,
221  const word x_words[],
222  const size_t x_size,
223  const BigInt& y,
224  secure_vector<word>& ws) const override;
225 
226  void curve_sqr(BigInt& z, const BigInt& x,
227  secure_vector<word>& ws) const override;
228  private:
229  virtual void redc(BigInt& x, secure_vector<word>& ws) const = 0;
230 
231  // Curve parameters
232  BigInt m_a, m_b;
233  size_t m_p_words; // cache of m_p.sig_words()
234  };
235 
236 
237 BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector<word>& ws) const
238  {
239  BOTAN_UNUSED(ws);
240  return inverse_mod(x, get_p());
241  }
242 
243 void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
244  secure_vector<word>& ws) const
245  {
246  if(ws.size() < get_ws_size())
247  ws.resize(get_ws_size());
248 
249  const size_t output_size = 2*m_p_words + 2;
250  if(z.size() < output_size)
251  z.grow_to(output_size);
252 
253  const size_t x_words = (x.size() >= m_p_words) ? m_p_words : x.sig_words();
254  const size_t y_words = (y.size() >= m_p_words) ? m_p_words : y.sig_words();
255 
256  bigint_mul(z.mutable_data(), z.size(),
257  x.data(), x.size(), x_words,
258  y.data(), y.size(), y_words,
259  ws.data(), ws.size());
260 
261  this->redc(z, ws);
262  }
263 
264 void CurveGFp_NIST::curve_mul_words(BigInt& z,
265  const word x_w[],
266  size_t x_size,
267  const BigInt& y,
268  secure_vector<word>& ws) const
269  {
270  if(ws.size() < get_ws_size())
271  ws.resize(get_ws_size());
272 
273  const size_t output_size = 2*m_p_words + 2;
274  if(z.size() < output_size)
275  z.grow_to(output_size);
276 
277  const size_t x_words = (x_size >= m_p_words) ? m_p_words : x_size;
278  const size_t y_words = (y.size() >= m_p_words) ? m_p_words : y.sig_words();
279 
280  bigint_mul(z.mutable_data(), z.size(),
281  x_w, x_size, x_words,
282  y.data(), y.size(), y_words,
283  ws.data(), ws.size());
284 
285  this->redc(z, ws);
286  }
287 
288 void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x,
289  secure_vector<word>& ws) const
290  {
291  if(ws.size() < get_ws_size())
292  ws.resize(get_ws_size());
293 
294  const size_t output_size = 2*m_p_words + 2;
295  if(z.size() < output_size)
296  z.grow_to(output_size);
297 
298  const size_t x_words = (x.size() >= m_p_words) ? m_p_words : x.sig_words();
299 
300  bigint_sqr(z.mutable_data(), output_size,
301  x.data(), x.size(), x_words,
302  ws.data(), ws.size());
303 
304  this->redc(z, ws);
305  }
306 
307 #if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
308 
309 /**
310 * The NIST P-192 curve
311 */
312 class CurveGFp_P192 final : public CurveGFp_NIST
313  {
314  public:
315  CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {}
316  const BigInt& get_p() const override { return prime_p192(); }
317  private:
318  void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p192(x, ws); }
319  };
320 
321 /**
322 * The NIST P-224 curve
323 */
324 class CurveGFp_P224 final : public CurveGFp_NIST
325  {
326  public:
327  CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {}
328  const BigInt& get_p() const override { return prime_p224(); }
329  private:
330  void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p224(x, ws); }
331  };
332 
333 /**
334 * The NIST P-256 curve
335 */
336 class CurveGFp_P256 final : public CurveGFp_NIST
337  {
338  public:
339  CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {}
340  const BigInt& get_p() const override { return prime_p256(); }
341  private:
342  void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); }
343  };
344 
345 /**
346 * The NIST P-384 curve
347 */
348 class CurveGFp_P384 final : public CurveGFp_NIST
349  {
350  public:
351  CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {}
352  const BigInt& get_p() const override { return prime_p384(); }
353  private:
354  void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); }
355  };
356 
357 #endif
358 
359 /**
360 * The NIST P-521 curve
361 */
362 class CurveGFp_P521 final : public CurveGFp_NIST
363  {
364  public:
365  CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {}
366  const BigInt& get_p() const override { return prime_p521(); }
367  private:
368  void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); }
369  };
370 
371 }
372 
373 std::shared_ptr<CurveGFp_Repr>
374 CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b)
375  {
376 #if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
377  if(p == prime_p192())
378  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b));
379  if(p == prime_p224())
380  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b));
381  if(p == prime_p256())
382  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b));
383  if(p == prime_p384())
384  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b));
385 #endif
386 
387  if(p == prime_p521())
388  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b));
389 
390  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b));
391  }
392 
393 }
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:351
const word * data() const
Definition: bigint.h:504
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:98
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:279
Definition: alg_id.cpp:13
void redc_p521(BigInt &x, secure_vector< word > &ws)
Definition: nistp_redc.cpp:22
#define BOTAN_UNUSED(...)
Definition: assert.h:117
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:296
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:22
const BigInt & prime_p521()
Definition: nistp_redc.cpp:14
word monty_inverse(word input)
Definition: numthry.cpp:341