Coverage Report

Created: 2020-06-30 13:58

/src/botan/src/lib/pubkey/ec_group/point_gfp.cpp
Line
Count
Source (jump to first uncovered line)
1
/*
2
* Point arithmetic on elliptic curves over GF(p)
3
*
4
* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
5
*     2008-2011,2012,2014,2015,2018 Jack Lloyd
6
*
7
* Botan is released under the Simplified BSD License (see license.txt)
8
*/
9
10
#include <botan/point_gfp.h>
11
#include <botan/numthry.h>
12
#include <botan/rng.h>
13
#include <botan/internal/rounding.h>
14
#include <botan/internal/ct_utils.h>
15
16
namespace Botan {
17
18
PointGFp::PointGFp(const CurveGFp& curve) :
19
   m_curve(curve),
20
   m_coord_x(0),
21
   m_coord_y(curve.get_1_rep()),
22
   m_coord_z(0)
23
100k
   {
24
100k
   // Assumes Montgomery rep of zero is zero
25
100k
   }
26
27
PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
28
   m_curve(curve),
29
   m_coord_x(x),
30
   m_coord_y(y),
31
   m_coord_z(m_curve.get_1_rep())
32
21.2k
   {
33
21.2k
   if(x < 0 || x >= curve.get_p())
34
1.24k
      throw Invalid_Argument("Invalid PointGFp affine x");
35
20.0k
   if(y < 0 || y >= curve.get_p())
36
1.76k
      throw Invalid_Argument("Invalid PointGFp affine y");
37
18.2k
38
18.2k
   secure_vector<word> monty_ws(m_curve.get_ws_size());
39
18.2k
   m_curve.to_rep(m_coord_x, monty_ws);
40
18.2k
   m_curve.to_rep(m_coord_y, monty_ws);
41
18.2k
   }
42
43
void PointGFp::randomize_repr(RandomNumberGenerator& rng)
44
11.5k
   {
45
11.5k
   secure_vector<word> ws(m_curve.get_ws_size());
46
11.5k
   randomize_repr(rng, ws);
47
11.5k
   }
48
49
void PointGFp::randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws)
50
61.5k
   {
51
61.5k
   const BigInt mask = BigInt::random_integer(rng, 2, m_curve.get_p());
52
61.5k
53
61.5k
   /*
54
61.5k
   * No reason to convert this to Montgomery representation first,
55
61.5k
   * just pretend the random mask was chosen as Redc(mask) and the
56
61.5k
   * random mask we generated above is in the Montgomery
57
61.5k
   * representation.
58
61.5k
   * //m_curve.to_rep(mask, ws);
59
61.5k
   */
60
61.5k
   const BigInt mask2 = m_curve.sqr_to_tmp(mask, ws);
61
61.5k
   const BigInt mask3 = m_curve.mul_to_tmp(mask2, mask, ws);
62
61.5k
63
61.5k
   m_coord_x = m_curve.mul_to_tmp(m_coord_x, mask2, ws);
64
61.5k
   m_coord_y = m_curve.mul_to_tmp(m_coord_y, mask3, ws);
65
61.5k
   m_coord_z = m_curve.mul_to_tmp(m_coord_z, mask, ws);
66
61.5k
   }
67
68
namespace {
69
70
inline void resize_ws(std::vector<BigInt>& ws_bn, size_t cap_size)
71
23.2M
   {
72
23.2M
   BOTAN_ASSERT(ws_bn.size() >= PointGFp::WORKSPACE_SIZE,
73
23.2M
                "Expected size for PointGFp workspace");
74
23.2M
75
208M
   for(size_t i = 0; i != ws_bn.size(); ++i)
76
185M
      if(ws_bn[i].size() < cap_size)
77
15.0M
         ws_bn[i].get_word_vector().resize(cap_size);
78
23.2M
   }
79
80
inline word all_zeros(const word x[], size_t len)
81
21.5M
   {
82
21.5M
   word z = 0;
83
176M
   for(size_t i = 0; i != len; ++i)
84
155M
      z |= x[i];
85
21.5M
   return CT::Mask<word>::is_zero(z).value();
86
21.5M
   }
87
88
}
89
90
void PointGFp::add_affine(const word x_words[], size_t x_size,
91
                          const word y_words[], size_t y_size,
92
                          std::vector<BigInt>& ws_bn)
93
5.85M
   {
94
5.85M
   if(all_zeros(x_words, x_size) & all_zeros(y_words, y_size))
95
721k
      {
96
721k
      return;
97
721k
      }
98
5.13M
99
5.13M
   if(is_zero())
100
27.9k
      {
101
27.9k
      m_coord_x.set_words(x_words, x_size);
102
27.9k
      m_coord_y.set_words(y_words, y_size);
103
27.9k
      m_coord_z = m_curve.get_1_rep();
104
27.9k
      return;
105
27.9k
      }
106
5.10M
107
5.10M
   resize_ws(ws_bn, m_curve.get_ws_size());
108
5.10M
109
5.10M
   secure_vector<word>& ws = ws_bn[0].get_word_vector();
110
5.10M
   secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
111
5.10M
112
5.10M
   BigInt& T0 = ws_bn[2];
113
5.10M
   BigInt& T1 = ws_bn[3];
114
5.10M
   BigInt& T2 = ws_bn[4];
115
5.10M
   BigInt& T3 = ws_bn[5];
116
5.10M
   BigInt& T4 = ws_bn[6];
117
5.10M
118
5.10M
   /*
119
5.10M
   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
120
5.10M
   simplified with Z2 = 1
121
5.10M
   */
122
5.10M
123
5.10M
   const BigInt& p = m_curve.get_p();
124
5.10M
125
5.10M
   m_curve.sqr(T3, m_coord_z, ws); // z1^2
126
5.10M
   m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2
127
5.10M
128
5.10M
   m_curve.mul(T2, m_coord_z, T3, ws); // z1^3
129
5.10M
   m_curve.mul(T0, y_words, y_size, T2, ws); // y2*z1^3
130
5.10M
131
5.10M
   T4.mod_sub(m_coord_x, p, sub_ws); // x2*z1^2 - x1*z2^2
132
5.10M
133
5.10M
   T0.mod_sub(m_coord_y, p, sub_ws);
134
5.10M
135
5.10M
   if(T4.is_zero())
136
867
      {
137
867
      if(T0.is_zero())
138
46
         {
139
46
         mult2(ws_bn);
140
46
         return;
141
46
         }
142
821
143
821
      // setting to zero:
144
821
      m_coord_x.clear();
145
821
      m_coord_y = m_curve.get_1_rep();
146
821
      m_coord_z.clear();
147
821
      return;
148
821
      }
149
5.10M
150
5.10M
   m_curve.sqr(T2, T4, ws);
151
5.10M
152
5.10M
   m_curve.mul(T3, m_coord_x, T2, ws);
153
5.10M
154
5.10M
   m_curve.mul(T1, T2, T4, ws);
155
5.10M
156
5.10M
   m_curve.sqr(m_coord_x, T0, ws);
157
5.10M
   m_coord_x.mod_sub(T1, p, sub_ws);
158
5.10M
159
5.10M
   m_coord_x.mod_sub(T3, p, sub_ws);
160
5.10M
   m_coord_x.mod_sub(T3, p, sub_ws);
161
5.10M
162
5.10M
   T3.mod_sub(m_coord_x, p, sub_ws);
163
5.10M
164
5.10M
   m_curve.mul(T2, T0, T3, ws);
165
5.10M
   m_curve.mul(T0, m_coord_y, T1, ws);
166
5.10M
   T2.mod_sub(T0, p, sub_ws);
167
5.10M
   m_coord_y.swap(T2);
168
5.10M
169
5.10M
   m_curve.mul(T0, m_coord_z, T4, ws);
170
5.10M
   m_coord_z.swap(T0);
171
5.10M
   }
172
173
void PointGFp::add(const word x_words[], size_t x_size,
174
                   const word y_words[], size_t y_size,
175
                   const word z_words[], size_t z_size,
176
                   std::vector<BigInt>& ws_bn)
177
4.90M
   {
178
4.90M
   if(all_zeros(x_words, x_size) & all_zeros(z_words, z_size))
179
533k
      return;
180
4.36M
181
4.36M
   if(is_zero())
182
49.9k
      {
183
49.9k
      m_coord_x.set_words(x_words, x_size);
184
49.9k
      m_coord_y.set_words(y_words, y_size);
185
49.9k
      m_coord_z.set_words(z_words, z_size);
186
49.9k
      return;
187
49.9k
      }
188
4.31M
189
4.31M
   resize_ws(ws_bn, m_curve.get_ws_size());
190
4.31M
191
4.31M
   secure_vector<word>& ws = ws_bn[0].get_word_vector();
192
4.31M
   secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
193
4.31M
194
4.31M
   BigInt& T0 = ws_bn[2];
195
4.31M
   BigInt& T1 = ws_bn[3];
196
4.31M
   BigInt& T2 = ws_bn[4];
197
4.31M
   BigInt& T3 = ws_bn[5];
198
4.31M
   BigInt& T4 = ws_bn[6];
199
4.31M
   BigInt& T5 = ws_bn[7];
200
4.31M
201
4.31M
   /*
202
4.31M
   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
203
4.31M
   */
204
4.31M
205
4.31M
   const BigInt& p = m_curve.get_p();
206
4.31M
207
4.31M
   m_curve.sqr(T0, z_words, z_size, ws); // z2^2
208
4.31M
   m_curve.mul(T1, m_coord_x, T0, ws); // x1*z2^2
209
4.31M
   m_curve.mul(T3, z_words, z_size, T0, ws); // z2^3
210
4.31M
   m_curve.mul(T2, m_coord_y, T3, ws); // y1*z2^3
211
4.31M
212
4.31M
   m_curve.sqr(T3, m_coord_z, ws); // z1^2
213
4.31M
   m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2
214
4.31M
215
4.31M
   m_curve.mul(T5, m_coord_z, T3, ws); // z1^3
216
4.31M
   m_curve.mul(T0, y_words, y_size, T5, ws); // y2*z1^3
217
4.31M
218
4.31M
   T4.mod_sub(T1, p, sub_ws); // x2*z1^2 - x1*z2^2
219
4.31M
220
4.31M
   T0.mod_sub(T2, p, sub_ws);
221
4.31M
222
4.31M
   if(T4.is_zero())
223
17.8k
      {
224
17.8k
      if(T0.is_zero())
225
5.30k
         {
226
5.30k
         mult2(ws_bn);
227
5.30k
         return;
228
5.30k
         }
229
12.5k
230
12.5k
      // setting to zero:
231
12.5k
      m_coord_x.clear();
232
12.5k
      m_coord_y = m_curve.get_1_rep();
233
12.5k
      m_coord_z.clear();
234
12.5k
      return;
235
12.5k
      }
236
4.30M
237
4.30M
   m_curve.sqr(T5, T4, ws);
238
4.30M
239
4.30M
   m_curve.mul(T3, T1, T5, ws);
240
4.30M
241
4.30M
   m_curve.mul(T1, T5, T4, ws);
242
4.30M
243
4.30M
   m_curve.sqr(m_coord_x, T0, ws);
244
4.30M
   m_coord_x.mod_sub(T1, p, sub_ws);
245
4.30M
   m_coord_x.mod_sub(T3, p, sub_ws);
246
4.30M
   m_coord_x.mod_sub(T3, p, sub_ws);
247
4.30M
248
4.30M
   T3.mod_sub(m_coord_x, p, sub_ws);
249
4.30M
250
4.30M
   m_curve.mul(m_coord_y, T0, T3, ws);
251
4.30M
   m_curve.mul(T3, T2, T1, ws);
252
4.30M
253
4.30M
   m_coord_y.mod_sub(T3, p, sub_ws);
254
4.30M
255
4.30M
   m_curve.mul(T3, z_words, z_size, m_coord_z, ws);
256
4.30M
   m_curve.mul(m_coord_z, T3, T4, ws);
257
4.30M
   }
258
259
void PointGFp::mult2i(size_t iterations, std::vector<BigInt>& ws_bn)
260
3.48M
   {
261
3.48M
   if(iterations == 0)
262
0
      return;
263
3.48M
264
3.48M
   if(m_coord_y.is_zero())
265
0
      {
266
0
      *this = PointGFp(m_curve); // setting myself to zero
267
0
      return;
268
0
      }
269
3.48M
270
3.48M
   /*
271
3.48M
   TODO we can save 2 squarings per iteration by computing
272
3.48M
   a*Z^4 using values cached from previous iteration
273
3.48M
   */
274
17.2M
   for(size_t i = 0; i != iterations; ++i)
275
13.7M
      mult2(ws_bn);
276
3.48M
   }
277
278
// *this *= 2
279
void PointGFp::mult2(std::vector<BigInt>& ws_bn)
280
15.0M
   {
281
15.0M
   if(is_zero())
282
1.23M
      return;
283
13.7M
284
13.7M
   if(m_coord_y.is_zero())
285
4.07k
      {
286
4.07k
      *this = PointGFp(m_curve); // setting myself to zero
287
4.07k
      return;
288
4.07k
      }
289
13.7M
290
13.7M
   resize_ws(ws_bn, m_curve.get_ws_size());
291
13.7M
292
13.7M
   secure_vector<word>& ws = ws_bn[0].get_word_vector();
293
13.7M
   secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
294
13.7M
295
13.7M
   BigInt& T0 = ws_bn[2];
296
13.7M
   BigInt& T1 = ws_bn[3];
297
13.7M
   BigInt& T2 = ws_bn[4];
298
13.7M
   BigInt& T3 = ws_bn[5];
299
13.7M
   BigInt& T4 = ws_bn[6];
300
13.7M
301
13.7M
   /*
302
13.7M
   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc
303
13.7M
   */
304
13.7M
   const BigInt& p = m_curve.get_p();
305
13.7M
306
13.7M
   m_curve.sqr(T0, m_coord_y, ws);
307
13.7M
308
13.7M
   m_curve.mul(T1, m_coord_x, T0, ws);
309
13.7M
   T1.mod_mul(4, p, sub_ws);
310
13.7M
311
13.7M
   if(m_curve.a_is_zero())
312
143k
      {
313
143k
      // if a == 0 then 3*x^2 + a*z^4 is just 3*x^2
314
143k
      m_curve.sqr(T4, m_coord_x, ws); // x^2
315
143k
      T4.mod_mul(3, p, sub_ws); // 3*x^2
316
143k
      }
317
13.6M
   else if(m_curve.a_is_minus_3())
318
11.2M
      {
319
11.2M
      /*
320
11.2M
      if a == -3 then
321
11.2M
        3*x^2 + a*z^4 == 3*x^2 - 3*z^4 == 3*(x^2-z^4) == 3*(x-z^2)*(x+z^2)
322
11.2M
      */
323
11.2M
      m_curve.sqr(T3, m_coord_z, ws); // z^2
324
11.2M
325
11.2M
      // (x-z^2)
326
11.2M
      T2 = m_coord_x;
327
11.2M
      T2.mod_sub(T3, p, sub_ws);
328
11.2M
329
11.2M
      // (x+z^2)
330
11.2M
      T3.mod_add(m_coord_x, p, sub_ws);
331
11.2M
332
11.2M
      m_curve.mul(T4, T2, T3, ws); // (x-z^2)*(x+z^2)
333
11.2M
334
11.2M
      T4.mod_mul(3, p, sub_ws); // 3*(x-z^2)*(x+z^2)
335
11.2M
      }
336
2.35M
   else
337
2.35M
      {
338
2.35M
      m_curve.sqr(T3, m_coord_z, ws); // z^2
339
2.35M
      m_curve.sqr(T4, T3, ws); // z^4
340
2.35M
      m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); // a*z^4
341
2.35M
342
2.35M
      m_curve.sqr(T4, m_coord_x, ws); // x^2
343
2.35M
      T4.mod_mul(3, p, sub_ws);
344
2.35M
      T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4
345
2.35M
      }
346
13.7M
347
13.7M
   m_curve.sqr(T2, T4, ws);
348
13.7M
   T2.mod_sub(T1, p, sub_ws);
349
13.7M
   T2.mod_sub(T1, p, sub_ws);
350
13.7M
351
13.7M
   m_curve.sqr(T3, T0, ws);
352
13.7M
   T3.mod_mul(8, p, sub_ws);
353
13.7M
354
13.7M
   T1.mod_sub(T2, p, sub_ws);
355
13.7M
356
13.7M
   m_curve.mul(T0, T4, T1, ws);
357
13.7M
   T0.mod_sub(T3, p, sub_ws);
358
13.7M
359
13.7M
   m_coord_x.swap(T2);
360
13.7M
361
13.7M
   m_curve.mul(T2, m_coord_y, m_coord_z, ws);
362
13.7M
   T2.mod_mul(2, p, sub_ws);
363
13.7M
364
13.7M
   m_coord_y.swap(T0);
365
13.7M
   m_coord_z.swap(T2);
366
13.7M
   }
367
368
// arithmetic operators
369
PointGFp& PointGFp::operator+=(const PointGFp& rhs)
370
18.8k
   {
371
18.8k
   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
372
18.8k
   add(rhs, ws);
373
18.8k
   return *this;
374
18.8k
   }
375
376
PointGFp& PointGFp::operator-=(const PointGFp& rhs)
377
0
   {
378
0
   PointGFp minus_rhs = PointGFp(rhs).negate();
379
0
380
0
   if(is_zero())
381
0
      *this = minus_rhs;
382
0
   else
383
0
      *this += minus_rhs;
384
0
385
0
   return *this;
386
0
   }
387
388
PointGFp& PointGFp::operator*=(const BigInt& scalar)
389
0
   {
390
0
   *this = scalar * *this;
391
0
   return *this;
392
0
   }
393
394
PointGFp operator*(const BigInt& scalar, const PointGFp& point)
395
21.2k
   {
396
21.2k
   BOTAN_DEBUG_ASSERT(point.on_the_curve());
397
21.2k
398
21.2k
   const size_t scalar_bits = scalar.bits();
399
21.2k
400
21.2k
   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
401
21.2k
402
21.2k
   PointGFp R[2] = { point.zero(), point };
403
21.2k
404
595k
   for(size_t i = scalar_bits; i > 0; i--)
405
574k
      {
406
574k
      const size_t b = scalar.get_bit(i - 1);
407
574k
      R[b ^ 1].add(R[b], ws);
408
574k
      R[b].mult2(ws);
409
574k
      }
410
21.2k
411
21.2k
   if(scalar.is_negative())
412
0
      R[0].negate();
413
21.2k
414
21.2k
   BOTAN_DEBUG_ASSERT(R[0].on_the_curve());
415
21.2k
416
21.2k
   return R[0];
417
21.2k
   }
418
419
//static
420
void PointGFp::force_all_affine(std::vector<PointGFp>& points,
421
                                secure_vector<word>& ws)
422
2.84k
   {
423
2.84k
   if(points.size() <= 1)
424
0
      {
425
0
      for(size_t i = 0; i != points.size(); ++i)
426
0
         points[i].force_affine();
427
0
      return;
428
0
      }
429
2.84k
430
2.84k
   /*
431
2.84k
   For >= 2 points use Montgomery's trick
432
2.84k
433
2.84k
   See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography"
434
2.84k
   (Hankerson, Menezes, Vanstone)
435
2.84k
436
2.84k
   TODO is it really necessary to save all k points in c?
437
2.84k
   */
438
2.84k
439
2.84k
   const CurveGFp& curve = points[0].m_curve;
440
2.84k
   const BigInt& rep_1 = curve.get_1_rep();
441
2.84k
442
2.84k
   if(ws.size() < curve.get_ws_size())
443
29
      ws.resize(curve.get_ws_size());
444
2.84k
445
2.84k
   std::vector<BigInt> c(points.size());
446
2.84k
   c[0] = points[0].m_coord_z;
447
2.84k
448
1.29M
   for(size_t i = 1; i != points.size(); ++i)
449
1.28M
      {
450
1.28M
      curve.mul(c[i], c[i-1], points[i].m_coord_z, ws);
451
1.28M
      }
452
2.84k
453
2.84k
   BigInt s_inv = curve.invert_element(c[c.size()-1], ws);
454
2.84k
455
2.84k
   BigInt z_inv, z2_inv, z3_inv;
456
2.84k
457
1.29M
   for(size_t i = points.size() - 1; i != 0; i--)
458
1.28M
      {
459
1.28M
      PointGFp& point = points[i];
460
1.28M
461
1.28M
      curve.mul(z_inv, s_inv, c[i-1], ws);
462
1.28M
463
1.28M
      s_inv = curve.mul_to_tmp(s_inv, point.m_coord_z, ws);
464
1.28M
465
1.28M
      curve.sqr(z2_inv, z_inv, ws);
466
1.28M
      curve.mul(z3_inv, z2_inv, z_inv, ws);
467
1.28M
      point.m_coord_x = curve.mul_to_tmp(point.m_coord_x, z2_inv, ws);
468
1.28M
      point.m_coord_y = curve.mul_to_tmp(point.m_coord_y, z3_inv, ws);
469
1.28M
      point.m_coord_z = rep_1;
470
1.28M
      }
471
2.84k
472
2.84k
   curve.sqr(z2_inv, s_inv, ws);
473
2.84k
   curve.mul(z3_inv, z2_inv, s_inv, ws);
474
2.84k
   points[0].m_coord_x = curve.mul_to_tmp(points[0].m_coord_x, z2_inv, ws);
475
2.84k
   points[0].m_coord_y = curve.mul_to_tmp(points[0].m_coord_y, z3_inv, ws);
476
2.84k
   points[0].m_coord_z = rep_1;
477
2.84k
   }
478
479
void PointGFp::force_affine()
480
0
   {
481
0
   if(is_zero())
482
0
      throw Invalid_State("Cannot convert zero ECC point to affine");
483
0
484
0
   secure_vector<word> ws;
485
0
486
0
   const BigInt z_inv = m_curve.invert_element(m_coord_z, ws);
487
0
   const BigInt z2_inv = m_curve.sqr_to_tmp(z_inv, ws);
488
0
   const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws);
489
0
   m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws);
490
0
   m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws);
491
0
   m_coord_z = m_curve.get_1_rep();
492
0
   }
493
494
bool PointGFp::is_affine() const
495
149k
   {
496
149k
   return m_curve.is_one(m_coord_z);
497
149k
   }
498
499
BigInt PointGFp::get_affine_x() const
500
81.7k
   {
501
81.7k
   if(is_zero())
502
1.55k
      throw Illegal_Transformation("Cannot convert zero point to affine");
503
80.1k
504
80.1k
   secure_vector<word> monty_ws;
505
80.1k
506
80.1k
   if(is_affine())
507
326
      return m_curve.from_rep_to_tmp(m_coord_x, monty_ws);
508
79.8k
509
79.8k
   BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
510
79.8k
   z2 = m_curve.invert_element(z2, monty_ws);
511
79.8k
512
79.8k
   BigInt r;
513
79.8k
   m_curve.mul(r, m_coord_x, z2, monty_ws);
514
79.8k
   m_curve.from_rep(r, monty_ws);
515
79.8k
   return r;
516
79.8k
   }
517
518
BigInt PointGFp::get_affine_y() const
519
69.7k
   {
520
69.7k
   if(is_zero())
521
0
      throw Illegal_Transformation("Cannot convert zero point to affine");
522
69.7k
523
69.7k
   secure_vector<word> monty_ws;
524
69.7k
525
69.7k
   if(is_affine())
526
326
      return m_curve.from_rep_to_tmp(m_coord_y, monty_ws);
527
69.3k
528
69.3k
   const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
529
69.3k
   const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
530
69.3k
   const BigInt z3_inv = m_curve.invert_element(z3, monty_ws);
531
69.3k
532
69.3k
   BigInt r;
533
69.3k
   m_curve.mul(r, m_coord_y, z3_inv, monty_ws);
534
69.3k
   m_curve.from_rep(r, monty_ws);
535
69.3k
   return r;
536
69.3k
   }
537
538
bool PointGFp::on_the_curve() const
539
45.1k
   {
540
45.1k
   /*
541
45.1k
   Is the point still on the curve?? (If everything is correct, the
542
45.1k
   point is always on its curve; then the function will return true.
543
45.1k
   If somehow the state is corrupted, which suggests a fault attack
544
45.1k
   (or internal computational error), then return false.
545
45.1k
   */
546
45.1k
   if(is_zero())
547
1.60k
      return true;
548
43.5k
549
43.5k
   secure_vector<word> monty_ws;
550
43.5k
551
43.5k
   const BigInt y2 = m_curve.from_rep_to_tmp(m_curve.sqr_to_tmp(m_coord_y, monty_ws), monty_ws);
552
43.5k
   const BigInt x3 = m_curve.mul_to_tmp(m_coord_x, m_curve.sqr_to_tmp(m_coord_x, monty_ws), monty_ws);
553
43.5k
   const BigInt ax = m_curve.mul_to_tmp(m_coord_x, m_curve.get_a_rep(), monty_ws);
554
43.5k
   const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
555
43.5k
556
43.5k
   if(m_coord_z == z2) // Is z equal to 1 (in Montgomery form)?
557
15.2k
      {
558
15.2k
      if(y2 != m_curve.from_rep_to_tmp(x3 + ax + m_curve.get_b_rep(), monty_ws))
559
243
         return false;
560
43.2k
      }
561
43.2k
562
43.2k
   const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
563
43.2k
   const BigInt ax_z4 = m_curve.mul_to_tmp(ax, m_curve.sqr_to_tmp(z2, monty_ws), monty_ws);
564
43.2k
   const BigInt b_z6 = m_curve.mul_to_tmp(m_curve.get_b_rep(), m_curve.sqr_to_tmp(z3, monty_ws), monty_ws);
565
43.2k
566
43.2k
   if(y2 != m_curve.from_rep_to_tmp(x3 + ax_z4 + b_z6, monty_ws))
567
3
      return false;
568
43.2k
569
43.2k
   return true;
570
43.2k
   }
571
572
// swaps the states of *this and other, does not throw!
573
void PointGFp::swap(PointGFp& other)
574
1.47M
   {
575
1.47M
   m_curve.swap(other.m_curve);
576
1.47M
   m_coord_x.swap(other.m_coord_x);
577
1.47M
   m_coord_y.swap(other.m_coord_y);
578
1.47M
   m_coord_z.swap(other.m_coord_z);
579
1.47M
   }
580
581
bool PointGFp::operator==(const PointGFp& other) const
582
25.0k
   {
583
25.0k
   if(m_curve != other.m_curve)
584
0
      return false;
585
25.0k
586
25.0k
   // If this is zero, only equal if other is also zero
587
25.0k
   if(is_zero())
588
88
      return other.is_zero();
589
24.9k
590
24.9k
   return (get_affine_x() == other.get_affine_x() &&
591
24.9k
           get_affine_y() == other.get_affine_y());
592
24.9k
   }
593
594
// encoding and decoding
595
std::vector<uint8_t> PointGFp::encode(PointGFp::Compression_Type format) const
596
19.7k
   {
597
19.7k
   if(is_zero())
598
0
      return std::vector<uint8_t>(1); // single 0 byte
599
19.7k
600
19.7k
   const size_t p_bytes = m_curve.get_p().bytes();
601
19.7k
602
19.7k
   const BigInt x = get_affine_x();
603
19.7k
   const BigInt y = get_affine_y();
604
19.7k
605
19.7k
   std::vector<uint8_t> result;
606
19.7k
607
19.7k
   if(format == PointGFp::UNCOMPRESSED)
608
19.4k
      {
609
19.4k
      result.resize(1 + 2*p_bytes);
610
19.4k
      result[0] = 0x04;
611
19.4k
      BigInt::encode_1363(&result[1], p_bytes, x);
612
19.4k
      BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
613
19.4k
      }
614
262
   else if(format == PointGFp::COMPRESSED)
615
262
      {
616
262
      result.resize(1 + p_bytes);
617
262
      result[0] = 0x02 | static_cast<uint8_t>(y.get_bit(0));
618
262
      BigInt::encode_1363(&result[1], p_bytes, x);
619
262
      }
620
0
   else if(format == PointGFp::HYBRID)
621
0
      {
622
0
      result.resize(1 + 2*p_bytes);
623
0
      result[0] = 0x06 | static_cast<uint8_t>(y.get_bit(0));
624
0
      BigInt::encode_1363(&result[1], p_bytes, x);
625
0
      BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
626
0
      }
627
0
   else
628
0
      throw Invalid_Argument("EC2OSP illegal point encoding");
629
19.7k
630
19.7k
   return result;
631
19.7k
   }
632
633
namespace {
634
635
BigInt decompress_point(bool yMod2,
636
                        const BigInt& x,
637
                        const BigInt& curve_p,
638
                        const BigInt& curve_a,
639
                        const BigInt& curve_b)
640
20.0k
   {
641
20.0k
   BigInt xpow3 = x * x * x;
642
20.0k
643
20.0k
   BigInt g = curve_a * x;
644
20.0k
   g += xpow3;
645
20.0k
   g += curve_b;
646
20.0k
   g = g % curve_p;
647
20.0k
648
20.0k
   BigInt z = ressol(g, curve_p);
649
20.0k
650
20.0k
   if(z < 0)
651
4.23k
      throw Illegal_Point("error during EC point decompression");
652
15.8k
653
15.8k
   if(z.get_bit(0) != yMod2)
654
7.05k
      z = curve_p - z;
655
15.8k
656
15.8k
   return z;
657
15.8k
   }
658
659
}
660
661
PointGFp OS2ECP(const uint8_t data[], size_t data_len,
662
                const CurveGFp& curve)
663
22.9k
   {
664
22.9k
   // Should we really be doing this?
665
22.9k
   if(data_len <= 1)
666
1.69k
      return PointGFp(curve); // return zero
667
21.2k
668
21.2k
   std::pair<BigInt, BigInt> xy = OS2ECP(data, data_len, curve.get_p(), curve.get_a(), curve.get_b());
669
21.2k
670
21.2k
   PointGFp point(curve, xy.first, xy.second);
671
21.2k
672
21.2k
   if(!point.on_the_curve())
673
239
      throw Illegal_Point("OS2ECP: Decoded point was not on the curve");
674
20.9k
675
20.9k
   return point;
676
20.9k
   }
677
678
std::pair<BigInt, BigInt> OS2ECP(const uint8_t data[], size_t data_len,
679
                                 const BigInt& curve_p,
680
                                 const BigInt& curve_a,
681
                                 const BigInt& curve_b)
682
21.4k
   {
683
21.4k
   if(data_len <= 1)
684
3
      throw Decoding_Error("OS2ECP invalid point");
685
21.4k
686
21.4k
   const uint8_t pc = data[0];
687
21.4k
688
21.4k
   BigInt x, y;
689
21.4k
690
21.4k
   if(pc == 2 || pc == 3)
691
19.1k
      {
692
19.1k
      //compressed form
693
19.1k
      x = BigInt::decode(&data[1], data_len - 1);
694
19.1k
695
19.1k
      const bool y_mod_2 = ((pc & 0x01) == 1);
696
19.1k
      y = decompress_point(y_mod_2, x, curve_p, curve_a, curve_b);
697
19.1k
      }
698
2.25k
   else if(pc == 4)
699
1.13k
      {
700
1.13k
      const size_t l = (data_len - 1) / 2;
701
1.13k
702
1.13k
      // uncompressed form
703
1.13k
      x = BigInt::decode(&data[1], l);
704
1.13k
      y = BigInt::decode(&data[l+1], l);
705
1.13k
      }
706
1.12k
   else if(pc == 6 || pc == 7)
707
883
      {
708
883
      const size_t l = (data_len - 1) / 2;
709
883
710
883
      // hybrid form
711
883
      x = BigInt::decode(&data[1], l);
712
883
      y = BigInt::decode(&data[l+1], l);
713
883
714
883
      const bool y_mod_2 = ((pc & 0x01) == 1);
715
883
716
883
      if(decompress_point(y_mod_2, x, curve_p, curve_a, curve_b) != y)
717
268
         throw Illegal_Point("OS2ECP: Decoding error in hybrid format");
718
238
      }
719
238
   else
720
238
      throw Invalid_Argument("OS2ECP: Unknown format type " + std::to_string(pc));
721
20.9k
722
20.9k
   return std::make_pair(x, y);
723
20.9k
   }
724
725
}