diff options
author | kallewoof <karljohan-alm@garage.co.jp> | 2023-02-03 12:59:37 +0900 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-02-03 12:59:37 +0900 |
commit | 1a632a38751b24bb18b5e20e65a4b07e4f46b4e0 (patch) | |
tree | 2929c0f89a66d5110ff541ffc73061da698f8437 /bip-0324.mediawiki | |
parent | f277d42e0de45c4966e72c0d00148c3c0178f096 (diff) | |
parent | cc177ab7bc5abcdcdf9c956ee88afd1052053328 (diff) | |
download | bips-1a632a38751b24bb18b5e20e65a4b07e4f46b4e0.tar.xz |
Merge pull request #1405 from sipa/202301_bip324_update
BIP324 reference code / test vector improvements
Diffstat (limited to 'bip-0324.mediawiki')
-rw-r--r-- | bip-0324.mediawiki | 16 |
1 files changed, 8 insertions, 8 deletions
diff --git a/bip-0324.mediawiki b/bip-0324.mediawiki index 8a8861a..47032dd 100644 --- a/bip-0324.mediawiki +++ b/bip-0324.mediawiki @@ -247,19 +247,19 @@ To find encodings of a given X coordinate ''x'', we first need the inverse of '' * ''XSwiftECInv(x, u, case)'': ** If ''case & 2 = 0'': *** If ''lift_x(-x - u)'' succeeds, return ''None''. -*** Let ''v = x'' if ''case & 1 = 0''; let ''v = -x - u (mod p)'' otherwise. +*** Let ''v = x''. *** Let ''s = -(u<sup>3</sup> + 7)/(u<sup>2</sup> + uv + v<sup>2</sup>) (mod p)''. ** If ''case & 2 = 2'': *** Let ''s = x - u (mod p)''. *** If ''s = 0'', return ''None''. *** Let ''r'' be the square root of ''-s(4(u<sup>3</sup> + 7) + 3u<sup>2</sup>s) (mod p).''<ref name="modsqrt">'''How to compute a square root mod ''p''?''' Due to the structure of ''p'', a candidate for the square root of ''a'' mod ''p'' can be computed as ''x = a<sup>(p+1)/4</sup> mod p''. If ''a'' is not a square mod ''p'', this formula returns the square root of ''-a mod p'' instead, so it is necessary to verify that ''x<sup>2</sup> mod p = a''. If that is the case ''-x mod p'' is a solution too, but we define "the" square root to be equal to that expression (the square root will therefore always be a square itself, as ''(p+1)/4'' is even). This algorithm is a specialization of the [https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm Tonelli-Shanks algorithm].</ref> Return ''None'' if it does not exist. -*** If ''case & 1 = 1'': -**** If ''r = 0'', return ''None''. -**** let ''r = -r (mod p)''. +** If ''case & 1 = 1'' and ''r = 0'', return ''None''. *** Let ''v = (-u + r/s)/2''. ** Let ''w'' be the square root of ''s (mod p)''. Return ''None'' if it does not exist. -** If ''case & 4 = 4'', let ''w = -w (mod p)''. -** Return ''w(u(c - 1)/2 - v)''. +** If ''case & 5 = 0'', return ''-w(u(1 - c)/2 + v)''. +** If ''case & 5 = 1'', return ''w(u(1 + c)/2 + v)''. +** If ''case & 5 = 4'', return ''w(u(1 - c)/2 + v)''. +** If ''case & 5 = 5'', return ''-w(u(1 + c)/2 + v)''. The overall ''XElligatorSwift'' algorithm, matching the name used in the paper, then uses this inverse to randomly''<ref name="ellswift_helps_parroting">'''Can the ElligatorSwift encoding be used to construct public key encodings that satisfy a certain structure (and not pseudorandom)?''' The algorithm chooses the first 32 bytes (i.e., the value ''u'') and then computes a corresponding ''t'' such that the mapping to the curve point holds. In general, picking ''u'' from a uniformly random distribution provides pseudorandomness. But we can also fix any of the 32 bytes in ''u'', and the algorithm will still find a corresponding ''t''. The fact that it is possible to fix the first 32 bytes, combined with the garbage bytes in the handshake, provides a limited but very simple method of parroting other protocols such as [https://tls13.xargs.org/ TLS 1.3], which can be deployed by one of the peers without explicit support from the other peer. More general methods of parroting, e.g., introduced by defining new protocol or a protocol upgrade, are not precluded.</ref> sample encodings of ''x'': @@ -586,8 +586,8 @@ Peers supporting the v2 transport protocol signal support by advertising the <co == Test Vectors == For development and testing purposes, we provide a collection of test vectors in CSV format, and a naive, highly inefficient, [[bip-0324/reference.py|reference implementation]] of the relevant algorithms. This code is for demonstration purposes only: -* [[bip-0324/xelligatorswift_test_vectors.csv|XElligatorSwift vectors]] give examples of ElligatorSwift-encoded public keys, and the X coordinate they map to. -* [[bip-0324/xswiftec_test_vectors.csv|XSwiftEC vectors]] give examples of ''(u, x)'' pairs, and the various ''t'' values that ''xswiftec_inv'' maps them to. +* [[bip-0324/ellswift_decode_test_vectors.csv|XElligatorSwift decoding vectors]] give examples of ElligatorSwift-encoded public keys, and the X coordinate they map to. +* [[bip-0324/xswiftec_inv_test_vectors.csv|XSwiftECInv vectors]] give examples of ''(u, x)'' pairs, and the various ''t'' values that ''xswiftec_inv'' maps them to. * [[bip-0324/packet_encoding_test_vectors.csv|Packet encoding vectors]] illustrate the lifecycle of the authenticated encryption scheme proposed in this document. == Rationale and References == |