summaryrefslogtreecommitdiff
path: root/bip-schnorr.mediawiki
diff options
context:
space:
mode:
authorPieter Wuille <pieter.wuille@gmail.com>2019-08-21 16:24:39 -0700
committerGitHub <noreply@github.com>2019-08-21 16:24:39 -0700
commitabe79d81e3478f6a1fcde2479819be44ae08dfdd (patch)
tree9daeee7abe967aeaa0090d201ef7f24dddebf3f5 /bip-schnorr.mediawiki
parentde9bc9c72cdaf5ea4705a62c4624be11f28ee148 (diff)
parenta462876b9a3a2c76fd1008cb5302c3335dd4cc87 (diff)
Merge pull request #58 from sipa/201908_computec
Clarify pseudocode of lift_x
Diffstat (limited to 'bip-schnorr.mediawiki')
-rw-r--r--bip-schnorr.mediawiki3
1 files changed, 2 insertions, 1 deletions
diff --git a/bip-schnorr.mediawiki b/bip-schnorr.mediawiki
index 43ea9d7..561ff6f 100644
--- a/bip-schnorr.mediawiki
+++ b/bip-schnorr.mediawiki
@@ -104,9 +104,10 @@ The following convention is used, with constants as defined for secp256k1:
** 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 encoding is ''x''.
** The function ''lift_x(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x'' and ''y(P)'' is a quadratic residue modulo ''p'', or fails if no such point exists<ref>Given an 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''. Given a candidate ''x'', the valid Y coordinates are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = &plusmn;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''. Due to [https://en.wikipedia.org/wiki/Euler%27s_criterion Euler's criterion] it then holds that ''c<sup>(p-1)/2</sup> = 1 mod p''. The same criterion applied to ''y'' results in ''y<sup>(p-1)/2</sup> mod p = &plusmn;c<sup>((p+1)/4)((p-1)/2)</sup> mod p = &plusmn;1 mod p''. Therefore ''y = +c<sup>(p+1)/4</sup> mod p'' is a quadratic residue and ''-y mod p'' is not.</ref>. The function ''lift_x(x)'' is equivalent to the following pseudocode:
+*** Let ''c = x<sup>3</sup> + 7 mod p''.
*** Let ''y = c<sup>(p+1)/4</sup> mod p''.
*** Fail if ''c &ne; y<sup>2</sup> mod p''.
-*** Return ''(r, y)''.
+*** Return the unique point ''P'' such that ''x(P) = x'' and ''y(P) = y''.
** The function ''point(x)'', where ''x'' is a 32-byte array, returns the point ''P = lift_x(int(x))''.
** The function ''hash(x)'', where ''x'' is a byte array, returns the 32-byte SHA256 hash of ''x''.
** The function ''jacobi(x)'', where ''x'' is an integer, returns the [https://en.wikipedia.org/wiki/Jacobi_symbol Jacobi symbol] of ''x / p''. It is equal to ''x<sup>(p-1)/2</sup> mod p'' ([https://en.wikipedia.org/wiki/Euler%27s_criterion Euler's criterion])<ref>For points ''P'' on the secp256k1 curve it holds that ''jacobi(y(P)) &ne; 0''.</ref>.