Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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
113 bigint_monty_sqr(z, x, m_p.data(), m_p_words, m_p_dash,
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 }
m_a
BigInt m_a
Definition: curve_gfp.cpp:55
m_a_r
BigInt m_a_r
Definition: curve_gfp.cpp:59
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:27
m_b
BigInt m_b
Definition: curve_gfp.cpp:55
Botan::bigint_monty_sqr
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
m_b_r
BigInt m_b_r
Definition: curve_gfp.cpp:59
Botan::bigint_sqr
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
Botan::bigint_monty_mul
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
Botan::redc_p521
void redc_p521(BigInt &x, secure_vector< word > &ws)
Definition: curve_nistp.cpp:59
Botan::BigInt::data
const word * data() const
Definition: bigint.h:425
Botan::BigInt::power_of_2
static BigInt power_of_2(size_t n)
Definition: bigint.h:492
Botan
Definition: alg_id.cpp:13
Botan::prime_p521
const BigInt & prime_p521()
Definition: curve_nistp.cpp:51
m_r2
BigInt m_r2
Definition: curve_gfp.cpp:59
Botan::monty_inverse
word monty_inverse(word input)
Definition: numthry.cpp:325
Botan::bigint_mul
void bigint_mul(BigInt &z, const BigInt &x, const BigInt &y, word workspace[])
Definition: mp_karat.cpp:252
m_p
BigInt m_p
Definition: curve_gfp.cpp:55
m_p_words
size_t m_p_words
Definition: curve_gfp.cpp:56
m_p_dash
word m_p_dash
Definition: curve_gfp.cpp:60