Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/ecdsa/ellipticcurve.py: 73%
Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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 if self.__h is not None:
140 return "CurveFp(p={0}, a={1}, b={2}, h={3})".format(
141 self.__p,
142 self.__a,
143 self.__b,
144 self.__h,
145 )
146 return "CurveFp(p={0}, a={1}, b={2})".format(
147 self.__p,
148 self.__a,
149 self.__b,
150 )
153class CurveEdTw(object):
154 """Parameters for a Twisted Edwards Elliptic Curve"""
156 if GMPY: # pragma: no branch
158 def __init__(self, p, a, d, h=None, hash_func=None):
159 """
160 The curve of points satisfying a*x^2 + y^2 = 1 + d*x^2*y^2 (mod p).
162 h is the cofactor of the curve.
163 hash_func is the hash function associated with the curve
164 (like SHA-512 for Ed25519)
165 """
166 self.__p = mpz(p)
167 self.__a = mpz(a)
168 self.__d = mpz(d)
169 self.__h = h
170 self.__hash_func = hash_func
172 else:
174 def __init__(self, p, a, d, h=None, hash_func=None):
175 """
176 The curve of points satisfying a*x^2 + y^2 = 1 + d*x^2*y^2 (mod p).
178 h is the cofactor of the curve.
179 hash_func is the hash function associated with the curve
180 (like SHA-512 for Ed25519)
181 """
182 self.__p = p
183 self.__a = a
184 self.__d = d
185 self.__h = h
186 self.__hash_func = hash_func
188 def __eq__(self, other):
189 """Returns True if other is an identical curve."""
190 if isinstance(other, CurveEdTw):
191 p = self.__p
192 return (
193 self.__p == other.__p
194 and self.__a % p == other.__a % p
195 and self.__d % p == other.__d % p
196 )
197 return NotImplemented
199 def __ne__(self, other):
200 """Return False if the other is an identical curve, True otherwise."""
201 return not self == other
203 def __hash__(self):
204 return hash((self.__p, self.__a, self.__d))
206 def contains_point(self, x, y):
207 """Is the point (x, y) on this curve?"""
208 return (
209 self.__a * x * x + y * y - 1 - self.__d * x * x * y * y
210 ) % self.__p == 0
212 def p(self):
213 return self.__p
215 def a(self):
216 return self.__a
218 def d(self):
219 return self.__d
221 def hash_func(self, data):
222 return self.__hash_func(data)
224 def cofactor(self):
225 return self.__h
227 def __str__(self):
228 if self.__h is not None:
229 return "CurveEdTw(p={0}, a={1}, d={2}, h={3})".format(
230 self.__p,
231 self.__a,
232 self.__d,
233 self.__h,
234 )
235 return "CurveEdTw(p={0}, a={1}, d={2})".format(
236 self.__p,
237 self.__a,
238 self.__d,
239 )
242class AbstractPoint(object):
243 """Class for common methods of elliptic curve points."""
245 @staticmethod
246 def _from_raw_encoding(data, raw_encoding_length):
247 """
248 Decode public point from :term:`raw encoding`.
250 :term:`raw encoding` is the same as the :term:`uncompressed` encoding,
251 but without the 0x04 byte at the beginning.
252 """
253 # real assert, from_bytes() should not call us with different length
254 assert len(data) == raw_encoding_length
255 xs = data[: raw_encoding_length // 2]
256 ys = data[raw_encoding_length // 2 :]
257 # real assert, raw_encoding_length is calculated by multiplying an
258 # integer by two so it will always be even
259 assert len(xs) == raw_encoding_length // 2
260 assert len(ys) == raw_encoding_length // 2
261 coord_x = string_to_number(xs)
262 coord_y = string_to_number(ys)
264 return coord_x, coord_y
266 @staticmethod
267 def _from_compressed(data, curve):
268 """Decode public point from compressed encoding."""
269 if data[:1] not in (b"\x02", b"\x03"):
270 raise MalformedPointError("Malformed compressed point encoding")
272 is_even = data[:1] == b"\x02"
273 x = string_to_number(data[1:])
274 p = curve.p()
275 alpha = (pow(x, 3, p) + (curve.a() * x) + curve.b()) % p
276 try:
277 beta = numbertheory.square_root_mod_prime(alpha, p)
278 except numbertheory.Error as e:
279 raise MalformedPointError(
280 "Encoding does not correspond to a point on curve", e
281 )
282 if is_even == bool(beta & 1):
283 y = p - beta
284 else:
285 y = beta
286 return x, y
288 @classmethod
289 def _from_hybrid(cls, data, raw_encoding_length, validate_encoding):
290 """Decode public point from hybrid encoding."""
291 # real assert, from_bytes() should not call us with different types
292 assert data[:1] in (b"\x06", b"\x07")
294 # primarily use the uncompressed as it's easiest to handle
295 x, y = cls._from_raw_encoding(data[1:], raw_encoding_length)
297 # but validate if it's self-consistent if we're asked to do that
298 if validate_encoding and (
299 y & 1
300 and data[:1] != b"\x07"
301 or (not y & 1)
302 and data[:1] != b"\x06"
303 ):
304 raise MalformedPointError("Inconsistent hybrid point encoding")
306 return x, y
308 @classmethod
309 def _from_edwards(cls, curve, data):
310 """Decode a point on an Edwards curve."""
311 data = bytearray(data)
312 p = curve.p()
313 # add 1 for the sign bit and then round up
314 exp_len = (bit_length(p) + 1 + 7) // 8
315 if len(data) != exp_len:
316 raise MalformedPointError("Point length doesn't match the curve.")
317 x_0 = (data[-1] & 0x80) >> 7
319 data[-1] &= 0x80 - 1
321 y = bytes_to_int(data, "little")
322 if GMPY:
323 y = mpz(y)
325 x2 = (
326 (y * y - 1)
327 * numbertheory.inverse_mod(curve.d() * y * y - curve.a(), p)
328 % p
329 )
331 try:
332 x = numbertheory.square_root_mod_prime(x2, p)
333 except numbertheory.Error as e:
334 raise MalformedPointError(
335 "Encoding does not correspond to a point on curve", e
336 )
338 if x % 2 != x_0:
339 x = -x % p
341 return x, y
343 @classmethod
344 def from_bytes(
345 cls, curve, data, validate_encoding=True, valid_encodings=None
346 ):
347 """
348 Initialise the object from byte encoding of a point.
350 The method does accept and automatically detect the type of point
351 encoding used. It supports the :term:`raw encoding`,
352 :term:`uncompressed`, :term:`compressed`, and :term:`hybrid` encodings.
354 Note: generally you will want to call the ``from_bytes()`` method of
355 either a child class, PointJacobi or Point.
357 :param data: single point encoding of the public key
358 :type data: :term:`bytes-like object`
359 :param curve: the curve on which the public key is expected to lay
360 :type curve: ~ecdsa.ellipticcurve.CurveFp
361 :param validate_encoding: whether to verify that the encoding of the
362 point is self-consistent, defaults to True, has effect only
363 on ``hybrid`` encoding
364 :type validate_encoding: bool
365 :param valid_encodings: list of acceptable point encoding formats,
366 supported ones are: :term:`uncompressed`, :term:`compressed`,
367 :term:`hybrid`, and :term:`raw encoding` (specified with ``raw``
368 name). All formats by default (specified with ``None``).
369 :type valid_encodings: :term:`set-like object`
371 :raises `~ecdsa.errors.MalformedPointError`: if the public point does
372 not lay on the curve or the encoding is invalid
374 :return: x and y coordinates of the encoded point
375 :rtype: tuple(int, int)
376 """
377 if not valid_encodings:
378 valid_encodings = set(
379 ["uncompressed", "compressed", "hybrid", "raw"]
380 )
381 if not all(
382 i in set(("uncompressed", "compressed", "hybrid", "raw"))
383 for i in valid_encodings
384 ):
385 raise ValueError(
386 "Only uncompressed, compressed, hybrid or raw encoding "
387 "supported."
388 )
389 data = normalise_bytes(data)
391 if isinstance(curve, CurveEdTw):
392 return cls._from_edwards(curve, data)
394 key_len = len(data)
395 raw_encoding_length = 2 * orderlen(curve.p())
396 if key_len == raw_encoding_length and "raw" in valid_encodings:
397 coord_x, coord_y = cls._from_raw_encoding(
398 data, raw_encoding_length
399 )
400 elif key_len == raw_encoding_length + 1 and (
401 "hybrid" in valid_encodings or "uncompressed" in valid_encodings
402 ):
403 if data[:1] in (b"\x06", b"\x07") and "hybrid" in valid_encodings:
404 coord_x, coord_y = cls._from_hybrid(
405 data, raw_encoding_length, validate_encoding
406 )
407 elif data[:1] == b"\x04" and "uncompressed" in valid_encodings:
408 coord_x, coord_y = cls._from_raw_encoding(
409 data[1:], raw_encoding_length
410 )
411 else:
412 raise MalformedPointError(
413 "Invalid X9.62 encoding of the public point"
414 )
415 elif (
416 key_len == raw_encoding_length // 2 + 1
417 and "compressed" in valid_encodings
418 ):
419 coord_x, coord_y = cls._from_compressed(data, curve)
420 else:
421 raise MalformedPointError(
422 "Length of string does not match lengths of "
423 "any of the enabled ({0}) encodings of the "
424 "curve.".format(", ".join(valid_encodings))
425 )
426 return coord_x, coord_y
428 def _raw_encode(self):
429 """Convert the point to the :term:`raw encoding`."""
430 prime = self.curve().p()
431 x_str = number_to_string(self.x(), prime)
432 y_str = number_to_string(self.y(), prime)
433 return x_str + y_str
435 def _compressed_encode(self):
436 """Encode the point into the compressed form."""
437 prime = self.curve().p()
438 x_str = number_to_string(self.x(), prime)
439 if self.y() & 1:
440 return b"\x03" + x_str
441 return b"\x02" + x_str
443 def _hybrid_encode(self):
444 """Encode the point into the hybrid form."""
445 raw_enc = self._raw_encode()
446 if self.y() & 1:
447 return b"\x07" + raw_enc
448 return b"\x06" + raw_enc
450 def _edwards_encode(self):
451 """Encode the point according to RFC8032 encoding."""
452 self.scale()
453 x, y, p = self.x(), self.y(), self.curve().p()
455 # add 1 for the sign bit and then round up
456 enc_len = (bit_length(p) + 1 + 7) // 8
457 y_str = int_to_bytes(y, enc_len, "little")
458 if x % 2:
459 y_str[-1] |= 0x80
460 return y_str
462 def to_bytes(self, encoding="raw"):
463 """
464 Convert the point to a byte string.
466 The method by default uses the :term:`raw encoding` (specified
467 by `encoding="raw"`. It can also output points in :term:`uncompressed`,
468 :term:`compressed`, and :term:`hybrid` formats.
470 For points on Edwards curves `encoding` is ignored and only the
471 encoding defined in RFC 8032 is supported.
473 :return: :term:`raw encoding` of a public on the curve
474 :rtype: bytes
475 """
476 assert encoding in ("raw", "uncompressed", "compressed", "hybrid")
477 curve = self.curve()
478 if isinstance(curve, CurveEdTw):
479 return self._edwards_encode()
480 elif encoding == "raw":
481 return self._raw_encode()
482 elif encoding == "uncompressed":
483 return b"\x04" + self._raw_encode()
484 elif encoding == "hybrid":
485 return self._hybrid_encode()
486 else:
487 return self._compressed_encode()
489 @staticmethod
490 def _naf(mult):
491 """Calculate non-adjacent form of number."""
492 ret = []
493 while mult:
494 if mult % 2:
495 nd = mult % 4
496 if nd >= 2:
497 nd -= 4
498 ret.append(nd)
499 mult -= nd
500 else:
501 ret.append(0)
502 mult //= 2
503 return ret
506class PointJacobi(AbstractPoint):
507 """
508 Point on a short Weierstrass elliptic curve. Uses Jacobi coordinates.
510 In Jacobian coordinates, there are three parameters, X, Y and Z.
511 They correspond to affine parameters 'x' and 'y' like so:
513 x = X / Z²
514 y = Y / Z³
515 """
517 def __init__(self, curve, x, y, z, order=None, generator=False):
518 """
519 Initialise a point that uses Jacobi representation internally.
521 :param CurveFp curve: curve on which the point resides
522 :param int x: the X parameter of Jacobi representation (equal to x when
523 converting from affine coordinates
524 :param int y: the Y parameter of Jacobi representation (equal to y when
525 converting from affine coordinates
526 :param int z: the Z parameter of Jacobi representation (equal to 1 when
527 converting from affine coordinates
528 :param int order: the point order, must be non zero when using
529 generator=True
530 :param bool generator: the point provided is a curve generator, as
531 such, it will be commonly used with scalar multiplication. This will
532 cause to precompute multiplication table generation for it
533 """
534 super(PointJacobi, self).__init__()
535 self.__curve = curve
536 if GMPY: # pragma: no branch
537 self.__coords = (mpz(x), mpz(y), mpz(z))
538 self.__order = order and mpz(order)
539 else: # pragma: no branch
540 self.__coords = (x, y, z)
541 self.__order = order
542 self.__generator = generator
543 self.__precompute = []
545 @classmethod
546 def from_bytes(
547 cls,
548 curve,
549 data,
550 validate_encoding=True,
551 valid_encodings=None,
552 order=None,
553 generator=False,
554 ):
555 """
556 Initialise the object from byte encoding of a point.
558 The method does accept and automatically detect the type of point
559 encoding used. It supports the :term:`raw encoding`,
560 :term:`uncompressed`, :term:`compressed`, and :term:`hybrid` encodings.
562 :param data: single point encoding of the public key
563 :type data: :term:`bytes-like object`
564 :param curve: the curve on which the public key is expected to lay
565 :type curve: ~ecdsa.ellipticcurve.CurveFp
566 :param validate_encoding: whether to verify that the encoding of the
567 point is self-consistent, defaults to True, has effect only
568 on ``hybrid`` encoding
569 :type validate_encoding: bool
570 :param valid_encodings: list of acceptable point encoding formats,
571 supported ones are: :term:`uncompressed`, :term:`compressed`,
572 :term:`hybrid`, and :term:`raw encoding` (specified with ``raw``
573 name). All formats by default (specified with ``None``).
574 :type valid_encodings: :term:`set-like object`
575 :param int order: the point order, must be non zero when using
576 generator=True
577 :param bool generator: the point provided is a curve generator, as
578 such, it will be commonly used with scalar multiplication. This
579 will cause to precompute multiplication table generation for it
581 :raises `~ecdsa.errors.MalformedPointError`: if the public point does
582 not lay on the curve or the encoding is invalid
584 :return: Point on curve
585 :rtype: PointJacobi
586 """
587 coord_x, coord_y = super(PointJacobi, cls).from_bytes(
588 curve, data, validate_encoding, valid_encodings
589 )
590 return PointJacobi(curve, coord_x, coord_y, 1, order, generator)
592 def _maybe_precompute(self):
593 if not self.__generator or self.__precompute:
594 return
596 # since this code will execute just once, and it's fully deterministic,
597 # depend on atomicity of the last assignment to switch from empty
598 # self.__precompute to filled one and just ignore the unlikely
599 # situation when two threads execute it at the same time (as it won't
600 # lead to inconsistent __precompute)
601 order = self.__order
602 assert order
603 precompute = []
604 i = 1
605 order *= 2
606 coord_x, coord_y, coord_z = self.__coords
607 doubler = PointJacobi(self.__curve, coord_x, coord_y, coord_z, order)
608 order *= 2
609 precompute.append((doubler.x(), doubler.y()))
611 while i < order:
612 i *= 2
613 doubler = doubler.double().scale()
614 precompute.append((doubler.x(), doubler.y()))
616 self.__precompute = precompute
618 def __getstate__(self):
619 # while this code can execute at the same time as _maybe_precompute()
620 # is updating the __precompute or scale() is updating the __coords,
621 # there is no requirement for consistency between __coords and
622 # __precompute
623 state = self.__dict__.copy()
624 return state
626 def __setstate__(self, state):
627 self.__dict__.update(state)
629 def __eq__(self, other):
630 """Compare for equality two points with each-other.
632 Note: only points that lay on the same curve can be equal.
633 """
634 x1, y1, z1 = self.__coords
635 if other is INFINITY:
636 return not z1
637 if isinstance(other, Point):
638 x2, y2, z2 = other.x(), other.y(), 1
639 elif isinstance(other, PointJacobi):
640 x2, y2, z2 = other.__coords
641 else:
642 return NotImplemented
643 if self.__curve != other.curve():
644 return False
645 p = self.__curve.p()
647 zz1 = z1 * z1 % p
648 zz2 = z2 * z2 % p
650 # compare the fractions by bringing them to the same denominator
651 # depend on short-circuit to save 4 multiplications in case of
652 # inequality
653 return (x1 * zz2 - x2 * zz1) % p == 0 and (
654 y1 * zz2 * z2 - y2 * zz1 * z1
655 ) % p == 0
657 def __ne__(self, other):
658 """Compare for inequality two points with each-other."""
659 return not self == other
661 def order(self):
662 """Return the order of the point.
664 None if it is undefined.
665 """
666 return self.__order
668 def curve(self):
669 """Return curve over which the point is defined."""
670 return self.__curve
672 def x(self):
673 """
674 Return affine x coordinate.
676 This method should be used only when the 'y' coordinate is not needed.
677 It's computationally more efficient to use `to_affine()` and then
678 call x() and y() on the returned instance. Or call `scale()`
679 and then x() and y() on the returned instance.
680 """
681 x, _, z = self.__coords
682 if z == 1:
683 return x
684 p = self.__curve.p()
685 z = numbertheory.inverse_mod(z, p)
686 return x * z**2 % p
688 def y(self):
689 """
690 Return affine y coordinate.
692 This method should be used only when the 'x' coordinate is not needed.
693 It's computationally more efficient to use `to_affine()` and then
694 call x() and y() on the returned instance. Or call `scale()`
695 and then x() and y() on the returned instance.
696 """
697 _, y, z = self.__coords
698 if z == 1:
699 return y
700 p = self.__curve.p()
701 z = numbertheory.inverse_mod(z, p)
702 return y * z**3 % p
704 def scale(self):
705 """
706 Return point scaled so that z == 1.
708 Modifies point in place, returns self.
709 """
710 x, y, z = self.__coords
711 if z == 1:
712 return self
714 # scaling is deterministic, so even if two threads execute the below
715 # code at the same time, they will set __coords to the same value
716 p = self.__curve.p()
717 z_inv = numbertheory.inverse_mod(z, p)
718 zz_inv = z_inv * z_inv % p
719 x = x * zz_inv % p
720 y = y * zz_inv * z_inv % p
721 self.__coords = (x, y, 1)
722 return self
724 def to_affine(self):
725 """Return point in affine form."""
726 _, _, z = self.__coords
727 p = self.__curve.p()
728 if not (z % p):
729 return INFINITY
730 self.scale()
731 x, y, z = self.__coords
732 assert z == 1
733 return Point(self.__curve, x, y, self.__order)
735 @staticmethod
736 def from_affine(point, generator=False):
737 """Create from an affine point.
739 :param bool generator: set to True to make the point to precalculate
740 multiplication table - useful for public point when verifying many
741 signatures (around 100 or so) or for generator points of a curve.
742 """
743 return PointJacobi(
744 point.curve(), point.x(), point.y(), 1, point.order(), generator
745 )
747 # please note that all the methods that use the equations from
748 # hyperelliptic
749 # are formatted in a way to maximise performance.
750 # Things that make code faster: multiplying instead of taking to the power
751 # (`xx = x * x; xxxx = xx * xx % p` is faster than `xxxx = x**4 % p` and
752 # `pow(x, 4, p)`),
753 # multiple assignments at the same time (`x1, x2 = self.x1, self.x2` is
754 # faster than `x1 = self.x1; x2 = self.x2`),
755 # similarly, sometimes the `% p` is skipped if it makes the calculation
756 # faster and the result of calculation is later reduced modulo `p`
758 def _double_with_z_1(self, X1, Y1, p, a):
759 """Add a point to itself with z == 1."""
760 # after:
761 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-mdbl-2007-bl
762 XX, YY = X1 * X1 % p, Y1 * Y1 % p
763 if not YY:
764 return 0, 0, 0
765 YYYY = YY * YY % p
766 S = 2 * ((X1 + YY) ** 2 - XX - YYYY) % p
767 M = 3 * XX + a
768 T = (M * M - 2 * S) % p
769 # X3 = T
770 Y3 = (M * (S - T) - 8 * YYYY) % p
771 Z3 = 2 * Y1 % p
772 return T, Y3, Z3
774 def _double(self, X1, Y1, Z1, p, a):
775 """Add a point to itself, arbitrary z."""
776 if Z1 == 1:
777 return self._double_with_z_1(X1, Y1, p, a)
778 if not Z1:
779 return 0, 0, 0
780 # after:
781 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl
782 XX, YY = X1 * X1 % p, Y1 * Y1 % p
783 if not YY:
784 return 0, 0, 0
785 YYYY = YY * YY % p
786 ZZ = Z1 * Z1 % p
787 S = 2 * ((X1 + YY) ** 2 - XX - YYYY) % p
788 M = (3 * XX + a * ZZ * ZZ) % p
789 T = (M * M - 2 * S) % p
790 # X3 = T
791 Y3 = (M * (S - T) - 8 * YYYY) % p
792 Z3 = ((Y1 + Z1) ** 2 - YY - ZZ) % p
794 return T, Y3, Z3
796 def double(self):
797 """Add a point to itself."""
798 X1, Y1, Z1 = self.__coords
800 if not Z1:
801 return INFINITY
803 p, a = self.__curve.p(), self.__curve.a()
805 X3, Y3, Z3 = self._double(X1, Y1, Z1, p, a)
807 if not Z3:
808 return INFINITY
809 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
811 def _add_with_z_1(self, X1, Y1, X2, Y2, p):
812 """add points when both Z1 and Z2 equal 1"""
813 # after:
814 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-mmadd-2007-bl
815 H = X2 - X1
816 HH = H * H
817 I = 4 * HH % p
818 J = H * I
819 r = 2 * (Y2 - Y1)
820 if not H and not r:
821 return self._double_with_z_1(X1, Y1, p, self.__curve.a())
822 V = X1 * I
823 X3 = (r**2 - J - 2 * V) % p
824 Y3 = (r * (V - X3) - 2 * Y1 * J) % p
825 Z3 = 2 * H % p
826 return X3, Y3, Z3
828 def _add_with_z_eq(self, X1, Y1, Z1, X2, Y2, p):
829 """add points when Z1 == Z2"""
830 # after:
831 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-zadd-2007-m
832 A = (X2 - X1) ** 2 % p
833 B = X1 * A % p
834 C = X2 * A
835 D = (Y2 - Y1) ** 2 % p
836 if not A and not D:
837 return self._double(X1, Y1, Z1, p, self.__curve.a())
838 X3 = (D - B - C) % p
839 Y3 = ((Y2 - Y1) * (B - X3) - Y1 * (C - B)) % p
840 Z3 = Z1 * (X2 - X1) % p
841 return X3, Y3, Z3
843 def _add_with_z2_1(self, X1, Y1, Z1, X2, Y2, p):
844 """add points when Z2 == 1"""
845 # after:
846 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-madd-2007-bl
847 Z1Z1 = Z1 * Z1 % p
848 U2, S2 = X2 * Z1Z1 % p, Y2 * Z1 * Z1Z1 % p
849 H = (U2 - X1) % p
850 HH = H * H % p
851 I = 4 * HH % p
852 J = H * I
853 r = 2 * (S2 - Y1) % p
854 if not r and not H:
855 return self._double_with_z_1(X2, Y2, p, self.__curve.a())
856 V = X1 * I
857 X3 = (r * r - J - 2 * V) % p
858 Y3 = (r * (V - X3) - 2 * Y1 * J) % p
859 Z3 = ((Z1 + H) ** 2 - Z1Z1 - HH) % p
860 return X3, Y3, Z3
862 def _add_with_z_ne(self, X1, Y1, Z1, X2, Y2, Z2, p):
863 """add points with arbitrary z"""
864 # after:
865 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl
866 Z1Z1 = Z1 * Z1 % p
867 Z2Z2 = Z2 * Z2 % p
868 U1 = X1 * Z2Z2 % p
869 U2 = X2 * Z1Z1 % p
870 S1 = Y1 * Z2 * Z2Z2 % p
871 S2 = Y2 * Z1 * Z1Z1 % p
872 H = U2 - U1
873 I = 4 * H * H % p
874 J = H * I % p
875 r = 2 * (S2 - S1) % p
876 if not H and not r:
877 return self._double(X1, Y1, Z1, p, self.__curve.a())
878 V = U1 * I
879 X3 = (r * r - J - 2 * V) % p
880 Y3 = (r * (V - X3) - 2 * S1 * J) % p
881 Z3 = ((Z1 + Z2) ** 2 - Z1Z1 - Z2Z2) * H % p
883 return X3, Y3, Z3
885 def __radd__(self, other):
886 """Add other to self."""
887 return self + other
889 def _add(self, X1, Y1, Z1, X2, Y2, Z2, p):
890 """add two points, select fastest method."""
891 if not Z1:
892 return X2 % p, Y2 % p, Z2 % p
893 if not Z2:
894 return X1 % p, Y1 % p, Z1 % p
895 if Z1 == Z2:
896 if Z1 == 1:
897 return self._add_with_z_1(X1, Y1, X2, Y2, p)
898 return self._add_with_z_eq(X1, Y1, Z1, X2, Y2, p)
899 if Z1 == 1:
900 return self._add_with_z2_1(X2, Y2, Z2, X1, Y1, p)
901 if Z2 == 1:
902 return self._add_with_z2_1(X1, Y1, Z1, X2, Y2, p)
903 return self._add_with_z_ne(X1, Y1, Z1, X2, Y2, Z2, p)
905 def __add__(self, other):
906 """Add two points on elliptic curve."""
907 if self == INFINITY:
908 return other
909 if other == INFINITY:
910 return self
911 if isinstance(other, Point):
912 other = PointJacobi.from_affine(other)
913 if self.__curve != other.__curve:
914 raise ValueError("The other point is on different curve")
916 p = self.__curve.p()
917 X1, Y1, Z1 = self.__coords
918 X2, Y2, Z2 = other.__coords
920 X3, Y3, Z3 = self._add(X1, Y1, Z1, X2, Y2, Z2, p)
922 if not Z3:
923 return INFINITY
924 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
926 def __rmul__(self, other):
927 """Multiply point by an integer."""
928 return self * other
930 def _mul_precompute(self, other):
931 """Multiply point by integer with precomputation table."""
932 X3, Y3, Z3, p = 0, 0, 0, self.__curve.p()
933 _add = self._add
934 for X2, Y2 in self.__precompute:
935 if other % 2:
936 if other % 4 >= 2:
937 other = (other + 1) // 2
938 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, 1, p)
939 else:
940 other = (other - 1) // 2
941 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, 1, p)
942 else:
943 other //= 2
945 if not Z3:
946 return INFINITY
947 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
949 def __mul__(self, other):
950 """Multiply point by an integer."""
951 if not self.__coords[1] or not other:
952 return INFINITY
953 if other == 1:
954 return self
955 if self.__order:
956 # order*2 as a protection for Minerva
957 other = other % (self.__order * 2)
958 self._maybe_precompute()
959 if self.__precompute:
960 return self._mul_precompute(other)
962 self = self.scale()
963 X2, Y2, _ = self.__coords
964 X3, Y3, Z3 = 0, 0, 0
965 p, a = self.__curve.p(), self.__curve.a()
966 _double = self._double
967 _add = self._add
968 # since adding points when at least one of them is scaled
969 # is quicker, reverse the NAF order
970 for i in reversed(self._naf(other)):
971 X3, Y3, Z3 = _double(X3, Y3, Z3, p, a)
972 if i < 0:
973 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, 1, p)
974 elif i > 0:
975 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, 1, p)
977 if not Z3:
978 return INFINITY
980 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
982 def mul_add(self, self_mul, other, other_mul):
983 """
984 Do two multiplications at the same time, add results.
986 calculates self*self_mul + other*other_mul
987 """
988 if other == INFINITY or other_mul == 0:
989 return self * self_mul
990 if self_mul == 0:
991 return other * other_mul
992 if not isinstance(other, PointJacobi):
993 other = PointJacobi.from_affine(other)
994 # when the points have precomputed answers, then multiplying them alone
995 # is faster (as it uses NAF and no point doublings)
996 self._maybe_precompute()
997 other._maybe_precompute()
998 if self.__precompute and other.__precompute:
999 return self * self_mul + other * other_mul
1001 if self.__order:
1002 self_mul = self_mul % self.__order
1003 other_mul = other_mul % self.__order
1005 # (X3, Y3, Z3) is the accumulator
1006 X3, Y3, Z3 = 0, 0, 0
1007 p, a = self.__curve.p(), self.__curve.a()
1009 # as we have 6 unique points to work with, we can't scale all of them,
1010 # but do scale the ones that are used most often
1011 self.scale()
1012 X1, Y1, Z1 = self.__coords
1013 other.scale()
1014 X2, Y2, Z2 = other.__coords
1016 _double = self._double
1017 _add = self._add
1019 # with NAF we have 3 options: no add, subtract, add
1020 # so with 2 points, we have 9 combinations:
1021 # 0, -A, +A, -B, -A-B, +A-B, +B, -A+B, +A+B
1022 # so we need 4 combined points:
1023 mAmB_X, mAmB_Y, mAmB_Z = _add(X1, -Y1, Z1, X2, -Y2, Z2, p)
1024 pAmB_X, pAmB_Y, pAmB_Z = _add(X1, Y1, Z1, X2, -Y2, Z2, p)
1025 mApB_X, mApB_Y, mApB_Z = pAmB_X, -pAmB_Y, pAmB_Z
1026 pApB_X, pApB_Y, pApB_Z = mAmB_X, -mAmB_Y, mAmB_Z
1027 # when the self and other sum to infinity, we need to add them
1028 # one by one to get correct result but as that's very unlikely to
1029 # happen in regular operation, we don't need to optimise this case
1030 if not pApB_Z:
1031 return self * self_mul + other * other_mul
1033 # gmp object creation has cumulatively higher overhead than the
1034 # speedup we get from calculating the NAF using gmp so ensure use
1035 # of int()
1036 self_naf = list(reversed(self._naf(int(self_mul))))
1037 other_naf = list(reversed(self._naf(int(other_mul))))
1038 # ensure that the lists are the same length (zip() will truncate
1039 # longer one otherwise)
1040 if len(self_naf) < len(other_naf):
1041 self_naf = [0] * (len(other_naf) - len(self_naf)) + self_naf
1042 elif len(self_naf) > len(other_naf):
1043 other_naf = [0] * (len(self_naf) - len(other_naf)) + other_naf
1045 for A, B in zip(self_naf, other_naf):
1046 X3, Y3, Z3 = _double(X3, Y3, Z3, p, a)
1048 # conditions ordered from most to least likely
1049 if A == 0:
1050 if B == 0:
1051 pass
1052 elif B < 0:
1053 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, Z2, p)
1054 else:
1055 assert B > 0
1056 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, Z2, p)
1057 elif A < 0:
1058 if B == 0:
1059 X3, Y3, Z3 = _add(X3, Y3, Z3, X1, -Y1, Z1, p)
1060 elif B < 0:
1061 X3, Y3, Z3 = _add(X3, Y3, Z3, mAmB_X, mAmB_Y, mAmB_Z, p)
1062 else:
1063 assert B > 0
1064 X3, Y3, Z3 = _add(X3, Y3, Z3, mApB_X, mApB_Y, mApB_Z, p)
1065 else:
1066 assert A > 0
1067 if B == 0:
1068 X3, Y3, Z3 = _add(X3, Y3, Z3, X1, Y1, Z1, p)
1069 elif B < 0:
1070 X3, Y3, Z3 = _add(X3, Y3, Z3, pAmB_X, pAmB_Y, pAmB_Z, p)
1071 else:
1072 assert B > 0
1073 X3, Y3, Z3 = _add(X3, Y3, Z3, pApB_X, pApB_Y, pApB_Z, p)
1075 if not Z3:
1076 return INFINITY
1078 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
1080 def __neg__(self):
1081 """Return negated point."""
1082 x, y, z = self.__coords
1083 return PointJacobi(self.__curve, x, -y, z, self.__order)
1086class Point(AbstractPoint):
1087 """A point on a short Weierstrass elliptic curve. Altering x and y is
1088 forbidden, but they can be read by the x() and y() methods."""
1090 def __init__(self, curve, x, y, order=None):
1091 """curve, x, y, order; order (optional) is the order of this point."""
1092 super(Point, self).__init__()
1093 self.__curve = curve
1094 if GMPY:
1095 self.__x = x and mpz(x)
1096 self.__y = y and mpz(y)
1097 self.__order = order and mpz(order)
1098 else:
1099 self.__x = x
1100 self.__y = y
1101 self.__order = order
1102 # self.curve is allowed to be None only for INFINITY:
1103 if self.__curve:
1104 assert self.__curve.contains_point(x, y)
1105 # for curves with cofactor 1, all points that are on the curve are
1106 # scalar multiples of the base point, so performing multiplication is
1107 # not necessary to verify that. See Section 3.2.2.1 of SEC 1 v2
1108 if curve and curve.cofactor() != 1 and order:
1109 assert self * order == INFINITY
1111 @classmethod
1112 def from_bytes(
1113 cls,
1114 curve,
1115 data,
1116 validate_encoding=True,
1117 valid_encodings=None,
1118 order=None,
1119 ):
1120 """
1121 Initialise the object from byte encoding of a point.
1123 The method does accept and automatically detect the type of point
1124 encoding used. It supports the :term:`raw encoding`,
1125 :term:`uncompressed`, :term:`compressed`, and :term:`hybrid` encodings.
1127 :param data: single point encoding of the public key
1128 :type data: :term:`bytes-like object`
1129 :param curve: the curve on which the public key is expected to lay
1130 :type curve: ~ecdsa.ellipticcurve.CurveFp
1131 :param validate_encoding: whether to verify that the encoding of the
1132 point is self-consistent, defaults to True, has effect only
1133 on ``hybrid`` encoding
1134 :type validate_encoding: bool
1135 :param valid_encodings: list of acceptable point encoding formats,
1136 supported ones are: :term:`uncompressed`, :term:`compressed`,
1137 :term:`hybrid`, and :term:`raw encoding` (specified with ``raw``
1138 name). All formats by default (specified with ``None``).
1139 :type valid_encodings: :term:`set-like object`
1140 :param int order: the point order, must be non zero when using
1141 generator=True
1143 :raises `~ecdsa.errors.MalformedPointError`: if the public point does
1144 not lay on the curve or the encoding is invalid
1146 :return: Point on curve
1147 :rtype: Point
1148 """
1149 coord_x, coord_y = super(Point, cls).from_bytes(
1150 curve, data, validate_encoding, valid_encodings
1151 )
1152 return Point(curve, coord_x, coord_y, order)
1154 def __eq__(self, other):
1155 """Return True if the points are identical, False otherwise.
1157 Note: only points that lay on the same curve can be equal.
1158 """
1159 if other is INFINITY:
1160 return self.__x is None or self.__y is None
1161 if isinstance(other, Point):
1162 return (
1163 self.__curve == other.__curve
1164 and self.__x == other.__x
1165 and self.__y == other.__y
1166 )
1167 return NotImplemented
1169 def __ne__(self, other):
1170 """Returns False if points are identical, True otherwise."""
1171 return not self == other
1173 def __neg__(self):
1174 return Point(self.__curve, self.__x, self.__curve.p() - self.__y)
1176 def __add__(self, other):
1177 """Add one point to another point."""
1179 # X9.62 B.3:
1181 if not isinstance(other, Point):
1182 return NotImplemented
1183 if other == INFINITY:
1184 return self
1185 if self == INFINITY:
1186 return other
1187 assert self.__curve == other.__curve
1188 if self.__x == other.__x:
1189 if (self.__y + other.__y) % self.__curve.p() == 0:
1190 return INFINITY
1191 else:
1192 return self.double()
1194 p = self.__curve.p()
1196 l = (
1197 (other.__y - self.__y)
1198 * numbertheory.inverse_mod(other.__x - self.__x, p)
1199 ) % p
1201 x3 = (l * l - self.__x - other.__x) % p
1202 y3 = (l * (self.__x - x3) - self.__y) % p
1204 return Point(self.__curve, x3, y3)
1206 def __mul__(self, other):
1207 """Multiply a point by an integer."""
1209 def leftmost_bit(x):
1210 assert x > 0
1211 result = 1
1212 while result <= x:
1213 result = 2 * result
1214 return result // 2
1216 e = other
1217 if e == 0 or (self.__order and e % self.__order == 0):
1218 return INFINITY
1219 if self == INFINITY:
1220 return INFINITY
1221 if e < 0:
1222 return (-self) * (-e)
1224 # From X9.62 D.3.2:
1226 e3 = 3 * e
1227 negative_self = Point(
1228 self.__curve,
1229 self.__x,
1230 (-self.__y) % self.__curve.p(),
1231 self.__order,
1232 )
1233 i = leftmost_bit(e3) // 2
1234 result = self
1235 # print("Multiplying %s by %d (e3 = %d):" % (self, other, e3))
1236 while i > 1:
1237 result = result.double()
1238 if (e3 & i) != 0 and (e & i) == 0:
1239 result = result + self
1240 if (e3 & i) == 0 and (e & i) != 0:
1241 result = result + negative_self
1242 # print(". . . i = %d, result = %s" % ( i, result ))
1243 i = i // 2
1245 return result
1247 def __rmul__(self, other):
1248 """Multiply a point by an integer."""
1250 return self * other
1252 def __str__(self):
1253 if self == INFINITY:
1254 return "infinity"
1255 return "(%d,%d)" % (self.__x, self.__y)
1257 def double(self):
1258 """Return a new point that is twice the old."""
1259 if self == INFINITY:
1260 return INFINITY
1262 # X9.62 B.3:
1264 p = self.__curve.p()
1265 a = self.__curve.a()
1267 l = (
1268 (3 * self.__x * self.__x + a)
1269 * numbertheory.inverse_mod(2 * self.__y, p)
1270 ) % p
1272 if not l:
1273 return INFINITY
1275 x3 = (l * l - 2 * self.__x) % p
1276 y3 = (l * (self.__x - x3) - self.__y) % p
1278 return Point(self.__curve, x3, y3)
1280 def x(self):
1281 return self.__x
1283 def y(self):
1284 return self.__y
1286 def curve(self):
1287 return self.__curve
1289 def order(self):
1290 return self.__order
1293class PointEdwards(AbstractPoint):
1294 """Point on Twisted Edwards curve.
1296 Internally represents the coordinates on the curve using four parameters,
1297 X, Y, Z, T. They correspond to affine parameters 'x' and 'y' like so:
1299 x = X / Z
1300 y = Y / Z
1301 x*y = T / Z
1302 """
1304 def __init__(self, curve, x, y, z, t, order=None, generator=False):
1305 """
1306 Initialise a point that uses the extended coordinates internally.
1307 """
1308 super(PointEdwards, self).__init__()
1309 self.__curve = curve
1310 if GMPY: # pragma: no branch
1311 self.__coords = (mpz(x), mpz(y), mpz(z), mpz(t))
1312 self.__order = order and mpz(order)
1313 else: # pragma: no branch
1314 self.__coords = (x, y, z, t)
1315 self.__order = order
1316 self.__generator = generator
1317 self.__precompute = []
1319 @classmethod
1320 def from_bytes(
1321 cls,
1322 curve,
1323 data,
1324 validate_encoding=None,
1325 valid_encodings=None,
1326 order=None,
1327 generator=False,
1328 ):
1329 """
1330 Initialise the object from byte encoding of a point.
1332 `validate_encoding` and `valid_encodings` are provided for
1333 compatibility with Weierstrass curves, they are ignored for Edwards
1334 points.
1336 :param data: single point encoding of the public key
1337 :type data: :term:`bytes-like object`
1338 :param curve: the curve on which the public key is expected to lay
1339 :type curve: ecdsa.ellipticcurve.CurveEdTw
1340 :param None validate_encoding: Ignored, encoding is always validated
1341 :param None valid_encodings: Ignored, there is just one encoding
1342 supported
1343 :param int order: the point order, must be non zero when using
1344 generator=True
1345 :param bool generator: Flag to mark the point as a curve generator,
1346 this will cause the library to pre-compute some values to
1347 make repeated usages of the point much faster
1349 :raises `~ecdsa.errors.MalformedPointError`: if the public point does
1350 not lay on the curve or the encoding is invalid
1352 :return: Initialised point on an Edwards curve
1353 :rtype: PointEdwards
1354 """
1355 coord_x, coord_y = super(PointEdwards, cls).from_bytes(
1356 curve, data, validate_encoding, valid_encodings
1357 )
1358 return PointEdwards(
1359 curve, coord_x, coord_y, 1, coord_x * coord_y, order, generator
1360 )
1362 def _maybe_precompute(self):
1363 if not self.__generator or self.__precompute:
1364 return self.__precompute
1366 # since this code will execute just once, and it's fully deterministic,
1367 # depend on atomicity of the last assignment to switch from empty
1368 # self.__precompute to filled one and just ignore the unlikely
1369 # situation when two threads execute it at the same time (as it won't
1370 # lead to inconsistent __precompute)
1371 order = self.__order
1372 assert order
1373 precompute = []
1374 i = 1
1375 order *= 2
1376 coord_x, coord_y, coord_z, coord_t = self.__coords
1377 prime = self.__curve.p()
1379 doubler = PointEdwards(
1380 self.__curve, coord_x, coord_y, coord_z, coord_t, order
1381 )
1382 # for "protection" against Minerva we need 1 or 2 more bits depending
1383 # on order bit size, but it's easier to just calculate one
1384 # point more always
1385 order *= 4
1387 while i < order:
1388 doubler = doubler.scale()
1389 coord_x, coord_y = doubler.x(), doubler.y()
1390 coord_t = coord_x * coord_y % prime
1391 precompute.append((coord_x, coord_y, coord_t))
1393 i *= 2
1394 doubler = doubler.double()
1396 self.__precompute = precompute
1397 return self.__precompute
1399 def x(self):
1400 """Return affine x coordinate."""
1401 X1, _, Z1, _ = self.__coords
1402 if Z1 == 1:
1403 return X1
1404 p = self.__curve.p()
1405 z_inv = numbertheory.inverse_mod(Z1, p)
1406 return X1 * z_inv % p
1408 def y(self):
1409 """Return affine y coordinate."""
1410 _, Y1, Z1, _ = self.__coords
1411 if Z1 == 1:
1412 return Y1
1413 p = self.__curve.p()
1414 z_inv = numbertheory.inverse_mod(Z1, p)
1415 return Y1 * z_inv % p
1417 def curve(self):
1418 """Return the curve of the point."""
1419 return self.__curve
1421 def order(self):
1422 return self.__order
1424 def scale(self):
1425 """
1426 Return point scaled so that z == 1.
1428 Modifies point in place, returns self.
1429 """
1430 X1, Y1, Z1, _ = self.__coords
1431 if Z1 == 1:
1432 return self
1434 p = self.__curve.p()
1435 z_inv = numbertheory.inverse_mod(Z1, p)
1436 x = X1 * z_inv % p
1437 y = Y1 * z_inv % p
1438 t = x * y % p
1439 self.__coords = (x, y, 1, t)
1440 return self
1442 def __eq__(self, other):
1443 """Compare for equality two points with each-other.
1445 Note: only points on the same curve can be equal.
1446 """
1447 x1, y1, z1, t1 = self.__coords
1448 if other is INFINITY:
1449 return not x1 or not t1
1450 if isinstance(other, PointEdwards):
1451 x2, y2, z2, t2 = other.__coords
1452 else:
1453 return NotImplemented
1454 if self.__curve != other.curve():
1455 return False
1456 p = self.__curve.p()
1458 # cross multiply to eliminate divisions
1459 xn1 = x1 * z2 % p
1460 xn2 = x2 * z1 % p
1461 yn1 = y1 * z2 % p
1462 yn2 = y2 * z1 % p
1463 return xn1 == xn2 and yn1 == yn2
1465 def __ne__(self, other):
1466 """Compare for inequality two points with each-other."""
1467 return not self == other
1469 def _add(self, X1, Y1, Z1, T1, X2, Y2, Z2, T2, p, a):
1470 """add two points, assume sane parameters."""
1471 # after add-2008-hwcd-2
1472 # from https://hyperelliptic.org/EFD/g1p/auto-twisted-extended.html
1473 # NOTE: there are more efficient formulas for Z1 or Z2 == 1
1474 A = X1 * X2 % p
1475 B = Y1 * Y2 % p
1476 C = Z1 * T2 % p
1477 D = T1 * Z2 % p
1478 E = D + C
1479 F = ((X1 - Y1) * (X2 + Y2) + B - A) % p
1480 G = B + a * A
1481 H = D - C
1482 if not H:
1483 return self._double(X1, Y1, Z1, T1, p, a)
1484 X3 = E * F % p
1485 Y3 = G * H % p
1486 T3 = E * H % p
1487 Z3 = F * G % p
1489 return X3, Y3, Z3, T3
1491 def __add__(self, other):
1492 """Add point to another."""
1493 if other == INFINITY:
1494 return self
1495 if (
1496 not isinstance(other, PointEdwards)
1497 or self.__curve != other.__curve
1498 ):
1499 raise ValueError("The other point is on a different curve.")
1501 p, a = self.__curve.p(), self.__curve.a()
1502 X1, Y1, Z1, T1 = self.__coords
1503 X2, Y2, Z2, T2 = other.__coords
1505 X3, Y3, Z3, T3 = self._add(X1, Y1, Z1, T1, X2, Y2, Z2, T2, p, a)
1507 if not X3 or not T3:
1508 return INFINITY
1509 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1511 def __radd__(self, other):
1512 """Add other to self."""
1513 return self + other
1515 def _double(self, X1, Y1, Z1, T1, p, a):
1516 """Double the point, assume sane parameters."""
1517 # after "dbl-2008-hwcd"
1518 # from https://hyperelliptic.org/EFD/g1p/auto-twisted-extended.html
1519 # NOTE: there are more efficient formulas for Z1 == 1
1520 A = X1 * X1 % p
1521 B = Y1 * Y1 % p
1522 C = 2 * Z1 * Z1 % p
1523 D = a * A % p
1524 E = ((X1 + Y1) * (X1 + Y1) - A - B) % p
1525 G = D + B
1526 F = G - C
1527 H = D - B
1528 X3 = E * F % p
1529 Y3 = G * H % p
1530 T3 = E * H % p
1531 Z3 = F * G % p
1533 return X3, Y3, Z3, T3
1535 def double(self):
1536 """Return point added to itself."""
1537 X1, Y1, Z1, T1 = self.__coords
1539 if not X1 or not T1:
1540 return INFINITY
1542 p, a = self.__curve.p(), self.__curve.a()
1544 X3, Y3, Z3, T3 = self._double(X1, Y1, Z1, T1, p, a)
1546 # both Ed25519 and Ed448 have prime order, so no point added to
1547 # itself will equal zero
1548 if not X3 or not T3: # pragma: no branch
1549 return INFINITY
1550 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1552 def __rmul__(self, other):
1553 """Multiply point by an integer."""
1554 return self * other
1556 def _mul_precompute(self, other):
1557 """Multiply point by integer with precomputation table."""
1558 X3, Y3, Z3, T3, p, a = 0, 1, 1, 0, self.__curve.p(), self.__curve.a()
1559 _add = self._add
1560 for X2, Y2, T2 in self.__precompute:
1561 rem = other % 4
1562 if rem == 0 or rem == 2:
1563 other //= 2
1564 elif rem == 3:
1565 other = (other + 1) // 2
1566 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, -X2, Y2, 1, -T2, p, a)
1567 else:
1568 assert rem == 1
1569 other = (other - 1) // 2
1570 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, X2, Y2, 1, T2, p, a)
1572 if not X3 or not T3:
1573 return INFINITY
1575 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1577 def __mul__(self, other):
1578 """Multiply point by an integer."""
1579 X2, Y2, Z2, T2 = self.__coords
1580 if not X2 or not T2 or not other:
1581 return INFINITY
1582 if other == 1:
1583 return self
1584 if self.__order:
1585 # order*2 as a "protection" for Minerva
1586 other = other % (self.__order * 2)
1587 if self._maybe_precompute():
1588 return self._mul_precompute(other)
1590 X3, Y3, Z3, T3 = 0, 1, 1, 0 # INFINITY in extended coordinates
1591 p, a = self.__curve.p(), self.__curve.a()
1592 _double = self._double
1593 _add = self._add
1595 for i in reversed(self._naf(other)):
1596 X3, Y3, Z3, T3 = _double(X3, Y3, Z3, T3, p, a)
1597 if i < 0:
1598 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, -X2, Y2, Z2, -T2, p, a)
1599 elif i > 0:
1600 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, X2, Y2, Z2, T2, p, a)
1602 if not X3 or not T3:
1603 return INFINITY
1605 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1608# This one point is the Point At Infinity for all purposes:
1609INFINITY = Point(None, None, None)