Botan  2.11.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 /**
283 * The NIST P-192 curve
284 */
285 class CurveGFp_P192 final : public CurveGFp_NIST
286  {
287  public:
288  CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {}
289  const BigInt& get_p() const override { return prime_p192(); }
290  private:
291  void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p192(x, ws); }
292  };
293 
294 /**
295 * The NIST P-224 curve
296 */
297 class CurveGFp_P224 final : public CurveGFp_NIST
298  {
299  public:
300  CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {}
301  const BigInt& get_p() const override { return prime_p224(); }
302  private:
303  void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p224(x, ws); }
304  };
305 
306 /**
307 * The NIST P-256 curve
308 */
309 class CurveGFp_P256 final : public CurveGFp_NIST
310  {
311  public:
312  CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {}
313  const BigInt& get_p() const override { return prime_p256(); }
314  private:
315  void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); }
316  BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
317  };
318 
319 BigInt CurveGFp_P256::invert_element(const BigInt& x, secure_vector<word>& ws) const
320  {
321  BigInt r, p2, p4, p8, p16, p32, tmp;
322 
323  curve_sqr(r, x, ws);
324 
325  curve_mul(p2, r, x, ws);
326  curve_sqr(r, p2, ws);
327  curve_sqr_tmp(r, tmp, ws);
328 
329  curve_mul(p4, r, p2, ws);
330 
331  curve_sqr(r, p4, ws);
332  for(size_t i = 0; i != 3; ++i)
333  curve_sqr_tmp(r, tmp, ws);
334  curve_mul(p8, r, p4, ws);
335 
336  curve_sqr(r, p8, ws);
337  for(size_t i = 0; i != 7; ++i)
338  curve_sqr_tmp(r, tmp, ws);
339  curve_mul(p16, r, p8, ws);
340 
341  curve_sqr(r, p16, ws);
342  for(size_t i = 0; i != 15; ++i)
343  curve_sqr_tmp(r, tmp, ws);
344  curve_mul(p32, r, p16, ws);
345 
346  curve_sqr(r, p32, ws);
347  for(size_t i = 0; i != 31; ++i)
348  curve_sqr_tmp(r, tmp, ws);
349  curve_mul_tmp(r, x, tmp, ws);
350 
351  for(size_t i = 0; i != 32*4; ++i)
352  curve_sqr_tmp(r, tmp, ws);
353  curve_mul_tmp(r, p32, tmp, ws);
354 
355  for(size_t i = 0; i != 32; ++i)
356  curve_sqr_tmp(r, tmp, ws);
357  curve_mul_tmp(r, p32, tmp, ws);
358 
359  for(size_t i = 0; i != 16; ++i)
360  curve_sqr_tmp(r, tmp, ws);
361  curve_mul_tmp(r, p16, tmp, ws);
362  for(size_t i = 0; i != 8; ++i)
363  curve_sqr_tmp(r, tmp, ws);
364  curve_mul_tmp(r, p8, tmp, ws);
365 
366  for(size_t i = 0; i != 4; ++i)
367  curve_sqr_tmp(r, tmp, ws);
368  curve_mul_tmp(r, p4, tmp, ws);
369 
370  for(size_t i = 0; i != 2; ++i)
371  curve_sqr_tmp(r, tmp, ws);
372  curve_mul_tmp(r, p2, tmp, ws);
373 
374  for(size_t i = 0; i != 2; ++i)
375  curve_sqr_tmp(r, tmp, ws);
376  curve_mul_tmp(r, x, tmp, ws);
377 
378  return r;
379  }
380 
381 /**
382 * The NIST P-384 curve
383 */
384 class CurveGFp_P384 final : public CurveGFp_NIST
385  {
386  public:
387  CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {}
388  const BigInt& get_p() const override { return prime_p384(); }
389  private:
390  void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); }
391  BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
392  };
393 
394 BigInt CurveGFp_P384::invert_element(const BigInt& x, secure_vector<word>& ws) const
395  {
396  // From https://briansmith.org/ecc-inversion-addition-chains-01
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 /**
468 * The NIST P-521 curve
469 */
470 class CurveGFp_P521 final : public CurveGFp_NIST
471  {
472  public:
473  CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {}
474  const BigInt& get_p() const override { return prime_p521(); }
475  private:
476  void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); }
477  BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
478  };
479 
480 BigInt CurveGFp_P521::invert_element(const BigInt& x, secure_vector<word>& ws) const
481  {
482  // Addition chain from https://eprint.iacr.org/2014/852.pdf section
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(p == prime_p192())
555  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b));
556  if(p == prime_p224())
557  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b));
558  if(p == prime_p256())
559  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b));
560  if(p == prime_p384())
561  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b));
562  if(p == prime_p521())
563  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b));
564 
565  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b));
566  }
567 
568 }
void redc_p256(BigInt &x, secure_vector< word > &ws)
Definition: nistp_redc.cpp:310
const BigInt & prime_p256()
Definition: nistp_redc.cpp:304
int(* final)(unsigned char *, CTX *)
void redc_p384(BigInt &x, secure_vector< word > &ws)
Definition: nistp_redc.cpp:439
const BigInt & prime_p224()
Definition: nistp_redc.cpp:201
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
const BigInt & prime_p192()
Definition: nistp_redc.cpp:105
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
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)
Definition: nistp_redc.cpp:207
const BigInt & prime_p521()
Definition: nistp_redc.cpp:15
const BigInt & prime_p384()
Definition: nistp_redc.cpp:433
void redc_p192(BigInt &x, secure_vector< word > &ws)
Definition: nistp_redc.cpp:111