/src/botan/src/lib/pubkey/ec_group/ec_group.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * ECC Domain Parameters |
3 | | * |
4 | | * (C) 2007 Falko Strenzke, FlexSecure GmbH |
5 | | * (C) 2008,2018 Jack Lloyd |
6 | | * (C) 2018 Tobias Niemann |
7 | | * |
8 | | * Botan is released under the Simplified BSD License (see license.txt) |
9 | | */ |
10 | | |
11 | | #include <botan/ec_group.h> |
12 | | #include <botan/internal/point_mul.h> |
13 | | #include <botan/internal/primality.h> |
14 | | #include <botan/ber_dec.h> |
15 | | #include <botan/der_enc.h> |
16 | | #include <botan/pem.h> |
17 | | #include <botan/reducer.h> |
18 | | #include <botan/mutex.h> |
19 | | #include <botan/rng.h> |
20 | | #include <vector> |
21 | | |
22 | | #if defined(BOTAN_HAS_EC_HASH_TO_CURVE) |
23 | | #include <botan/internal/ec_h2c.h> |
24 | | #endif |
25 | | |
26 | | namespace Botan { |
27 | | |
28 | | class EC_Group_Data final |
29 | | { |
30 | | public: |
31 | | |
32 | | EC_Group_Data(const BigInt& p, |
33 | | const BigInt& a, |
34 | | const BigInt& b, |
35 | | const BigInt& g_x, |
36 | | const BigInt& g_y, |
37 | | const BigInt& order, |
38 | | const BigInt& cofactor, |
39 | | const OID& oid, |
40 | | EC_Group_Source source) : |
41 | | m_curve(p, a, b), |
42 | | m_base_point(m_curve, g_x, g_y), |
43 | | m_g_x(g_x), |
44 | | m_g_y(g_y), |
45 | | m_order(order), |
46 | | m_cofactor(cofactor), |
47 | | m_mod_order(order), |
48 | | m_base_mult(m_base_point, m_mod_order), |
49 | | m_oid(oid), |
50 | | m_p_bits(p.bits()), |
51 | | m_order_bits(order.bits()), |
52 | | m_a_is_minus_3(a == p - 3), |
53 | | m_a_is_zero(a.is_zero()), |
54 | | m_source(source) |
55 | 2.94k | { |
56 | 2.94k | } |
57 | | |
58 | | bool params_match(const BigInt& p, const BigInt& a, const BigInt& b, |
59 | | const BigInt& g_x, const BigInt& g_y, |
60 | | const BigInt& order, const BigInt& cofactor) const |
61 | 120k | { |
62 | 120k | return (this->p() == p && |
63 | 120k | this->a() == a && |
64 | 120k | this->b() == b && |
65 | 120k | this->order() == order && |
66 | 120k | this->cofactor() == cofactor && |
67 | 120k | this->g_x() == g_x && |
68 | 120k | this->g_y() == g_y); |
69 | 120k | } |
70 | | |
71 | | bool params_match(const EC_Group_Data& other) const |
72 | 24.8k | { |
73 | 24.8k | return params_match(other.p(), other.a(), other.b(), |
74 | 24.8k | other.g_x(), other.g_y(), |
75 | 24.8k | other.order(), other.cofactor()); |
76 | 24.8k | } |
77 | | |
78 | | void set_oid(const OID& oid) |
79 | 0 | { |
80 | 0 | BOTAN_STATE_CHECK(m_oid.empty()); |
81 | 0 | m_oid = oid; |
82 | 0 | } |
83 | | |
84 | 169k | const OID& oid() const { return m_oid; } |
85 | 150k | const BigInt& p() const { return m_curve.get_p(); } |
86 | 31.8k | const BigInt& a() const { return m_curve.get_a(); } |
87 | 30.9k | const BigInt& b() const { return m_curve.get_b(); } |
88 | 72.6k | const BigInt& order() const { return m_order; } |
89 | 52.3k | const BigInt& cofactor() const { return m_cofactor; } |
90 | 24.9k | const BigInt& g_x() const { return m_g_x; } |
91 | 24.8k | const BigInt& g_y() const { return m_g_y; } |
92 | | |
93 | 140 | size_t p_bits() const { return m_p_bits; } |
94 | 7.56k | size_t p_bytes() const { return (m_p_bits + 7) / 8; } |
95 | | |
96 | 643 | size_t order_bits() const { return m_order_bits; } |
97 | 353 | size_t order_bytes() const { return (m_order_bits + 7) / 8; } |
98 | | |
99 | 35.6k | const CurveGFp& curve() const { return m_curve; } |
100 | 1.16k | const EC_Point& base_point() const { return m_base_point; } |
101 | | |
102 | 0 | bool a_is_minus_3() const { return m_a_is_minus_3; } |
103 | 0 | bool a_is_zero() const { return m_a_is_zero; } |
104 | | |
105 | 619 | BigInt mod_order(const BigInt& x) const { return m_mod_order.reduce(x); } |
106 | | |
107 | | BigInt square_mod_order(const BigInt& x) const |
108 | 0 | { |
109 | 0 | return m_mod_order.square(x); |
110 | 0 | } |
111 | | |
112 | | BigInt multiply_mod_order(const BigInt& x, const BigInt& y) const |
113 | 672 | { |
114 | 672 | return m_mod_order.multiply(x, y); |
115 | 672 | } |
116 | | |
117 | | BigInt multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const |
118 | 0 | { |
119 | 0 | return m_mod_order.multiply(m_mod_order.multiply(x, y), z); |
120 | 0 | } |
121 | | |
122 | | BigInt inverse_mod_order(const BigInt& x) const |
123 | 14.0k | { |
124 | 14.0k | return inverse_mod(x, m_order); |
125 | 14.0k | } |
126 | | |
127 | | EC_Point blinded_base_point_multiply(const BigInt& k, |
128 | | RandomNumberGenerator& rng, |
129 | | std::vector<BigInt>& ws) const |
130 | 34.3k | { |
131 | 34.3k | return m_base_mult.mul(k, rng, m_order, ws); |
132 | 34.3k | } |
133 | | |
134 | 0 | EC_Group_Source source() const { return m_source; } |
135 | | |
136 | | private: |
137 | | CurveGFp m_curve; |
138 | | EC_Point m_base_point; |
139 | | |
140 | | BigInt m_g_x; |
141 | | BigInt m_g_y; |
142 | | BigInt m_order; |
143 | | BigInt m_cofactor; |
144 | | Modular_Reducer m_mod_order; |
145 | | EC_Point_Base_Point_Precompute m_base_mult; |
146 | | OID m_oid; |
147 | | size_t m_p_bits; |
148 | | size_t m_order_bits; |
149 | | bool m_a_is_minus_3; |
150 | | bool m_a_is_zero; |
151 | | EC_Group_Source m_source; |
152 | | }; |
153 | | |
154 | | class EC_Group_Data_Map final |
155 | | { |
156 | | public: |
157 | 8 | EC_Group_Data_Map() {} |
158 | | |
159 | | size_t clear() |
160 | 5.12k | { |
161 | 5.12k | lock_guard_type<mutex_type> lock(m_mutex); |
162 | 5.12k | size_t count = m_registered_curves.size(); |
163 | 5.12k | m_registered_curves.clear(); |
164 | 5.12k | return count; |
165 | 5.12k | } |
166 | | |
167 | | std::shared_ptr<EC_Group_Data> lookup(const OID& oid) |
168 | 21.5k | { |
169 | 21.5k | lock_guard_type<mutex_type> lock(m_mutex); |
170 | | |
171 | 21.5k | for(auto i : m_registered_curves) |
172 | 114k | { |
173 | 114k | if(i->oid() == oid) |
174 | 19.4k | return i; |
175 | 114k | } |
176 | | |
177 | | // Not found, check hardcoded data |
178 | 2.16k | std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid); |
179 | | |
180 | 2.16k | if(data) |
181 | 2.07k | { |
182 | 2.07k | for(auto curve : m_registered_curves) |
183 | 34.1k | { |
184 | 34.1k | if(curve->oid().empty() == true && curve->params_match(*data)) |
185 | 0 | { |
186 | 0 | curve->set_oid(oid); |
187 | 0 | return curve; |
188 | 0 | } |
189 | 34.1k | } |
190 | | |
191 | 2.07k | m_registered_curves.push_back(data); |
192 | 2.07k | return data; |
193 | 2.07k | } |
194 | | |
195 | | // Nope, unknown curve |
196 | 93 | return std::shared_ptr<EC_Group_Data>(); |
197 | 2.16k | } |
198 | | |
199 | | std::shared_ptr<EC_Group_Data> lookup_or_create(const BigInt& p, |
200 | | const BigInt& a, |
201 | | const BigInt& b, |
202 | | const BigInt& g_x, |
203 | | const BigInt& g_y, |
204 | | const BigInt& order, |
205 | | const BigInt& cofactor, |
206 | | const OID& oid, |
207 | | EC_Group_Source source) |
208 | 882 | { |
209 | 882 | lock_guard_type<mutex_type> lock(m_mutex); |
210 | | |
211 | 882 | for(auto i : m_registered_curves) |
212 | 95.1k | { |
213 | | /* |
214 | | * The params may be the same but you are trying to register under a |
215 | | * different OID than the one we are using, so using a different |
216 | | * group, since EC_Group's model assumes a single OID per group. |
217 | | */ |
218 | 95.1k | if(!oid.empty() && !i->oid().empty() && i->oid() != oid) |
219 | 0 | { |
220 | 0 | continue; |
221 | 0 | } |
222 | | |
223 | 95.1k | const bool same_oid = !oid.empty() && i->oid() == oid; |
224 | 95.1k | const bool same_params = i->params_match(p, a, b, g_x, g_y, order, cofactor); |
225 | | |
226 | | /* |
227 | | * If the params and OID are the same then we are done, just return |
228 | | * the already registered curve obj. |
229 | | */ |
230 | 95.1k | if(same_params && same_oid) |
231 | 0 | { |
232 | 0 | return i; |
233 | 0 | } |
234 | | |
235 | | /* |
236 | | * If same params and the new OID is empty, then that's ok too |
237 | | */ |
238 | 95.1k | if(same_params && oid.empty()) |
239 | 4 | { |
240 | 4 | return i; |
241 | 4 | } |
242 | | |
243 | | /* |
244 | | * Check for someone trying to reuse an already in-use OID |
245 | | */ |
246 | 95.1k | if(same_oid && !same_params) |
247 | 0 | { |
248 | 0 | throw Invalid_Argument("Attempting to register a curve using OID " + oid.to_string() + |
249 | 0 | " but a distinct curve is already registered using that OID"); |
250 | 0 | } |
251 | | |
252 | | /* |
253 | | * If the same curve was previously created without an OID but is now |
254 | | * being registered again using an OID, save that OID. |
255 | | */ |
256 | 95.1k | if(same_params && i->oid().empty() && !oid.empty()) |
257 | 0 | { |
258 | 0 | i->set_oid(oid); |
259 | 0 | return i; |
260 | 0 | } |
261 | 95.1k | } |
262 | | |
263 | | /* |
264 | | Not found in current list, so we need to create a new entry |
265 | | |
266 | | If an OID is set, try to look up relative our static tables to detect a duplicate |
267 | | registration under an OID |
268 | | */ |
269 | | |
270 | 878 | std::shared_ptr<EC_Group_Data> new_group = |
271 | 878 | std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid, source); |
272 | | |
273 | 878 | if(oid.has_value()) |
274 | 0 | { |
275 | 0 | std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid); |
276 | 0 | if(data != nullptr && !new_group->params_match(*data)) |
277 | 0 | throw Invalid_Argument("Attempting to register an EC group under OID of hardcoded group"); |
278 | 0 | } |
279 | 878 | else |
280 | 878 | { |
281 | | // Here try to use the order as a hint to look up the group id, to identify common groups |
282 | 878 | const OID oid_from_store = EC_Group::EC_group_identity_from_order(order); |
283 | 878 | if(oid_from_store.has_value()) |
284 | 0 | { |
285 | 0 | std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid_from_store); |
286 | | |
287 | | /* |
288 | | If EC_group_identity_from_order returned an OID then looking up that OID |
289 | | must always return a result. |
290 | | */ |
291 | 0 | BOTAN_ASSERT_NOMSG(data != nullptr); |
292 | | |
293 | | /* |
294 | | It is possible (if unlikely) that someone is registering another group |
295 | | that happens to have an order equal to that of a well known group - |
296 | | so verify all values before assigning the OID. |
297 | | */ |
298 | 0 | if(new_group->params_match(*data)) |
299 | 0 | { |
300 | 0 | new_group->set_oid(oid_from_store); |
301 | 0 | } |
302 | 0 | } |
303 | 878 | } |
304 | | |
305 | 878 | m_registered_curves.push_back(new_group); |
306 | 878 | return new_group; |
307 | 878 | } |
308 | | |
309 | | private: |
310 | | mutex_type m_mutex; |
311 | | std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves; |
312 | | }; |
313 | | |
314 | | //static |
315 | | EC_Group_Data_Map& EC_Group::ec_group_data() |
316 | 27.5k | { |
317 | | /* |
318 | | * This exists purely to ensure the allocator is constructed before g_ec_data, |
319 | | * which ensures that its destructor runs after ~g_ec_data is complete. |
320 | | */ |
321 | | |
322 | 27.5k | static Allocator_Initializer g_init_allocator; |
323 | 27.5k | static EC_Group_Data_Map g_ec_data; |
324 | 27.5k | return g_ec_data; |
325 | 27.5k | } |
326 | | |
327 | | //static |
328 | | size_t EC_Group::clear_registered_curve_data() |
329 | 5.12k | { |
330 | 5.12k | return ec_group_data().clear(); |
331 | 5.12k | } |
332 | | |
333 | | //static |
334 | | std::shared_ptr<EC_Group_Data> |
335 | | EC_Group::load_EC_group_info(const char* p_str, |
336 | | const char* a_str, |
337 | | const char* b_str, |
338 | | const char* g_x_str, |
339 | | const char* g_y_str, |
340 | | const char* order_str, |
341 | | const OID& oid) |
342 | 2.07k | { |
343 | 2.07k | const BigInt p(p_str); |
344 | 2.07k | const BigInt a(a_str); |
345 | 2.07k | const BigInt b(b_str); |
346 | 2.07k | const BigInt g_x(g_x_str); |
347 | 2.07k | const BigInt g_y(g_y_str); |
348 | 2.07k | const BigInt order(order_str); |
349 | 2.07k | const BigInt cofactor(1); // implicit |
350 | | |
351 | 2.07k | return std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid, EC_Group_Source::Builtin); |
352 | 2.07k | } |
353 | | |
354 | | //static |
355 | | std::shared_ptr<EC_Group_Data> EC_Group::BER_decode_EC_group(const uint8_t bits[], size_t len, |
356 | | EC_Group_Source source) |
357 | 5.04k | { |
358 | 5.04k | BER_Decoder ber(bits, len); |
359 | 5.04k | BER_Object obj = ber.get_next_object(); |
360 | | |
361 | 5.04k | if(obj.type() == ASN1_Type::Null) [[unlikely]] |
362 | 2 | { |
363 | 2 | throw Decoding_Error("Cannot handle ImplicitCA ECC parameters"); |
364 | 2 | } |
365 | 5.04k | else if(obj.type() == ASN1_Type::ObjectId) |
366 | 3.52k | { |
367 | 3.52k | OID dom_par_oid; |
368 | 3.52k | BER_Decoder(bits, len).decode(dom_par_oid); |
369 | 3.52k | return ec_group_data().lookup(dom_par_oid); |
370 | 3.52k | } |
371 | 1.51k | else if(obj.type() == ASN1_Type::Sequence) |
372 | 1.42k | { |
373 | 1.42k | BigInt p, a, b, order, cofactor; |
374 | 1.42k | std::vector<uint8_t> base_pt; |
375 | 1.42k | std::vector<uint8_t> seed; |
376 | | |
377 | 1.42k | BER_Decoder(bits, len) |
378 | 1.42k | .start_sequence() |
379 | 1.42k | .decode_and_check<size_t>(1, "Unknown ECC param version code") |
380 | 1.42k | .start_sequence() |
381 | 1.42k | .decode_and_check(OID("1.2.840.10045.1.1"), |
382 | 1.42k | "Only prime ECC fields supported") |
383 | 1.42k | .decode(p) |
384 | 1.42k | .end_cons() |
385 | 1.42k | .start_sequence() |
386 | 1.42k | .decode_octet_string_bigint(a) |
387 | 1.42k | .decode_octet_string_bigint(b) |
388 | 1.42k | .decode_optional_string(seed, ASN1_Type::BitString, ASN1_Type::BitString) |
389 | 1.42k | .end_cons() |
390 | 1.42k | .decode(base_pt, ASN1_Type::OctetString) |
391 | 1.42k | .decode(order) |
392 | 1.42k | .decode(cofactor) |
393 | 1.42k | .end_cons() |
394 | 1.42k | .verify_end(); |
395 | | |
396 | 1.42k | if(p.bits() < 64 || p.is_negative() || !is_bailie_psw_probable_prime(p)) |
397 | 34 | throw Decoding_Error("Invalid ECC p parameter"); |
398 | | |
399 | 1.39k | if(a.is_negative() || a >= p) |
400 | 5 | throw Decoding_Error("Invalid ECC a parameter"); |
401 | | |
402 | 1.38k | if(b <= 0 || b >= p) |
403 | 21 | throw Decoding_Error("Invalid ECC b parameter"); |
404 | | |
405 | 1.36k | if(order <= 0 || !is_bailie_psw_probable_prime(order)) |
406 | 207 | throw Decoding_Error("Invalid ECC order parameter"); |
407 | | |
408 | 1.15k | if(cofactor <= 0 || cofactor >= 16) |
409 | 72 | throw Decoding_Error("Invalid ECC cofactor parameter"); |
410 | | |
411 | 1.08k | std::pair<BigInt, BigInt> base_xy = Botan::OS2ECP(base_pt.data(), base_pt.size(), p, a, b); |
412 | | |
413 | 1.08k | return ec_group_data().lookup_or_create(p, a, b, base_xy.first, base_xy.second, |
414 | 1.08k | order, cofactor, OID(), source); |
415 | 1.15k | } |
416 | 91 | else |
417 | 91 | { |
418 | 91 | throw Decoding_Error("Unexpected tag while decoding ECC domain params"); |
419 | 91 | } |
420 | 5.04k | } |
421 | | |
422 | | EC_Group::EC_Group() |
423 | 20.8k | { |
424 | 20.8k | } |
425 | | |
426 | | EC_Group::~EC_Group() |
427 | 57.5k | { |
428 | | // shared_ptr possibly freed here |
429 | 57.5k | } |
430 | | |
431 | | EC_Group::EC_Group(const OID& domain_oid) |
432 | 78 | { |
433 | 78 | this->m_data = ec_group_data().lookup(domain_oid); |
434 | 78 | if(!this->m_data) |
435 | 2 | throw Invalid_Argument("Unknown EC_Group " + domain_oid.to_string()); |
436 | 78 | } |
437 | | |
438 | | EC_Group::EC_Group(const std::string& str) |
439 | 17.9k | { |
440 | 17.9k | if(str.empty()) |
441 | 0 | return; // no initialization / uninitialized |
442 | | |
443 | 17.9k | try |
444 | 17.9k | { |
445 | 17.9k | const OID oid = OID::from_string(str); |
446 | 17.9k | if(oid.has_value()) |
447 | 17.9k | m_data = ec_group_data().lookup(oid); |
448 | 17.9k | } |
449 | 17.9k | catch(...) |
450 | 17.9k | { |
451 | 0 | } |
452 | | |
453 | 17.9k | if(m_data == nullptr) |
454 | 0 | { |
455 | 0 | if(str.size() > 30 && str.substr(0, 29) == "-----BEGIN EC PARAMETERS-----") |
456 | 0 | { |
457 | | // OK try it as PEM ... |
458 | 0 | secure_vector<uint8_t> ber = PEM_Code::decode_check_label(str, "EC PARAMETERS"); |
459 | 0 | this->m_data = BER_decode_EC_group(ber.data(), ber.size(), EC_Group_Source::ExternalSource); |
460 | 0 | } |
461 | 0 | } |
462 | | |
463 | 17.9k | if(m_data == nullptr) |
464 | 0 | throw Invalid_Argument("Unknown ECC group '" + str + "'"); |
465 | 17.9k | } |
466 | | |
467 | | //static |
468 | | EC_Group EC_Group::EC_Group_from_PEM(const std::string& pem) |
469 | 0 | { |
470 | 0 | const auto ber = PEM_Code::decode_check_label(pem, "EC PARAMETERS"); |
471 | 0 | return EC_Group(ber.data(), ber.size()); |
472 | 0 | } |
473 | | |
474 | | EC_Group::EC_Group(const BigInt& p, |
475 | | const BigInt& a, |
476 | | const BigInt& b, |
477 | | const BigInt& base_x, |
478 | | const BigInt& base_y, |
479 | | const BigInt& order, |
480 | | const BigInt& cofactor, |
481 | | const OID& oid) |
482 | 0 | { |
483 | 0 | m_data = ec_group_data().lookup_or_create(p, a, b, base_x, base_y, order, cofactor, oid, |
484 | 0 | EC_Group_Source::ExternalSource); |
485 | 0 | } |
486 | | |
487 | | EC_Group::EC_Group(const uint8_t ber[], size_t ber_len) |
488 | 5.04k | { |
489 | 5.04k | m_data = BER_decode_EC_group(ber, ber_len, EC_Group_Source::ExternalSource); |
490 | 5.04k | } |
491 | | |
492 | | const EC_Group_Data& EC_Group::data() const |
493 | 207k | { |
494 | 207k | if(m_data == nullptr) |
495 | 91 | throw Invalid_State("EC_Group uninitialized"); |
496 | 207k | return *m_data; |
497 | 207k | } |
498 | | |
499 | | bool EC_Group::a_is_minus_3() const |
500 | 0 | { |
501 | 0 | return data().a_is_minus_3(); |
502 | 0 | } |
503 | | |
504 | | bool EC_Group::a_is_zero() const |
505 | 0 | { |
506 | 0 | return data().a_is_zero(); |
507 | 0 | } |
508 | | |
509 | | size_t EC_Group::get_p_bits() const |
510 | 140 | { |
511 | 140 | return data().p_bits(); |
512 | 140 | } |
513 | | |
514 | | size_t EC_Group::get_p_bytes() const |
515 | 7.56k | { |
516 | 7.56k | return data().p_bytes(); |
517 | 7.56k | } |
518 | | |
519 | | size_t EC_Group::get_order_bits() const |
520 | 643 | { |
521 | 643 | return data().order_bits(); |
522 | 643 | } |
523 | | |
524 | | size_t EC_Group::get_order_bytes() const |
525 | 353 | { |
526 | 353 | return data().order_bytes(); |
527 | 353 | } |
528 | | |
529 | | const BigInt& EC_Group::get_p() const |
530 | 5.47k | { |
531 | 5.47k | return data().p(); |
532 | 5.47k | } |
533 | | |
534 | | const BigInt& EC_Group::get_a() const |
535 | 5.47k | { |
536 | 5.47k | return data().a(); |
537 | 5.47k | } |
538 | | |
539 | | const BigInt& EC_Group::get_b() const |
540 | 5.47k | { |
541 | 5.47k | return data().b(); |
542 | 5.47k | } |
543 | | |
544 | | const EC_Point& EC_Group::get_base_point() const |
545 | 1.16k | { |
546 | 1.16k | return data().base_point(); |
547 | 1.16k | } |
548 | | |
549 | | const BigInt& EC_Group::get_order() const |
550 | 47.4k | { |
551 | 47.4k | return data().order(); |
552 | 47.4k | } |
553 | | |
554 | | const BigInt& EC_Group::get_g_x() const |
555 | 0 | { |
556 | 0 | return data().g_x(); |
557 | 0 | } |
558 | | |
559 | | const BigInt& EC_Group::get_g_y() const |
560 | 0 | { |
561 | 0 | return data().g_y(); |
562 | 0 | } |
563 | | |
564 | | const BigInt& EC_Group::get_cofactor() const |
565 | 27.4k | { |
566 | 27.4k | return data().cofactor(); |
567 | 27.4k | } |
568 | | |
569 | | BigInt EC_Group::mod_order(const BigInt& k) const |
570 | 619 | { |
571 | 619 | return data().mod_order(k); |
572 | 619 | } |
573 | | |
574 | | BigInt EC_Group::square_mod_order(const BigInt& x) const |
575 | 0 | { |
576 | 0 | return data().square_mod_order(x); |
577 | 0 | } |
578 | | |
579 | | BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y) const |
580 | 672 | { |
581 | 672 | return data().multiply_mod_order(x, y); |
582 | 672 | } |
583 | | |
584 | | BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const |
585 | 0 | { |
586 | 0 | return data().multiply_mod_order(x, y, z); |
587 | 0 | } |
588 | | |
589 | | BigInt EC_Group::inverse_mod_order(const BigInt& x) const |
590 | 14.0k | { |
591 | 14.0k | return data().inverse_mod_order(x); |
592 | 14.0k | } |
593 | | |
594 | | const OID& EC_Group::get_curve_oid() const |
595 | 21.1k | { |
596 | 21.1k | return data().oid(); |
597 | 21.1k | } |
598 | | |
599 | | EC_Group_Source EC_Group::source() const |
600 | 0 | { |
601 | 0 | return data().source(); |
602 | 0 | } |
603 | | |
604 | | size_t EC_Group::point_size(EC_Point::Compression_Type format) const |
605 | 0 | { |
606 | | // Hybrid and standard format are (x,y), compressed is y, +1 format byte |
607 | 0 | if(format == EC_Point::COMPRESSED) |
608 | 0 | return (1 + get_p_bytes()); |
609 | 0 | else |
610 | 0 | return (1 + 2*get_p_bytes()); |
611 | 0 | } |
612 | | |
613 | | EC_Point EC_Group::OS2ECP(const uint8_t bits[], size_t len) const |
614 | 29.0k | { |
615 | 29.0k | return Botan::OS2ECP(bits, len, data().curve()); |
616 | 29.0k | } |
617 | | |
618 | | EC_Point EC_Group::point(const BigInt& x, const BigInt& y) const |
619 | 6.65k | { |
620 | | #if 0 |
621 | | BigInt l = (x*x*x + x*get_a() + get_b()) % get_p(); |
622 | | BigInt r = (y*y) % get_p(); |
623 | | |
624 | | if(l != r) |
625 | | { |
626 | | printf("invalid point in EC_Group::point\n"); |
627 | | } |
628 | | #endif |
629 | | // TODO: randomize the representation? |
630 | 6.65k | return EC_Point(data().curve(), x, y); |
631 | 6.65k | } |
632 | | |
633 | | EC_Point EC_Group::point_multiply(const BigInt& x, const EC_Point& pt, const BigInt& y) const |
634 | 0 | { |
635 | 0 | EC_Point_Multi_Point_Precompute xy_mul(get_base_point(), pt); |
636 | 0 | return xy_mul.multi_exp(x, y); |
637 | 0 | } |
638 | | |
639 | | EC_Point EC_Group::blinded_base_point_multiply(const BigInt& k, |
640 | | RandomNumberGenerator& rng, |
641 | | std::vector<BigInt>& ws) const |
642 | 34.3k | { |
643 | 34.3k | return data().blinded_base_point_multiply(k, rng, ws); |
644 | 34.3k | } |
645 | | |
646 | | BigInt EC_Group::blinded_base_point_multiply_x(const BigInt& k, |
647 | | RandomNumberGenerator& rng, |
648 | | std::vector<BigInt>& ws) const |
649 | 0 | { |
650 | 0 | const EC_Point pt = data().blinded_base_point_multiply(k, rng, ws); |
651 | |
|
652 | 0 | if(pt.is_zero()) |
653 | 0 | return BigInt::zero(); |
654 | 0 | return pt.get_affine_x(); |
655 | 0 | } |
656 | | |
657 | | BigInt EC_Group::random_scalar(RandomNumberGenerator& rng) const |
658 | 17.9k | { |
659 | 17.9k | return BigInt::random_integer(rng, BigInt::one(), get_order()); |
660 | 17.9k | } |
661 | | |
662 | | EC_Point EC_Group::blinded_var_point_multiply(const EC_Point& point, |
663 | | const BigInt& k, |
664 | | RandomNumberGenerator& rng, |
665 | | std::vector<BigInt>& ws) const |
666 | 28.2k | { |
667 | 28.2k | EC_Point_Var_Point_Precompute mul(point, rng, ws); |
668 | 28.2k | return mul.mul(k, rng, get_order(), ws); |
669 | 28.2k | } |
670 | | |
671 | | EC_Point EC_Group::zero_point() const |
672 | 0 | { |
673 | 0 | return EC_Point(data().curve()); |
674 | 0 | } |
675 | | |
676 | | EC_Point EC_Group::hash_to_curve(const std::string& hash_fn, |
677 | | const uint8_t input[], |
678 | | size_t input_len, |
679 | | const std::string& domain, |
680 | | bool random_oracle) const |
681 | 0 | { |
682 | 0 | return this->hash_to_curve(hash_fn, |
683 | 0 | input, |
684 | 0 | input_len, |
685 | 0 | reinterpret_cast<const uint8_t*>(domain.c_str()), |
686 | 0 | domain.size(), |
687 | 0 | random_oracle); |
688 | 0 | } |
689 | | |
690 | | EC_Point EC_Group::hash_to_curve(const std::string& hash_fn, |
691 | | const uint8_t input[], |
692 | | size_t input_len, |
693 | | const uint8_t domain_sep[], |
694 | | size_t domain_sep_len, |
695 | | bool random_oracle) const |
696 | 0 | { |
697 | 0 | #if defined(BOTAN_HAS_EC_HASH_TO_CURVE) |
698 | | |
699 | | // Only have SSWU currently |
700 | 0 | if(get_a().is_zero() || get_b().is_zero() || get_p() % 4 == 1) |
701 | 0 | { |
702 | 0 | throw Not_Implemented("EC_Group::hash_to_curve not available for this curve type"); |
703 | 0 | } |
704 | | |
705 | 0 | return hash_to_curve_sswu(*this, hash_fn, |
706 | 0 | input, input_len, |
707 | 0 | domain_sep, domain_sep_len, |
708 | 0 | random_oracle); |
709 | |
|
710 | | #else |
711 | | BOTAN_UNUSED(hash_fn, random_oracle, input, input_len, domain_sep, domain_sep_len); |
712 | | throw Not_Implemented("EC_Group::hash_to_curve functionality not available in this configuration"); |
713 | | #endif |
714 | 0 | } |
715 | | |
716 | | std::vector<uint8_t> |
717 | | EC_Group::DER_encode(EC_Group_Encoding form) const |
718 | 0 | { |
719 | 0 | std::vector<uint8_t> output; |
720 | |
|
721 | 0 | DER_Encoder der(output); |
722 | |
|
723 | 0 | if(form == EC_Group_Encoding::Explicit) |
724 | 0 | { |
725 | 0 | const size_t ecpVers1 = 1; |
726 | 0 | const OID curve_type("1.2.840.10045.1.1"); // prime field |
727 | |
|
728 | 0 | const size_t p_bytes = get_p_bytes(); |
729 | |
|
730 | 0 | der.start_sequence() |
731 | 0 | .encode(ecpVers1) |
732 | 0 | .start_sequence() |
733 | 0 | .encode(curve_type) |
734 | 0 | .encode(get_p()) |
735 | 0 | .end_cons() |
736 | 0 | .start_sequence() |
737 | 0 | .encode(BigInt::encode_1363(get_a(), p_bytes), |
738 | 0 | ASN1_Type::OctetString) |
739 | 0 | .encode(BigInt::encode_1363(get_b(), p_bytes), |
740 | 0 | ASN1_Type::OctetString) |
741 | 0 | .end_cons() |
742 | 0 | .encode(get_base_point().encode(EC_Point::UNCOMPRESSED), ASN1_Type::OctetString) |
743 | 0 | .encode(get_order()) |
744 | 0 | .encode(get_cofactor()) |
745 | 0 | .end_cons(); |
746 | 0 | } |
747 | 0 | else if(form == EC_Group_Encoding::NamedCurve) |
748 | 0 | { |
749 | 0 | const OID oid = get_curve_oid(); |
750 | 0 | if(oid.empty()) |
751 | 0 | { |
752 | 0 | throw Encoding_Error("Cannot encode EC_Group as OID because OID not set"); |
753 | 0 | } |
754 | 0 | der.encode(oid); |
755 | 0 | } |
756 | 0 | else if(form == EC_Group_Encoding::ImplicitCA) |
757 | 0 | { |
758 | 0 | der.encode_null(); |
759 | 0 | } |
760 | 0 | else |
761 | 0 | { |
762 | 0 | throw Internal_Error("EC_Group::DER_encode: Unknown encoding"); |
763 | 0 | } |
764 | | |
765 | 0 | return output; |
766 | 0 | } |
767 | | |
768 | | std::string EC_Group::PEM_encode() const |
769 | 0 | { |
770 | 0 | const std::vector<uint8_t> der = DER_encode(EC_Group_Encoding::Explicit); |
771 | 0 | return PEM_Code::encode(der, "EC PARAMETERS"); |
772 | 0 | } |
773 | | |
774 | | bool EC_Group::operator==(const EC_Group& other) const |
775 | 0 | { |
776 | 0 | if(m_data == other.m_data) |
777 | 0 | return true; // same shared rep |
778 | | |
779 | 0 | return (get_p() == other.get_p() && |
780 | 0 | get_a() == other.get_a() && |
781 | 0 | get_b() == other.get_b() && |
782 | 0 | get_g_x() == other.get_g_x() && |
783 | 0 | get_g_y() == other.get_g_y() && |
784 | 0 | get_order() == other.get_order() && |
785 | 0 | get_cofactor() == other.get_cofactor()); |
786 | 0 | } |
787 | | |
788 | | bool EC_Group::verify_public_element(const EC_Point& point) const |
789 | 0 | { |
790 | | //check that public point is not at infinity |
791 | 0 | if(point.is_zero()) |
792 | 0 | return false; |
793 | | |
794 | | //check that public point is on the curve |
795 | 0 | if(point.on_the_curve() == false) |
796 | 0 | return false; |
797 | | |
798 | | //check that public point has order q |
799 | 0 | if((point * get_order()).is_zero() == false) |
800 | 0 | return false; |
801 | | |
802 | 0 | if(get_cofactor() > 1) |
803 | 0 | { |
804 | 0 | if((point * get_cofactor()).is_zero()) |
805 | 0 | return false; |
806 | 0 | } |
807 | | |
808 | 0 | return true; |
809 | 0 | } |
810 | | |
811 | | bool EC_Group::verify_group(RandomNumberGenerator& rng, |
812 | | bool strong) const |
813 | 0 | { |
814 | 0 | const bool is_builtin = source() == EC_Group_Source::Builtin; |
815 | |
|
816 | 0 | if(is_builtin && !strong) |
817 | 0 | return true; |
818 | | |
819 | 0 | const BigInt& p = get_p(); |
820 | 0 | const BigInt& a = get_a(); |
821 | 0 | const BigInt& b = get_b(); |
822 | 0 | const BigInt& order = get_order(); |
823 | 0 | const EC_Point& base_point = get_base_point(); |
824 | |
|
825 | 0 | if(p <= 3 || order <= 0) |
826 | 0 | return false; |
827 | 0 | if(a < 0 || a >= p) |
828 | 0 | return false; |
829 | 0 | if(b <= 0 || b >= p) |
830 | 0 | return false; |
831 | | |
832 | 0 | const size_t test_prob = 128; |
833 | 0 | const bool is_randomly_generated = is_builtin; |
834 | | |
835 | | //check if field modulus is prime |
836 | 0 | if(!is_prime(p, rng, test_prob, is_randomly_generated)) |
837 | 0 | { |
838 | 0 | return false; |
839 | 0 | } |
840 | | |
841 | | //check if order is prime |
842 | 0 | if(!is_prime(order, rng, test_prob, is_randomly_generated)) |
843 | 0 | { |
844 | 0 | return false; |
845 | 0 | } |
846 | | |
847 | | //compute the discriminant: 4*a^3 + 27*b^2 which must be nonzero |
848 | 0 | const Modular_Reducer mod_p(p); |
849 | |
|
850 | 0 | const BigInt discriminant = mod_p.reduce( |
851 | 0 | mod_p.multiply(4, mod_p.cube(a)) + |
852 | 0 | mod_p.multiply(27, mod_p.square(b))); |
853 | |
|
854 | 0 | if(discriminant == 0) |
855 | 0 | { |
856 | 0 | return false; |
857 | 0 | } |
858 | | |
859 | | //check for valid cofactor |
860 | 0 | if(get_cofactor() < 1) |
861 | 0 | { |
862 | 0 | return false; |
863 | 0 | } |
864 | | |
865 | | //check if the base point is on the curve |
866 | 0 | if(!base_point.on_the_curve()) |
867 | 0 | { |
868 | 0 | return false; |
869 | 0 | } |
870 | 0 | if((base_point * get_cofactor()).is_zero()) |
871 | 0 | { |
872 | 0 | return false; |
873 | 0 | } |
874 | | //check if order of the base point is correct |
875 | 0 | if(!(base_point * order).is_zero()) |
876 | 0 | { |
877 | 0 | return false; |
878 | 0 | } |
879 | | |
880 | 0 | return true; |
881 | 0 | } |
882 | | |
883 | | } |