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