Module sapio_secp256k1::ellswift

source ·
Expand description

This module provides an implementation of ElligatorSwift as well as a version of x-only ECDH using it (including compatibility with BIP324).

ElligatorSwift is described in https://eprint.iacr.org/2022/759 by Chavez-Saab, Rodriguez-Henriquez, and Tibouchi. It permits encoding uniformly chosen public keys as 64-byte arrays which are indistinguishable from uniformly random arrays.

Let f be the function from pairs of field elements to point X coordinates, defined as follows (all operations modulo p = 2^256 - 2^32 - 977) f(u,t):

  • Let C = 0xa2d2ba93507f1df233770c2a797962cc61f6d15da14ecd47d8d27ae1cd5f852, a square root of -3.
  • If u=0, set u=1 instead.
  • If t=0, set t=1 instead.
  • If u^3 + t^2 + 7 = 0, multiply t by 2.
  • Let X = (u^3 + 7 - t^2) / (2 * t)
  • Let Y = (X + t) / (C * u)
  • Return the first in [u + 4 * Y^2, (-X/Y - u) / 2, (X/Y - u) / 2] that is an X coordinate on the curve (at least one of them is, for any u and t).

Then an ElligatorSwift encoding of x consists of the 32-byte big-endian encodings of field elements u and t concatenated, where f(u,t) = x. The encoding algorithm is described in the paper, and effectively picks a uniformly random pair (u,t) among those which encode x.

If the Y coordinate is relevant, it is given the same parity as t.

Changes w.r.t. the paper:

  • The u=0, t=0, and u^3+t^2+7=0 conditions result in decoding to the point at infinity in the paper. Here they are remapped to finite points.
  • The paper uses an additional encoding bit for the parity of y. Here the parity of t is used (negating t does not affect the decoded x coordinate, so this is possible).

Structs

  • ElligatorSwift
    ElligatorSwift is an encoding of a uniformly chosen point on the curve as a 64-byte array that is indistinguishable from a uniformly random array. This object holds two field elements u and t, which are the inputs to the ElligatorSwift encoding function.
  • ElligatorSwiftSharedSecret
    The result of ElligatorSwift::shared_secret, which is a shared secret computed from the x-only ECDH using both parties’ public keys (ElligatorSwift encoded) and our own private key.

Enums

  • ElligatorSwiftParty
    Represents which party we are in the ECDH, A is the initiator, B is the responder. This is important because the hash of the shared secret is different depending on which party we are. In this context, “we” means the party that is using this library, and possesses the secret key passed to ElligatorSwift::shared_secret.