Botan  2.9.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  m_a_is_zero = m_a.is_zero();
39  m_a_is_minus_3 = (m_a + 3 == m_p);
40  }
41 
42  bool a_is_zero() const override { return m_a_is_zero; }
43  bool a_is_minus_3() const override { return m_a_is_minus_3; }
44 
45  const BigInt& get_a() const override { return m_a; }
46 
47  const BigInt& get_b() const override { return m_b; }
48 
49  const BigInt& get_p() const override { return m_p; }
50 
51  const BigInt& get_a_rep() const override { return m_a_r; }
52 
53  const BigInt& get_b_rep() const override { return m_b_r; }
54 
55  const BigInt& get_1_rep() const override { return m_r; }
56 
57  bool is_one(const BigInt& x) const override { return x == m_r; }
58 
59  size_t get_p_words() const override { return m_p_words; }
60 
61  size_t get_ws_size() const override { return 2*m_p_words + 4; }
62 
63  BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
64 
65  void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
66 
67  void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
68 
69  void curve_mul_words(BigInt& z,
70  const word x_words[],
71  const size_t x_size,
72  const BigInt& y,
73  secure_vector<word>& ws) const override;
74 
75  void curve_sqr_words(BigInt& z,
76  const word x_words[],
77  size_t x_size,
78  secure_vector<word>& ws) const override;
79 
80  private:
81  BigInt m_p;
82  BigInt m_a, m_b;
83  BigInt m_a_r, m_b_r;
84  size_t m_p_words; // cache of m_p.sig_words()
85 
86  // Montgomery parameters
87  BigInt m_r, m_r2, m_r3;
88  word m_p_dash;
89 
90  bool m_a_is_zero;
91  bool m_a_is_minus_3;
92  };
93 
94 BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const
95  {
96  // Should we use Montgomery inverse instead?
97  const BigInt inv = inverse_mod(x, m_p);
98  BigInt res;
99  curve_mul(res, inv, m_r3, ws);
100  return res;
101  }
102 
103 void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const
104  {
105  const BigInt tx = x;
106  curve_mul(x, tx, m_r2, ws);
107  }
108 
109 void CurveGFp_Montgomery::from_curve_rep(BigInt& z, secure_vector<word>& ws) const
110  {
111  if(ws.size() < get_ws_size())
112  ws.resize(get_ws_size());
113 
114  const size_t output_size = 2*m_p_words + 2;
115  if(z.size() < output_size)
116  z.grow_to(output_size);
117 
118  bigint_monty_redc(z.mutable_data(),
119  m_p.data(), m_p_words, m_p_dash,
120  ws.data(), ws.size());
121  }
122 
123 void CurveGFp_Montgomery::curve_mul_words(BigInt& z,
124  const word x_w[],
125  size_t x_size,
126  const BigInt& y,
127  secure_vector<word>& ws) const
128  {
129  BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
130 
131  if(ws.size() < get_ws_size())
132  ws.resize(get_ws_size());
133 
134  const size_t output_size = 2*m_p_words + 2;
135  if(z.size() < output_size)
136  z.grow_to(output_size);
137 
138  bigint_mul(z.mutable_data(), z.size(),
139  x_w, x_size, std::min(m_p_words, x_size),
140  y.data(), y.size(), std::min(m_p_words, y.size()),
141  ws.data(), ws.size());
142 
143  bigint_monty_redc(z.mutable_data(),
144  m_p.data(), m_p_words, m_p_dash,
145  ws.data(), ws.size());
146  }
147 
148 void CurveGFp_Montgomery::curve_sqr_words(BigInt& z,
149  const word x[],
150  size_t x_size,
151  secure_vector<word>& ws) const
152  {
153  if(ws.size() < get_ws_size())
154  ws.resize(get_ws_size());
155 
156  const size_t output_size = 2*m_p_words + 2;
157  if(z.size() < output_size)
158  z.grow_to(output_size);
159 
160  bigint_sqr(z.mutable_data(), z.size(),
161  x, x_size, std::min(m_p_words, x_size),
162  ws.data(), ws.size());
163 
164  bigint_monty_redc(z.mutable_data(),
165  m_p.data(), m_p_words, m_p_dash,
166  ws.data(), ws.size());
167  }
168 
169 class CurveGFp_NIST : public CurveGFp_Repr
170  {
171  public:
172  CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) :
173  m_1(1), m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS)
174  {
175  // All Solinas prime curves are assumed a == -3
176  }
177 
178  bool a_is_zero() const override { return false; }
179  bool a_is_minus_3() const override { return true; }
180 
181  const BigInt& get_a() const override { return m_a; }
182 
183  const BigInt& get_b() const override { return m_b; }
184 
185  const BigInt& get_1_rep() const override { return m_1; }
186 
187  size_t get_p_words() const override { return m_p_words; }
188 
189  size_t get_ws_size() const override { return 2*m_p_words + 4; }
190 
191  const BigInt& get_a_rep() const override { return m_a; }
192 
193  const BigInt& get_b_rep() const override { return m_b; }
194 
195  bool is_one(const BigInt& x) const override { return x == 1; }
196 
197  void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override
198  { redc_mod_p(x, ws); }
199 
200  void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override
201  { redc_mod_p(x, ws); }
202 
203  virtual void redc_mod_p(BigInt& z, secure_vector<word>& ws) const = 0;
204 
205  BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
206 
207  void curve_mul_words(BigInt& z,
208  const word x_words[],
209  const size_t x_size,
210  const BigInt& y,
211  secure_vector<word>& ws) const override;
212 
213  void curve_mul_tmp(BigInt& x, const BigInt& y, BigInt& tmp, secure_vector<word>& ws) const
214  {
215  curve_mul(tmp, x, y, ws);
216  x.swap(tmp);
217  }
218 
219  void curve_sqr_tmp(BigInt& x, BigInt& tmp, secure_vector<word>& ws) const
220  {
221  curve_sqr(tmp, x, ws);
222  x.swap(tmp);
223  }
224 
225  void curve_sqr_words(BigInt& z,
226  const word x_words[],
227  size_t x_size,
228  secure_vector<word>& ws) const override;
229  private:
230  // Curve parameters
231  BigInt m_1;
232  BigInt m_a, m_b;
233  size_t m_p_words; // cache of m_p.sig_words()
234  };
235 
236 BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector<word>& ws) const
237  {
238  BOTAN_UNUSED(ws);
239  return inverse_mod(x, get_p());
240  }
241 
242 void CurveGFp_NIST::curve_mul_words(BigInt& z,
243  const word x_w[],
244  size_t x_size,
245  const BigInt& y,
246  secure_vector<word>& ws) const
247  {
248  BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
249 
250  if(ws.size() < get_ws_size())
251  ws.resize(get_ws_size());
252 
253  const size_t output_size = 2*m_p_words + 2;
254  if(z.size() < output_size)
255  z.grow_to(output_size);
256 
257  bigint_mul(z.mutable_data(), z.size(),
258  x_w, x_size, std::min(m_p_words, x_size),
259  y.data(), y.size(), std::min(m_p_words, y.size()),
260  ws.data(), ws.size());
261 
262  this->redc_mod_p(z, ws);
263  }
264 
265 void CurveGFp_NIST::curve_sqr_words(BigInt& z, const word x[], size_t x_size,
266  secure_vector<word>& ws) const
267  {
268  if(ws.size() < get_ws_size())
269  ws.resize(get_ws_size());
270 
271  const size_t output_size = 2*m_p_words + 2;
272  if(z.size() < output_size)
273  z.grow_to(output_size);
274 
275  bigint_sqr(z.mutable_data(), output_size,
276  x, x_size, std::min(m_p_words, x_size),
277  ws.data(), ws.size());
278 
279  this->redc_mod_p(z, ws);
280  }
281 
282 #if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
283 
284 /**
285 * The NIST P-192 curve
286 */
287 class CurveGFp_P192 final : public CurveGFp_NIST
288  {
289  public:
290  CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {}
291  const BigInt& get_p() const override { return prime_p192(); }
292  private:
293  void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p192(x, ws); }
294  };
295 
296 /**
297 * The NIST P-224 curve
298 */
299 class CurveGFp_P224 final : public CurveGFp_NIST
300  {
301  public:
302  CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {}
303  const BigInt& get_p() const override { return prime_p224(); }
304  private:
305  void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p224(x, ws); }
306  };
307 
308 /**
309 * The NIST P-256 curve
310 */
311 class CurveGFp_P256 final : public CurveGFp_NIST
312  {
313  public:
314  CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {}
315  const BigInt& get_p() const override { return prime_p256(); }
316  private:
317  void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); }
318  BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
319  };
320 
321 BigInt CurveGFp_P256::invert_element(const BigInt& x, secure_vector<word>& ws) const
322  {
323  BigInt r, p2, p4, p8, p16, p32, tmp;
324 
325  curve_sqr(r, x, ws);
326 
327  curve_mul(p2, r, x, ws);
328  curve_sqr(r, p2, ws);
329  curve_sqr_tmp(r, tmp, ws);
330 
331  curve_mul(p4, r, p2, ws);
332 
333  curve_sqr(r, p4, ws);
334  for(size_t i = 0; i != 3; ++i)
335  curve_sqr_tmp(r, tmp, ws);
336  curve_mul(p8, r, p4, ws);;
337 
338  curve_sqr(r, p8, ws);
339  for(size_t i = 0; i != 7; ++i)
340  curve_sqr_tmp(r, tmp, ws);
341  curve_mul(p16, r, p8, ws);
342 
343  curve_sqr(r, p16, ws);
344  for(size_t i = 0; i != 15; ++i)
345  curve_sqr_tmp(r, tmp, ws);
346  curve_mul(p32, r, p16, ws);
347 
348  curve_sqr(r, p32, ws);
349  for(size_t i = 0; i != 31; ++i)
350  curve_sqr_tmp(r, tmp, ws);
351  curve_mul_tmp(r, x, tmp, ws);
352 
353  for(size_t i = 0; i != 32*4; ++i)
354  curve_sqr_tmp(r, tmp, ws);
355  curve_mul_tmp(r, p32, tmp, ws);
356 
357  for(size_t i = 0; i != 32; ++i)
358  curve_sqr_tmp(r, tmp, ws);
359  curve_mul_tmp(r, p32, tmp, ws);
360 
361  for(size_t i = 0; i != 16; ++i)
362  curve_sqr_tmp(r, tmp, ws);
363  curve_mul_tmp(r, p16, tmp, ws);
364  for(size_t i = 0; i != 8; ++i)
365  curve_sqr_tmp(r, tmp, ws);
366  curve_mul_tmp(r, p8, tmp, ws);
367 
368  for(size_t i = 0; i != 4; ++i)
369  curve_sqr_tmp(r, tmp, ws);
370  curve_mul_tmp(r, p4, tmp, ws);
371 
372  for(size_t i = 0; i != 2; ++i)
373  curve_sqr_tmp(r, tmp, ws);
374  curve_mul_tmp(r, p2, tmp, ws);
375 
376  for(size_t i = 0; i != 2; ++i)
377  curve_sqr_tmp(r, tmp, ws);
378  curve_mul_tmp(r, x, tmp, ws);
379 
380  return r;
381  }
382 
383 /**
384 * The NIST P-384 curve
385 */
386 class CurveGFp_P384 final : public CurveGFp_NIST
387  {
388  public:
389  CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {}
390  const BigInt& get_p() const override { return prime_p384(); }
391  private:
392  void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); }
393  BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
394  };
395 
396 BigInt CurveGFp_P384::invert_element(const BigInt& x, secure_vector<word>& ws) const
397  {
398  BigInt r, x2, x3, x15, x30, tmp, rl;
399 
400  r = x;
401  curve_sqr_tmp(r, tmp, ws);
402  curve_mul_tmp(r, x, tmp, ws);
403  x2 = r;
404 
405  curve_sqr_tmp(r, tmp, ws);
406  curve_mul_tmp(r, x, tmp, ws);
407 
408  x3 = r;
409 
410  for(size_t i = 0; i != 3; ++i)
411  curve_sqr_tmp(r, tmp, ws);
412  curve_mul_tmp(r, x3, tmp, ws);
413 
414  rl = r;
415  for(size_t i = 0; i != 6; ++i)
416  curve_sqr_tmp(r, tmp, ws);
417  curve_mul_tmp(r, rl, tmp, ws);
418 
419  for(size_t i = 0; i != 3; ++i)
420  curve_sqr_tmp(r, tmp, ws);
421  curve_mul_tmp(r, x3, tmp, ws);
422 
423  x15 = r;
424  for(size_t i = 0; i != 15; ++i)
425  curve_sqr_tmp(r, tmp, ws);
426  curve_mul_tmp(r, x15, tmp, ws);
427 
428  x30 = r;
429  for(size_t i = 0; i != 30; ++i)
430  curve_sqr_tmp(r, tmp, ws);
431  curve_mul_tmp(r, x30, tmp, ws);
432 
433  rl = r;
434  for(size_t i = 0; i != 60; ++i)
435  curve_sqr_tmp(r, tmp, ws);
436  curve_mul_tmp(r, rl, tmp, ws);
437 
438  rl = r;
439  for(size_t i = 0; i != 120; ++i)
440  curve_sqr_tmp(r, tmp, ws);
441  curve_mul_tmp(r, rl, tmp, ws);
442 
443  for(size_t i = 0; i != 15; ++i)
444  curve_sqr_tmp(r, tmp, ws);
445  curve_mul_tmp(r, x15, tmp, ws);
446 
447  for(size_t i = 0; i != 31; ++i)
448  curve_sqr_tmp(r, tmp, ws);
449  curve_mul_tmp(r, x30, tmp, ws);
450 
451  for(size_t i = 0; i != 2; ++i)
452  curve_sqr_tmp(r, tmp, ws);
453  curve_mul_tmp(r, x2, tmp, ws);
454 
455  for(size_t i = 0; i != 94; ++i)
456  curve_sqr_tmp(r, tmp, ws);
457  curve_mul_tmp(r, x30, tmp, ws);
458 
459  for(size_t i = 0; i != 2; ++i)
460  curve_sqr_tmp(r, tmp, ws);
461 
462  curve_mul_tmp(r, x, tmp, ws);
463 
464  return r;
465  }
466 
467 #endif
468 
469 /**
470 * The NIST P-521 curve
471 */
472 class CurveGFp_P521 final : public CurveGFp_NIST
473  {
474  public:
475  CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {}
476  const BigInt& get_p() const override { return prime_p521(); }
477  private:
478  void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); }
479  BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
480  };
481 
482 BigInt CurveGFp_P521::invert_element(const BigInt& x, secure_vector<word>& ws) const
483  {
484  BigInt r;
485  BigInt rl;
486  BigInt a7;
487  BigInt tmp;
488 
489  curve_sqr(r, x, ws);
490  curve_mul_tmp(r, x, tmp, ws);
491 
492  curve_sqr_tmp(r, tmp, ws);
493  curve_mul_tmp(r, x, tmp, ws);
494 
495  rl = r;
496 
497  for(size_t i = 0; i != 3; ++i)
498  curve_sqr_tmp(r, tmp, ws);
499  curve_mul_tmp(r, rl, tmp, ws);
500 
501  curve_sqr_tmp(r, tmp, ws);
502  curve_mul_tmp(r, x, tmp, ws);
503  a7 = r; // need this value later
504 
505  curve_sqr_tmp(r, tmp, ws);
506  curve_mul_tmp(r, x, tmp, ws);
507 
508  rl = r;
509  for(size_t i = 0; i != 8; ++i)
510  curve_sqr_tmp(r, tmp, ws);
511  curve_mul_tmp(r, rl, tmp, ws);
512 
513  rl = r;
514  for(size_t i = 0; i != 16; ++i)
515  curve_sqr_tmp(r, tmp, ws);
516  curve_mul_tmp(r, rl, tmp, ws);
517 
518  rl = r;
519  for(size_t i = 0; i != 32; ++i)
520  curve_sqr_tmp(r, tmp, ws);
521  curve_mul_tmp(r, rl, tmp, ws);
522 
523  rl = r;
524  for(size_t i = 0; i != 64; ++i)
525  curve_sqr_tmp(r, tmp, ws);
526  curve_mul_tmp(r, rl, tmp, ws);
527 
528  rl = r;
529  for(size_t i = 0; i != 128; ++i)
530  curve_sqr_tmp(r, tmp, ws);
531  curve_mul_tmp(r, rl, tmp, ws);
532 
533  rl = r;
534  for(size_t i = 0; i != 256; ++i)
535  curve_sqr_tmp(r, tmp, ws);
536  curve_mul_tmp(r, rl, tmp, ws);
537 
538  for(size_t i = 0; i != 7; ++i)
539  curve_sqr_tmp(r, tmp, ws);
540  curve_mul_tmp(r, a7, tmp, ws);
541 
542  for(size_t i = 0; i != 2; ++i)
543  curve_sqr_tmp(r, tmp, ws);
544  curve_mul_tmp(r, x, tmp, ws);
545 
546  return r;
547  }
548 
549 }
550 
551 std::shared_ptr<CurveGFp_Repr>
552 CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b)
553  {
554 #if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
555  if(p == prime_p192())
556  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b));
557  if(p == prime_p224())
558  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b));
559  if(p == prime_p256())
560  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b));
561  if(p == prime_p384())
562  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b));
563 #endif
564 
565  if(p == prime_p521())
566  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b));
567 
568  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b));
569  }
570 
571 }
void redc_p256(BigInt &x, secure_vector< word > &ws)
const BigInt & prime_p192()
int(* final)(unsigned char *, CTX *)
const BigInt & prime_p256()
void redc_p384(BigInt &x, secure_vector< word > &ws)
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:357
const word * data() const
Definition: bigint.h:623
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
const BigInt & prime_p224()
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:290
Definition: alg_id.cpp:13
void redc_p521(BigInt &x, secure_vector< word > &ws)
Definition: nistp_redc.cpp:23
#define BOTAN_UNUSED(...)
Definition: assert.h:142
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:298
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:109
word monty_inverse(word a)
Definition: numthry.cpp:384
void redc_p224(BigInt &x, secure_vector< word > &ws)
const BigInt & prime_p521()
Definition: nistp_redc.cpp:15
void redc_p192(BigInt &x, secure_vector< word > &ws)
const BigInt & prime_p384()