diff options
author | Jonas Nick <jonasd.nick@gmail.com> | 2022-06-20 13:16:27 +0000 |
---|---|---|
committer | Jonas Nick <jonasd.nick@gmail.com> | 2022-06-20 13:43:56 +0000 |
commit | 0144413e91bf5d71b54126783acaf339422abe7e (patch) | |
tree | d7f6abf4221490157e25f21b270e2109d4147fdd | |
parent | df443f8db30862b4776b4c06c47b62ded0790dc5 (diff) | |
download | bips-0144413e91bf5d71b54126783acaf339422abe7e.tar.xz |
bip-0340: clarify that lift_x fails with out-of-range inputs
Without this commit, it's not defined what happens if x is not in range 0..p-1.
However, lift_x may easily be called with out of range values. The reference
implementation of lift_x correctly returns failure in such cases.
-rw-r--r-- | bip-0340.mediawiki | 5 |
1 files changed, 3 insertions, 2 deletions
diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 9573846..a67afe3 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -109,8 +109,9 @@ The following conventions are used, with constants as defined for [https://www.s ** 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 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''<ref> - 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 = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = ±c<sup>(p+1)/4</sup> 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''.</ref> and ''has_even_y(P)'', or fails if no such point exists. The function ''lift_x(x)'' is equivalent to the following pseudocode: +** The function ''lift_x(x)'', where ''x'' is a 256-bit unsigned integer, returns the point ''P'' for which ''x(P) = x''<ref> + 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 = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = ±c<sup>(p+1)/4</sup> 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''.</ref> and ''has_even_y(P)'', or fails if ''x'' is greater than ''p-1'' or no such point exists. The function ''lift_x(x)'' is equivalent to the following pseudocode: +*** Fail if ''x ≥ p''. *** Let ''c = x<sup>3</sup> + 7 mod p''. *** Let ''y = c<sup>(p+1)/4</sup> mod p''. *** Fail if ''c ≠ y<sup>2</sup> mod p''. |