From 3b1fb9600b938172dd98a63e4906a861af9c3ab0 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Wed, 2 Sep 2020 14:20:42 -0700 Subject: Clarify that R=infinity is invalid in BIP340 Also rename is_infinity to is_infinite is reference implementation, to match the wording in BIP340. --- bip-0340.mediawiki | 6 ++++-- bip-0340/reference.py | 5 ++++- bip-0340/test-vectors.py | 2 +- 3 files changed, 9 insertions(+), 4 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 9502a69..f22194f 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -110,7 +110,7 @@ The following conventions are used, with constants as defined for [https://www.s ** The function ''bytes(x)'', where ''x'' is an integer, returns the 32-byte encoding of ''x'', most significant byte first. ** The function ''bytes(P)'', where ''P'' is a point, returns ''bytes(x(P))''. ** The function ''int(x)'', where ''x'' is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is ''x''. -** The function ''has_even_y(P)'', where ''P'' is a point, returns ''y(P) mod 2 = 0''. +** The function ''has_even_y(P)'', where ''P'' is a point for which ''not is_infinite(P)'', returns ''y(P) mod 2 = 0''. ** The function ''lift_x(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x'' Given a candidate X coordinate ''x'' in the range ''0..p-1'', there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then ''x'' is not a valid X coordinate either, i.e., no point ''P'' exists for which ''x(P) = x''. The valid Y coordinates for a given candidate ''x'' are the square roots of ''c = x3 + 7 mod p'' and they can be computed as ''y = ±c(p+1)/4 mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''. and ''has_even_y(P)'', or fails if no such point exists. The function ''lift_x(x)'' is equivalent to the following pseudocode: *** Let ''c = x3 + 7 mod p''. @@ -184,7 +184,9 @@ The algorithm ''Verify(pk, m, sig)'' is defined as: * Let ''s = int(sig[32:64])''; fail if ''s ≥ n''. * Let ''e = int(hashBIP0340/challenge(bytes(r) || bytes(P) || m)) mod n''. * Let ''R = s⋅G - e⋅P''. -* Fail if ''not has_even_y(R)'' or ''x(R) ≠ r''. +* Fail if ''is_infinite(R)''. +* Fail if ''not has_even_y(R)''. +* Fail if ''x(R) ≠ r''. * Return success iff no failure occurred before reaching this point. For every valid secret key ''sk'' and message ''m'', ''Verify(PubKey(sk),m,Sign(sk,m))'' will succeed. diff --git a/bip-0340/reference.py b/bip-0340/reference.py index 5d17db5..5b38c0a 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -26,13 +26,15 @@ def tagged_hash(tag: str, msg: bytes) -> bytes: tag_hash = hashlib.sha256(tag.encode()).digest() return hashlib.sha256(tag_hash + tag_hash + msg).digest() -def is_infinity(P: Optional[Point]) -> bool: +def is_infinite(P: Optional[Point]) -> bool: return P is None def x(P: Point) -> int: + assert not is_infinite(P) return P[0] def y(P: Point) -> int: + assert not is_infinite(P) return P[1] def point_add(P1: Optional[Point], P2: Optional[Point]) -> Optional[Point]: @@ -83,6 +85,7 @@ def hash_sha256(b: bytes) -> bytes: return hashlib.sha256(b).digest() def has_even_y(P: Point) -> bool: + assert not is_infinite(P) return y(P) % 2 == 0 def pubkey_gen(seckey: bytes) -> bytes: diff --git a/bip-0340/test-vectors.py b/bip-0340/test-vectors.py index e5b8847..d1bf6b2 100644 --- a/bip-0340/test-vectors.py +++ b/bip-0340/test-vectors.py @@ -6,7 +6,7 @@ def is_square(x): def has_square_y(P): """Determine if P has a square Y coordinate. Used in an earlier draft of BIP340.""" - assert not is_infinity(P) + assert not is_infinite(P) return is_square(P[1]) def vector0(): -- cgit v1.2.3