Coverage Report

Created: 2020-05-23 13:54

/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
87.8k
   {
24
87.8k
   // Assumes Montgomery rep of zero is zero
25
87.8k
   }
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
18.6k
   {
33
18.6k
   if(x < 0 || x >= curve.get_p())
34
1.25k
      throw Invalid_Argument("Invalid PointGFp affine x");
35
17.3k
   if(y < 0 || y >= curve.get_p())
36
1.44k
      throw Invalid_Argument("Invalid PointGFp affine y");
37
15.9k
38
15.9k
   secure_vector<word> monty_ws(m_curve.get_ws_size());
39
15.9k
   m_curve.to_rep(m_coord_x, monty_ws);
40
15.9k
   m_curve.to_rep(m_coord_y, monty_ws);
41
15.9k
   }
42
43
void PointGFp::randomize_repr(RandomNumberGenerator& rng)
44
10.2k
   {
45
10.2k
   secure_vector<word> ws(m_curve.get_ws_size());
46
10.2k
   randomize_repr(rng, ws);
47
10.2k
   }
48
49
void PointGFp::randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws)
50
53.4k
   {
51
53.4k
   const BigInt mask = BigInt::random_integer(rng, 2, m_curve.get_p());
52
53.4k
53
53.4k
   /*
54
53.4k
   * No reason to convert this to Montgomery representation first,
55
53.4k
   * just pretend the random mask was chosen as Redc(mask) and the
56
53.4k
   * random mask we generated above is in the Montgomery
57
53.4k
   * representation.
58
53.4k
   * //m_curve.to_rep(mask, ws);
59
53.4k
   */
60
53.4k
   const BigInt mask2 = m_curve.sqr_to_tmp(mask, ws);
61
53.4k
   const BigInt mask3 = m_curve.mul_to_tmp(mask2, mask, ws);
62
53.4k
63
53.4k
   m_coord_x = m_curve.mul_to_tmp(m_coord_x, mask2, ws);
64
53.4k
   m_coord_y = m_curve.mul_to_tmp(m_coord_y, mask3, ws);
65
53.4k
   m_coord_z = m_curve.mul_to_tmp(m_coord_z, mask, ws);
66
53.4k
   }
67
68
namespace {
69
70
inline void resize_ws(std::vector<BigInt>& ws_bn, size_t cap_size)
71
20.1M
   {
72
20.1M
   BOTAN_ASSERT(ws_bn.size() >= PointGFp::WORKSPACE_SIZE,
73
20.1M
                "Expected size for PointGFp workspace");
74
20.1M
75
181M
   for(size_t i = 0; i != ws_bn.size(); ++i)
76
161M
      if(ws_bn[i].size() < cap_size)
77
13.0M
         ws_bn[i].get_word_vector().resize(cap_size);
78
20.1M
   }
79
80
inline word all_zeros(const word x[], size_t len)
81
18.7M
   {
82
18.7M
   word z = 0;
83
153M
   for(size_t i = 0; i != len; ++i)
84
134M
      z |= x[i];
85
18.7M
   return CT::Mask<word>::is_zero(z).value();
86
18.7M
   }
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.05M
   {
94
5.05M
   if(all_zeros(x_words, x_size) & all_zeros(y_words, y_size))
95
625k
      {
96
625k
      return;
97
625k
      }
98
4.43M
99
4.43M
   if(is_zero())
100
24.1k
      {
101
24.1k
      m_coord_x.set_words(x_words, x_size);
102
24.1k
      m_coord_y.set_words(y_words, y_size);
103
24.1k
      m_coord_z = m_curve.get_1_rep();
104
24.1k
      return;
105
24.1k
      }
106
4.40M
107
4.40M
   resize_ws(ws_bn, m_curve.get_ws_size());
108
4.40M
109
4.40M
   secure_vector<word>& ws = ws_bn[0].get_word_vector();
110
4.40M
   secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
111
4.40M
112
4.40M
   BigInt& T0 = ws_bn[2];
113
4.40M
   BigInt& T1 = ws_bn[3];
114
4.40M
   BigInt& T2 = ws_bn[4];
115
4.40M
   BigInt& T3 = ws_bn[5];
116
4.40M
   BigInt& T4 = ws_bn[6];
117
4.40M
118
4.40M
   /*
119
4.40M
   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
120
4.40M
   simplified with Z2 = 1
121
4.40M
   */
122
4.40M
123
4.40M
   const BigInt& p = m_curve.get_p();
124
4.40M
125
4.40M
   m_curve.sqr(T3, m_coord_z, ws); // z1^2
126
4.40M
   m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2
127
4.40M
128
4.40M
   m_curve.mul(T2, m_coord_z, T3, ws); // z1^3
129
4.40M
   m_curve.mul(T0, y_words, y_size, T2, ws); // y2*z1^3
130
4.40M
131
4.40M
   T4.mod_sub(m_coord_x, p, sub_ws); // x2*z1^2 - x1*z2^2
132
4.40M
133
4.40M
   T0.mod_sub(m_coord_y, p, sub_ws);
134
4.40M
135
4.40M
   if(T4.is_zero())
136
635
      {
137
635
      if(T0.is_zero())
138
37
         {
139
37
         mult2(ws_bn);
140
37
         return;
141
37
         }
142
598
143
598
      // setting to zero:
144
598
      m_coord_x.clear();
145
598
      m_coord_y = m_curve.get_1_rep();
146
598
      m_coord_z.clear();
147
598
      return;
148
598
      }
149
4.40M
150
4.40M
   m_curve.sqr(T2, T4, ws);
151
4.40M
152
4.40M
   m_curve.mul(T3, m_coord_x, T2, ws);
153
4.40M
154
4.40M
   m_curve.mul(T1, T2, T4, ws);
155
4.40M
156
4.40M
   m_curve.sqr(m_coord_x, T0, ws);
157
4.40M
   m_coord_x.mod_sub(T1, p, sub_ws);
158
4.40M
159
4.40M
   m_coord_x.mod_sub(T3, p, sub_ws);
160
4.40M
   m_coord_x.mod_sub(T3, p, sub_ws);
161
4.40M
162
4.40M
   T3.mod_sub(m_coord_x, p, sub_ws);
163
4.40M
164
4.40M
   m_curve.mul(T2, T0, T3, ws);
165
4.40M
   m_curve.mul(T0, m_coord_y, T1, ws);
166
4.40M
   T2.mod_sub(T0, p, sub_ws);
167
4.40M
   m_coord_y.swap(T2);
168
4.40M
169
4.40M
   m_curve.mul(T0, m_coord_z, T4, ws);
170
4.40M
   m_coord_z.swap(T0);
171
4.40M
   }
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.31M
   {
178
4.31M
   if(all_zeros(x_words, x_size) & all_zeros(z_words, z_size))
179
462k
      return;
180
3.85M
181
3.85M
   if(is_zero())
182
46.8k
      {
183
46.8k
      m_coord_x.set_words(x_words, x_size);
184
46.8k
      m_coord_y.set_words(y_words, y_size);
185
46.8k
      m_coord_z.set_words(z_words, z_size);
186
46.8k
      return;
187
46.8k
      }
188
3.80M
189
3.80M
   resize_ws(ws_bn, m_curve.get_ws_size());
190
3.80M
191
3.80M
   secure_vector<word>& ws = ws_bn[0].get_word_vector();
192
3.80M
   secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
193
3.80M
194
3.80M
   BigInt& T0 = ws_bn[2];
195
3.80M
   BigInt& T1 = ws_bn[3];
196
3.80M
   BigInt& T2 = ws_bn[4];
197
3.80M
   BigInt& T3 = ws_bn[5];
198
3.80M
   BigInt& T4 = ws_bn[6];
199
3.80M
   BigInt& T5 = ws_bn[7];
200
3.80M
201
3.80M
   /*
202
3.80M
   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
203
3.80M
   */
204
3.80M
205
3.80M
   const BigInt& p = m_curve.get_p();
206
3.80M
207
3.80M
   m_curve.sqr(T0, z_words, z_size, ws); // z2^2
208
3.80M
   m_curve.mul(T1, m_coord_x, T0, ws); // x1*z2^2
209
3.80M
   m_curve.mul(T3, z_words, z_size, T0, ws); // z2^3
210
3.80M
   m_curve.mul(T2, m_coord_y, T3, ws); // y1*z2^3
211
3.80M
212
3.80M
   m_curve.sqr(T3, m_coord_z, ws); // z1^2
213
3.80M
   m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2
214
3.80M
215
3.80M
   m_curve.mul(T5, m_coord_z, T3, ws); // z1^3
216
3.80M
   m_curve.mul(T0, y_words, y_size, T5, ws); // y2*z1^3
217
3.80M
218
3.80M
   T4.mod_sub(T1, p, sub_ws); // x2*z1^2 - x1*z2^2
219
3.80M
220
3.80M
   T0.mod_sub(T2, p, sub_ws);
221
3.80M
222
3.80M
   if(T4.is_zero())
223
21.4k
      {
224
21.4k
      if(T0.is_zero())
225
5.85k
         {
226
5.85k
         mult2(ws_bn);
227
5.85k
         return;
228
5.85k
         }
229
15.5k
230
15.5k
      // setting to zero:
231
15.5k
      m_coord_x.clear();
232
15.5k
      m_coord_y = m_curve.get_1_rep();
233
15.5k
      m_coord_z.clear();
234
15.5k
      return;
235
15.5k
      }
236
3.78M
237
3.78M
   m_curve.sqr(T5, T4, ws);
238
3.78M
239
3.78M
   m_curve.mul(T3, T1, T5, ws);
240
3.78M
241
3.78M
   m_curve.mul(T1, T5, T4, ws);
242
3.78M
243
3.78M
   m_curve.sqr(m_coord_x, T0, ws);
244
3.78M
   m_coord_x.mod_sub(T1, p, sub_ws);
245
3.78M
   m_coord_x.mod_sub(T3, p, sub_ws);
246
3.78M
   m_coord_x.mod_sub(T3, p, sub_ws);
247
3.78M
248
3.78M
   T3.mod_sub(m_coord_x, p, sub_ws);
249
3.78M
250
3.78M
   m_curve.mul(m_coord_y, T0, T3, ws);
251
3.78M
   m_curve.mul(T3, T2, T1, ws);
252
3.78M
253
3.78M
   m_coord_y.mod_sub(T3, p, sub_ws);
254
3.78M
255
3.78M
   m_curve.mul(T3, z_words, z_size, m_coord_z, ws);
256
3.78M
   m_curve.mul(m_coord_z, T3, T4, ws);
257
3.78M
   }
258
259
void PointGFp::mult2i(size_t iterations, std::vector<BigInt>& ws_bn)
260
2.98M
   {
261
2.98M
   if(iterations == 0)
262
0
      return;
263
2.98M
264
2.98M
   if(m_coord_y.is_zero())
265
0
      {
266
0
      *this = PointGFp(m_curve); // setting myself to zero
267
0
      return;
268
0
      }
269
2.98M
270
2.98M
   /*
271
2.98M
   TODO we can save 2 squarings per iteration by computing
272
2.98M
   a*Z^4 using values cached from previous iteration
273
2.98M
   */
274
14.7M
   for(size_t i = 0; i != iterations; ++i)
275
11.8M
      mult2(ws_bn);
276
2.98M
   }
277
278
// *this *= 2
279
void PointGFp::mult2(std::vector<BigInt>& ws_bn)
280
12.9M
   {
281
12.9M
   if(is_zero())
282
1.04M
      return;
283
11.9M
284
11.9M
   if(m_coord_y.is_zero())
285
5.00k
      {
286
5.00k
      *this = PointGFp(m_curve); // setting myself to zero
287
5.00k
      return;
288
5.00k
      }
289
11.9M
290
11.9M
   resize_ws(ws_bn, m_curve.get_ws_size());
291
11.9M
292
11.9M
   secure_vector<word>& ws = ws_bn[0].get_word_vector();
293
11.9M
   secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
294
11.9M
295
11.9M
   BigInt& T0 = ws_bn[2];
296
11.9M
   BigInt& T1 = ws_bn[3];
297
11.9M
   BigInt& T2 = ws_bn[4];
298
11.9M
   BigInt& T3 = ws_bn[5];
299
11.9M
   BigInt& T4 = ws_bn[6];
300
11.9M
301
11.9M
   /*
302
11.9M
   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc
303
11.9M
   */
304
11.9M
   const BigInt& p = m_curve.get_p();
305
11.9M
306
11.9M
   m_curve.sqr(T0, m_coord_y, ws);
307
11.9M
308
11.9M
   m_curve.mul(T1, m_coord_x, T0, ws);
309
11.9M
   T1.mod_mul(4, p, sub_ws);
310
11.9M
311
11.9M
   if(m_curve.a_is_zero())
312
129k
      {
313
129k
      // if a == 0 then 3*x^2 + a*z^4 is just 3*x^2
314
129k
      m_curve.sqr(T4, m_coord_x, ws); // x^2
315
129k
      T4.mod_mul(3, p, sub_ws); // 3*x^2
316
129k
      }
317
11.8M
   else if(m_curve.a_is_minus_3())
318
9.98M
      {
319
9.98M
      /*
320
9.98M
      if a == -3 then
321
9.98M
        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
9.98M
      */
323
9.98M
      m_curve.sqr(T3, m_coord_z, ws); // z^2
324
9.98M
325
9.98M
      // (x-z^2)
326
9.98M
      T2 = m_coord_x;
327
9.98M
      T2.mod_sub(T3, p, sub_ws);
328
9.98M
329
9.98M
      // (x+z^2)
330
9.98M
      T3.mod_add(m_coord_x, p, sub_ws);
331
9.98M
332
9.98M
      m_curve.mul(T4, T2, T3, ws); // (x-z^2)*(x+z^2)
333
9.98M
334
9.98M
      T4.mod_mul(3, p, sub_ws); // 3*(x-z^2)*(x+z^2)
335
9.98M
      }
336
1.82M
   else
337
1.82M
      {
338
1.82M
      m_curve.sqr(T3, m_coord_z, ws); // z^2
339
1.82M
      m_curve.sqr(T4, T3, ws); // z^4
340
1.82M
      m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); // a*z^4
341
1.82M
342
1.82M
      m_curve.sqr(T4, m_coord_x, ws); // x^2
343
1.82M
      T4.mod_mul(3, p, sub_ws);
344
1.82M
      T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4
345
1.82M
      }
346
11.9M
347
11.9M
   m_curve.sqr(T2, T4, ws);
348
11.9M
   T2.mod_sub(T1, p, sub_ws);
349
11.9M
   T2.mod_sub(T1, p, sub_ws);
350
11.9M
351
11.9M
   m_curve.sqr(T3, T0, ws);
352
11.9M
   T3.mod_mul(8, p, sub_ws);
353
11.9M
354
11.9M
   T1.mod_sub(T2, p, sub_ws);
355
11.9M
356
11.9M
   m_curve.mul(T0, T4, T1, ws);
357
11.9M
   T0.mod_sub(T3, p, sub_ws);
358
11.9M
359
11.9M
   m_coord_x.swap(T2);
360
11.9M
361
11.9M
   m_curve.mul(T2, m_coord_y, m_coord_z, ws);
362
11.9M
   T2.mod_mul(2, p, sub_ws);
363
11.9M
364
11.9M
   m_coord_y.swap(T0);
365
11.9M
   m_coord_z.swap(T2);
366
11.9M
   }
367
368
// arithmetic operators
369
PointGFp& PointGFp::operator+=(const PointGFp& rhs)
370
15.5k
   {
371
15.5k
   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
372
15.5k
   add(rhs, ws);
373
15.5k
   return *this;
374
15.5k
   }
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
18.3k
   {
396
18.3k
   BOTAN_DEBUG_ASSERT(point.on_the_curve());
397
18.3k
398
18.3k
   const size_t scalar_bits = scalar.bits();
399
18.3k
400
18.3k
   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
401
18.3k
402
18.3k
   PointGFp R[2] = { point.zero(), point };
403
18.3k
404
582k
   for(size_t i = scalar_bits; i > 0; i--)
405
563k
      {
406
563k
      const size_t b = scalar.get_bit(i - 1);
407
563k
      R[b ^ 1].add(R[b], ws);
408
563k
      R[b].mult2(ws);
409
563k
      }
410
18.3k
411
18.3k
   if(scalar.is_negative())
412
0
      R[0].negate();
413
18.3k
414
18.3k
   BOTAN_DEBUG_ASSERT(R[0].on_the_curve());
415
18.3k
416
18.3k
   return R[0];
417
18.3k
   }
418
419
//static
420
void PointGFp::force_all_affine(std::vector<PointGFp>& points,
421
                                secure_vector<word>& ws)
422
2.29k
   {
423
2.29k
   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.29k
430
2.29k
   /*
431
2.29k
   For >= 2 points use Montgomery's trick
432
2.29k
433
2.29k
   See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography"
434
2.29k
   (Hankerson, Menezes, Vanstone)
435
2.29k
436
2.29k
   TODO is it really necessary to save all k points in c?
437
2.29k
   */
438
2.29k
439
2.29k
   const CurveGFp& curve = points[0].m_curve;
440
2.29k
   const BigInt& rep_1 = curve.get_1_rep();
441
2.29k
442
2.29k
   if(ws.size() < curve.get_ws_size())
443
32
      ws.resize(curve.get_ws_size());
444
2.29k
445
2.29k
   std::vector<BigInt> c(points.size());
446
2.29k
   c[0] = points[0].m_coord_z;
447
2.29k
448
1.15M
   for(size_t i = 1; i != points.size(); ++i)
449
1.15M
      {
450
1.15M
      curve.mul(c[i], c[i-1], points[i].m_coord_z, ws);
451
1.15M
      }
452
2.29k
453
2.29k
   BigInt s_inv = curve.invert_element(c[c.size()-1], ws);
454
2.29k
455
2.29k
   BigInt z_inv, z2_inv, z3_inv;
456
2.29k
457
1.15M
   for(size_t i = points.size() - 1; i != 0; i--)
458
1.15M
      {
459
1.15M
      PointGFp& point = points[i];
460
1.15M
461
1.15M
      curve.mul(z_inv, s_inv, c[i-1], ws);
462
1.15M
463
1.15M
      s_inv = curve.mul_to_tmp(s_inv, point.m_coord_z, ws);
464
1.15M
465
1.15M
      curve.sqr(z2_inv, z_inv, ws);
466
1.15M
      curve.mul(z3_inv, z2_inv, z_inv, ws);
467
1.15M
      point.m_coord_x = curve.mul_to_tmp(point.m_coord_x, z2_inv, ws);
468
1.15M
      point.m_coord_y = curve.mul_to_tmp(point.m_coord_y, z3_inv, ws);
469
1.15M
      point.m_coord_z = rep_1;
470
1.15M
      }
471
2.29k
472
2.29k
   curve.sqr(z2_inv, s_inv, ws);
473
2.29k
   curve.mul(z3_inv, z2_inv, s_inv, ws);
474
2.29k
   points[0].m_coord_x = curve.mul_to_tmp(points[0].m_coord_x, z2_inv, ws);
475
2.29k
   points[0].m_coord_y = curve.mul_to_tmp(points[0].m_coord_y, z3_inv, ws);
476
2.29k
   points[0].m_coord_z = rep_1;
477
2.29k
   }
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
126k
   {
496
126k
   return m_curve.is_one(m_coord_z);
497
126k
   }
498
499
BigInt PointGFp::get_affine_x() const
500
69.3k
   {
501
69.3k
   if(is_zero())
502
1.31k
      throw Illegal_Transformation("Cannot convert zero point to affine");
503
68.0k
504
68.0k
   secure_vector<word> monty_ws;
505
68.0k
506
68.0k
   if(is_affine())
507
246
      return m_curve.from_rep_to_tmp(m_coord_x, monty_ws);
508
67.8k
509
67.8k
   BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
510
67.8k
   z2 = m_curve.invert_element(z2, monty_ws);
511
67.8k
512
67.8k
   BigInt r;
513
67.8k
   m_curve.mul(r, m_coord_x, z2, monty_ws);
514
67.8k
   m_curve.from_rep(r, monty_ws);
515
67.8k
   return r;
516
67.8k
   }
517
518
BigInt PointGFp::get_affine_y() const
519
58.7k
   {
520
58.7k
   if(is_zero())
521
0
      throw Illegal_Transformation("Cannot convert zero point to affine");
522
58.7k
523
58.7k
   secure_vector<word> monty_ws;
524
58.7k
525
58.7k
   if(is_affine())
526
246
      return m_curve.from_rep_to_tmp(m_coord_y, monty_ws);
527
58.5k
528
58.5k
   const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
529
58.5k
   const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
530
58.5k
   const BigInt z3_inv = m_curve.invert_element(z3, monty_ws);
531
58.5k
532
58.5k
   BigInt r;
533
58.5k
   m_curve.mul(r, m_coord_y, z3_inv, monty_ws);
534
58.5k
   m_curve.from_rep(r, monty_ws);
535
58.5k
   return r;
536
58.5k
   }
537
538
bool PointGFp::on_the_curve() const
539
39.8k
   {
540
39.8k
   /*
541
39.8k
   Is the point still on the curve?? (If everything is correct, the
542
39.8k
   point is always on its curve; then the function will return true.
543
39.8k
   If somehow the state is corrupted, which suggests a fault attack
544
39.8k
   (or internal computational error), then return false.
545
39.8k
   */
546
39.8k
   if(is_zero())
547
1.36k
      return true;
548
38.4k
549
38.4k
   secure_vector<word> monty_ws;
550
38.4k
551
38.4k
   const BigInt y2 = m_curve.from_rep_to_tmp(m_curve.sqr_to_tmp(m_coord_y, monty_ws), monty_ws);
552
38.4k
   const BigInt x3 = m_curve.mul_to_tmp(m_coord_x, m_curve.sqr_to_tmp(m_coord_x, monty_ws), monty_ws);
553
38.4k
   const BigInt ax = m_curve.mul_to_tmp(m_coord_x, m_curve.get_a_rep(), monty_ws);
554
38.4k
   const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
555
38.4k
556
38.4k
   if(m_coord_z == z2) // Is z equal to 1 (in Montgomery form)?
557
13.3k
      {
558
13.3k
      if(y2 != m_curve.from_rep_to_tmp(x3 + ax + m_curve.get_b_rep(), monty_ws))
559
226
         return false;
560
38.2k
      }
561
38.2k
562
38.2k
   const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
563
38.2k
   const BigInt ax_z4 = m_curve.mul_to_tmp(ax, m_curve.sqr_to_tmp(z2, monty_ws), monty_ws);
564
38.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
38.2k
566
38.2k
   if(y2 != m_curve.from_rep_to_tmp(x3 + ax_z4 + b_z6, monty_ws))
567
2
      return false;
568
38.2k
569
38.2k
   return true;
570
38.2k
   }
571
572
// swaps the states of *this and other, does not throw!
573
void PointGFp::swap(PointGFp& other)
574
1.31M
   {
575
1.31M
   m_curve.swap(other.m_curve);
576
1.31M
   m_coord_x.swap(other.m_coord_x);
577
1.31M
   m_coord_y.swap(other.m_coord_y);
578
1.31M
   m_coord_z.swap(other.m_coord_z);
579
1.31M
   }
580
581
bool PointGFp::operator==(const PointGFp& other) const
582
20.7k
   {
583
20.7k
   if(m_curve != other.m_curve)
584
0
      return false;
585
20.7k
586
20.7k
   // If this is zero, only equal if other is also zero
587
20.7k
   if(is_zero())
588
72
      return other.is_zero();
589
20.7k
590
20.7k
   return (get_affine_x() == other.get_affine_x() &&
591
20.7k
           get_affine_y() == other.get_affine_y());
592
20.7k
   }
593
594
// encoding and decoding
595
std::vector<uint8_t> PointGFp::encode(PointGFp::Compression_Type format) const
596
17.3k
   {
597
17.3k
   if(is_zero())
598
0
      return std::vector<uint8_t>(1); // single 0 byte
599
17.3k
600
17.3k
   const size_t p_bytes = m_curve.get_p().bytes();
601
17.3k
602
17.3k
   const BigInt x = get_affine_x();
603
17.3k
   const BigInt y = get_affine_y();
604
17.3k
605
17.3k
   std::vector<uint8_t> result;
606
17.3k
607
17.3k
   if(format == PointGFp::UNCOMPRESSED)
608
17.2k
      {
609
17.2k
      result.resize(1 + 2*p_bytes);
610
17.2k
      result[0] = 0x04;
611
17.2k
      BigInt::encode_1363(&result[1], p_bytes, x);
612
17.2k
      BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
613
17.2k
      }
614
66
   else if(format == PointGFp::COMPRESSED)
615
66
      {
616
66
      result.resize(1 + p_bytes);
617
66
      result[0] = 0x02 | static_cast<uint8_t>(y.get_bit(0));
618
66
      BigInt::encode_1363(&result[1], p_bytes, x);
619
66
      }
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
17.3k
630
17.3k
   return result;
631
17.3k
   }
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
17.6k
   {
641
17.6k
   BigInt xpow3 = x * x * x;
642
17.6k
643
17.6k
   BigInt g = curve_a * x;
644
17.6k
   g += xpow3;
645
17.6k
   g += curve_b;
646
17.6k
   g = g % curve_p;
647
17.6k
648
17.6k
   BigInt z = ressol(g, curve_p);
649
17.6k
650
17.6k
   if(z < 0)
651
3.58k
      throw Illegal_Point("error during EC point decompression");
652
14.1k
653
14.1k
   if(z.get_bit(0) != yMod2)
654
6.19k
      z = curve_p - z;
655
14.1k
656
14.1k
   return z;
657
14.1k
   }
658
659
}
660
661
PointGFp OS2ECP(const uint8_t data[], size_t data_len,
662
                const CurveGFp& curve)
663
20.0k
   {
664
20.0k
   // Should we really be doing this?
665
20.0k
   if(data_len <= 1)
666
1.45k
      return PointGFp(curve); // return zero
667
18.5k
668
18.5k
   std::pair<BigInt, BigInt> xy = OS2ECP(data, data_len, curve.get_p(), curve.get_a(), curve.get_b());
669
18.5k
670
18.5k
   PointGFp point(curve, xy.first, xy.second);
671
18.5k
672
18.5k
   if(!point.on_the_curve())
673
218
      throw Illegal_Point("OS2ECP: Decoded point was not on the curve");
674
18.3k
675
18.3k
   return point;
676
18.3k
   }
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
18.7k
   {
683
18.7k
   if(data_len <= 1)
684
1
      throw Decoding_Error("OS2ECP invalid point");
685
18.7k
686
18.7k
   const uint8_t pc = data[0];
687
18.7k
688
18.7k
   BigInt x, y;
689
18.7k
690
18.7k
   if(pc == 2 || pc == 3)
691
16.9k
      {
692
16.9k
      //compressed form
693
16.9k
      x = BigInt::decode(&data[1], data_len - 1);
694
16.9k
695
16.9k
      const bool y_mod_2 = ((pc & 0x01) == 1);
696
16.9k
      y = decompress_point(y_mod_2, x, curve_p, curve_a, curve_b);
697
16.9k
      }
698
1.79k
   else if(pc == 4)
699
860
      {
700
860
      const size_t l = (data_len - 1) / 2;
701
860
702
860
      // uncompressed form
703
860
      x = BigInt::decode(&data[1], l);
704
860
      y = BigInt::decode(&data[l+1], l);
705
860
      }
706
939
   else if(pc == 6 || pc == 7)
707
742
      {
708
742
      const size_t l = (data_len - 1) / 2;
709
742
710
742
      // hybrid form
711
742
      x = BigInt::decode(&data[1], l);
712
742
      y = BigInt::decode(&data[l+1], l);
713
742
714
742
      const bool y_mod_2 = ((pc & 0x01) == 1);
715
742
716
742
      if(decompress_point(y_mod_2, x, curve_p, curve_a, curve_b) != y)
717
210
         throw Illegal_Point("OS2ECP: Decoding error in hybrid format");
718
197
      }
719
197
   else
720
197
      throw Invalid_Argument("OS2ECP: Unknown format type " + std::to_string(pc));
721
18.3k
722
18.3k
   return std::make_pair(x, y);
723
18.3k
   }
724
725
}