Coverage Report

Created: 2020-11-21 08:34

/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.41k
         {
52
1.41k
         }
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
127k
      const OID& oid() const { return m_oid; }
74
3.35k
      const BigInt& p() const { return m_curve.get_p(); }
75
3.35k
      const BigInt& a() const { return m_curve.get_a(); }
76
3.35k
      const BigInt& b() const { return m_curve.get_b(); }
77
43.7k
      const BigInt& order() const { return m_order; }
78
23.8k
      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
735
      size_t p_bits() const { return m_p_bits; }
83
10.1k
      size_t p_bytes() const { return (m_p_bits + 7) / 8; }
84
85
680
      size_t order_bits() const { return m_order_bits; }
86
340
      size_t order_bytes() const { return (m_order_bits + 7) / 8; }
87
88
27.9k
      const CurveGFp& curve() const { return m_curve; }
89
1.49k
      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
664
      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
664
         {
103
664
         return m_mod_order.multiply(x, y);
104
664
         }
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
12.2k
         {
113
12.2k
         return inverse_mod(x, m_order);
114
12.2k
         }
115
116
      PointGFp blinded_base_point_multiply(const BigInt& k,
117
                                           RandomNumberGenerator& rng,
118
                                           std::vector<BigInt>& ws) const
119
28.5k
         {
120
28.5k
         return m_base_mult.mul(k, rng, m_order, ws);
121
28.5k
         }
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.39k
         {
150
3.39k
         lock_guard_type<mutex_type> lock(m_mutex);
151
3.39k
         size_t count = m_registered_curves.size();
152
3.39k
         m_registered_curves.clear();
153
3.39k
         return count;
154
3.39k
         }
155
156
      std::shared_ptr<EC_Group_Data> lookup(const OID& oid)
157
22.4k
         {
158
22.4k
         lock_guard_type<mutex_type> lock(m_mutex);
159
160
22.4k
         for(auto i : m_registered_curves)
161
105k
            {
162
105k
            if(i->oid() == oid)
163
21.0k
               return i;
164
105k
            }
165
166
         // Not found, check hardcoded data
167
1.38k
         std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid);
168
169
1.38k
         if(data)
170
1.24k
            {
171
1.24k
            m_registered_curves.push_back(data);
172
1.24k
            return data;
173
1.24k
            }
174
175
         // Nope, unknown curve
176
136
         return std::shared_ptr<EC_Group_Data>();
177
136
         }
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
168
         {
189
168
         lock_guard_type<mutex_type> lock(m_mutex);
190
191
168
         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
168
         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
168
            }
241
242
         // Not found or no OID, add data and return
243
168
         std::shared_ptr<EC_Group_Data> d =
244
168
            std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid, source);
245
246
168
         m_registered_curves.push_back(d);
247
168
         return d;
248
168
         }
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
26.0k
   {
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
26.0k
   static Allocator_Initializer g_init_allocator;
264
26.0k
   static EC_Group_Data_Map g_ec_data;
265
26.0k
   return g_ec_data;
266
26.0k
   }
267
268
//static
269
size_t EC_Group::clear_registered_curve_data()
270
3.39k
   {
271
3.39k
   return ec_group_data().clear();
272
3.39k
   }
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.24k
   {
284
1.24k
   const BigInt p(p_str);
285
1.24k
   const BigInt a(a_str);
286
1.24k
   const BigInt b(b_str);
287
1.24k
   const BigInt g_x(g_x_str);
288
1.24k
   const BigInt g_y(g_y_str);
289
1.24k
   const BigInt order(order_str);
290
1.24k
   const BigInt cofactor(1); // implicit
291
292
1.24k
   return std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid, EC_Group_Source::Builtin);
293
1.24k
   }
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.49k
   {
299
4.49k
   BER_Decoder ber(bits, len);
300
4.49k
   BER_Object obj = ber.get_next_object();
301
302
4.49k
   if(obj.type() == NULL_TAG)
303
11
      {
304
11
      throw Decoding_Error("Cannot handle ImplicitCA ECC parameters");
305
11
      }
306
4.48k
   else if(obj.type() == OBJECT_ID)
307
3.83k
      {
308
3.83k
      OID dom_par_oid;
309
3.83k
      BER_Decoder(bits, len).decode(dom_par_oid);
310
3.83k
      return ec_group_data().lookup(dom_par_oid);
311
3.83k
      }
312
646
   else if(obj.type() == SEQUENCE)
313
480
      {
314
480
      BigInt p, a, b, order, cofactor;
315
480
      std::vector<uint8_t> base_pt;
316
480
      std::vector<uint8_t> seed;
317
318
480
      BER_Decoder(bits, len)
319
480
         .start_cons(SEQUENCE)
320
480
           .decode_and_check<size_t>(1, "Unknown ECC param version code")
321
480
           .start_cons(SEQUENCE)
322
480
            .decode_and_check(OID("1.2.840.10045.1.1"),
323
480
                              "Only prime ECC fields supported")
324
480
             .decode(p)
325
480
           .end_cons()
326
480
           .start_cons(SEQUENCE)
327
480
             .decode_octet_string_bigint(a)
328
480
             .decode_octet_string_bigint(b)
329
480
             .decode_optional_string(seed, BIT_STRING, BIT_STRING)
330
480
           .end_cons()
331
480
           .decode(base_pt, OCTET_STRING)
332
480
           .decode(order)
333
480
           .decode(cofactor)
334
480
         .end_cons()
335
480
         .verify_end();
336
337
480
      if(p.bits() < 64 || p.is_negative() || !is_bailie_psw_probable_prime(p))
338
19
         throw Decoding_Error("Invalid ECC p parameter");
339
340
461
      if(a.is_negative() || a >= p)
341
10
         throw Decoding_Error("Invalid ECC a parameter");
342
343
451
      if(b <= 0 || b >= p)
344
5
         throw Decoding_Error("Invalid ECC b parameter");
345
346
446
      if(order <= 0 || !is_bailie_psw_probable_prime(order))
347
55
         throw Decoding_Error("Invalid ECC order parameter");
348
349
391
      if(cofactor <= 0 || cofactor >= 16)
350
34
         throw Decoding_Error("Invalid ECC cofactor parameter");
351
352
357
      std::pair<BigInt, BigInt> base_xy = Botan::OS2ECP(base_pt.data(), base_pt.size(), p, a, b);
353
354
357
      return ec_group_data().lookup_or_create(p, a, b, base_xy.first, base_xy.second,
355
357
                                              order, cofactor, OID(), source);
356
357
      }
357
166
   else
358
166
      {
359
166
      throw Decoding_Error("Unexpected tag while decoding ECC domain params");
360
166
      }
361
4.49k
   }
362
363
EC_Group::EC_Group()
364
20.2k
   {
365
20.2k
   }
366
367
EC_Group::~EC_Group()
368
56.4k
   {
369
   // shared_ptr possibly freed here
370
56.4k
   }
371
372
EC_Group::EC_Group(const OID& domain_oid)
373
648
   {
374
648
   this->m_data = ec_group_data().lookup(domain_oid);
375
648
   if(!this->m_data)
376
0
      throw Invalid_Argument("Unknown EC_Group " + domain_oid.to_string());
377
648
   }
378
379
EC_Group::EC_Group(const std::string& str)
380
18.0k
   {
381
18.0k
   if(str == "")
382
0
      return; // no initialization / uninitialized
383
384
18.0k
   try
385
18.0k
      {
386
18.0k
      const OID oid = OID::from_string(str);
387
18.0k
      if(oid.has_value())
388
18.0k
         m_data = ec_group_data().lookup(oid);
389
18.0k
      }
390
18.0k
   catch(...)
391
0
      {
392
0
      }
393
394
18.0k
   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
18.0k
   if(m_data == nullptr)
405
0
      throw Invalid_Argument("Unknown ECC group '" + str + "'");
406
18.0k
   }
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.49k
   {
430
4.49k
   m_data = BER_decode_EC_group(ber, ber_len, EC_Group_Source::ExternalSource);
431
4.49k
   }
432
433
const EC_Group_Data& EC_Group::data() const
434
183k
   {
435
183k
   if(m_data == nullptr)
436
136
      throw Invalid_State("EC_Group uninitialized");
437
183k
   return *m_data;
438
183k
   }
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
735
   {
452
735
   return data().p_bits();
453
735
   }
454
455
size_t EC_Group::get_p_bytes() const
456
10.1k
   {
457
10.1k
   return data().p_bytes();
458
10.1k
   }
459
460
size_t EC_Group::get_order_bits() const
461
680
   {
462
680
   return data().order_bits();
463
680
   }
464
465
size_t EC_Group::get_order_bytes() const
466
340
   {
467
340
   return data().order_bytes();
468
340
   }
469
470
const BigInt& EC_Group::get_p() const
471
3.35k
   {
472
3.35k
   return data().p();
473
3.35k
   }
474
475
const BigInt& EC_Group::get_a() const
476
3.35k
   {
477
3.35k
   return data().a();
478
3.35k
   }
479
480
const BigInt& EC_Group::get_b() const
481
3.35k
   {
482
3.35k
   return data().b();
483
3.35k
   }
484
485
const PointGFp& EC_Group::get_base_point() const
486
1.49k
   {
487
1.49k
   return data().base_point();
488
1.49k
   }
489
490
const BigInt& EC_Group::get_order() const
491
43.7k
   {
492
43.7k
   return data().order();
493
43.7k
   }
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
23.8k
   {
507
23.8k
   return data().cofactor();
508
23.8k
   }
509
510
BigInt EC_Group::mod_order(const BigInt& k) const
511
664
   {
512
664
   return data().mod_order(k);
513
664
   }
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
664
   {
522
664
   return data().multiply_mod_order(x, y);
523
664
   }
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
12.2k
   {
532
12.2k
   return data().inverse_mod_order(x);
533
12.2k
   }
534
535
const OID& EC_Group::get_curve_oid() const
536
21.9k
   {
537
21.9k
   return data().oid();
538
21.9k
   }
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
24.2k
   {
556
24.2k
   return Botan::OS2ECP(bits, len, data().curve());
557
24.2k
   }
558
559
PointGFp EC_Group::point(const BigInt& x, const BigInt& y) const
560
3.77k
   {
561
   // TODO: randomize the representation?
562
3.77k
   return PointGFp(data().curve(), x, y);
563
3.77k
   }
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
28.5k
   {
575
28.5k
   return data().blinded_base_point_multiply(k, rng, ws);
576
28.5k
   }
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
18.5k
   {
591
18.5k
   return BigInt::random_integer(rng, 1, get_order());
592
18.5k
   }
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
23.3k
   {
599
23.3k
   PointGFp_Var_Point_Precompute mul(point, rng, ws);
600
23.3k
   return mul.mul(k, rng, get_order(), ws);
601
23.3k
   }
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_DOMPAR_ENC_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_cons(SEQUENCE)
623
0
            .encode(ecpVers1)
624
0
            .start_cons(SEQUENCE)
625
0
               .encode(curve_type)
626
0
               .encode(get_p())
627
0
            .end_cons()
628
0
            .start_cons(SEQUENCE)
629
0
               .encode(BigInt::encode_1363(get_a(), p_bytes),
630
0
                       OCTET_STRING)
631
0
               .encode(BigInt::encode_1363(get_b(), p_bytes),
632
0
                       OCTET_STRING)
633
0
            .end_cons()
634
0
              .encode(get_base_point().encode(PointGFp::UNCOMPRESSED), OCTET_STRING)
635
0
            .encode(get_order())
636
0
            .encode(get_cofactor())
637
0
         .end_cons();
638
0
      }
639
0
   else if(form == EC_DOMPAR_ENC_OID)
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_DOMPAR_ENC_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_DOMPAR_ENC_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
   /*
672
   * No point comparing order/cofactor as they are uniquely determined
673
   * by the curve equation (p,a,b) and the base point.
674
   */
675
0
   return (get_p() == other.get_p() &&
676
0
           get_a() == other.get_a() &&
677
0
           get_b() == other.get_b() &&
678
0
           get_g_x() == other.get_g_x() &&
679
0
           get_g_y() == other.get_g_y());
680
0
   }
681
682
bool EC_Group::verify_public_element(const PointGFp& point) const
683
0
   {
684
   //check that public point is not at infinity
685
0
   if(point.is_zero())
686
0
      return false;
687
688
   //check that public point is on the curve
689
0
   if(point.on_the_curve() == false)
690
0
      return false;
691
692
   //check that public point has order q
693
0
   if((point * get_order()).is_zero() == false)
694
0
      return false;
695
696
0
   if(get_cofactor() > 1)
697
0
      {
698
0
      if((point * get_cofactor()).is_zero())
699
0
         return false;
700
0
      }
701
702
0
   return true;
703
0
   }
704
705
bool EC_Group::verify_group(RandomNumberGenerator& rng,
706
                            bool strong) const
707
0
   {
708
0
   const bool is_builtin = source() == EC_Group_Source::Builtin;
709
710
0
   if(is_builtin && !strong)
711
0
      return true;
712
713
0
   const BigInt& p = get_p();
714
0
   const BigInt& a = get_a();
715
0
   const BigInt& b = get_b();
716
0
   const BigInt& order = get_order();
717
0
   const PointGFp& base_point = get_base_point();
718
719
0
   if(p <= 3 || order <= 0)
720
0
      return false;
721
0
   if(a < 0 || a >= p)
722
0
      return false;
723
0
   if(b <= 0 || b >= p)
724
0
      return false;
725
726
0
   const size_t test_prob = 128;
727
0
   const bool is_randomly_generated = is_builtin;
728
729
   //check if field modulus is prime
730
0
   if(!is_prime(p, rng, test_prob, is_randomly_generated))
731
0
      {
732
0
      return false;
733
0
      }
734
735
   //check if order is prime
736
0
   if(!is_prime(order, rng, test_prob, is_randomly_generated))
737
0
      {
738
0
      return false;
739
0
      }
740
741
   //compute the discriminant: 4*a^3 + 27*b^2 which must be nonzero
742
0
   const Modular_Reducer mod_p(p);
743
744
0
   const BigInt discriminant = mod_p.reduce(
745
0
      mod_p.multiply(4, mod_p.cube(a)) +
746
0
      mod_p.multiply(27, mod_p.square(b)));
747
748
0
   if(discriminant == 0)
749
0
      {
750
0
      return false;
751
0
      }
752
753
   //check for valid cofactor
754
0
   if(get_cofactor() < 1)
755
0
      {
756
0
      return false;
757
0
      }
758
759
   //check if the base point is on the curve
760
0
   if(!base_point.on_the_curve())
761
0
      {
762
0
      return false;
763
0
      }
764
0
   if((base_point * get_cofactor()).is_zero())
765
0
      {
766
0
      return false;
767
0
      }
768
   //check if order of the base point is correct
769
0
   if(!(base_point * order).is_zero())
770
0
      {
771
0
      return false;
772
0
      }
773
774
0
   return true;
775
0
   }
776
777
}