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