Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/ecdsa/ellipticcurve.py: 74%
804 statements
« prev ^ index » next coverage.py v7.3.1, created at 2023-09-25 07:19 +0000
1#! /usr/bin/env python
2# -*- coding: utf-8 -*-
3#
4# Implementation of elliptic curves, for cryptographic applications.
5#
6# This module doesn't provide any way to choose a random elliptic
7# curve, nor to verify that an elliptic curve was chosen randomly,
8# because one can simply use NIST's standard curves.
9#
10# Notes from X9.62-1998 (draft):
11# Nomenclature:
12# - Q is a public key.
13# The "Elliptic Curve Domain Parameters" include:
14# - q is the "field size", which in our case equals p.
15# - p is a big prime.
16# - G is a point of prime order (5.1.1.1).
17# - n is the order of G (5.1.1.1).
18# Public-key validation (5.2.2):
19# - Verify that Q is not the point at infinity.
20# - Verify that X_Q and Y_Q are in [0,p-1].
21# - Verify that Q is on the curve.
22# - Verify that nQ is the point at infinity.
23# Signature generation (5.3):
24# - Pick random k from [1,n-1].
25# Signature checking (5.4.2):
26# - Verify that r and s are in [1,n-1].
27#
28# Revision history:
29# 2005.12.31 - Initial version.
30# 2008.11.25 - Change CurveFp.is_on to contains_point.
31#
32# Written in 2005 by Peter Pearson and placed in the public domain.
33# Modified extensively as part of python-ecdsa.
35from __future__ import division
37try:
38 from gmpy2 import mpz
40 GMPY = True
41except ImportError: # pragma: no branch
42 try:
43 from gmpy import mpz
45 GMPY = True
46 except ImportError:
47 GMPY = False
50from six import python_2_unicode_compatible
51from . import numbertheory
52from ._compat import normalise_bytes, int_to_bytes, bit_length, bytes_to_int
53from .errors import MalformedPointError
54from .util import orderlen, string_to_number, number_to_string
57@python_2_unicode_compatible
58class CurveFp(object):
59 """
60 :term:`Short Weierstrass Elliptic Curve <short Weierstrass curve>` over a
61 prime field.
62 """
64 if GMPY: # pragma: no branch
66 def __init__(self, p, a, b, h=None):
67 """
68 The curve of points satisfying y^2 = x^3 + a*x + b (mod p).
70 h is an integer that is the cofactor of the elliptic curve domain
71 parameters; it is the number of points satisfying the elliptic
72 curve equation divided by the order of the base point. It is used
73 for selection of efficient algorithm for public point verification.
74 """
75 self.__p = mpz(p)
76 self.__a = mpz(a)
77 self.__b = mpz(b)
78 # h is not used in calculations and it can be None, so don't use
79 # gmpy with it
80 self.__h = h
82 else: # pragma: no branch
84 def __init__(self, p, a, b, h=None):
85 """
86 The curve of points satisfying y^2 = x^3 + a*x + b (mod p).
88 h is an integer that is the cofactor of the elliptic curve domain
89 parameters; it is the number of points satisfying the elliptic
90 curve equation divided by the order of the base point. It is used
91 for selection of efficient algorithm for public point verification.
92 """
93 self.__p = p
94 self.__a = a
95 self.__b = b
96 self.__h = h
98 def __eq__(self, other):
99 """Return True if other is an identical curve, False otherwise.
101 Note: the value of the cofactor of the curve is not taken into account
102 when comparing curves, as it's derived from the base point and
103 intrinsic curve characteristic (but it's complex to compute),
104 only the prime and curve parameters are considered.
105 """
106 if isinstance(other, CurveFp):
107 p = self.__p
108 return (
109 self.__p == other.__p
110 and self.__a % p == other.__a % p
111 and self.__b % p == other.__b % p
112 )
113 return NotImplemented
115 def __ne__(self, other):
116 """Return False if other is an identical curve, True otherwise."""
117 return not self == other
119 def __hash__(self):
120 return hash((self.__p, self.__a, self.__b))
122 def p(self):
123 return self.__p
125 def a(self):
126 return self.__a
128 def b(self):
129 return self.__b
131 def cofactor(self):
132 return self.__h
134 def contains_point(self, x, y):
135 """Is the point (x,y) on this curve?"""
136 return (y * y - ((x * x + self.__a) * x + self.__b)) % self.__p == 0
138 def __str__(self):
139 return "CurveFp(p=%d, a=%d, b=%d, h=%d)" % (
140 self.__p,
141 self.__a,
142 self.__b,
143 self.__h,
144 )
147class CurveEdTw(object):
148 """Parameters for a Twisted Edwards Elliptic Curve"""
150 if GMPY: # pragma: no branch
152 def __init__(self, p, a, d, h=None, hash_func=None):
153 """
154 The curve of points satisfying a*x^2 + y^2 = 1 + d*x^2*y^2 (mod p).
156 h is the cofactor of the curve.
157 hash_func is the hash function associated with the curve
158 (like SHA-512 for Ed25519)
159 """
160 self.__p = mpz(p)
161 self.__a = mpz(a)
162 self.__d = mpz(d)
163 self.__h = h
164 self.__hash_func = hash_func
166 else:
168 def __init__(self, p, a, d, h=None, hash_func=None):
169 """
170 The curve of points satisfying a*x^2 + y^2 = 1 + d*x^2*y^2 (mod p).
172 h is the cofactor of the curve.
173 hash_func is the hash function associated with the curve
174 (like SHA-512 for Ed25519)
175 """
176 self.__p = p
177 self.__a = a
178 self.__d = d
179 self.__h = h
180 self.__hash_func = hash_func
182 def __eq__(self, other):
183 """Returns True if other is an identical curve."""
184 if isinstance(other, CurveEdTw):
185 p = self.__p
186 return (
187 self.__p == other.__p
188 and self.__a % p == other.__a % p
189 and self.__d % p == other.__d % p
190 )
191 return NotImplemented
193 def __ne__(self, other):
194 """Return False if the other is an identical curve, True otherwise."""
195 return not self == other
197 def __hash__(self):
198 return hash((self.__p, self.__a, self.__d))
200 def contains_point(self, x, y):
201 """Is the point (x, y) on this curve?"""
202 return (
203 self.__a * x * x + y * y - 1 - self.__d * x * x * y * y
204 ) % self.__p == 0
206 def p(self):
207 return self.__p
209 def a(self):
210 return self.__a
212 def d(self):
213 return self.__d
215 def hash_func(self, data):
216 return self.__hash_func(data)
218 def cofactor(self):
219 return self.__h
221 def __str__(self):
222 return "CurveEdTw(p={0}, a={1}, d={2}, h={3})".format(
223 self.__p,
224 self.__a,
225 self.__d,
226 self.__h,
227 )
230class AbstractPoint(object):
231 """Class for common methods of elliptic curve points."""
233 @staticmethod
234 def _from_raw_encoding(data, raw_encoding_length):
235 """
236 Decode public point from :term:`raw encoding`.
238 :term:`raw encoding` is the same as the :term:`uncompressed` encoding,
239 but without the 0x04 byte at the beginning.
240 """
241 # real assert, from_bytes() should not call us with different length
242 assert len(data) == raw_encoding_length
243 xs = data[: raw_encoding_length // 2]
244 ys = data[raw_encoding_length // 2 :]
245 # real assert, raw_encoding_length is calculated by multiplying an
246 # integer by two so it will always be even
247 assert len(xs) == raw_encoding_length // 2
248 assert len(ys) == raw_encoding_length // 2
249 coord_x = string_to_number(xs)
250 coord_y = string_to_number(ys)
252 return coord_x, coord_y
254 @staticmethod
255 def _from_compressed(data, curve):
256 """Decode public point from compressed encoding."""
257 if data[:1] not in (b"\x02", b"\x03"):
258 raise MalformedPointError("Malformed compressed point encoding")
260 is_even = data[:1] == b"\x02"
261 x = string_to_number(data[1:])
262 p = curve.p()
263 alpha = (pow(x, 3, p) + (curve.a() * x) + curve.b()) % p
264 try:
265 beta = numbertheory.square_root_mod_prime(alpha, p)
266 except numbertheory.Error as e:
267 raise MalformedPointError(
268 "Encoding does not correspond to a point on curve", e
269 )
270 if is_even == bool(beta & 1):
271 y = p - beta
272 else:
273 y = beta
274 return x, y
276 @classmethod
277 def _from_hybrid(cls, data, raw_encoding_length, validate_encoding):
278 """Decode public point from hybrid encoding."""
279 # real assert, from_bytes() should not call us with different types
280 assert data[:1] in (b"\x06", b"\x07")
282 # primarily use the uncompressed as it's easiest to handle
283 x, y = cls._from_raw_encoding(data[1:], raw_encoding_length)
285 # but validate if it's self-consistent if we're asked to do that
286 if validate_encoding and (
287 y & 1
288 and data[:1] != b"\x07"
289 or (not y & 1)
290 and data[:1] != b"\x06"
291 ):
292 raise MalformedPointError("Inconsistent hybrid point encoding")
294 return x, y
296 @classmethod
297 def _from_edwards(cls, curve, data):
298 """Decode a point on an Edwards curve."""
299 data = bytearray(data)
300 p = curve.p()
301 # add 1 for the sign bit and then round up
302 exp_len = (bit_length(p) + 1 + 7) // 8
303 if len(data) != exp_len:
304 raise MalformedPointError("Point length doesn't match the curve.")
305 x_0 = (data[-1] & 0x80) >> 7
307 data[-1] &= 0x80 - 1
309 y = bytes_to_int(data, "little")
310 if GMPY:
311 y = mpz(y)
313 x2 = (
314 (y * y - 1)
315 * numbertheory.inverse_mod(curve.d() * y * y - curve.a(), p)
316 % p
317 )
319 try:
320 x = numbertheory.square_root_mod_prime(x2, p)
321 except numbertheory.Error as e:
322 raise MalformedPointError(
323 "Encoding does not correspond to a point on curve", e
324 )
326 if x % 2 != x_0:
327 x = -x % p
329 return x, y
331 @classmethod
332 def from_bytes(
333 cls, curve, data, validate_encoding=True, valid_encodings=None
334 ):
335 """
336 Initialise the object from byte encoding of a point.
338 The method does accept and automatically detect the type of point
339 encoding used. It supports the :term:`raw encoding`,
340 :term:`uncompressed`, :term:`compressed`, and :term:`hybrid` encodings.
342 Note: generally you will want to call the ``from_bytes()`` method of
343 either a child class, PointJacobi or Point.
345 :param data: single point encoding of the public key
346 :type data: :term:`bytes-like object`
347 :param curve: the curve on which the public key is expected to lay
348 :type curve: ~ecdsa.ellipticcurve.CurveFp
349 :param validate_encoding: whether to verify that the encoding of the
350 point is self-consistent, defaults to True, has effect only
351 on ``hybrid`` encoding
352 :type validate_encoding: bool
353 :param valid_encodings: list of acceptable point encoding formats,
354 supported ones are: :term:`uncompressed`, :term:`compressed`,
355 :term:`hybrid`, and :term:`raw encoding` (specified with ``raw``
356 name). All formats by default (specified with ``None``).
357 :type valid_encodings: :term:`set-like object`
359 :raises `~ecdsa.errors.MalformedPointError`: if the public point does
360 not lay on the curve or the encoding is invalid
362 :return: x and y coordinates of the encoded point
363 :rtype: tuple(int, int)
364 """
365 if not valid_encodings:
366 valid_encodings = set(
367 ["uncompressed", "compressed", "hybrid", "raw"]
368 )
369 if not all(
370 i in set(("uncompressed", "compressed", "hybrid", "raw"))
371 for i in valid_encodings
372 ):
373 raise ValueError(
374 "Only uncompressed, compressed, hybrid or raw encoding "
375 "supported."
376 )
377 data = normalise_bytes(data)
379 if isinstance(curve, CurveEdTw):
380 return cls._from_edwards(curve, data)
382 key_len = len(data)
383 raw_encoding_length = 2 * orderlen(curve.p())
384 if key_len == raw_encoding_length and "raw" in valid_encodings:
385 coord_x, coord_y = cls._from_raw_encoding(
386 data, raw_encoding_length
387 )
388 elif key_len == raw_encoding_length + 1 and (
389 "hybrid" in valid_encodings or "uncompressed" in valid_encodings
390 ):
391 if data[:1] in (b"\x06", b"\x07") and "hybrid" in valid_encodings:
392 coord_x, coord_y = cls._from_hybrid(
393 data, raw_encoding_length, validate_encoding
394 )
395 elif data[:1] == b"\x04" and "uncompressed" in valid_encodings:
396 coord_x, coord_y = cls._from_raw_encoding(
397 data[1:], raw_encoding_length
398 )
399 else:
400 raise MalformedPointError(
401 "Invalid X9.62 encoding of the public point"
402 )
403 elif (
404 key_len == raw_encoding_length // 2 + 1
405 and "compressed" in valid_encodings
406 ):
407 coord_x, coord_y = cls._from_compressed(data, curve)
408 else:
409 raise MalformedPointError(
410 "Length of string does not match lengths of "
411 "any of the enabled ({0}) encodings of the "
412 "curve.".format(", ".join(valid_encodings))
413 )
414 return coord_x, coord_y
416 def _raw_encode(self):
417 """Convert the point to the :term:`raw encoding`."""
418 prime = self.curve().p()
419 x_str = number_to_string(self.x(), prime)
420 y_str = number_to_string(self.y(), prime)
421 return x_str + y_str
423 def _compressed_encode(self):
424 """Encode the point into the compressed form."""
425 prime = self.curve().p()
426 x_str = number_to_string(self.x(), prime)
427 if self.y() & 1:
428 return b"\x03" + x_str
429 return b"\x02" + x_str
431 def _hybrid_encode(self):
432 """Encode the point into the hybrid form."""
433 raw_enc = self._raw_encode()
434 if self.y() & 1:
435 return b"\x07" + raw_enc
436 return b"\x06" + raw_enc
438 def _edwards_encode(self):
439 """Encode the point according to RFC8032 encoding."""
440 self.scale()
441 x, y, p = self.x(), self.y(), self.curve().p()
443 # add 1 for the sign bit and then round up
444 enc_len = (bit_length(p) + 1 + 7) // 8
445 y_str = int_to_bytes(y, enc_len, "little")
446 if x % 2:
447 y_str[-1] |= 0x80
448 return y_str
450 def to_bytes(self, encoding="raw"):
451 """
452 Convert the point to a byte string.
454 The method by default uses the :term:`raw encoding` (specified
455 by `encoding="raw"`. It can also output points in :term:`uncompressed`,
456 :term:`compressed`, and :term:`hybrid` formats.
458 For points on Edwards curves `encoding` is ignored and only the
459 encoding defined in RFC 8032 is supported.
461 :return: :term:`raw encoding` of a public on the curve
462 :rtype: bytes
463 """
464 assert encoding in ("raw", "uncompressed", "compressed", "hybrid")
465 curve = self.curve()
466 if isinstance(curve, CurveEdTw):
467 return self._edwards_encode()
468 elif encoding == "raw":
469 return self._raw_encode()
470 elif encoding == "uncompressed":
471 return b"\x04" + self._raw_encode()
472 elif encoding == "hybrid":
473 return self._hybrid_encode()
474 else:
475 return self._compressed_encode()
477 @staticmethod
478 def _naf(mult):
479 """Calculate non-adjacent form of number."""
480 ret = []
481 while mult:
482 if mult % 2:
483 nd = mult % 4
484 if nd >= 2:
485 nd -= 4
486 ret.append(nd)
487 mult -= nd
488 else:
489 ret.append(0)
490 mult //= 2
491 return ret
494class PointJacobi(AbstractPoint):
495 """
496 Point on a short Weierstrass elliptic curve. Uses Jacobi coordinates.
498 In Jacobian coordinates, there are three parameters, X, Y and Z.
499 They correspond to affine parameters 'x' and 'y' like so:
501 x = X / Z²
502 y = Y / Z³
503 """
505 def __init__(self, curve, x, y, z, order=None, generator=False):
506 """
507 Initialise a point that uses Jacobi representation internally.
509 :param CurveFp curve: curve on which the point resides
510 :param int x: the X parameter of Jacobi representation (equal to x when
511 converting from affine coordinates
512 :param int y: the Y parameter of Jacobi representation (equal to y when
513 converting from affine coordinates
514 :param int z: the Z parameter of Jacobi representation (equal to 1 when
515 converting from affine coordinates
516 :param int order: the point order, must be non zero when using
517 generator=True
518 :param bool generator: the point provided is a curve generator, as
519 such, it will be commonly used with scalar multiplication. This will
520 cause to precompute multiplication table generation for it
521 """
522 super(PointJacobi, self).__init__()
523 self.__curve = curve
524 if GMPY: # pragma: no branch
525 self.__coords = (mpz(x), mpz(y), mpz(z))
526 self.__order = order and mpz(order)
527 else: # pragma: no branch
528 self.__coords = (x, y, z)
529 self.__order = order
530 self.__generator = generator
531 self.__precompute = []
533 @classmethod
534 def from_bytes(
535 cls,
536 curve,
537 data,
538 validate_encoding=True,
539 valid_encodings=None,
540 order=None,
541 generator=False,
542 ):
543 """
544 Initialise the object from byte encoding of a point.
546 The method does accept and automatically detect the type of point
547 encoding used. It supports the :term:`raw encoding`,
548 :term:`uncompressed`, :term:`compressed`, and :term:`hybrid` encodings.
550 :param data: single point encoding of the public key
551 :type data: :term:`bytes-like object`
552 :param curve: the curve on which the public key is expected to lay
553 :type curve: ~ecdsa.ellipticcurve.CurveFp
554 :param validate_encoding: whether to verify that the encoding of the
555 point is self-consistent, defaults to True, has effect only
556 on ``hybrid`` encoding
557 :type validate_encoding: bool
558 :param valid_encodings: list of acceptable point encoding formats,
559 supported ones are: :term:`uncompressed`, :term:`compressed`,
560 :term:`hybrid`, and :term:`raw encoding` (specified with ``raw``
561 name). All formats by default (specified with ``None``).
562 :type valid_encodings: :term:`set-like object`
563 :param int order: the point order, must be non zero when using
564 generator=True
565 :param bool generator: the point provided is a curve generator, as
566 such, it will be commonly used with scalar multiplication. This
567 will cause to precompute multiplication table generation for it
569 :raises `~ecdsa.errors.MalformedPointError`: if the public point does
570 not lay on the curve or the encoding is invalid
572 :return: Point on curve
573 :rtype: PointJacobi
574 """
575 coord_x, coord_y = super(PointJacobi, cls).from_bytes(
576 curve, data, validate_encoding, valid_encodings
577 )
578 return PointJacobi(curve, coord_x, coord_y, 1, order, generator)
580 def _maybe_precompute(self):
581 if not self.__generator or self.__precompute:
582 return
584 # since this code will execute just once, and it's fully deterministic,
585 # depend on atomicity of the last assignment to switch from empty
586 # self.__precompute to filled one and just ignore the unlikely
587 # situation when two threads execute it at the same time (as it won't
588 # lead to inconsistent __precompute)
589 order = self.__order
590 assert order
591 precompute = []
592 i = 1
593 order *= 2
594 coord_x, coord_y, coord_z = self.__coords
595 doubler = PointJacobi(self.__curve, coord_x, coord_y, coord_z, order)
596 order *= 2
597 precompute.append((doubler.x(), doubler.y()))
599 while i < order:
600 i *= 2
601 doubler = doubler.double().scale()
602 precompute.append((doubler.x(), doubler.y()))
604 self.__precompute = precompute
606 def __getstate__(self):
607 # while this code can execute at the same time as _maybe_precompute()
608 # is updating the __precompute or scale() is updating the __coords,
609 # there is no requirement for consistency between __coords and
610 # __precompute
611 state = self.__dict__.copy()
612 return state
614 def __setstate__(self, state):
615 self.__dict__.update(state)
617 def __eq__(self, other):
618 """Compare for equality two points with each-other.
620 Note: only points that lay on the same curve can be equal.
621 """
622 x1, y1, z1 = self.__coords
623 if other is INFINITY:
624 return not y1 or not z1
625 if isinstance(other, Point):
626 x2, y2, z2 = other.x(), other.y(), 1
627 elif isinstance(other, PointJacobi):
628 x2, y2, z2 = other.__coords
629 else:
630 return NotImplemented
631 if self.__curve != other.curve():
632 return False
633 p = self.__curve.p()
635 zz1 = z1 * z1 % p
636 zz2 = z2 * z2 % p
638 # compare the fractions by bringing them to the same denominator
639 # depend on short-circuit to save 4 multiplications in case of
640 # inequality
641 return (x1 * zz2 - x2 * zz1) % p == 0 and (
642 y1 * zz2 * z2 - y2 * zz1 * z1
643 ) % p == 0
645 def __ne__(self, other):
646 """Compare for inequality two points with each-other."""
647 return not self == other
649 def order(self):
650 """Return the order of the point.
652 None if it is undefined.
653 """
654 return self.__order
656 def curve(self):
657 """Return curve over which the point is defined."""
658 return self.__curve
660 def x(self):
661 """
662 Return affine x coordinate.
664 This method should be used only when the 'y' coordinate is not needed.
665 It's computationally more efficient to use `to_affine()` and then
666 call x() and y() on the returned instance. Or call `scale()`
667 and then x() and y() on the returned instance.
668 """
669 x, _, z = self.__coords
670 if z == 1:
671 return x
672 p = self.__curve.p()
673 z = numbertheory.inverse_mod(z, p)
674 return x * z**2 % p
676 def y(self):
677 """
678 Return affine y coordinate.
680 This method should be used only when the 'x' coordinate is not needed.
681 It's computationally more efficient to use `to_affine()` and then
682 call x() and y() on the returned instance. Or call `scale()`
683 and then x() and y() on the returned instance.
684 """
685 _, y, z = self.__coords
686 if z == 1:
687 return y
688 p = self.__curve.p()
689 z = numbertheory.inverse_mod(z, p)
690 return y * z**3 % p
692 def scale(self):
693 """
694 Return point scaled so that z == 1.
696 Modifies point in place, returns self.
697 """
698 x, y, z = self.__coords
699 if z == 1:
700 return self
702 # scaling is deterministic, so even if two threads execute the below
703 # code at the same time, they will set __coords to the same value
704 p = self.__curve.p()
705 z_inv = numbertheory.inverse_mod(z, p)
706 zz_inv = z_inv * z_inv % p
707 x = x * zz_inv % p
708 y = y * zz_inv * z_inv % p
709 self.__coords = (x, y, 1)
710 return self
712 def to_affine(self):
713 """Return point in affine form."""
714 _, y, z = self.__coords
715 if not y or not z:
716 return INFINITY
717 self.scale()
718 x, y, z = self.__coords
719 return Point(self.__curve, x, y, self.__order)
721 @staticmethod
722 def from_affine(point, generator=False):
723 """Create from an affine point.
725 :param bool generator: set to True to make the point to precalculate
726 multiplication table - useful for public point when verifying many
727 signatures (around 100 or so) or for generator points of a curve.
728 """
729 return PointJacobi(
730 point.curve(), point.x(), point.y(), 1, point.order(), generator
731 )
733 # please note that all the methods that use the equations from
734 # hyperelliptic
735 # are formatted in a way to maximise performance.
736 # Things that make code faster: multiplying instead of taking to the power
737 # (`xx = x * x; xxxx = xx * xx % p` is faster than `xxxx = x**4 % p` and
738 # `pow(x, 4, p)`),
739 # multiple assignments at the same time (`x1, x2 = self.x1, self.x2` is
740 # faster than `x1 = self.x1; x2 = self.x2`),
741 # similarly, sometimes the `% p` is skipped if it makes the calculation
742 # faster and the result of calculation is later reduced modulo `p`
744 def _double_with_z_1(self, X1, Y1, p, a):
745 """Add a point to itself with z == 1."""
746 # after:
747 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-mdbl-2007-bl
748 XX, YY = X1 * X1 % p, Y1 * Y1 % p
749 if not YY:
750 return 0, 0, 1
751 YYYY = YY * YY % p
752 S = 2 * ((X1 + YY) ** 2 - XX - YYYY) % p
753 M = 3 * XX + a
754 T = (M * M - 2 * S) % p
755 # X3 = T
756 Y3 = (M * (S - T) - 8 * YYYY) % p
757 Z3 = 2 * Y1 % p
758 return T, Y3, Z3
760 def _double(self, X1, Y1, Z1, p, a):
761 """Add a point to itself, arbitrary z."""
762 if Z1 == 1:
763 return self._double_with_z_1(X1, Y1, p, a)
764 if not Y1 or not Z1:
765 return 0, 0, 1
766 # after:
767 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl
768 XX, YY = X1 * X1 % p, Y1 * Y1 % p
769 if not YY:
770 return 0, 0, 1
771 YYYY = YY * YY % p
772 ZZ = Z1 * Z1 % p
773 S = 2 * ((X1 + YY) ** 2 - XX - YYYY) % p
774 M = (3 * XX + a * ZZ * ZZ) % p
775 T = (M * M - 2 * S) % p
776 # X3 = T
777 Y3 = (M * (S - T) - 8 * YYYY) % p
778 Z3 = ((Y1 + Z1) ** 2 - YY - ZZ) % p
780 return T, Y3, Z3
782 def double(self):
783 """Add a point to itself."""
784 X1, Y1, Z1 = self.__coords
786 if not Y1:
787 return INFINITY
789 p, a = self.__curve.p(), self.__curve.a()
791 X3, Y3, Z3 = self._double(X1, Y1, Z1, p, a)
793 if not Y3 or not Z3:
794 return INFINITY
795 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
797 def _add_with_z_1(self, X1, Y1, X2, Y2, p):
798 """add points when both Z1 and Z2 equal 1"""
799 # after:
800 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-mmadd-2007-bl
801 H = X2 - X1
802 HH = H * H
803 I = 4 * HH % p
804 J = H * I
805 r = 2 * (Y2 - Y1)
806 if not H and not r:
807 return self._double_with_z_1(X1, Y1, p, self.__curve.a())
808 V = X1 * I
809 X3 = (r**2 - J - 2 * V) % p
810 Y3 = (r * (V - X3) - 2 * Y1 * J) % p
811 Z3 = 2 * H % p
812 return X3, Y3, Z3
814 def _add_with_z_eq(self, X1, Y1, Z1, X2, Y2, p):
815 """add points when Z1 == Z2"""
816 # after:
817 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-zadd-2007-m
818 A = (X2 - X1) ** 2 % p
819 B = X1 * A % p
820 C = X2 * A
821 D = (Y2 - Y1) ** 2 % p
822 if not A and not D:
823 return self._double(X1, Y1, Z1, p, self.__curve.a())
824 X3 = (D - B - C) % p
825 Y3 = ((Y2 - Y1) * (B - X3) - Y1 * (C - B)) % p
826 Z3 = Z1 * (X2 - X1) % p
827 return X3, Y3, Z3
829 def _add_with_z2_1(self, X1, Y1, Z1, X2, Y2, p):
830 """add points when Z2 == 1"""
831 # after:
832 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-madd-2007-bl
833 Z1Z1 = Z1 * Z1 % p
834 U2, S2 = X2 * Z1Z1 % p, Y2 * Z1 * Z1Z1 % p
835 H = (U2 - X1) % p
836 HH = H * H % p
837 I = 4 * HH % p
838 J = H * I
839 r = 2 * (S2 - Y1) % p
840 if not r and not H:
841 return self._double_with_z_1(X2, Y2, p, self.__curve.a())
842 V = X1 * I
843 X3 = (r * r - J - 2 * V) % p
844 Y3 = (r * (V - X3) - 2 * Y1 * J) % p
845 Z3 = ((Z1 + H) ** 2 - Z1Z1 - HH) % p
846 return X3, Y3, Z3
848 def _add_with_z_ne(self, X1, Y1, Z1, X2, Y2, Z2, p):
849 """add points with arbitrary z"""
850 # after:
851 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl
852 Z1Z1 = Z1 * Z1 % p
853 Z2Z2 = Z2 * Z2 % p
854 U1 = X1 * Z2Z2 % p
855 U2 = X2 * Z1Z1 % p
856 S1 = Y1 * Z2 * Z2Z2 % p
857 S2 = Y2 * Z1 * Z1Z1 % p
858 H = U2 - U1
859 I = 4 * H * H % p
860 J = H * I % p
861 r = 2 * (S2 - S1) % p
862 if not H and not r:
863 return self._double(X1, Y1, Z1, p, self.__curve.a())
864 V = U1 * I
865 X3 = (r * r - J - 2 * V) % p
866 Y3 = (r * (V - X3) - 2 * S1 * J) % p
867 Z3 = ((Z1 + Z2) ** 2 - Z1Z1 - Z2Z2) * H % p
869 return X3, Y3, Z3
871 def __radd__(self, other):
872 """Add other to self."""
873 return self + other
875 def _add(self, X1, Y1, Z1, X2, Y2, Z2, p):
876 """add two points, select fastest method."""
877 if not Y1 or not Z1:
878 return X2, Y2, Z2
879 if not Y2 or not Z2:
880 return X1, Y1, Z1
881 if Z1 == Z2:
882 if Z1 == 1:
883 return self._add_with_z_1(X1, Y1, X2, Y2, p)
884 return self._add_with_z_eq(X1, Y1, Z1, X2, Y2, p)
885 if Z1 == 1:
886 return self._add_with_z2_1(X2, Y2, Z2, X1, Y1, p)
887 if Z2 == 1:
888 return self._add_with_z2_1(X1, Y1, Z1, X2, Y2, p)
889 return self._add_with_z_ne(X1, Y1, Z1, X2, Y2, Z2, p)
891 def __add__(self, other):
892 """Add two points on elliptic curve."""
893 if self == INFINITY:
894 return other
895 if other == INFINITY:
896 return self
897 if isinstance(other, Point):
898 other = PointJacobi.from_affine(other)
899 if self.__curve != other.__curve:
900 raise ValueError("The other point is on different curve")
902 p = self.__curve.p()
903 X1, Y1, Z1 = self.__coords
904 X2, Y2, Z2 = other.__coords
906 X3, Y3, Z3 = self._add(X1, Y1, Z1, X2, Y2, Z2, p)
908 if not Y3 or not Z3:
909 return INFINITY
910 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
912 def __rmul__(self, other):
913 """Multiply point by an integer."""
914 return self * other
916 def _mul_precompute(self, other):
917 """Multiply point by integer with precomputation table."""
918 X3, Y3, Z3, p = 0, 0, 1, self.__curve.p()
919 _add = self._add
920 for X2, Y2 in self.__precompute:
921 if other % 2:
922 if other % 4 >= 2:
923 other = (other + 1) // 2
924 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, 1, p)
925 else:
926 other = (other - 1) // 2
927 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, 1, p)
928 else:
929 other //= 2
931 if not Y3 or not Z3:
932 return INFINITY
933 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
935 def __mul__(self, other):
936 """Multiply point by an integer."""
937 if not self.__coords[1] or not other:
938 return INFINITY
939 if other == 1:
940 return self
941 if self.__order:
942 # order*2 as a protection for Minerva
943 other = other % (self.__order * 2)
944 self._maybe_precompute()
945 if self.__precompute:
946 return self._mul_precompute(other)
948 self = self.scale()
949 X2, Y2, _ = self.__coords
950 X3, Y3, Z3 = 0, 0, 1
951 p, a = self.__curve.p(), self.__curve.a()
952 _double = self._double
953 _add = self._add
954 # since adding points when at least one of them is scaled
955 # is quicker, reverse the NAF order
956 for i in reversed(self._naf(other)):
957 X3, Y3, Z3 = _double(X3, Y3, Z3, p, a)
958 if i < 0:
959 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, 1, p)
960 elif i > 0:
961 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, 1, p)
963 if not Y3 or not Z3:
964 return INFINITY
966 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
968 def mul_add(self, self_mul, other, other_mul):
969 """
970 Do two multiplications at the same time, add results.
972 calculates self*self_mul + other*other_mul
973 """
974 if other == INFINITY or other_mul == 0:
975 return self * self_mul
976 if self_mul == 0:
977 return other * other_mul
978 if not isinstance(other, PointJacobi):
979 other = PointJacobi.from_affine(other)
980 # when the points have precomputed answers, then multiplying them alone
981 # is faster (as it uses NAF and no point doublings)
982 self._maybe_precompute()
983 other._maybe_precompute()
984 if self.__precompute and other.__precompute:
985 return self * self_mul + other * other_mul
987 if self.__order:
988 self_mul = self_mul % self.__order
989 other_mul = other_mul % self.__order
991 # (X3, Y3, Z3) is the accumulator
992 X3, Y3, Z3 = 0, 0, 1
993 p, a = self.__curve.p(), self.__curve.a()
995 # as we have 6 unique points to work with, we can't scale all of them,
996 # but do scale the ones that are used most often
997 self.scale()
998 X1, Y1, Z1 = self.__coords
999 other.scale()
1000 X2, Y2, Z2 = other.__coords
1002 _double = self._double
1003 _add = self._add
1005 # with NAF we have 3 options: no add, subtract, add
1006 # so with 2 points, we have 9 combinations:
1007 # 0, -A, +A, -B, -A-B, +A-B, +B, -A+B, +A+B
1008 # so we need 4 combined points:
1009 mAmB_X, mAmB_Y, mAmB_Z = _add(X1, -Y1, Z1, X2, -Y2, Z2, p)
1010 pAmB_X, pAmB_Y, pAmB_Z = _add(X1, Y1, Z1, X2, -Y2, Z2, p)
1011 mApB_X, mApB_Y, mApB_Z = _add(X1, -Y1, Z1, X2, Y2, Z2, p)
1012 pApB_X, pApB_Y, pApB_Z = _add(X1, Y1, Z1, X2, Y2, Z2, p)
1013 # when the self and other sum to infinity, we need to add them
1014 # one by one to get correct result but as that's very unlikely to
1015 # happen in regular operation, we don't need to optimise this case
1016 if not pApB_Y or not pApB_Z:
1017 return self * self_mul + other * other_mul
1019 # gmp object creation has cumulatively higher overhead than the
1020 # speedup we get from calculating the NAF using gmp so ensure use
1021 # of int()
1022 self_naf = list(reversed(self._naf(int(self_mul))))
1023 other_naf = list(reversed(self._naf(int(other_mul))))
1024 # ensure that the lists are the same length (zip() will truncate
1025 # longer one otherwise)
1026 if len(self_naf) < len(other_naf):
1027 self_naf = [0] * (len(other_naf) - len(self_naf)) + self_naf
1028 elif len(self_naf) > len(other_naf):
1029 other_naf = [0] * (len(self_naf) - len(other_naf)) + other_naf
1031 for A, B in zip(self_naf, other_naf):
1032 X3, Y3, Z3 = _double(X3, Y3, Z3, p, a)
1034 # conditions ordered from most to least likely
1035 if A == 0:
1036 if B == 0:
1037 pass
1038 elif B < 0:
1039 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, Z2, p)
1040 else:
1041 assert B > 0
1042 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, Z2, p)
1043 elif A < 0:
1044 if B == 0:
1045 X3, Y3, Z3 = _add(X3, Y3, Z3, X1, -Y1, Z1, p)
1046 elif B < 0:
1047 X3, Y3, Z3 = _add(X3, Y3, Z3, mAmB_X, mAmB_Y, mAmB_Z, p)
1048 else:
1049 assert B > 0
1050 X3, Y3, Z3 = _add(X3, Y3, Z3, mApB_X, mApB_Y, mApB_Z, p)
1051 else:
1052 assert A > 0
1053 if B == 0:
1054 X3, Y3, Z3 = _add(X3, Y3, Z3, X1, Y1, Z1, p)
1055 elif B < 0:
1056 X3, Y3, Z3 = _add(X3, Y3, Z3, pAmB_X, pAmB_Y, pAmB_Z, p)
1057 else:
1058 assert B > 0
1059 X3, Y3, Z3 = _add(X3, Y3, Z3, pApB_X, pApB_Y, pApB_Z, p)
1061 if not Y3 or not Z3:
1062 return INFINITY
1064 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
1066 def __neg__(self):
1067 """Return negated point."""
1068 x, y, z = self.__coords
1069 return PointJacobi(self.__curve, x, -y, z, self.__order)
1072class Point(AbstractPoint):
1073 """A point on a short Weierstrass elliptic curve. Altering x and y is
1074 forbidden, but they can be read by the x() and y() methods."""
1076 def __init__(self, curve, x, y, order=None):
1077 """curve, x, y, order; order (optional) is the order of this point."""
1078 super(Point, self).__init__()
1079 self.__curve = curve
1080 if GMPY:
1081 self.__x = x and mpz(x)
1082 self.__y = y and mpz(y)
1083 self.__order = order and mpz(order)
1084 else:
1085 self.__x = x
1086 self.__y = y
1087 self.__order = order
1088 # self.curve is allowed to be None only for INFINITY:
1089 if self.__curve:
1090 assert self.__curve.contains_point(x, y)
1091 # for curves with cofactor 1, all points that are on the curve are
1092 # scalar multiples of the base point, so performing multiplication is
1093 # not necessary to verify that. See Section 3.2.2.1 of SEC 1 v2
1094 if curve and curve.cofactor() != 1 and order:
1095 assert self * order == INFINITY
1097 @classmethod
1098 def from_bytes(
1099 cls,
1100 curve,
1101 data,
1102 validate_encoding=True,
1103 valid_encodings=None,
1104 order=None,
1105 ):
1106 """
1107 Initialise the object from byte encoding of a point.
1109 The method does accept and automatically detect the type of point
1110 encoding used. It supports the :term:`raw encoding`,
1111 :term:`uncompressed`, :term:`compressed`, and :term:`hybrid` encodings.
1113 :param data: single point encoding of the public key
1114 :type data: :term:`bytes-like object`
1115 :param curve: the curve on which the public key is expected to lay
1116 :type curve: ~ecdsa.ellipticcurve.CurveFp
1117 :param validate_encoding: whether to verify that the encoding of the
1118 point is self-consistent, defaults to True, has effect only
1119 on ``hybrid`` encoding
1120 :type validate_encoding: bool
1121 :param valid_encodings: list of acceptable point encoding formats,
1122 supported ones are: :term:`uncompressed`, :term:`compressed`,
1123 :term:`hybrid`, and :term:`raw encoding` (specified with ``raw``
1124 name). All formats by default (specified with ``None``).
1125 :type valid_encodings: :term:`set-like object`
1126 :param int order: the point order, must be non zero when using
1127 generator=True
1129 :raises `~ecdsa.errors.MalformedPointError`: if the public point does
1130 not lay on the curve or the encoding is invalid
1132 :return: Point on curve
1133 :rtype: Point
1134 """
1135 coord_x, coord_y = super(Point, cls).from_bytes(
1136 curve, data, validate_encoding, valid_encodings
1137 )
1138 return Point(curve, coord_x, coord_y, order)
1140 def __eq__(self, other):
1141 """Return True if the points are identical, False otherwise.
1143 Note: only points that lay on the same curve can be equal.
1144 """
1145 if isinstance(other, Point):
1146 return (
1147 self.__curve == other.__curve
1148 and self.__x == other.__x
1149 and self.__y == other.__y
1150 )
1151 return NotImplemented
1153 def __ne__(self, other):
1154 """Returns False if points are identical, True otherwise."""
1155 return not self == other
1157 def __neg__(self):
1158 return Point(self.__curve, self.__x, self.__curve.p() - self.__y)
1160 def __add__(self, other):
1161 """Add one point to another point."""
1163 # X9.62 B.3:
1165 if not isinstance(other, Point):
1166 return NotImplemented
1167 if other == INFINITY:
1168 return self
1169 if self == INFINITY:
1170 return other
1171 assert self.__curve == other.__curve
1172 if self.__x == other.__x:
1173 if (self.__y + other.__y) % self.__curve.p() == 0:
1174 return INFINITY
1175 else:
1176 return self.double()
1178 p = self.__curve.p()
1180 l = (
1181 (other.__y - self.__y)
1182 * numbertheory.inverse_mod(other.__x - self.__x, p)
1183 ) % p
1185 x3 = (l * l - self.__x - other.__x) % p
1186 y3 = (l * (self.__x - x3) - self.__y) % p
1188 return Point(self.__curve, x3, y3)
1190 def __mul__(self, other):
1191 """Multiply a point by an integer."""
1193 def leftmost_bit(x):
1194 assert x > 0
1195 result = 1
1196 while result <= x:
1197 result = 2 * result
1198 return result // 2
1200 e = other
1201 if e == 0 or (self.__order and e % self.__order == 0):
1202 return INFINITY
1203 if self == INFINITY:
1204 return INFINITY
1205 if e < 0:
1206 return (-self) * (-e)
1208 # From X9.62 D.3.2:
1210 e3 = 3 * e
1211 negative_self = Point(self.__curve, self.__x, -self.__y, self.__order)
1212 i = leftmost_bit(e3) // 2
1213 result = self
1214 # print_("Multiplying %s by %d (e3 = %d):" % (self, other, e3))
1215 while i > 1:
1216 result = result.double()
1217 if (e3 & i) != 0 and (e & i) == 0:
1218 result = result + self
1219 if (e3 & i) == 0 and (e & i) != 0:
1220 result = result + negative_self
1221 # print_(". . . i = %d, result = %s" % ( i, result ))
1222 i = i // 2
1224 return result
1226 def __rmul__(self, other):
1227 """Multiply a point by an integer."""
1229 return self * other
1231 def __str__(self):
1232 if self == INFINITY:
1233 return "infinity"
1234 return "(%d,%d)" % (self.__x, self.__y)
1236 def double(self):
1237 """Return a new point that is twice the old."""
1239 if self == INFINITY:
1240 return INFINITY
1242 # X9.62 B.3:
1244 p = self.__curve.p()
1245 a = self.__curve.a()
1247 l = (
1248 (3 * self.__x * self.__x + a)
1249 * numbertheory.inverse_mod(2 * self.__y, p)
1250 ) % p
1252 x3 = (l * l - 2 * self.__x) % p
1253 y3 = (l * (self.__x - x3) - self.__y) % p
1255 return Point(self.__curve, x3, y3)
1257 def x(self):
1258 return self.__x
1260 def y(self):
1261 return self.__y
1263 def curve(self):
1264 return self.__curve
1266 def order(self):
1267 return self.__order
1270class PointEdwards(AbstractPoint):
1271 """Point on Twisted Edwards curve.
1273 Internally represents the coordinates on the curve using four parameters,
1274 X, Y, Z, T. They correspond to affine parameters 'x' and 'y' like so:
1276 x = X / Z
1277 y = Y / Z
1278 x*y = T / Z
1279 """
1281 def __init__(self, curve, x, y, z, t, order=None, generator=False):
1282 """
1283 Initialise a point that uses the extended coordinates internally.
1284 """
1285 super(PointEdwards, self).__init__()
1286 self.__curve = curve
1287 if GMPY: # pragma: no branch
1288 self.__coords = (mpz(x), mpz(y), mpz(z), mpz(t))
1289 self.__order = order and mpz(order)
1290 else: # pragma: no branch
1291 self.__coords = (x, y, z, t)
1292 self.__order = order
1293 self.__generator = generator
1294 self.__precompute = []
1296 @classmethod
1297 def from_bytes(
1298 cls,
1299 curve,
1300 data,
1301 validate_encoding=None,
1302 valid_encodings=None,
1303 order=None,
1304 generator=False,
1305 ):
1306 """
1307 Initialise the object from byte encoding of a point.
1309 `validate_encoding` and `valid_encodings` are provided for
1310 compatibility with Weierstrass curves, they are ignored for Edwards
1311 points.
1313 :param data: single point encoding of the public key
1314 :type data: :term:`bytes-like object`
1315 :param curve: the curve on which the public key is expected to lay
1316 :type curve: ecdsa.ellipticcurve.CurveEdTw
1317 :param None validate_encoding: Ignored, encoding is always validated
1318 :param None valid_encodings: Ignored, there is just one encoding
1319 supported
1320 :param int order: the point order, must be non zero when using
1321 generator=True
1322 :param bool generator: Flag to mark the point as a curve generator,
1323 this will cause the library to pre-compute some values to
1324 make repeated usages of the point much faster
1326 :raises `~ecdsa.errors.MalformedPointError`: if the public point does
1327 not lay on the curve or the encoding is invalid
1329 :return: Initialised point on an Edwards curve
1330 :rtype: PointEdwards
1331 """
1332 coord_x, coord_y = super(PointEdwards, cls).from_bytes(
1333 curve, data, validate_encoding, valid_encodings
1334 )
1335 return PointEdwards(
1336 curve, coord_x, coord_y, 1, coord_x * coord_y, order, generator
1337 )
1339 def _maybe_precompute(self):
1340 if not self.__generator or self.__precompute:
1341 return self.__precompute
1343 # since this code will execute just once, and it's fully deterministic,
1344 # depend on atomicity of the last assignment to switch from empty
1345 # self.__precompute to filled one and just ignore the unlikely
1346 # situation when two threads execute it at the same time (as it won't
1347 # lead to inconsistent __precompute)
1348 order = self.__order
1349 assert order
1350 precompute = []
1351 i = 1
1352 order *= 2
1353 coord_x, coord_y, coord_z, coord_t = self.__coords
1354 prime = self.__curve.p()
1356 doubler = PointEdwards(
1357 self.__curve, coord_x, coord_y, coord_z, coord_t, order
1358 )
1359 # for "protection" against Minerva we need 1 or 2 more bits depending
1360 # on order bit size, but it's easier to just calculate one
1361 # point more always
1362 order *= 4
1364 while i < order:
1365 doubler = doubler.scale()
1366 coord_x, coord_y = doubler.x(), doubler.y()
1367 coord_t = coord_x * coord_y % prime
1368 precompute.append((coord_x, coord_y, coord_t))
1370 i *= 2
1371 doubler = doubler.double()
1373 self.__precompute = precompute
1374 return self.__precompute
1376 def x(self):
1377 """Return affine x coordinate."""
1378 X1, _, Z1, _ = self.__coords
1379 if Z1 == 1:
1380 return X1
1381 p = self.__curve.p()
1382 z_inv = numbertheory.inverse_mod(Z1, p)
1383 return X1 * z_inv % p
1385 def y(self):
1386 """Return affine y coordinate."""
1387 _, Y1, Z1, _ = self.__coords
1388 if Z1 == 1:
1389 return Y1
1390 p = self.__curve.p()
1391 z_inv = numbertheory.inverse_mod(Z1, p)
1392 return Y1 * z_inv % p
1394 def curve(self):
1395 """Return the curve of the point."""
1396 return self.__curve
1398 def order(self):
1399 return self.__order
1401 def scale(self):
1402 """
1403 Return point scaled so that z == 1.
1405 Modifies point in place, returns self.
1406 """
1407 X1, Y1, Z1, _ = self.__coords
1408 if Z1 == 1:
1409 return self
1411 p = self.__curve.p()
1412 z_inv = numbertheory.inverse_mod(Z1, p)
1413 x = X1 * z_inv % p
1414 y = Y1 * z_inv % p
1415 t = x * y % p
1416 self.__coords = (x, y, 1, t)
1417 return self
1419 def __eq__(self, other):
1420 """Compare for equality two points with each-other.
1422 Note: only points on the same curve can be equal.
1423 """
1424 x1, y1, z1, t1 = self.__coords
1425 if other is INFINITY:
1426 return not x1 or not t1
1427 if isinstance(other, PointEdwards):
1428 x2, y2, z2, t2 = other.__coords
1429 else:
1430 return NotImplemented
1431 if self.__curve != other.curve():
1432 return False
1433 p = self.__curve.p()
1435 # cross multiply to eliminate divisions
1436 xn1 = x1 * z2 % p
1437 xn2 = x2 * z1 % p
1438 yn1 = y1 * z2 % p
1439 yn2 = y2 * z1 % p
1440 return xn1 == xn2 and yn1 == yn2
1442 def __ne__(self, other):
1443 """Compare for inequality two points with each-other."""
1444 return not self == other
1446 def _add(self, X1, Y1, Z1, T1, X2, Y2, Z2, T2, p, a):
1447 """add two points, assume sane parameters."""
1448 # after add-2008-hwcd-2
1449 # from https://hyperelliptic.org/EFD/g1p/auto-twisted-extended.html
1450 # NOTE: there are more efficient formulas for Z1 or Z2 == 1
1451 A = X1 * X2 % p
1452 B = Y1 * Y2 % p
1453 C = Z1 * T2 % p
1454 D = T1 * Z2 % p
1455 E = D + C
1456 F = ((X1 - Y1) * (X2 + Y2) + B - A) % p
1457 G = B + a * A
1458 H = D - C
1459 if not H:
1460 return self._double(X1, Y1, Z1, T1, p, a)
1461 X3 = E * F % p
1462 Y3 = G * H % p
1463 T3 = E * H % p
1464 Z3 = F * G % p
1466 return X3, Y3, Z3, T3
1468 def __add__(self, other):
1469 """Add point to another."""
1470 if other == INFINITY:
1471 return self
1472 if (
1473 not isinstance(other, PointEdwards)
1474 or self.__curve != other.__curve
1475 ):
1476 raise ValueError("The other point is on a different curve.")
1478 p, a = self.__curve.p(), self.__curve.a()
1479 X1, Y1, Z1, T1 = self.__coords
1480 X2, Y2, Z2, T2 = other.__coords
1482 X3, Y3, Z3, T3 = self._add(X1, Y1, Z1, T1, X2, Y2, Z2, T2, p, a)
1484 if not X3 or not T3:
1485 return INFINITY
1486 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1488 def __radd__(self, other):
1489 """Add other to self."""
1490 return self + other
1492 def _double(self, X1, Y1, Z1, T1, p, a):
1493 """Double the point, assume sane parameters."""
1494 # after "dbl-2008-hwcd"
1495 # from https://hyperelliptic.org/EFD/g1p/auto-twisted-extended.html
1496 # NOTE: there are more efficient formulas for Z1 == 1
1497 A = X1 * X1 % p
1498 B = Y1 * Y1 % p
1499 C = 2 * Z1 * Z1 % p
1500 D = a * A % p
1501 E = ((X1 + Y1) * (X1 + Y1) - A - B) % p
1502 G = D + B
1503 F = G - C
1504 H = D - B
1505 X3 = E * F % p
1506 Y3 = G * H % p
1507 T3 = E * H % p
1508 Z3 = F * G % p
1510 return X3, Y3, Z3, T3
1512 def double(self):
1513 """Return point added to itself."""
1514 X1, Y1, Z1, T1 = self.__coords
1516 if not X1 or not T1:
1517 return INFINITY
1519 p, a = self.__curve.p(), self.__curve.a()
1521 X3, Y3, Z3, T3 = self._double(X1, Y1, Z1, T1, p, a)
1523 if not X3 or not T3:
1524 return INFINITY
1525 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1527 def __rmul__(self, other):
1528 """Multiply point by an integer."""
1529 return self * other
1531 def _mul_precompute(self, other):
1532 """Multiply point by integer with precomputation table."""
1533 X3, Y3, Z3, T3, p, a = 0, 1, 1, 0, self.__curve.p(), self.__curve.a()
1534 _add = self._add
1535 for X2, Y2, T2 in self.__precompute:
1536 rem = other % 4
1537 if rem == 0 or rem == 2:
1538 other //= 2
1539 elif rem == 3:
1540 other = (other + 1) // 2
1541 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, -X2, Y2, 1, -T2, p, a)
1542 else:
1543 assert rem == 1
1544 other = (other - 1) // 2
1545 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, X2, Y2, 1, T2, p, a)
1547 if not X3 or not T3:
1548 return INFINITY
1550 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1552 def __mul__(self, other):
1553 """Multiply point by an integer."""
1554 X2, Y2, Z2, T2 = self.__coords
1555 if not X2 or not T2 or not other:
1556 return INFINITY
1557 if other == 1:
1558 return self
1559 if self.__order:
1560 # order*2 as a "protection" for Minerva
1561 other = other % (self.__order * 2)
1562 if self._maybe_precompute():
1563 return self._mul_precompute(other)
1565 X3, Y3, Z3, T3 = 0, 1, 1, 0 # INFINITY in extended coordinates
1566 p, a = self.__curve.p(), self.__curve.a()
1567 _double = self._double
1568 _add = self._add
1570 for i in reversed(self._naf(other)):
1571 X3, Y3, Z3, T3 = _double(X3, Y3, Z3, T3, p, a)
1572 if i < 0:
1573 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, -X2, Y2, Z2, -T2, p, a)
1574 elif i > 0:
1575 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, X2, Y2, Z2, T2, p, a)
1577 if not X3 or not T3:
1578 return INFINITY
1580 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1583# This one point is the Point At Infinity for all purposes:
1584INFINITY = Point(None, None, None)