Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/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 y1 or 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 _, y, z = self.__coords
727 if not y or not z:
728 return INFINITY
729 self.scale()
730 x, y, z = self.__coords
731 return Point(self.__curve, x, y, self.__order)
733 @staticmethod
734 def from_affine(point, generator=False):
735 """Create from an affine point.
737 :param bool generator: set to True to make the point to precalculate
738 multiplication table - useful for public point when verifying many
739 signatures (around 100 or so) or for generator points of a curve.
740 """
741 return PointJacobi(
742 point.curve(), point.x(), point.y(), 1, point.order(), generator
743 )
745 # please note that all the methods that use the equations from
746 # hyperelliptic
747 # are formatted in a way to maximise performance.
748 # Things that make code faster: multiplying instead of taking to the power
749 # (`xx = x * x; xxxx = xx * xx % p` is faster than `xxxx = x**4 % p` and
750 # `pow(x, 4, p)`),
751 # multiple assignments at the same time (`x1, x2 = self.x1, self.x2` is
752 # faster than `x1 = self.x1; x2 = self.x2`),
753 # similarly, sometimes the `% p` is skipped if it makes the calculation
754 # faster and the result of calculation is later reduced modulo `p`
756 def _double_with_z_1(self, X1, Y1, p, a):
757 """Add a point to itself with z == 1."""
758 # after:
759 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-mdbl-2007-bl
760 XX, YY = X1 * X1 % p, Y1 * Y1 % p
761 if not YY:
762 return 0, 0, 1
763 YYYY = YY * YY % p
764 S = 2 * ((X1 + YY) ** 2 - XX - YYYY) % p
765 M = 3 * XX + a
766 T = (M * M - 2 * S) % p
767 # X3 = T
768 Y3 = (M * (S - T) - 8 * YYYY) % p
769 Z3 = 2 * Y1 % p
770 return T, Y3, Z3
772 def _double(self, X1, Y1, Z1, p, a):
773 """Add a point to itself, arbitrary z."""
774 if Z1 == 1:
775 return self._double_with_z_1(X1, Y1, p, a)
776 if not Y1 or not Z1:
777 return 0, 0, 1
778 # after:
779 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl
780 XX, YY = X1 * X1 % p, Y1 * Y1 % p
781 if not YY:
782 return 0, 0, 1
783 YYYY = YY * YY % p
784 ZZ = Z1 * Z1 % p
785 S = 2 * ((X1 + YY) ** 2 - XX - YYYY) % p
786 M = (3 * XX + a * ZZ * ZZ) % p
787 T = (M * M - 2 * S) % p
788 # X3 = T
789 Y3 = (M * (S - T) - 8 * YYYY) % p
790 Z3 = ((Y1 + Z1) ** 2 - YY - ZZ) % p
792 return T, Y3, Z3
794 def double(self):
795 """Add a point to itself."""
796 X1, Y1, Z1 = self.__coords
798 if not Y1:
799 return INFINITY
801 p, a = self.__curve.p(), self.__curve.a()
803 X3, Y3, Z3 = self._double(X1, Y1, Z1, p, a)
805 if not Y3 or not Z3:
806 return INFINITY
807 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
809 def _add_with_z_1(self, X1, Y1, X2, Y2, p):
810 """add points when both Z1 and Z2 equal 1"""
811 # after:
812 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-mmadd-2007-bl
813 H = X2 - X1
814 HH = H * H
815 I = 4 * HH % p
816 J = H * I
817 r = 2 * (Y2 - Y1)
818 if not H and not r:
819 return self._double_with_z_1(X1, Y1, p, self.__curve.a())
820 V = X1 * I
821 X3 = (r**2 - J - 2 * V) % p
822 Y3 = (r * (V - X3) - 2 * Y1 * J) % p
823 Z3 = 2 * H % p
824 return X3, Y3, Z3
826 def _add_with_z_eq(self, X1, Y1, Z1, X2, Y2, p):
827 """add points when Z1 == Z2"""
828 # after:
829 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-zadd-2007-m
830 A = (X2 - X1) ** 2 % p
831 B = X1 * A % p
832 C = X2 * A
833 D = (Y2 - Y1) ** 2 % p
834 if not A and not D:
835 return self._double(X1, Y1, Z1, p, self.__curve.a())
836 X3 = (D - B - C) % p
837 Y3 = ((Y2 - Y1) * (B - X3) - Y1 * (C - B)) % p
838 Z3 = Z1 * (X2 - X1) % p
839 return X3, Y3, Z3
841 def _add_with_z2_1(self, X1, Y1, Z1, X2, Y2, p):
842 """add points when Z2 == 1"""
843 # after:
844 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-madd-2007-bl
845 Z1Z1 = Z1 * Z1 % p
846 U2, S2 = X2 * Z1Z1 % p, Y2 * Z1 * Z1Z1 % p
847 H = (U2 - X1) % p
848 HH = H * H % p
849 I = 4 * HH % p
850 J = H * I
851 r = 2 * (S2 - Y1) % p
852 if not r and not H:
853 return self._double_with_z_1(X2, Y2, p, self.__curve.a())
854 V = X1 * I
855 X3 = (r * r - J - 2 * V) % p
856 Y3 = (r * (V - X3) - 2 * Y1 * J) % p
857 Z3 = ((Z1 + H) ** 2 - Z1Z1 - HH) % p
858 return X3, Y3, Z3
860 def _add_with_z_ne(self, X1, Y1, Z1, X2, Y2, Z2, p):
861 """add points with arbitrary z"""
862 # after:
863 # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl
864 Z1Z1 = Z1 * Z1 % p
865 Z2Z2 = Z2 * Z2 % p
866 U1 = X1 * Z2Z2 % p
867 U2 = X2 * Z1Z1 % p
868 S1 = Y1 * Z2 * Z2Z2 % p
869 S2 = Y2 * Z1 * Z1Z1 % p
870 H = U2 - U1
871 I = 4 * H * H % p
872 J = H * I % p
873 r = 2 * (S2 - S1) % p
874 if not H and not r:
875 return self._double(X1, Y1, Z1, p, self.__curve.a())
876 V = U1 * I
877 X3 = (r * r - J - 2 * V) % p
878 Y3 = (r * (V - X3) - 2 * S1 * J) % p
879 Z3 = ((Z1 + Z2) ** 2 - Z1Z1 - Z2Z2) * H % p
881 return X3, Y3, Z3
883 def __radd__(self, other):
884 """Add other to self."""
885 return self + other
887 def _add(self, X1, Y1, Z1, X2, Y2, Z2, p):
888 """add two points, select fastest method."""
889 if not Y1 or not Z1:
890 return X2, Y2, Z2
891 if not Y2 or not Z2:
892 return X1, Y1, Z1
893 if Z1 == Z2:
894 if Z1 == 1:
895 return self._add_with_z_1(X1, Y1, X2, Y2, p)
896 return self._add_with_z_eq(X1, Y1, Z1, X2, Y2, p)
897 if Z1 == 1:
898 return self._add_with_z2_1(X2, Y2, Z2, X1, Y1, p)
899 if Z2 == 1:
900 return self._add_with_z2_1(X1, Y1, Z1, X2, Y2, p)
901 return self._add_with_z_ne(X1, Y1, Z1, X2, Y2, Z2, p)
903 def __add__(self, other):
904 """Add two points on elliptic curve."""
905 if self == INFINITY:
906 return other
907 if other == INFINITY:
908 return self
909 if isinstance(other, Point):
910 other = PointJacobi.from_affine(other)
911 if self.__curve != other.__curve:
912 raise ValueError("The other point is on different curve")
914 p = self.__curve.p()
915 X1, Y1, Z1 = self.__coords
916 X2, Y2, Z2 = other.__coords
918 X3, Y3, Z3 = self._add(X1, Y1, Z1, X2, Y2, Z2, p)
920 if not Y3 or not Z3:
921 return INFINITY
922 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
924 def __rmul__(self, other):
925 """Multiply point by an integer."""
926 return self * other
928 def _mul_precompute(self, other):
929 """Multiply point by integer with precomputation table."""
930 X3, Y3, Z3, p = 0, 0, 1, self.__curve.p()
931 _add = self._add
932 for X2, Y2 in self.__precompute:
933 if other % 2:
934 if other % 4 >= 2:
935 other = (other + 1) // 2
936 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, 1, p)
937 else:
938 other = (other - 1) // 2
939 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, 1, p)
940 else:
941 other //= 2
943 if not Y3 or not Z3:
944 return INFINITY
945 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
947 def __mul__(self, other):
948 """Multiply point by an integer."""
949 if not self.__coords[1] or not other:
950 return INFINITY
951 if other == 1:
952 return self
953 if self.__order:
954 # order*2 as a protection for Minerva
955 other = other % (self.__order * 2)
956 self._maybe_precompute()
957 if self.__precompute:
958 return self._mul_precompute(other)
960 self = self.scale()
961 X2, Y2, _ = self.__coords
962 X3, Y3, Z3 = 0, 0, 1
963 p, a = self.__curve.p(), self.__curve.a()
964 _double = self._double
965 _add = self._add
966 # since adding points when at least one of them is scaled
967 # is quicker, reverse the NAF order
968 for i in reversed(self._naf(other)):
969 X3, Y3, Z3 = _double(X3, Y3, Z3, p, a)
970 if i < 0:
971 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, 1, p)
972 elif i > 0:
973 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, 1, p)
975 if not Y3 or not Z3:
976 return INFINITY
978 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
980 def mul_add(self, self_mul, other, other_mul):
981 """
982 Do two multiplications at the same time, add results.
984 calculates self*self_mul + other*other_mul
985 """
986 if other == INFINITY or other_mul == 0:
987 return self * self_mul
988 if self_mul == 0:
989 return other * other_mul
990 if not isinstance(other, PointJacobi):
991 other = PointJacobi.from_affine(other)
992 # when the points have precomputed answers, then multiplying them alone
993 # is faster (as it uses NAF and no point doublings)
994 self._maybe_precompute()
995 other._maybe_precompute()
996 if self.__precompute and other.__precompute:
997 return self * self_mul + other * other_mul
999 if self.__order:
1000 self_mul = self_mul % self.__order
1001 other_mul = other_mul % self.__order
1003 # (X3, Y3, Z3) is the accumulator
1004 X3, Y3, Z3 = 0, 0, 1
1005 p, a = self.__curve.p(), self.__curve.a()
1007 # as we have 6 unique points to work with, we can't scale all of them,
1008 # but do scale the ones that are used most often
1009 self.scale()
1010 X1, Y1, Z1 = self.__coords
1011 other.scale()
1012 X2, Y2, Z2 = other.__coords
1014 _double = self._double
1015 _add = self._add
1017 # with NAF we have 3 options: no add, subtract, add
1018 # so with 2 points, we have 9 combinations:
1019 # 0, -A, +A, -B, -A-B, +A-B, +B, -A+B, +A+B
1020 # so we need 4 combined points:
1021 mAmB_X, mAmB_Y, mAmB_Z = _add(X1, -Y1, Z1, X2, -Y2, Z2, p)
1022 pAmB_X, pAmB_Y, pAmB_Z = _add(X1, Y1, Z1, X2, -Y2, Z2, p)
1023 mApB_X, mApB_Y, mApB_Z = pAmB_X, -pAmB_Y, pAmB_Z
1024 pApB_X, pApB_Y, pApB_Z = mAmB_X, -mAmB_Y, mAmB_Z
1025 # when the self and other sum to infinity, we need to add them
1026 # one by one to get correct result but as that's very unlikely to
1027 # happen in regular operation, we don't need to optimise this case
1028 if not pApB_Y or not pApB_Z:
1029 return self * self_mul + other * other_mul
1031 # gmp object creation has cumulatively higher overhead than the
1032 # speedup we get from calculating the NAF using gmp so ensure use
1033 # of int()
1034 self_naf = list(reversed(self._naf(int(self_mul))))
1035 other_naf = list(reversed(self._naf(int(other_mul))))
1036 # ensure that the lists are the same length (zip() will truncate
1037 # longer one otherwise)
1038 if len(self_naf) < len(other_naf):
1039 self_naf = [0] * (len(other_naf) - len(self_naf)) + self_naf
1040 elif len(self_naf) > len(other_naf):
1041 other_naf = [0] * (len(self_naf) - len(other_naf)) + other_naf
1043 for A, B in zip(self_naf, other_naf):
1044 X3, Y3, Z3 = _double(X3, Y3, Z3, p, a)
1046 # conditions ordered from most to least likely
1047 if A == 0:
1048 if B == 0:
1049 pass
1050 elif B < 0:
1051 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, Z2, p)
1052 else:
1053 assert B > 0
1054 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, Z2, p)
1055 elif A < 0:
1056 if B == 0:
1057 X3, Y3, Z3 = _add(X3, Y3, Z3, X1, -Y1, Z1, p)
1058 elif B < 0:
1059 X3, Y3, Z3 = _add(X3, Y3, Z3, mAmB_X, mAmB_Y, mAmB_Z, p)
1060 else:
1061 assert B > 0
1062 X3, Y3, Z3 = _add(X3, Y3, Z3, mApB_X, mApB_Y, mApB_Z, p)
1063 else:
1064 assert A > 0
1065 if B == 0:
1066 X3, Y3, Z3 = _add(X3, Y3, Z3, X1, Y1, Z1, p)
1067 elif B < 0:
1068 X3, Y3, Z3 = _add(X3, Y3, Z3, pAmB_X, pAmB_Y, pAmB_Z, p)
1069 else:
1070 assert B > 0
1071 X3, Y3, Z3 = _add(X3, Y3, Z3, pApB_X, pApB_Y, pApB_Z, p)
1073 if not Y3 or not Z3:
1074 return INFINITY
1076 return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
1078 def __neg__(self):
1079 """Return negated point."""
1080 x, y, z = self.__coords
1081 return PointJacobi(self.__curve, x, -y, z, self.__order)
1084class Point(AbstractPoint):
1085 """A point on a short Weierstrass elliptic curve. Altering x and y is
1086 forbidden, but they can be read by the x() and y() methods."""
1088 def __init__(self, curve, x, y, order=None):
1089 """curve, x, y, order; order (optional) is the order of this point."""
1090 super(Point, self).__init__()
1091 self.__curve = curve
1092 if GMPY:
1093 self.__x = x and mpz(x)
1094 self.__y = y and mpz(y)
1095 self.__order = order and mpz(order)
1096 else:
1097 self.__x = x
1098 self.__y = y
1099 self.__order = order
1100 # self.curve is allowed to be None only for INFINITY:
1101 if self.__curve:
1102 assert self.__curve.contains_point(x, y)
1103 # for curves with cofactor 1, all points that are on the curve are
1104 # scalar multiples of the base point, so performing multiplication is
1105 # not necessary to verify that. See Section 3.2.2.1 of SEC 1 v2
1106 if curve and curve.cofactor() != 1 and order:
1107 assert self * order == INFINITY
1109 @classmethod
1110 def from_bytes(
1111 cls,
1112 curve,
1113 data,
1114 validate_encoding=True,
1115 valid_encodings=None,
1116 order=None,
1117 ):
1118 """
1119 Initialise the object from byte encoding of a point.
1121 The method does accept and automatically detect the type of point
1122 encoding used. It supports the :term:`raw encoding`,
1123 :term:`uncompressed`, :term:`compressed`, and :term:`hybrid` encodings.
1125 :param data: single point encoding of the public key
1126 :type data: :term:`bytes-like object`
1127 :param curve: the curve on which the public key is expected to lay
1128 :type curve: ~ecdsa.ellipticcurve.CurveFp
1129 :param validate_encoding: whether to verify that the encoding of the
1130 point is self-consistent, defaults to True, has effect only
1131 on ``hybrid`` encoding
1132 :type validate_encoding: bool
1133 :param valid_encodings: list of acceptable point encoding formats,
1134 supported ones are: :term:`uncompressed`, :term:`compressed`,
1135 :term:`hybrid`, and :term:`raw encoding` (specified with ``raw``
1136 name). All formats by default (specified with ``None``).
1137 :type valid_encodings: :term:`set-like object`
1138 :param int order: the point order, must be non zero when using
1139 generator=True
1141 :raises `~ecdsa.errors.MalformedPointError`: if the public point does
1142 not lay on the curve or the encoding is invalid
1144 :return: Point on curve
1145 :rtype: Point
1146 """
1147 coord_x, coord_y = super(Point, cls).from_bytes(
1148 curve, data, validate_encoding, valid_encodings
1149 )
1150 return Point(curve, coord_x, coord_y, order)
1152 def __eq__(self, other):
1153 """Return True if the points are identical, False otherwise.
1155 Note: only points that lay on the same curve can be equal.
1156 """
1157 if isinstance(other, Point):
1158 return (
1159 self.__curve == other.__curve
1160 and self.__x == other.__x
1161 and self.__y == other.__y
1162 )
1163 return NotImplemented
1165 def __ne__(self, other):
1166 """Returns False if points are identical, True otherwise."""
1167 return not self == other
1169 def __neg__(self):
1170 return Point(self.__curve, self.__x, self.__curve.p() - self.__y)
1172 def __add__(self, other):
1173 """Add one point to another point."""
1175 # X9.62 B.3:
1177 if not isinstance(other, Point):
1178 return NotImplemented
1179 if other == INFINITY:
1180 return self
1181 if self == INFINITY:
1182 return other
1183 assert self.__curve == other.__curve
1184 if self.__x == other.__x:
1185 if (self.__y + other.__y) % self.__curve.p() == 0:
1186 return INFINITY
1187 else:
1188 return self.double()
1190 p = self.__curve.p()
1192 l = (
1193 (other.__y - self.__y)
1194 * numbertheory.inverse_mod(other.__x - self.__x, p)
1195 ) % p
1197 x3 = (l * l - self.__x - other.__x) % p
1198 y3 = (l * (self.__x - x3) - self.__y) % p
1200 return Point(self.__curve, x3, y3)
1202 def __mul__(self, other):
1203 """Multiply a point by an integer."""
1205 def leftmost_bit(x):
1206 assert x > 0
1207 result = 1
1208 while result <= x:
1209 result = 2 * result
1210 return result // 2
1212 e = other
1213 if e == 0 or (self.__order and e % self.__order == 0):
1214 return INFINITY
1215 if self == INFINITY:
1216 return INFINITY
1217 if e < 0:
1218 return (-self) * (-e)
1220 # From X9.62 D.3.2:
1222 e3 = 3 * e
1223 negative_self = Point(self.__curve, self.__x, -self.__y, self.__order)
1224 i = leftmost_bit(e3) // 2
1225 result = self
1226 # print("Multiplying %s by %d (e3 = %d):" % (self, other, e3))
1227 while i > 1:
1228 result = result.double()
1229 if (e3 & i) != 0 and (e & i) == 0:
1230 result = result + self
1231 if (e3 & i) == 0 and (e & i) != 0:
1232 result = result + negative_self
1233 # print(". . . i = %d, result = %s" % ( i, result ))
1234 i = i // 2
1236 return result
1238 def __rmul__(self, other):
1239 """Multiply a point by an integer."""
1241 return self * other
1243 def __str__(self):
1244 if self == INFINITY:
1245 return "infinity"
1246 return "(%d,%d)" % (self.__x, self.__y)
1248 def double(self):
1249 """Return a new point that is twice the old."""
1251 if self == INFINITY:
1252 return INFINITY
1254 # X9.62 B.3:
1256 p = self.__curve.p()
1257 a = self.__curve.a()
1259 l = (
1260 (3 * self.__x * self.__x + a)
1261 * numbertheory.inverse_mod(2 * self.__y, p)
1262 ) % p
1264 x3 = (l * l - 2 * self.__x) % p
1265 y3 = (l * (self.__x - x3) - self.__y) % p
1267 return Point(self.__curve, x3, y3)
1269 def x(self):
1270 return self.__x
1272 def y(self):
1273 return self.__y
1275 def curve(self):
1276 return self.__curve
1278 def order(self):
1279 return self.__order
1282class PointEdwards(AbstractPoint):
1283 """Point on Twisted Edwards curve.
1285 Internally represents the coordinates on the curve using four parameters,
1286 X, Y, Z, T. They correspond to affine parameters 'x' and 'y' like so:
1288 x = X / Z
1289 y = Y / Z
1290 x*y = T / Z
1291 """
1293 def __init__(self, curve, x, y, z, t, order=None, generator=False):
1294 """
1295 Initialise a point that uses the extended coordinates internally.
1296 """
1297 super(PointEdwards, self).__init__()
1298 self.__curve = curve
1299 if GMPY: # pragma: no branch
1300 self.__coords = (mpz(x), mpz(y), mpz(z), mpz(t))
1301 self.__order = order and mpz(order)
1302 else: # pragma: no branch
1303 self.__coords = (x, y, z, t)
1304 self.__order = order
1305 self.__generator = generator
1306 self.__precompute = []
1308 @classmethod
1309 def from_bytes(
1310 cls,
1311 curve,
1312 data,
1313 validate_encoding=None,
1314 valid_encodings=None,
1315 order=None,
1316 generator=False,
1317 ):
1318 """
1319 Initialise the object from byte encoding of a point.
1321 `validate_encoding` and `valid_encodings` are provided for
1322 compatibility with Weierstrass curves, they are ignored for Edwards
1323 points.
1325 :param data: single point encoding of the public key
1326 :type data: :term:`bytes-like object`
1327 :param curve: the curve on which the public key is expected to lay
1328 :type curve: ecdsa.ellipticcurve.CurveEdTw
1329 :param None validate_encoding: Ignored, encoding is always validated
1330 :param None valid_encodings: Ignored, there is just one encoding
1331 supported
1332 :param int order: the point order, must be non zero when using
1333 generator=True
1334 :param bool generator: Flag to mark the point as a curve generator,
1335 this will cause the library to pre-compute some values to
1336 make repeated usages of the point much faster
1338 :raises `~ecdsa.errors.MalformedPointError`: if the public point does
1339 not lay on the curve or the encoding is invalid
1341 :return: Initialised point on an Edwards curve
1342 :rtype: PointEdwards
1343 """
1344 coord_x, coord_y = super(PointEdwards, cls).from_bytes(
1345 curve, data, validate_encoding, valid_encodings
1346 )
1347 return PointEdwards(
1348 curve, coord_x, coord_y, 1, coord_x * coord_y, order, generator
1349 )
1351 def _maybe_precompute(self):
1352 if not self.__generator or self.__precompute:
1353 return self.__precompute
1355 # since this code will execute just once, and it's fully deterministic,
1356 # depend on atomicity of the last assignment to switch from empty
1357 # self.__precompute to filled one and just ignore the unlikely
1358 # situation when two threads execute it at the same time (as it won't
1359 # lead to inconsistent __precompute)
1360 order = self.__order
1361 assert order
1362 precompute = []
1363 i = 1
1364 order *= 2
1365 coord_x, coord_y, coord_z, coord_t = self.__coords
1366 prime = self.__curve.p()
1368 doubler = PointEdwards(
1369 self.__curve, coord_x, coord_y, coord_z, coord_t, order
1370 )
1371 # for "protection" against Minerva we need 1 or 2 more bits depending
1372 # on order bit size, but it's easier to just calculate one
1373 # point more always
1374 order *= 4
1376 while i < order:
1377 doubler = doubler.scale()
1378 coord_x, coord_y = doubler.x(), doubler.y()
1379 coord_t = coord_x * coord_y % prime
1380 precompute.append((coord_x, coord_y, coord_t))
1382 i *= 2
1383 doubler = doubler.double()
1385 self.__precompute = precompute
1386 return self.__precompute
1388 def x(self):
1389 """Return affine x coordinate."""
1390 X1, _, Z1, _ = self.__coords
1391 if Z1 == 1:
1392 return X1
1393 p = self.__curve.p()
1394 z_inv = numbertheory.inverse_mod(Z1, p)
1395 return X1 * z_inv % p
1397 def y(self):
1398 """Return affine y coordinate."""
1399 _, Y1, Z1, _ = self.__coords
1400 if Z1 == 1:
1401 return Y1
1402 p = self.__curve.p()
1403 z_inv = numbertheory.inverse_mod(Z1, p)
1404 return Y1 * z_inv % p
1406 def curve(self):
1407 """Return the curve of the point."""
1408 return self.__curve
1410 def order(self):
1411 return self.__order
1413 def scale(self):
1414 """
1415 Return point scaled so that z == 1.
1417 Modifies point in place, returns self.
1418 """
1419 X1, Y1, Z1, _ = self.__coords
1420 if Z1 == 1:
1421 return self
1423 p = self.__curve.p()
1424 z_inv = numbertheory.inverse_mod(Z1, p)
1425 x = X1 * z_inv % p
1426 y = Y1 * z_inv % p
1427 t = x * y % p
1428 self.__coords = (x, y, 1, t)
1429 return self
1431 def __eq__(self, other):
1432 """Compare for equality two points with each-other.
1434 Note: only points on the same curve can be equal.
1435 """
1436 x1, y1, z1, t1 = self.__coords
1437 if other is INFINITY:
1438 return not x1 or not t1
1439 if isinstance(other, PointEdwards):
1440 x2, y2, z2, t2 = other.__coords
1441 else:
1442 return NotImplemented
1443 if self.__curve != other.curve():
1444 return False
1445 p = self.__curve.p()
1447 # cross multiply to eliminate divisions
1448 xn1 = x1 * z2 % p
1449 xn2 = x2 * z1 % p
1450 yn1 = y1 * z2 % p
1451 yn2 = y2 * z1 % p
1452 return xn1 == xn2 and yn1 == yn2
1454 def __ne__(self, other):
1455 """Compare for inequality two points with each-other."""
1456 return not self == other
1458 def _add(self, X1, Y1, Z1, T1, X2, Y2, Z2, T2, p, a):
1459 """add two points, assume sane parameters."""
1460 # after add-2008-hwcd-2
1461 # from https://hyperelliptic.org/EFD/g1p/auto-twisted-extended.html
1462 # NOTE: there are more efficient formulas for Z1 or Z2 == 1
1463 A = X1 * X2 % p
1464 B = Y1 * Y2 % p
1465 C = Z1 * T2 % p
1466 D = T1 * Z2 % p
1467 E = D + C
1468 F = ((X1 - Y1) * (X2 + Y2) + B - A) % p
1469 G = B + a * A
1470 H = D - C
1471 if not H:
1472 return self._double(X1, Y1, Z1, T1, p, a)
1473 X3 = E * F % p
1474 Y3 = G * H % p
1475 T3 = E * H % p
1476 Z3 = F * G % p
1478 return X3, Y3, Z3, T3
1480 def __add__(self, other):
1481 """Add point to another."""
1482 if other == INFINITY:
1483 return self
1484 if (
1485 not isinstance(other, PointEdwards)
1486 or self.__curve != other.__curve
1487 ):
1488 raise ValueError("The other point is on a different curve.")
1490 p, a = self.__curve.p(), self.__curve.a()
1491 X1, Y1, Z1, T1 = self.__coords
1492 X2, Y2, Z2, T2 = other.__coords
1494 X3, Y3, Z3, T3 = self._add(X1, Y1, Z1, T1, X2, Y2, Z2, T2, p, a)
1496 if not X3 or not T3:
1497 return INFINITY
1498 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1500 def __radd__(self, other):
1501 """Add other to self."""
1502 return self + other
1504 def _double(self, X1, Y1, Z1, T1, p, a):
1505 """Double the point, assume sane parameters."""
1506 # after "dbl-2008-hwcd"
1507 # from https://hyperelliptic.org/EFD/g1p/auto-twisted-extended.html
1508 # NOTE: there are more efficient formulas for Z1 == 1
1509 A = X1 * X1 % p
1510 B = Y1 * Y1 % p
1511 C = 2 * Z1 * Z1 % p
1512 D = a * A % p
1513 E = ((X1 + Y1) * (X1 + Y1) - A - B) % p
1514 G = D + B
1515 F = G - C
1516 H = D - B
1517 X3 = E * F % p
1518 Y3 = G * H % p
1519 T3 = E * H % p
1520 Z3 = F * G % p
1522 return X3, Y3, Z3, T3
1524 def double(self):
1525 """Return point added to itself."""
1526 X1, Y1, Z1, T1 = self.__coords
1528 if not X1 or not T1:
1529 return INFINITY
1531 p, a = self.__curve.p(), self.__curve.a()
1533 X3, Y3, Z3, T3 = self._double(X1, Y1, Z1, T1, p, a)
1535 # both Ed25519 and Ed448 have prime order, so no point added to
1536 # itself will equal zero
1537 if not X3 or not T3: # pragma: no branch
1538 return INFINITY
1539 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1541 def __rmul__(self, other):
1542 """Multiply point by an integer."""
1543 return self * other
1545 def _mul_precompute(self, other):
1546 """Multiply point by integer with precomputation table."""
1547 X3, Y3, Z3, T3, p, a = 0, 1, 1, 0, self.__curve.p(), self.__curve.a()
1548 _add = self._add
1549 for X2, Y2, T2 in self.__precompute:
1550 rem = other % 4
1551 if rem == 0 or rem == 2:
1552 other //= 2
1553 elif rem == 3:
1554 other = (other + 1) // 2
1555 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, -X2, Y2, 1, -T2, p, a)
1556 else:
1557 assert rem == 1
1558 other = (other - 1) // 2
1559 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, X2, Y2, 1, T2, p, a)
1561 if not X3 or not T3:
1562 return INFINITY
1564 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1566 def __mul__(self, other):
1567 """Multiply point by an integer."""
1568 X2, Y2, Z2, T2 = self.__coords
1569 if not X2 or not T2 or not other:
1570 return INFINITY
1571 if other == 1:
1572 return self
1573 if self.__order:
1574 # order*2 as a "protection" for Minerva
1575 other = other % (self.__order * 2)
1576 if self._maybe_precompute():
1577 return self._mul_precompute(other)
1579 X3, Y3, Z3, T3 = 0, 1, 1, 0 # INFINITY in extended coordinates
1580 p, a = self.__curve.p(), self.__curve.a()
1581 _double = self._double
1582 _add = self._add
1584 for i in reversed(self._naf(other)):
1585 X3, Y3, Z3, T3 = _double(X3, Y3, Z3, T3, p, a)
1586 if i < 0:
1587 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, -X2, Y2, Z2, -T2, p, a)
1588 elif i > 0:
1589 X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, X2, Y2, Z2, T2, p, a)
1591 if not X3 or not T3:
1592 return INFINITY
1594 return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
1597# This one point is the Point At Infinity for all purposes:
1598INFINITY = Point(None, None, None)