/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 | | namespace Botan { |
23 | | |
24 | | class EC_Group_Data final |
25 | | { |
26 | | public: |
27 | | |
28 | | EC_Group_Data(const BigInt& p, |
29 | | const BigInt& a, |
30 | | const BigInt& b, |
31 | | const BigInt& g_x, |
32 | | const BigInt& g_y, |
33 | | const BigInt& order, |
34 | | const BigInt& cofactor, |
35 | | const OID& oid, |
36 | | EC_Group_Source source) : |
37 | | m_curve(p, a, b), |
38 | | m_base_point(m_curve, g_x, g_y), |
39 | | m_g_x(g_x), |
40 | | m_g_y(g_y), |
41 | | m_order(order), |
42 | | m_cofactor(cofactor), |
43 | | m_mod_order(order), |
44 | | m_base_mult(m_base_point, m_mod_order), |
45 | | m_oid(oid), |
46 | | m_p_bits(p.bits()), |
47 | | m_order_bits(order.bits()), |
48 | | m_a_is_minus_3(a == p - 3), |
49 | | m_a_is_zero(a.is_zero()), |
50 | | m_source(source) |
51 | 1.34k | { |
52 | 1.34k | } |
53 | | |
54 | | bool match(const BigInt& p, const BigInt& a, const BigInt& b, |
55 | | const BigInt& g_x, const BigInt& g_y, |
56 | | const BigInt& order, const BigInt& cofactor) const |
57 | 0 | { |
58 | 0 | return (this->p() == p && |
59 | 0 | this->a() == a && |
60 | 0 | this->b() == b && |
61 | 0 | this->order() == order && |
62 | 0 | this->cofactor() == cofactor && |
63 | 0 | this->g_x() == g_x && |
64 | 0 | this->g_y() == g_y); |
65 | 0 | } |
66 | | |
67 | | void set_oid(const OID& oid) |
68 | 0 | { |
69 | 0 | BOTAN_STATE_CHECK(m_oid.empty()); |
70 | 0 | m_oid = oid; |
71 | 0 | } |
72 | | |
73 | 119k | const OID& oid() const { return m_oid; } |
74 | 3.48k | const BigInt& p() const { return m_curve.get_p(); } |
75 | 3.48k | const BigInt& a() const { return m_curve.get_a(); } |
76 | 3.48k | const BigInt& b() const { return m_curve.get_b(); } |
77 | 42.2k | const BigInt& order() const { return m_order; } |
78 | 19.7k | const BigInt& cofactor() const { return m_cofactor; } |
79 | 0 | const BigInt& g_x() const { return m_g_x; } |
80 | 0 | const BigInt& g_y() const { return m_g_y; } |
81 | | |
82 | 892 | size_t p_bits() const { return m_p_bits; } |
83 | 6.81k | size_t p_bytes() const { return (m_p_bits + 7) / 8; } |
84 | | |
85 | 726 | size_t order_bits() const { return m_order_bits; } |
86 | 363 | size_t order_bytes() const { return (m_order_bits + 7) / 8; } |
87 | | |
88 | 25.3k | const CurveGFp& curve() const { return m_curve; } |
89 | 1.55k | const PointGFp& base_point() const { return m_base_point; } |
90 | | |
91 | 0 | bool a_is_minus_3() const { return m_a_is_minus_3; } |
92 | 0 | bool a_is_zero() const { return m_a_is_zero; } |
93 | | |
94 | 704 | BigInt mod_order(const BigInt& x) const { return m_mod_order.reduce(x); } |
95 | | |
96 | | BigInt square_mod_order(const BigInt& x) const |
97 | 0 | { |
98 | 0 | return m_mod_order.square(x); |
99 | 0 | } |
100 | | |
101 | | BigInt multiply_mod_order(const BigInt& x, const BigInt& y) const |
102 | 704 | { |
103 | 704 | return m_mod_order.multiply(x, y); |
104 | 704 | } |
105 | | |
106 | | BigInt multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const |
107 | 0 | { |
108 | 0 | return m_mod_order.multiply(m_mod_order.multiply(x, y), z); |
109 | 0 | } |
110 | | |
111 | | BigInt inverse_mod_order(const BigInt& x) const |
112 | 10.2k | { |
113 | 10.2k | return inverse_mod(x, m_order); |
114 | 10.2k | } |
115 | | |
116 | | PointGFp blinded_base_point_multiply(const BigInt& k, |
117 | | RandomNumberGenerator& rng, |
118 | | std::vector<BigInt>& ws) const |
119 | 31.4k | { |
120 | 31.4k | return m_base_mult.mul(k, rng, m_order, ws); |
121 | 31.4k | } |
122 | | |
123 | 0 | EC_Group_Source source() const { return m_source; } |
124 | | |
125 | | private: |
126 | | CurveGFp m_curve; |
127 | | PointGFp m_base_point; |
128 | | |
129 | | BigInt m_g_x; |
130 | | BigInt m_g_y; |
131 | | BigInt m_order; |
132 | | BigInt m_cofactor; |
133 | | Modular_Reducer m_mod_order; |
134 | | PointGFp_Base_Point_Precompute m_base_mult; |
135 | | OID m_oid; |
136 | | size_t m_p_bits; |
137 | | size_t m_order_bits; |
138 | | bool m_a_is_minus_3; |
139 | | bool m_a_is_zero; |
140 | | EC_Group_Source m_source; |
141 | | }; |
142 | | |
143 | | class EC_Group_Data_Map final |
144 | | { |
145 | | public: |
146 | 9 | EC_Group_Data_Map() {} |
147 | | |
148 | | size_t clear() |
149 | 3.45k | { |
150 | 3.45k | lock_guard_type<mutex_type> lock(m_mutex); |
151 | 3.45k | size_t count = m_registered_curves.size(); |
152 | 3.45k | m_registered_curves.clear(); |
153 | 3.45k | return count; |
154 | 3.45k | } |
155 | | |
156 | | std::shared_ptr<EC_Group_Data> lookup(const OID& oid) |
157 | 25.0k | { |
158 | 25.0k | lock_guard_type<mutex_type> lock(m_mutex); |
159 | | |
160 | 25.0k | for(auto i : m_registered_curves) |
161 | 94.6k | { |
162 | 94.6k | if(i->oid() == oid) |
163 | 23.6k | return i; |
164 | 94.6k | } |
165 | | |
166 | | // Not found, check hardcoded data |
167 | 1.30k | std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid); |
168 | | |
169 | 1.30k | if(data) |
170 | 1.15k | { |
171 | 1.15k | m_registered_curves.push_back(data); |
172 | 1.15k | return data; |
173 | 1.15k | } |
174 | | |
175 | | // Nope, unknown curve |
176 | 157 | return std::shared_ptr<EC_Group_Data>(); |
177 | 157 | } |
178 | | |
179 | | std::shared_ptr<EC_Group_Data> lookup_or_create(const BigInt& p, |
180 | | const BigInt& a, |
181 | | const BigInt& b, |
182 | | const BigInt& g_x, |
183 | | const BigInt& g_y, |
184 | | const BigInt& order, |
185 | | const BigInt& cofactor, |
186 | | const OID& oid, |
187 | | EC_Group_Source source) |
188 | 195 | { |
189 | 195 | lock_guard_type<mutex_type> lock(m_mutex); |
190 | | |
191 | 195 | for(auto i : m_registered_curves) |
192 | 0 | { |
193 | 0 | if(!oid.empty()) |
194 | 0 | { |
195 | 0 | if(i->oid() == oid) |
196 | 0 | { |
197 | 0 | if(!i->match(p, a, b, g_x, g_y, order, cofactor)) |
198 | 0 | throw Invalid_Argument("Attempting to register a curve using OID " + oid.to_string() + |
199 | 0 | " but another curve is already registered using that OID"); |
200 | 0 | return i; |
201 | 0 | } |
202 | 0 | else if(i->oid().has_value()) |
203 | 0 | continue; // distinct OIDs so not a match |
204 | 0 | } |
205 | | |
206 | 0 | if(i->match(p, a, b, g_x, g_y, order, cofactor)) |
207 | 0 | { |
208 | | /* |
209 | | * If the same curve was previously created without an OID |
210 | | * but has been registered again using an OID, save that OID. |
211 | | */ |
212 | 0 | if(oid.empty() == false) |
213 | 0 | { |
214 | 0 | if(i->oid().empty() == true) |
215 | 0 | { |
216 | 0 | i->set_oid(oid); |
217 | 0 | } |
218 | 0 | else |
219 | 0 | { |
220 | 0 | throw Invalid_Argument("Cannot register ECC group with OID " + oid.to_string() + |
221 | 0 | " already registered using " + i->oid().to_string()); |
222 | 0 | } |
223 | 0 | } |
224 | 0 | return i; |
225 | 0 | } |
226 | 0 | } |
227 | | |
228 | | // Not found - if OID is set try looking up that way |
229 | | |
230 | 195 | if(oid.has_value()) |
231 | 0 | { |
232 | | // Not located in existing store - try hardcoded data set |
233 | 0 | std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid); |
234 | |
|
235 | 0 | if(data) |
236 | 0 | { |
237 | 0 | m_registered_curves.push_back(data); |
238 | 0 | return data; |
239 | 0 | } |
240 | 195 | } |
241 | | |
242 | | // Not found or no OID, add data and return |
243 | 195 | std::shared_ptr<EC_Group_Data> d = |
244 | 195 | std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid, source); |
245 | | |
246 | 195 | m_registered_curves.push_back(d); |
247 | 195 | return d; |
248 | 195 | } |
249 | | |
250 | | private: |
251 | | mutex_type m_mutex; |
252 | | std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves; |
253 | | }; |
254 | | |
255 | | //static |
256 | | EC_Group_Data_Map& EC_Group::ec_group_data() |
257 | 28.6k | { |
258 | | /* |
259 | | * This exists purely to ensure the allocator is constructed before g_ec_data, |
260 | | * which ensures that its destructor runs after ~g_ec_data is complete. |
261 | | */ |
262 | | |
263 | 28.6k | static Allocator_Initializer g_init_allocator; |
264 | 28.6k | static EC_Group_Data_Map g_ec_data; |
265 | 28.6k | return g_ec_data; |
266 | 28.6k | } |
267 | | |
268 | | //static |
269 | | size_t EC_Group::clear_registered_curve_data() |
270 | 3.45k | { |
271 | 3.45k | return ec_group_data().clear(); |
272 | 3.45k | } |
273 | | |
274 | | //static |
275 | | std::shared_ptr<EC_Group_Data> |
276 | | EC_Group::load_EC_group_info(const char* p_str, |
277 | | const char* a_str, |
278 | | const char* b_str, |
279 | | const char* g_x_str, |
280 | | const char* g_y_str, |
281 | | const char* order_str, |
282 | | const OID& oid) |
283 | 1.15k | { |
284 | 1.15k | const BigInt p(p_str); |
285 | 1.15k | const BigInt a(a_str); |
286 | 1.15k | const BigInt b(b_str); |
287 | 1.15k | const BigInt g_x(g_x_str); |
288 | 1.15k | const BigInt g_y(g_y_str); |
289 | 1.15k | const BigInt order(order_str); |
290 | 1.15k | const BigInt cofactor(1); // implicit |
291 | | |
292 | 1.15k | return std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid, EC_Group_Source::Builtin); |
293 | 1.15k | } |
294 | | |
295 | | //static |
296 | | std::shared_ptr<EC_Group_Data> EC_Group::BER_decode_EC_group(const uint8_t bits[], size_t len, |
297 | | EC_Group_Source source) |
298 | 4.70k | { |
299 | 4.70k | BER_Decoder ber(bits, len); |
300 | 4.70k | BER_Object obj = ber.get_next_object(); |
301 | | |
302 | 4.70k | if(obj.type() == ASN1_Type::Null) |
303 | 9 | { |
304 | 9 | throw Decoding_Error("Cannot handle ImplicitCA ECC parameters"); |
305 | 9 | } |
306 | 4.69k | else if(obj.type() == ASN1_Type::ObjectId) |
307 | 3.96k | { |
308 | 3.96k | OID dom_par_oid; |
309 | 3.96k | BER_Decoder(bits, len).decode(dom_par_oid); |
310 | 3.96k | return ec_group_data().lookup(dom_par_oid); |
311 | 3.96k | } |
312 | 724 | else if(obj.type() == ASN1_Type::Sequence) |
313 | 533 | { |
314 | 533 | BigInt p, a, b, order, cofactor; |
315 | 533 | std::vector<uint8_t> base_pt; |
316 | 533 | std::vector<uint8_t> seed; |
317 | | |
318 | 533 | BER_Decoder(bits, len) |
319 | 533 | .start_sequence() |
320 | 533 | .decode_and_check<size_t>(1, "Unknown ECC param version code") |
321 | 533 | .start_sequence() |
322 | 533 | .decode_and_check(OID("1.2.840.10045.1.1"), |
323 | 533 | "Only prime ECC fields supported") |
324 | 533 | .decode(p) |
325 | 533 | .end_cons() |
326 | 533 | .start_sequence() |
327 | 533 | .decode_octet_string_bigint(a) |
328 | 533 | .decode_octet_string_bigint(b) |
329 | 533 | .decode_optional_string(seed, ASN1_Type::BitString, ASN1_Type::BitString) |
330 | 533 | .end_cons() |
331 | 533 | .decode(base_pt, ASN1_Type::OctetString) |
332 | 533 | .decode(order) |
333 | 533 | .decode(cofactor) |
334 | 533 | .end_cons() |
335 | 533 | .verify_end(); |
336 | | |
337 | 533 | if(p.bits() < 64 || p.is_negative() || !is_bailie_psw_probable_prime(p)) |
338 | 13 | throw Decoding_Error("Invalid ECC p parameter"); |
339 | | |
340 | 520 | if(a.is_negative() || a >= p) |
341 | 4 | throw Decoding_Error("Invalid ECC a parameter"); |
342 | | |
343 | 516 | if(b <= 0 || b >= p) |
344 | 6 | throw Decoding_Error("Invalid ECC b parameter"); |
345 | | |
346 | 510 | if(order <= 0 || !is_bailie_psw_probable_prime(order)) |
347 | 86 | throw Decoding_Error("Invalid ECC order parameter"); |
348 | | |
349 | 424 | if(cofactor <= 0 || cofactor >= 16) |
350 | 47 | throw Decoding_Error("Invalid ECC cofactor parameter"); |
351 | | |
352 | 377 | std::pair<BigInt, BigInt> base_xy = Botan::OS2ECP(base_pt.data(), base_pt.size(), p, a, b); |
353 | | |
354 | 377 | return ec_group_data().lookup_or_create(p, a, b, base_xy.first, base_xy.second, |
355 | 377 | order, cofactor, OID(), source); |
356 | 377 | } |
357 | 191 | else |
358 | 191 | { |
359 | 191 | throw Decoding_Error("Unexpected tag while decoding ECC domain params"); |
360 | 191 | } |
361 | 4.70k | } |
362 | | |
363 | | EC_Group::EC_Group() |
364 | 22.5k | { |
365 | 22.5k | } |
366 | | |
367 | | EC_Group::~EC_Group() |
368 | 59.4k | { |
369 | | // shared_ptr possibly freed here |
370 | 59.4k | } |
371 | | |
372 | | EC_Group::EC_Group(const OID& domain_oid) |
373 | 737 | { |
374 | 737 | this->m_data = ec_group_data().lookup(domain_oid); |
375 | 737 | if(!this->m_data) |
376 | 0 | throw Invalid_Argument("Unknown EC_Group " + domain_oid.to_string()); |
377 | 737 | } |
378 | | |
379 | | EC_Group::EC_Group(const std::string& str) |
380 | 20.3k | { |
381 | 20.3k | if(str == "") |
382 | 0 | return; // no initialization / uninitialized |
383 | | |
384 | 20.3k | try |
385 | 20.3k | { |
386 | 20.3k | const OID oid = OID::from_string(str); |
387 | 20.3k | if(oid.has_value()) |
388 | 20.3k | m_data = ec_group_data().lookup(oid); |
389 | 20.3k | } |
390 | 20.3k | catch(...) |
391 | 0 | { |
392 | 0 | } |
393 | | |
394 | 20.3k | if(m_data == nullptr) |
395 | 0 | { |
396 | 0 | if(str.size() > 30 && str.substr(0, 29) == "-----BEGIN EC PARAMETERS-----") |
397 | 0 | { |
398 | | // OK try it as PEM ... |
399 | 0 | secure_vector<uint8_t> ber = PEM_Code::decode_check_label(str, "EC PARAMETERS"); |
400 | 0 | this->m_data = BER_decode_EC_group(ber.data(), ber.size(), EC_Group_Source::ExternalSource); |
401 | 0 | } |
402 | 0 | } |
403 | | |
404 | 20.3k | if(m_data == nullptr) |
405 | 0 | throw Invalid_Argument("Unknown ECC group '" + str + "'"); |
406 | 20.3k | } |
407 | | |
408 | | //static |
409 | | EC_Group EC_Group::EC_Group_from_PEM(const std::string& pem) |
410 | 0 | { |
411 | 0 | const auto ber = PEM_Code::decode_check_label(pem, "EC PARAMETERS"); |
412 | 0 | return EC_Group(ber.data(), ber.size()); |
413 | 0 | } |
414 | | |
415 | | EC_Group::EC_Group(const BigInt& p, |
416 | | const BigInt& a, |
417 | | const BigInt& b, |
418 | | const BigInt& base_x, |
419 | | const BigInt& base_y, |
420 | | const BigInt& order, |
421 | | const BigInt& cofactor, |
422 | | const OID& oid) |
423 | 0 | { |
424 | 0 | m_data = ec_group_data().lookup_or_create(p, a, b, base_x, base_y, order, cofactor, oid, |
425 | 0 | EC_Group_Source::ExternalSource); |
426 | 0 | } |
427 | | |
428 | | EC_Group::EC_Group(const uint8_t ber[], size_t ber_len) |
429 | 4.70k | { |
430 | 4.70k | m_data = BER_decode_EC_group(ber, ber_len, EC_Group_Source::ExternalSource); |
431 | 4.70k | } |
432 | | |
433 | | const EC_Group_Data& EC_Group::data() const |
434 | 175k | { |
435 | 175k | if(m_data == nullptr) |
436 | 157 | throw Invalid_State("EC_Group uninitialized"); |
437 | 175k | return *m_data; |
438 | 175k | } |
439 | | |
440 | | bool EC_Group::a_is_minus_3() const |
441 | 0 | { |
442 | 0 | return data().a_is_minus_3(); |
443 | 0 | } |
444 | | |
445 | | bool EC_Group::a_is_zero() const |
446 | 0 | { |
447 | 0 | return data().a_is_zero(); |
448 | 0 | } |
449 | | |
450 | | size_t EC_Group::get_p_bits() const |
451 | 892 | { |
452 | 892 | return data().p_bits(); |
453 | 892 | } |
454 | | |
455 | | size_t EC_Group::get_p_bytes() const |
456 | 6.81k | { |
457 | 6.81k | return data().p_bytes(); |
458 | 6.81k | } |
459 | | |
460 | | size_t EC_Group::get_order_bits() const |
461 | 726 | { |
462 | 726 | return data().order_bits(); |
463 | 726 | } |
464 | | |
465 | | size_t EC_Group::get_order_bytes() const |
466 | 363 | { |
467 | 363 | return data().order_bytes(); |
468 | 363 | } |
469 | | |
470 | | const BigInt& EC_Group::get_p() const |
471 | 3.48k | { |
472 | 3.48k | return data().p(); |
473 | 3.48k | } |
474 | | |
475 | | const BigInt& EC_Group::get_a() const |
476 | 3.48k | { |
477 | 3.48k | return data().a(); |
478 | 3.48k | } |
479 | | |
480 | | const BigInt& EC_Group::get_b() const |
481 | 3.48k | { |
482 | 3.48k | return data().b(); |
483 | 3.48k | } |
484 | | |
485 | | const PointGFp& EC_Group::get_base_point() const |
486 | 1.55k | { |
487 | 1.55k | return data().base_point(); |
488 | 1.55k | } |
489 | | |
490 | | const BigInt& EC_Group::get_order() const |
491 | 42.2k | { |
492 | 42.2k | return data().order(); |
493 | 42.2k | } |
494 | | |
495 | | const BigInt& EC_Group::get_g_x() const |
496 | 0 | { |
497 | 0 | return data().g_x(); |
498 | 0 | } |
499 | | |
500 | | const BigInt& EC_Group::get_g_y() const |
501 | 0 | { |
502 | 0 | return data().g_y(); |
503 | 0 | } |
504 | | |
505 | | const BigInt& EC_Group::get_cofactor() const |
506 | 19.7k | { |
507 | 19.7k | return data().cofactor(); |
508 | 19.7k | } |
509 | | |
510 | | BigInt EC_Group::mod_order(const BigInt& k) const |
511 | 704 | { |
512 | 704 | return data().mod_order(k); |
513 | 704 | } |
514 | | |
515 | | BigInt EC_Group::square_mod_order(const BigInt& x) const |
516 | 0 | { |
517 | 0 | return data().square_mod_order(x); |
518 | 0 | } |
519 | | |
520 | | BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y) const |
521 | 704 | { |
522 | 704 | return data().multiply_mod_order(x, y); |
523 | 704 | } |
524 | | |
525 | | BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const |
526 | 0 | { |
527 | 0 | return data().multiply_mod_order(x, y, z); |
528 | 0 | } |
529 | | |
530 | | BigInt EC_Group::inverse_mod_order(const BigInt& x) const |
531 | 10.2k | { |
532 | 10.2k | return data().inverse_mod_order(x); |
533 | 10.2k | } |
534 | | |
535 | | const OID& EC_Group::get_curve_oid() const |
536 | 24.5k | { |
537 | 24.5k | return data().oid(); |
538 | 24.5k | } |
539 | | |
540 | | EC_Group_Source EC_Group::source() const |
541 | 0 | { |
542 | 0 | return data().source(); |
543 | 0 | } |
544 | | |
545 | | size_t EC_Group::point_size(PointGFp::Compression_Type format) const |
546 | 0 | { |
547 | | // Hybrid and standard format are (x,y), compressed is y, +1 format byte |
548 | 0 | if(format == PointGFp::COMPRESSED) |
549 | 0 | return (1 + get_p_bytes()); |
550 | 0 | else |
551 | 0 | return (1 + 2*get_p_bytes()); |
552 | 0 | } |
553 | | |
554 | | PointGFp EC_Group::OS2ECP(const uint8_t bits[], size_t len) const |
555 | 21.4k | { |
556 | 21.4k | return Botan::OS2ECP(bits, len, data().curve()); |
557 | 21.4k | } |
558 | | |
559 | | PointGFp EC_Group::point(const BigInt& x, const BigInt& y) const |
560 | 3.95k | { |
561 | | // TODO: randomize the representation? |
562 | 3.95k | return PointGFp(data().curve(), x, y); |
563 | 3.95k | } |
564 | | |
565 | | PointGFp EC_Group::point_multiply(const BigInt& x, const PointGFp& pt, const BigInt& y) const |
566 | 0 | { |
567 | 0 | PointGFp_Multi_Point_Precompute xy_mul(get_base_point(), pt); |
568 | 0 | return xy_mul.multi_exp(x, y); |
569 | 0 | } |
570 | | |
571 | | PointGFp EC_Group::blinded_base_point_multiply(const BigInt& k, |
572 | | RandomNumberGenerator& rng, |
573 | | std::vector<BigInt>& ws) const |
574 | 31.4k | { |
575 | 31.4k | return data().blinded_base_point_multiply(k, rng, ws); |
576 | 31.4k | } |
577 | | |
578 | | BigInt EC_Group::blinded_base_point_multiply_x(const BigInt& k, |
579 | | RandomNumberGenerator& rng, |
580 | | std::vector<BigInt>& ws) const |
581 | 0 | { |
582 | 0 | const PointGFp pt = data().blinded_base_point_multiply(k, rng, ws); |
583 | |
|
584 | 0 | if(pt.is_zero()) |
585 | 0 | return 0; |
586 | 0 | return pt.get_affine_x(); |
587 | 0 | } |
588 | | |
589 | | BigInt EC_Group::random_scalar(RandomNumberGenerator& rng) const |
590 | 20.9k | { |
591 | 20.9k | return BigInt::random_integer(rng, 1, get_order()); |
592 | 20.9k | } |
593 | | |
594 | | PointGFp EC_Group::blinded_var_point_multiply(const PointGFp& point, |
595 | | const BigInt& k, |
596 | | RandomNumberGenerator& rng, |
597 | | std::vector<BigInt>& ws) const |
598 | 19.4k | { |
599 | 19.4k | PointGFp_Var_Point_Precompute mul(point, rng, ws); |
600 | 19.4k | return mul.mul(k, rng, get_order(), ws); |
601 | 19.4k | } |
602 | | |
603 | | PointGFp EC_Group::zero_point() const |
604 | 0 | { |
605 | 0 | return PointGFp(data().curve()); |
606 | 0 | } |
607 | | |
608 | | std::vector<uint8_t> |
609 | | EC_Group::DER_encode(EC_Group_Encoding form) const |
610 | 0 | { |
611 | 0 | std::vector<uint8_t> output; |
612 | |
|
613 | 0 | DER_Encoder der(output); |
614 | |
|
615 | 0 | if(form == EC_Group_Encoding::Explicit) |
616 | 0 | { |
617 | 0 | const size_t ecpVers1 = 1; |
618 | 0 | const OID curve_type("1.2.840.10045.1.1"); // prime field |
619 | |
|
620 | 0 | const size_t p_bytes = get_p_bytes(); |
621 | |
|
622 | 0 | der.start_sequence() |
623 | 0 | .encode(ecpVers1) |
624 | 0 | .start_sequence() |
625 | 0 | .encode(curve_type) |
626 | 0 | .encode(get_p()) |
627 | 0 | .end_cons() |
628 | 0 | .start_sequence() |
629 | 0 | .encode(BigInt::encode_1363(get_a(), p_bytes), |
630 | 0 | ASN1_Type::OctetString) |
631 | 0 | .encode(BigInt::encode_1363(get_b(), p_bytes), |
632 | 0 | ASN1_Type::OctetString) |
633 | 0 | .end_cons() |
634 | 0 | .encode(get_base_point().encode(PointGFp::UNCOMPRESSED), ASN1_Type::OctetString) |
635 | 0 | .encode(get_order()) |
636 | 0 | .encode(get_cofactor()) |
637 | 0 | .end_cons(); |
638 | 0 | } |
639 | 0 | else if(form == EC_Group_Encoding::NamedCurve) |
640 | 0 | { |
641 | 0 | const OID oid = get_curve_oid(); |
642 | 0 | if(oid.empty()) |
643 | 0 | { |
644 | 0 | throw Encoding_Error("Cannot encode EC_Group as OID because OID not set"); |
645 | 0 | } |
646 | 0 | der.encode(oid); |
647 | 0 | } |
648 | 0 | else if(form == EC_Group_Encoding::ImplicitCA) |
649 | 0 | { |
650 | 0 | der.encode_null(); |
651 | 0 | } |
652 | 0 | else |
653 | 0 | { |
654 | 0 | throw Internal_Error("EC_Group::DER_encode: Unknown encoding"); |
655 | 0 | } |
656 | | |
657 | 0 | return output; |
658 | 0 | } |
659 | | |
660 | | std::string EC_Group::PEM_encode() const |
661 | 0 | { |
662 | 0 | const std::vector<uint8_t> der = DER_encode(EC_Group_Encoding::Explicit); |
663 | 0 | return PEM_Code::encode(der, "EC PARAMETERS"); |
664 | 0 | } |
665 | | |
666 | | bool EC_Group::operator==(const EC_Group& other) const |
667 | 0 | { |
668 | 0 | if(m_data == other.m_data) |
669 | 0 | return true; // same shared rep |
670 | | |
671 | 0 | return (get_p() == other.get_p() && |
672 | 0 | get_a() == other.get_a() && |
673 | 0 | get_b() == other.get_b() && |
674 | 0 | get_g_x() == other.get_g_x() && |
675 | 0 | get_g_y() == other.get_g_y() && |
676 | 0 | get_order() == other.get_order() && |
677 | 0 | get_cofactor() == other.get_cofactor()); |
678 | 0 | } |
679 | | |
680 | | bool EC_Group::verify_public_element(const PointGFp& point) const |
681 | 0 | { |
682 | | //check that public point is not at infinity |
683 | 0 | if(point.is_zero()) |
684 | 0 | return false; |
685 | | |
686 | | //check that public point is on the curve |
687 | 0 | if(point.on_the_curve() == false) |
688 | 0 | return false; |
689 | | |
690 | | //check that public point has order q |
691 | 0 | if((point * get_order()).is_zero() == false) |
692 | 0 | return false; |
693 | | |
694 | 0 | if(get_cofactor() > 1) |
695 | 0 | { |
696 | 0 | if((point * get_cofactor()).is_zero()) |
697 | 0 | return false; |
698 | 0 | } |
699 | | |
700 | 0 | return true; |
701 | 0 | } |
702 | | |
703 | | bool EC_Group::verify_group(RandomNumberGenerator& rng, |
704 | | bool strong) const |
705 | 0 | { |
706 | 0 | const bool is_builtin = source() == EC_Group_Source::Builtin; |
707 | |
|
708 | 0 | if(is_builtin && !strong) |
709 | 0 | return true; |
710 | | |
711 | 0 | const BigInt& p = get_p(); |
712 | 0 | const BigInt& a = get_a(); |
713 | 0 | const BigInt& b = get_b(); |
714 | 0 | const BigInt& order = get_order(); |
715 | 0 | const PointGFp& base_point = get_base_point(); |
716 | |
|
717 | 0 | if(p <= 3 || order <= 0) |
718 | 0 | return false; |
719 | 0 | if(a < 0 || a >= p) |
720 | 0 | return false; |
721 | 0 | if(b <= 0 || b >= p) |
722 | 0 | return false; |
723 | | |
724 | 0 | const size_t test_prob = 128; |
725 | 0 | const bool is_randomly_generated = is_builtin; |
726 | | |
727 | | //check if field modulus is prime |
728 | 0 | if(!is_prime(p, rng, test_prob, is_randomly_generated)) |
729 | 0 | { |
730 | 0 | return false; |
731 | 0 | } |
732 | | |
733 | | //check if order is prime |
734 | 0 | if(!is_prime(order, rng, test_prob, is_randomly_generated)) |
735 | 0 | { |
736 | 0 | return false; |
737 | 0 | } |
738 | | |
739 | | //compute the discriminant: 4*a^3 + 27*b^2 which must be nonzero |
740 | 0 | const Modular_Reducer mod_p(p); |
741 | |
|
742 | 0 | const BigInt discriminant = mod_p.reduce( |
743 | 0 | mod_p.multiply(4, mod_p.cube(a)) + |
744 | 0 | mod_p.multiply(27, mod_p.square(b))); |
745 | |
|
746 | 0 | if(discriminant == 0) |
747 | 0 | { |
748 | 0 | return false; |
749 | 0 | } |
750 | | |
751 | | //check for valid cofactor |
752 | 0 | if(get_cofactor() < 1) |
753 | 0 | { |
754 | 0 | return false; |
755 | 0 | } |
756 | | |
757 | | //check if the base point is on the curve |
758 | 0 | if(!base_point.on_the_curve()) |
759 | 0 | { |
760 | 0 | return false; |
761 | 0 | } |
762 | 0 | if((base_point * get_cofactor()).is_zero()) |
763 | 0 | { |
764 | 0 | return false; |
765 | 0 | } |
766 | | //check if order of the base point is correct |
767 | 0 | if(!(base_point * order).is_zero()) |
768 | 0 | { |
769 | 0 | return false; |
770 | 0 | } |
771 | | |
772 | 0 | return true; |
773 | 0 | } |
774 | | |
775 | | } |