Botan  2.1.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 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/internal/mp_core.h>
12 #include <botan/internal/mp_asmi.h>
13 
14 namespace Botan {
15 
16 namespace {
17 
18 class CurveGFp_Montgomery final : public CurveGFp_Repr
19  {
20  public:
21  CurveGFp_Montgomery(const BigInt& p, const BigInt& a, const BigInt& b) :
22  m_p(p), m_a(a), m_b(b),
23  m_p_words(m_p.sig_words()),
24  m_p_dash(monty_inverse(m_p.word_at(0)))
25  {
26  const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
27 
28  m_r2 = (r * r) % p;
29  m_a_r = (m_a * r) % p;
30  m_b_r = (m_b * r) % p;
31  }
32 
33  const BigInt& get_a() const override { return m_a; }
34 
35  const BigInt& get_b() const override { return m_b; }
36 
37  const BigInt& get_p() const override { return m_p; }
38 
39  const BigInt& get_a_rep() const override { return m_a_r; }
40 
41  const BigInt& get_b_rep() const override { return m_b_r; }
42 
43  size_t get_p_words() const override { return m_p_words; }
44 
45  void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
46 
47  void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
48 
49  void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
50  secure_vector<word>& ws) const override;
51 
52  void curve_sqr(BigInt& z, const BigInt& x,
53  secure_vector<word>& ws) const override;
54  private:
55  BigInt m_p, m_a, m_b;
56  size_t m_p_words; // cache of m_p.sig_words()
57 
58  // Montgomery parameters
59  BigInt m_r2, m_a_r, m_b_r;
60  word m_p_dash;
61  };
62 
63 void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const
64  {
65  const BigInt tx = x;
66  curve_mul(x, tx, m_r2, ws);
67  }
68 
69 void CurveGFp_Montgomery::from_curve_rep(BigInt& x, secure_vector<word>& ws) const
70  {
71  const BigInt tx = x;
72  curve_mul(x, tx, 1, ws);
73  }
74 
75 void CurveGFp_Montgomery::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
76  secure_vector<word>& ws) const
77  {
78  if(x.is_zero() || y.is_zero())
79  {
80  z = 0;
81  return;
82  }
83 
84  const size_t output_size = 2*m_p_words + 1;
85  ws.resize(2*(m_p_words+2));
86 
87  z.grow_to(output_size);
88  z.clear();
89 
90  bigint_monty_mul(z, x, y, m_p.data(), m_p_words, m_p_dash, ws.data());
91 
92  }
93 
94 void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x,
95  secure_vector<word>& ws) const
96  {
97  if(x.is_zero())
98  {
99  z = 0;
100  return;
101  }
102 
103  const size_t x_sw = x.sig_words();
104  BOTAN_ASSERT(x_sw <= m_p_words, "Input in range");
105 
106  const size_t output_size = 2*m_p_words + 1;
107 
108  ws.resize(2*(m_p_words+2));
109 
110  z.grow_to(output_size);
111  z.clear();
112 
114  ws.data());
115  }
116 
117 class CurveGFp_NIST : public CurveGFp_Repr
118  {
119  public:
120  CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) :
121  m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS)
122  {
123  }
124 
125  const BigInt& get_a() const override { return m_a; }
126 
127  const BigInt& get_b() const override { return m_b; }
128 
129  size_t get_p_words() const override { return m_p_words; }
130 
131  const BigInt& get_a_rep() const override { return m_a; }
132 
133  const BigInt& get_b_rep() const override { return m_b; }
134 
135  void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override
136  { redc(x, ws); }
137 
138  void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override
139  { redc(x, ws); }
140 
141  void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
142  secure_vector<word>& ws) const override;
143 
144  void curve_sqr(BigInt& z, const BigInt& x,
145  secure_vector<word>& ws) const override;
146  private:
147  virtual void redc(BigInt& x, secure_vector<word>& ws) const = 0;
148 
149  // Curve parameters
150  BigInt m_a, m_b;
151  size_t m_p_words; // cache of m_p.sig_words()
152  };
153 
154 void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
155  secure_vector<word>& ws) const
156  {
157  if(x.is_zero() || y.is_zero())
158  {
159  z = 0;
160  return;
161  }
162 
163  const size_t p_words = get_p_words();
164  const size_t output_size = 2*p_words + 1;
165  ws.resize(2*(p_words+2));
166 
167  z.grow_to(output_size);
168  z.clear();
169 
170  bigint_mul(z, x, y, ws.data());
171 
172  this->redc(z, ws);
173  }
174 
175 void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x,
176  secure_vector<word>& ws) const
177  {
178  if(x.is_zero())
179  {
180  z = 0;
181  return;
182  }
183 
184  const size_t p_words = get_p_words();
185  const size_t output_size = 2*p_words + 1;
186 
187  ws.resize(2*(p_words+2));
188 
189  z.grow_to(output_size);
190  z.clear();
191 
192  bigint_sqr(z.mutable_data(), output_size, ws.data(),
193  x.data(), x.size(), x.sig_words());
194 
195  this->redc(z, ws);
196  }
197 
198 #if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
199 
200 /**
201 * The NIST P-192 curve
202 */
203 class CurveGFp_P192 final : public CurveGFp_NIST
204  {
205  public:
206  CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {}
207  const BigInt& get_p() const override { return prime_p192(); }
208  private:
209  void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p192(x, ws); }
210  };
211 
212 /**
213 * The NIST P-224 curve
214 */
215 class CurveGFp_P224 final : public CurveGFp_NIST
216  {
217  public:
218  CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {}
219  const BigInt& get_p() const override { return prime_p224(); }
220  private:
221  void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p224(x, ws); }
222  };
223 
224 /**
225 * The NIST P-256 curve
226 */
227 class CurveGFp_P256 final : public CurveGFp_NIST
228  {
229  public:
230  CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {}
231  const BigInt& get_p() const override { return prime_p256(); }
232  private:
233  void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); }
234  };
235 
236 /**
237 * The NIST P-384 curve
238 */
239 class CurveGFp_P384 final : public CurveGFp_NIST
240  {
241  public:
242  CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {}
243  const BigInt& get_p() const override { return prime_p384(); }
244  private:
245  void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); }
246  };
247 
248 #endif
249 
250 /**
251 * The NIST P-521 curve
252 */
253 class CurveGFp_P521 final : public CurveGFp_NIST
254  {
255  public:
256  CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {}
257  const BigInt& get_p() const override { return prime_p521(); }
258  private:
259  void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); }
260  };
261 
262 }
263 
264 std::shared_ptr<CurveGFp_Repr>
265 CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b)
266  {
267 #if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
268  if(p == prime_p192())
269  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b));
270  if(p == prime_p224())
271  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b));
272  if(p == prime_p256())
273  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b));
274  if(p == prime_p384())
275  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b));
276 #endif
277 
278  if(p == prime_p521())
279  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b));
280 
281  return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b));
282  }
283 
284 }
BigInt m_a
Definition: curve_gfp.cpp:55
BigInt m_a_r
Definition: curve_gfp.cpp:59
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:27
BigInt m_b
Definition: curve_gfp.cpp:55
void bigint_monty_sqr(BigInt &z, const BigInt &x, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:109
BigInt m_b_r
Definition: curve_gfp.cpp:59
void bigint_sqr(word z[], size_t z_size, word workspace[], const word x[], size_t x_size, size_t x_sw)
Definition: mp_karat.cpp:312
void bigint_monty_mul(BigInt &z, const BigInt &x, const BigInt &y, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:97
void redc_p521(BigInt &x, secure_vector< word > &ws)
Definition: curve_nistp.cpp:59
const word * data() const
Definition: bigint.h:425
static BigInt power_of_2(size_t n)
Definition: bigint.h:492
Definition: alg_id.cpp:13
const BigInt & prime_p521()
Definition: curve_nistp.cpp:51
BigInt m_r2
Definition: curve_gfp.cpp:59
word monty_inverse(word input)
Definition: numthry.cpp:325
void bigint_mul(BigInt &z, const BigInt &x, const BigInt &y, word workspace[])
Definition: mp_karat.cpp:252
BigInt m_p
Definition: curve_gfp.cpp:55
size_t m_p_words
Definition: curve_gfp.cpp:56
word m_p_dash
Definition: curve_gfp.cpp:60