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