1 /*
2 * Point arithmetic on elliptic curves over GF(p)
3 *
4 * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
5 * 2008-2011 Jack Lloyd
6 *
7 * Distributed under the terms of the Botan license
8 */
9
10 #include <botan/point_gfp.h>
11 #include <botan/numthry.h>
12 #include <botan/reducer.h>
13 #include <botan/internal/mp_core.h>
14 #include <botan/internal/assert.h>
15
16 namespace Botan {
17
PointGFp(const CurveGFp & curve)18 PointGFp::PointGFp(const CurveGFp& curve) :
19 curve(curve), ws(2 * (curve.get_p_words() + 2))
20 {
21 coord_x = 0;
22 coord_y = monty_mult(1, curve.get_r2());
23 coord_z = 0;
24 }
25
PointGFp(const CurveGFp & curve,const BigInt & x,const BigInt & y)26 PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
27 curve(curve), ws(2 * (curve.get_p_words() + 2))
28 {
29 if(x <= 0 || x >= curve.get_p())
30 throw Invalid_Argument("Invalid PointGFp x");
31 if(y <= 0 || y >= curve.get_p())
32 throw Invalid_Argument("Invalid PointGFp y");
33 coord_x = monty_mult(x, curve.get_r2());
34 coord_y = monty_mult(y, curve.get_r2());
35 coord_z = monty_mult(1, curve.get_r2());
36 }
37
38 // Montgomery multiplication
monty_mult(BigInt & z,const BigInt & x,const BigInt & y) const39 void PointGFp::monty_mult(BigInt& z, const BigInt& x, const BigInt& y) const
40 {
41 //assert(&z != &x && &z != &y);
42
43 if(x.is_zero() || y.is_zero())
44 {
45 z = 0;
46 return;
47 }
48
49 const BigInt& p = curve.get_p();
50 const size_t p_size = curve.get_p_words();
51 const word p_dash = curve.get_p_dash();
52
53 SecureVector<word>& z_reg = z.get_reg();
54 z_reg.resize(2*p_size+1);
55 zeroise(z_reg);
56
57 bigint_monty_mul(&z_reg[0], z_reg.size(),
58 x.data(), x.size(), x.sig_words(),
59 y.data(), y.size(), y.sig_words(),
60 p.data(), p_size, p_dash,
61 &ws[0]);
62 }
63
64 // Montgomery squaring
monty_sqr(BigInt & z,const BigInt & x) const65 void PointGFp::monty_sqr(BigInt& z, const BigInt& x) const
66 {
67 //assert(&z != &x);
68
69 if(x.is_zero())
70 {
71 z = 0;
72 return;
73 }
74
75 const BigInt& p = curve.get_p();
76 const word p_dash = curve.get_p_dash();
77 const size_t p_size = curve.get_p_words();
78
79 const size_t x_sw = x.sig_words();
80 BOTAN_ASSERT(x_sw <= p_size, "x value in range");
81
82 SecureVector<word>& z_reg = z.get_reg();
83 z_reg.resize(2*p_size+1);
84 zeroise(z_reg);
85
86 bigint_monty_sqr(&z_reg[0], z_reg.size(),
87 x.data(), x.size(), x_sw,
88 p.data(), p_size, p_dash,
89 &ws[0]);
90 }
91
92 // Point addition
add(const PointGFp & rhs,std::vector<BigInt> & ws_bn)93 void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
94 {
95 if(is_zero())
96 {
97 coord_x = rhs.coord_x;
98 coord_y = rhs.coord_y;
99 coord_z = rhs.coord_z;
100 return;
101 }
102 else if(rhs.is_zero())
103 return;
104
105 const BigInt& p = curve.get_p();
106
107 BigInt& rhs_z2 = ws_bn[0];
108 BigInt& U1 = ws_bn[1];
109 BigInt& S1 = ws_bn[2];
110
111 BigInt& lhs_z2 = ws_bn[3];
112 BigInt& U2 = ws_bn[4];
113 BigInt& S2 = ws_bn[5];
114
115 BigInt& H = ws_bn[6];
116 BigInt& r = ws_bn[7];
117
118 monty_sqr(rhs_z2, rhs.coord_z);
119 monty_mult(U1, coord_x, rhs_z2);
120 monty_mult(S1, coord_y, monty_mult(rhs.coord_z, rhs_z2));
121
122 monty_sqr(lhs_z2, coord_z);
123 monty_mult(U2, rhs.coord_x, lhs_z2);
124 monty_mult(S2, rhs.coord_y, monty_mult(coord_z, lhs_z2));
125
126 H = U2;
127 H -= U1;
128 if(H.is_negative())
129 H += p;
130
131 r = S2;
132 r -= S1;
133 if(r.is_negative())
134 r += p;
135
136 if(H.is_zero())
137 {
138 if(r.is_zero())
139 {
140 mult2(ws_bn);
141 return;
142 }
143
144 *this = PointGFp(curve); // setting myself to zero
145 return;
146 }
147
148 monty_sqr(U2, H);
149
150 monty_mult(S2, U2, H);
151
152 U2 = monty_mult(U1, U2);
153
154 monty_sqr(coord_x, r);
155 coord_x -= S2;
156 coord_x -= (U2 << 1);
157 while(coord_x.is_negative())
158 coord_x += p;
159
160 U2 -= coord_x;
161 if(U2.is_negative())
162 U2 += p;
163
164 monty_mult(coord_y, r, U2);
165 coord_y -= monty_mult(S1, S2);
166 if(coord_y.is_negative())
167 coord_y += p;
168
169 monty_mult(coord_z, monty_mult(coord_z, rhs.coord_z), H);
170 }
171
172 // *this *= 2
mult2(std::vector<BigInt> & ws_bn)173 void PointGFp::mult2(std::vector<BigInt>& ws_bn)
174 {
175 if(is_zero())
176 return;
177 else if(coord_y.is_zero())
178 {
179 *this = PointGFp(curve); // setting myself to zero
180 return;
181 }
182
183 const BigInt& p = curve.get_p();
184
185 BigInt& y_2 = ws_bn[0];
186 BigInt& S = ws_bn[1];
187 BigInt& z4 = ws_bn[2];
188 BigInt& a_z4 = ws_bn[3];
189 BigInt& M = ws_bn[4];
190 BigInt& U = ws_bn[5];
191 BigInt& x = ws_bn[6];
192 BigInt& y = ws_bn[7];
193 BigInt& z = ws_bn[8];
194
195 monty_sqr(y_2, coord_y);
196
197 monty_mult(S, coord_x, y_2);
198 S <<= 2; // * 4
199 while(S >= p)
200 S -= p;
201
202 monty_sqr(z4, monty_sqr(coord_z));
203 monty_mult(a_z4, curve.get_a_r(), z4);
204
205 M = 3 * monty_sqr(coord_x);
206 M += a_z4;
207 while(M >= p)
208 M -= p;
209
210 monty_sqr(x, M);
211 x -= (S << 1);
212 while(x.is_negative())
213 x += p;
214
215 monty_sqr(U, y_2);
216 U <<= 3;
217 while(U >= p)
218 U -= p;
219
220 S -= x;
221 while(S.is_negative())
222 S += p;
223
224 monty_mult(y, M, S);
225 y -= U;
226 if(y.is_negative())
227 y += p;
228
229 monty_mult(z, coord_y, coord_z);
230 z <<= 1;
231 if(z >= p)
232 z -= p;
233
234 coord_x = x;
235 coord_y = y;
236 coord_z = z;
237 }
238
239 // arithmetic operators
operator +=(const PointGFp & rhs)240 PointGFp& PointGFp::operator+=(const PointGFp& rhs)
241 {
242 std::vector<BigInt> ws(9);
243 add(rhs, ws);
244 return *this;
245 }
246
operator -=(const PointGFp & rhs)247 PointGFp& PointGFp::operator-=(const PointGFp& rhs)
248 {
249 PointGFp minus_rhs = PointGFp(rhs).negate();
250
251 if(is_zero())
252 *this = minus_rhs;
253 else
254 *this += minus_rhs;
255
256 return *this;
257 }
258
operator *=(const BigInt & scalar)259 PointGFp& PointGFp::operator*=(const BigInt& scalar)
260 {
261 *this = scalar * *this;
262 return *this;
263 }
264
multi_exponentiate(const PointGFp & p1,const BigInt & z1,const PointGFp & p2,const BigInt & z2)265 PointGFp multi_exponentiate(const PointGFp& p1, const BigInt& z1,
266 const PointGFp& p2, const BigInt& z2)
267 {
268 const PointGFp p3 = p1 + p2;
269
270 PointGFp H(p1.curve); // create as zero
271 size_t bits_left = std::max(z1.bits(), z2.bits());
272
273 std::vector<BigInt> ws(9);
274
275 while(bits_left)
276 {
277 H.mult2(ws);
278
279 const bool z1_b = z1.get_bit(bits_left - 1);
280 const bool z2_b = z2.get_bit(bits_left - 1);
281
282 if(z1_b == true && z2_b == true)
283 H.add(p3, ws);
284 else if(z1_b)
285 H.add(p1, ws);
286 else if(z2_b)
287 H.add(p2, ws);
288
289 --bits_left;
290 }
291
292 if(z1.is_negative() != z2.is_negative())
293 H.negate();
294
295 return H;
296 }
297
operator *(const BigInt & scalar,const PointGFp & point)298 PointGFp operator*(const BigInt& scalar, const PointGFp& point)
299 {
300 const CurveGFp& curve = point.get_curve();
301
302 if(scalar.is_zero())
303 return PointGFp(curve); // zero point
304
305 std::vector<BigInt> ws(9);
306
307 if(scalar.abs() <= 2) // special cases for small values
308 {
309 byte value = scalar.abs().byte_at(0);
310
311 PointGFp result = point;
312
313 if(value == 2)
314 result.mult2(ws);
315
316 if(scalar.is_negative())
317 result.negate();
318
319 return result;
320 }
321
322 const size_t scalar_bits = scalar.bits();
323
324 #if 0
325
326 PointGFp x1 = PointGFp(curve);
327 PointGFp x2 = point;
328
329 size_t bits_left = scalar_bits;
330
331 // Montgomery Ladder
332 while(bits_left)
333 {
334 const bool bit_set = scalar.get_bit(bits_left - 1);
335
336 if(bit_set)
337 {
338 x1.add(x2, ws);
339 x2.mult2(ws);
340 }
341 else
342 {
343 x2.add(x1, ws);
344 x1.mult2(ws);
345 }
346
347 --bits_left;
348 }
349
350 if(scalar.is_negative())
351 x1.negate();
352
353 return x1;
354
355 #else
356 const size_t window_size = 4;
357
358 std::vector<PointGFp> Ps(1 << window_size);
359 Ps[0] = PointGFp(curve);
360 Ps[1] = point;
361
362 for(size_t i = 2; i != Ps.size(); ++i)
363 {
364 Ps[i] = Ps[i-1];
365 Ps[i].add(point, ws);
366 }
367
368 PointGFp H(curve); // create as zero
369 size_t bits_left = scalar_bits;
370
371 while(bits_left >= window_size)
372 {
373 for(size_t i = 0; i != window_size; ++i)
374 H.mult2(ws);
375
376 const u32bit nibble = scalar.get_substring(bits_left - window_size,
377 window_size);
378
379 H.add(Ps[nibble], ws);
380
381 bits_left -= window_size;
382 }
383
384 while(bits_left)
385 {
386 H.mult2(ws);
387 if(scalar.get_bit(bits_left-1))
388 H.add(point, ws);
389
390 --bits_left;
391 }
392
393 if(scalar.is_negative())
394 H.negate();
395
396 return H;
397 #endif
398 }
399
get_affine_x() const400 BigInt PointGFp::get_affine_x() const
401 {
402 if(is_zero())
403 throw Illegal_Transformation("Cannot convert zero point to affine");
404
405 const BigInt& r2 = curve.get_r2();
406
407 BigInt z2 = monty_sqr(coord_z);
408 z2 = inverse_mod(z2, curve.get_p());
409
410 z2 = monty_mult(z2, r2);
411 return monty_mult(coord_x, z2);
412 }
413
get_affine_y() const414 BigInt PointGFp::get_affine_y() const
415 {
416 if(is_zero())
417 throw Illegal_Transformation("Cannot convert zero point to affine");
418
419 const BigInt& r2 = curve.get_r2();
420
421 BigInt z3 = monty_mult(coord_z, monty_sqr(coord_z));
422 z3 = inverse_mod(z3, curve.get_p());
423 z3 = monty_mult(z3, r2);
424 return monty_mult(coord_y, z3);
425 }
426
on_the_curve() const427 bool PointGFp::on_the_curve() const
428 {
429 /*
430 Is the point still on the curve?? (If everything is correct, the
431 point is always on its curve; then the function will return true.
432 If somehow the state is corrupted, which suggests a fault attack
433 (or internal computational error), then return false.
434 */
435
436 if(is_zero())
437 return true;
438
439 BigInt y2 = monty_mult(monty_sqr(coord_y), 1);
440 BigInt x3 = monty_mult(coord_x, monty_sqr(coord_x));
441
442 BigInt ax = monty_mult(coord_x, curve.get_a_r());
443
444 const BigInt& b_r = curve.get_b_r();
445
446 BigInt z2 = monty_sqr(coord_z);
447
448 if(coord_z == z2) // Is z equal to 1 (in Montgomery form)?
449 {
450 if(y2 != monty_mult(x3 + ax + b_r, 1))
451 return false;
452 }
453
454 BigInt z3 = monty_mult(coord_z, z2);
455
456 BigInt ax_z4 = monty_mult(ax, monty_sqr(z2));
457
458 BigInt b_z6 = monty_mult(b_r, monty_sqr(z3));
459
460 if(y2 != monty_mult(x3 + ax_z4 + b_z6, 1))
461 return false;
462
463 return true;
464 }
465
466 // swaps the states of *this and other, does not throw!
swap(PointGFp & other)467 void PointGFp::swap(PointGFp& other)
468 {
469 curve.swap(other.curve);
470 coord_x.swap(other.coord_x);
471 coord_y.swap(other.coord_y);
472 coord_z.swap(other.coord_z);
473 ws.swap(other.ws);
474 }
475
operator ==(const PointGFp & other) const476 bool PointGFp::operator==(const PointGFp& other) const
477 {
478 if(get_curve() != other.get_curve())
479 return false;
480
481 // If this is zero, only equal if other is also zero
482 if(is_zero())
483 return other.is_zero();
484
485 return (get_affine_x() == other.get_affine_x() &&
486 get_affine_y() == other.get_affine_y());
487 }
488
489 // encoding and decoding
EC2OSP(const PointGFp & point,byte format)490 SecureVector<byte> EC2OSP(const PointGFp& point, byte format)
491 {
492 if(point.is_zero())
493 return SecureVector<byte>(1); // single 0 byte
494
495 const size_t p_bytes = point.get_curve().get_p().bytes();
496
497 BigInt x = point.get_affine_x();
498 BigInt y = point.get_affine_y();
499
500 SecureVector<byte> bX = BigInt::encode_1363(x, p_bytes);
501 SecureVector<byte> bY = BigInt::encode_1363(y, p_bytes);
502
503 if(format == PointGFp::UNCOMPRESSED)
504 {
505 SecureVector<byte> result;
506 result.push_back(0x04);
507
508 result += bX;
509 result += bY;
510
511 return result;
512 }
513 else if(format == PointGFp::COMPRESSED)
514 {
515 SecureVector<byte> result;
516 result.push_back(0x02 | static_cast<byte>(y.get_bit(0)));
517
518 result += bX;
519
520 return result;
521 }
522 else if(format == PointGFp::HYBRID)
523 {
524 SecureVector<byte> result;
525 result.push_back(0x06 | static_cast<byte>(y.get_bit(0)));
526
527 result += bX;
528 result += bY;
529
530 return result;
531 }
532 else
533 throw Invalid_Argument("illegal point encoding format specification");
534 }
535
536 namespace {
537
decompress_point(bool yMod2,const BigInt & x,const CurveGFp & curve)538 BigInt decompress_point(bool yMod2,
539 const BigInt& x,
540 const CurveGFp& curve)
541 {
542 BigInt xpow3 = x * x * x;
543
544 BigInt g = curve.get_a() * x;
545 g += xpow3;
546 g += curve.get_b();
547 g = g % curve.get_p();
548
549 BigInt z = ressol(g, curve.get_p());
550
551 if(z < 0)
552 throw Illegal_Point("error during decompression");
553
554 if(z.get_bit(0) != yMod2)
555 z = curve.get_p() - z;
556
557 return z;
558 }
559
560 }
561
OS2ECP(const byte data[],size_t data_len,const CurveGFp & curve)562 PointGFp OS2ECP(const byte data[], size_t data_len,
563 const CurveGFp& curve)
564 {
565 if(data_len <= 1)
566 return PointGFp(curve); // return zero
567
568 const byte pc = data[0];
569
570 BigInt x, y;
571
572 if(pc == 2 || pc == 3)
573 {
574 //compressed form
575 x = BigInt::decode(&data[1], data_len - 1);
576
577 const bool y_mod_2 = ((pc & 0x01) == 1);
578 y = decompress_point(y_mod_2, x, curve);
579 }
580 else if(pc == 4)
581 {
582 const size_t l = (data_len - 1) / 2;
583
584 // uncompressed form
585 x = BigInt::decode(&data[1], l);
586 y = BigInt::decode(&data[l+1], l);
587 }
588 else if(pc == 6 || pc == 7)
589 {
590 const size_t l = (data_len - 1) / 2;
591
592 // hybrid form
593 x = BigInt::decode(&data[1], l);
594 y = BigInt::decode(&data[l+1], l);
595
596 const bool y_mod_2 = ((pc & 0x01) == 1);
597
598 if(decompress_point(y_mod_2, x, curve) != y)
599 throw Illegal_Point("OS2ECP: Decoding error in hybrid format");
600 }
601 else
602 throw Invalid_Argument("OS2ECP: Unknown format type");
603
604 PointGFp result(curve, x, y);
605
606 if(!result.on_the_curve())
607 throw Illegal_Point("OS2ECP: Decoded point was not on the curve");
608
609 return result;
610 }
611
612 }
613