Coverage Report

Created: 2021-02-21 07:20

/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
}