btclib.ecc package

Submodules

btclib.ecc.bms module

Bitcoin message signing (BMS).

Bitcoin uses a P2PKH address-based scheme for message signature: such a signature does prove the control of the private key corresponding to the address and, consequently, of the associated bitcoins (if any). Message signature adopts a custom compact 65-bytes (fixed size) serialization format (i.e. not the ASN.1 DER format used for transactions, which would results in 71-bytes average signature).

One should never sign a vague statement that could be reused out of the context it was intended for. Always include at least:

  • name (nickname, customer id, e-mail, etc.)

  • date and time

  • who the message is intended for (name, business name, e-mail, etc.)

  • specific purpose of the message

To mitigate the risk of signing a possibly deceiving message, for any given message a magic “Bitcoin Signed Message:n” prefix is added, then the hash of the resulting message is signed.

This BMS scheme relies on ECDSA, i.e. it works with private/public key pairs, not addresses: the address is only used to identify a key pair. At signing time, a wallet infrastructure is required to access the private key corresponding to a given address; alternatively, the private key must be provided explicitly.

To verify the ECDSA signature the public key is not needed because (EC)DSA allows public key recovery: public keys that correctly verify the signature can be implied from the signature itself. In the case of the Bitcoin secp256k1 curve, two public keys are recovered (up to four with non-zero but negligible probability); at verification time the address must match that public key in the recovery set marked as the right one at signature time.

The (r, s) DSA signature is serialized as [1-byte recovery flag][32-bytes r][32-bytes s], in a compact 65-bytes (fixed-size) encoding.

The serialized signature is then base64-encoded to transport it across channels that are designed to deal with textual data. Base64-encoding uses 10 digits, 26 lowercase characters, 26 uppercase characters, ‘+’ (plus sign), and ‘/’ (forward slash). The equal sign ‘=’ is used as encoding end marker.

The recovery flag is used at verification time to discriminate among recovered public keys (and among address types in the case of scheme extension beyond P2PKH). Explicitly, the recovery flag value is:

key_id + (4 if compressed else 0) + 27

where:

  • key_id is the index in the [0, 3] range identifying which of the recovered public keys is the one associated to the address

  • compressed indicates if the address is the hash of the compressed public key representation

  • 27 identify a P2PKH address, which is the only kind of address supported by Bitcoin Core; when the recovery flag is in the [31, 34] range of compressed addresses, Electrum also check for P2WPKH-P2SH and P2WPKH (SegWit always uses compressed public keys); BIP137 (Trezor) uses, instead, 35 and 39 instead of 27 for P2WPKH-P2SH and P2WPKH (respectively)

rec flag

key id

address type

27

0

P2PKH uncompressed

28

1

P2PKH uncompressed

29

2

P2PKH uncompressed

30

3

P2PKH uncompressed

31

0

P2PKH compressed (also Electrum P2WPKH-P2SH/P2WPKH)

32

1

P2PKH compressed (also Electrum P2WPKH-P2SH/P2WPKH)

33

2

P2PKH compressed (also Electrum P2WPKH-P2SH/P2WPKH)

34

3

P2PKH compressed (also Electrum P2WPKH-P2SH/P2WPKH)

35

0

BIP137 (Trezor) P2WPKH-P2SH

36

1

BIP137 (Trezor) P2WPKH-P2SH

37

2

BIP137 (Trezor) P2WPKH-P2SH

38

3

BIP137 (Trezor) P2WPKH-P2SH

39

0

BIP137 (Trezor) P2WPKH

40

1

BIP137 (Trezor) P2WPKH

41

2

BIP137 (Trezor) P2WPKH

42

3

BIP137 (Trezor) P2WPKH

This implementation endorses the Electrum approach: a signature generated with a compressed WIF (i.e. without explicit address or with a compressed P2PKH address) is valid also for the P2WPKH-P2SH and P2WPKH addresses derived from the same WIF.

Nonetheless, it is possible to obtain the BIP137 behaviour if at signing time the compressed WIF is supplemented with a P2WPKH-P2SH or P2WPKH address: in this case the signature will be valid only for that same address.

https://github.com/bitcoin/bitcoin/pull/524

https://github.com/bitcoin/bips/blob/master/bip-0137.mediawiki

class btclib.ecc.bms.Sig(rf: int, dsa_sig: btclib.ecc.der.Sig, check_validity: dataclasses.InitVar = True)

Bases: object

assert_valid() None
classmethod b64decode(data: Union[bytes, str], check_validity: bool = True) Sig

Return the verified components of the provided BMS signature.

The address-based BMS signature can be represented as (rf, r, s) tuple or as base64-encoding of the compact format [1-byte rf][32-bytes r][32-bytes s].

b64encode(check_validity: bool = True) str

Return the BMS address-based signature as base64-encoding.

First off, the signature is serialized in the [1-byte rf][32-bytes r][32-bytes s] compact format, then it is base64-encoded.

check_validity: InitVar = True
dsa_sig: Sig
classmethod parse(data: Union[BytesIO, bytes, str], check_validity: bool = True) Sig
rf: int
serialize(check_validity: bool = True) bytes
btclib.ecc.bms.assert_as_valid(msg: Union[bytes, str], addr: Union[bytes, str], sig: Union[Sig, bytes, str], lower_s: bool = True) None
btclib.ecc.bms.gen_keys(prv_key: Optional[Union[int, bytes, str, BIP32KeyData]] = None, network: Optional[str] = None, compressed: Optional[bool] = None) Tuple[str, str]

Return a private/public key pair.

The private key is a WIF, the public key is a base58 P2PKH address.

btclib.ecc.bms.sign(msg: Union[bytes, str], prv_key: Union[int, bytes, str, BIP32KeyData], addr: Optional[Union[bytes, str]] = None) Sig

Generate address-based compact signature for the provided message.

btclib.ecc.bms.verify(msg: Union[bytes, str], addr: Union[bytes, str], sig: Union[Sig, bytes, str], lower_s: bool = True) bool

Verify address-based compact signature for the provided message.

btclib.ecc.borromean module

Borromean signature functions.

btclib.ecc.borromean.assert_as_valid(msg: Union[bytes, str], e0: bytes, s: Dict[int, List[int]], pubk_rings: Dict[int, List[Tuple[int, int]]]) bool
btclib.ecc.borromean.sign(msg: Union[bytes, str], ks: Sequence[int], sign_key_idx: Sequence[int], sign_keys: Sequence[int], pubk_rings: Dict[int, List[Tuple[int, int]]]) Tuple[bytes, Dict[int, List[int]]]

Borromean ring signature - signing algorithm

https://github.com/ElementsProject/borromean-signatures-writeup https://github.com/Blockstream/borromean_paper/blob/master/borromean_draft_0.01_9ade1e49.pdf

inputs: - msg: message to be signed (bytes) - sign_key_idx: list of indexes representing each signing key per ring - sign_keys: list containing the whole set of signing keys (one per ring) - pubk_rings: dictionary of sequences representing single rings of pub_keys

btclib.ecc.borromean.verify(msg: Union[bytes, str], e0: bytes, s: Dict[int, List[int]], pubk_rings: Dict[int, List[Tuple[int, int]]]) bool

Borromean ring signature - verification algorithm

inputs:

  • msg: message to be signed

  • e0: pinned e-value needed to start the verification algorithm

  • s: s-values, both real (one per ring) and forged

  • pubk_rings: dictionary of sequences representing single rings of pub_keys

btclib.ecc.curve module

Elliptic curve classes and functions.

class btclib.ecc.curve.Curve(p: Union[bytes, str, int], a: Union[bytes, str, int], b: Union[bytes, str, int], G: Tuple[int, int], n: Union[bytes, str, int], cofactor: int, weakness_check: bool = True, name: Optional[str] = None)

Bases: CurveSubGroup

Prime order subgroup of the points of an elliptic curve over Fp.

class btclib.ecc.curve.CurveSubGroup(p: Union[bytes, str, int], a: Union[bytes, str, int], b: Union[bytes, str, int], G: Tuple[int, int])

Bases: CurveGroup

Subgroup of the points of an elliptic curve over Fp generated by G.

btclib.ecc.curve.double_mult(u: Union[bytes, str, int], H: Tuple[int, int], v: Union[bytes, str, int], Q: Tuple[int, int], ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1)) Tuple[int, int]

Double scalar multiplication (u*H + v*Q).

btclib.ecc.curve.mult(m: Union[bytes, str, int], Q: Optional[Tuple[int, int]] = None, ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1)) Tuple[int, int]

Elliptic curve scalar multiplication.

btclib.ecc.curve.multi_mult(scalars: Sequence[Union[bytes, str, int]], points: Sequence[Tuple[int, int]], ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1)) Tuple[int, int]

Return the multi scalar multiplication u1*Q1 + … + un*Qn.

Use Bos-Coster’s algorithm for efficient computation.

btclib.ecc.curve_group module

Elliptic CurveGroup class and functions.

Note that CurveGroup does not have to be a cyclic subgroup. For the cyclic subgroup class CurveSubGroup and the cyclic subgroup class of prime order Curve, see the btclib.curve module.

class btclib.ecc.curve_group.CurveGroup(p: Union[bytes, str, int], a: Union[bytes, str, int], b: Union[bytes, str, int])

Bases: object

Finite group of the points of an elliptic curve over Fp.

The elliptic curve is the set of points (x, y) that are solutions to a Weierstrass equation y^2 = x^3 + a*x + b, with x, y, a, and b in Fp (p being a prime), together with a point at infinity INF. The constants a, b must satisfy the relationship 4 a^3 + 27 b^2 ≠ 0.

The group is defined by the point addition group law.

add(Q1: Tuple[int, int], Q2: Tuple[int, int]) Tuple[int, int]

Return the sum of two points.

The input points must be on the curve.

add_aff(Q: Tuple[int, int], R: Tuple[int, int]) Tuple[int, int]
add_jac(Q: Tuple[int, int, int], R: Tuple[int, int, int]) Tuple[int, int, int]
aff_from_jac(Q: Tuple[int, int, int]) Tuple[int, int]
double_aff(Q: Tuple[int, int]) Tuple[int, int]
double_jac(Q: Tuple[int, int, int]) Tuple[int, int, int]
is_on_curve(Q: Tuple[int, int]) bool

Return True if the point is on the curve.

jac_equality(QJ: Tuple[int, int, int], PJ: Tuple[int, int, int]) bool

Return True if Jacobian points are equal in affine coordinates.

The input points are assumed to be on curve.

negate(Q: Tuple[int, int]) Tuple[int, int]

Return the opposite point.

The input point is not checked to be on the curve.

negate_jac(Q: Tuple[int, int, int]) Tuple[int, int, int]

Return the opposite Jacobian point.

The input point is not checked to be on the curve.

require_on_curve(Q: Tuple[int, int]) None

Require the input curve Point to be on the curve.

An Error is raised if not.

x_aff_from_jac(Q: Tuple[int, int, int]) int
y(x: int) int

Return the y coordinate from x, as in (x, y).

y_aff_from_jac(Q: Tuple[int, int, int]) int
y_even(x: int) int

Return the odd/even affine y-coordinate associated to x.

y_low(x: int) int

Return the low/high affine y-coordinate associated to x.

y_quadratic_residue(x: int) int

Return the quadratic residue affine y-coordinate.

btclib.ecc.curve_group.cached_multiples(Q: Tuple[int, int, int], ec: CurveGroup) List[Tuple[int, int, int]]
btclib.ecc.curve_group.cached_multiples_fixwind(Q: Tuple[int, int, int], ec: CurveGroup, w: int = 4) List[List[Tuple[int, int, int]]]

Made to precompute values for mult_fixed_window_cached. Do not use it for other functions. Made to be used for w=4, do not use w.

btclib.ecc.curve_group.convert_number_to_base(i: int, base: int) List[int]

Return the digits of an integer in the requested base.

btclib.ecc.curve_group.jac_from_aff(Q: Tuple[int, int]) Tuple[int, int, int]

Return the Jacobian representation of the affine point.

The input point is assumed to be on curve.

btclib.ecc.curve_group.mult_aff(m: int, Q: Tuple[int, int], ec: CurveGroup) Tuple[int, int]

Scalar multiplication of a curve point in affine coordinates.

This implementation uses ‘double & add’ algorithm, ‘right-to-left’ binary decomposition of the m coefficient, affine coordinates.

The input point is assumed to be on curve and the m coefficient is assumed to have been reduced mod n if appropriate (e.g. cyclic groups of order n).

btclib.ecc.curve_group.mult_base_3(m: int, Q: Tuple[int, int, int], ec: CurveGroup) Tuple[int, int, int]

Scalar multiplication using ternary decomposition of the scalar.

This implementation uses ‘triple & add’ algorithm, ‘left-to-right’ ternary decomposition of the m coefficient, Jacobian coordinates.

The input point is assumed to be on curve and the m coefficient is assumed to have been reduced mod n if appropriate (e.g. cyclic groups of order n).

btclib.ecc.curve_group.mult_fixed_window(m: int, Q: Tuple[int, int, int], ec: CurveGroup, w: int = 4, cached: bool = False) Tuple[int, int, int]

Scalar multiplication using “fixed window”.

This implementation uses ‘multiple-double & add’ algorithm, ‘left-to-right’ window decomposition of the m coefficient, Jacobian coordinates.

For 256-bit scalars it is suggested to choose w=4 or w=5.

The input point is assumed to be on curve and the m coefficient is assumed to have been reduced mod n if appropriate (e.g. cyclic groups of order n).

btclib.ecc.curve_group.mult_fixed_window_cached(m: int, Q: Tuple[int, int, int], ec: CurveGroup, w: int = 4) Tuple[int, int, int]

Scalar multiplication using “fixed window” & cached values.

This implementation uses ‘multiple-double & add’ algorithm, ‘left-to-right’ window decomposition of the m coefficient, Jacobian coordinates.

For 256-bit scalars it is suggested to choose w=4. Thanks to the pre-computed values, it just needs addictions.

The input point is assumed to be on curve and the m coefficient is assumed to have been reduced mod n if appropriate (e.g. cyclic groups of order n).

btclib.ecc.curve_group.mult_jac(m: int, Q: Tuple[int, int, int], ec: CurveGroup) Tuple[int, int, int]

Scalar multiplication of a curve point in Jacobian coordinates.

This implementation uses ‘double & add’ algorithm, ‘right-to-left’ binary decomposition of the m coefficient, Jacobian coordinates.

The input point is assumed to be on curve and the m coefficient is assumed to have been reduced mod n if appropriate (e.g. cyclic groups of order n).

btclib.ecc.curve_group.mult_mont_ladder(m: int, Q: Tuple[int, int, int], ec: CurveGroup) Tuple[int, int, int]

Scalar multiplication using ‘Montgomery ladder’ algorithm.

This implementation uses ‘Montgomery ladder’ algorithm, ‘left-to-right’ binary decomposition of the m coefficient, Jacobian coordinates.

It is constant-time and resistant to the FLUSH+RELOAD attack, (see https://eprint.iacr.org/2014/140.pdf) as it prevents branch prediction avoiding any if.

The input point is assumed to be on curve and the m coefficient is assumed to have been reduced mod n if appropriate (e.g. cyclic groups of order n).

btclib.ecc.curve_group.mult_recursive_aff(m: int, Q: Tuple[int, int], ec: CurveGroup) Tuple[int, int]

Scalar multiplication of a curve point in affine coordinates.

This implementation uses a recursive version of ‘double & add’, affine coordinates.

The input point is assumed to be on curve and the m coefficient is assumed to have been reduced mod n if appropriate (e.g. cyclic groups of order n).

btclib.ecc.curve_group.mult_recursive_jac(m: int, Q: Tuple[int, int, int], ec: CurveGroup) Tuple[int, int, int]

Scalar multiplication of a curve point in affine coordinates.

This implementation uses a recursive version of ‘double & add’, jacobian coordinates.

The input point is assumed to be on curve and the m coefficient is assumed to have been reduced mod n if appropriate (e.g. cyclic groups of order n).

btclib.ecc.curve_group.multiples(Q: Tuple[int, int, int], size: int, ec: CurveGroup) List[Tuple[int, int, int]]

Return {k_i * Q} for k_i in {0, …, size-1)

btclib.ecc.curve_group_2 module

Elliptic curve point multiplication functions.

The implemented algorithms are:
  • Montgomery Ladder

  • Scalar multiplication on basis 3

  • Fixed window

  • Sliding window

  • w-ary non-adjacent form (wNAF)

References:
TODO:
btclib.ecc.curve_group_2.mods(m: int, w: int) int

Signed modulo function.

btclib.ecc.curve_group_2.mult_endomorphism_secp256k1(m: int, Q: Tuple[int, int, int], ec: CurveGroup) Tuple[int, int, int]

Scalar multiplication in Jacobian coordinates using efficient endomorphism.

btclib.ecc.curve_group_2.mult_sliding_window(m: int, Q: Tuple[int, int, int], ec: CurveGroup, w: int = 4) Tuple[int, int, int]

Scalar multiplication using “sliding window”.

It has the benefit that the pre-computation stage is roughly half as complex as the normal windowed method. It is not constant time. For 256-bit scalars choose w=4 or w=5.

The input point is assumed to be on curve and the m coefficient is assumed to have been reduced mod n if appropriate (e.g. cyclic groups of order n).

btclib.ecc.curve_group_2.mult_w_NAF(m: int, Q: Tuple[int, int, int], ec: CurveGroup, w: int = 4) Tuple[int, int, int]

Scalar multiplication in Jacobian coordinates using wNAF.

This implementation uses the same method called “w-ary non-adjacent form” (wNAF) we make use of the fact that point subtraction is as easy as point addition to perform fewer operations compared to sliding-window In fact, on Weierstrass curves, known P, -P can be computed on the fly.

The input point is assumed to be on curve and the m coefficient is assumed to have been reduced mod n if appropriate (e.g. cyclic groups of order n). ‘right-to-left’ method.

FIXME: - Make it constant time (if necessary) - Try to avoid exception in negation for w=1

btclib.ecc.curve_group_2.multiplier_decomposer(m: int, ec: CurveGroup) Tuple[int, int]

Decompose m in two integers m1 e m2 so that mP = m1*P + m2*lambda*P.

Used for point multiplication with efficiently computable endomorphisms.

Based on alghoritm 3.74 of D. Hankerson, ‘Guide to Elliptic Curve Cryptography’. Values computed for secp256k1.

btclib.ecc.curve_group_2.wNAF_of_m(m: int, w: int) List[int]

wNAF (width-w Non-adjacent form) of number m

Given an integer m, wNAF is a method of rapresentation with powers of 2, where the coefficients are odd or 0, and where at most one of any w consecutive digits is nonzero. It has the following propreties: - m has a unique width-w NAF. -The length of wNAF(m) is at most one more than the length of the binary representation of k. -The average density of nonzero digits is approximately 1/(w + 1).

For complete reference see: D. Hankerson, ‘Guide to Elliptic Curve Cryptography’ chapter 3

btclib.ecc.curve_group_f module

CurveGroup explorer functions.

These functions are meant to explore low-cardinality CurveGroup, for didactical (and fun) reason only.

btclib.ecc.curve_group_f.find_all_points(ec: CurveGroup) List[Tuple[int, int]]

Attemp to find all group points, if p is low.

Very unsofisticated walk-through approach, for didactical sake only.

btclib.ecc.curve_group_f.find_subgroup_points(ec: CurveGroup, G: Tuple[int, int]) List[Tuple[int, int]]

Attemp to count all G-generated subgroup points, if p is low.

Very unsofisticated walk-through approach, for didactical sake only.

btclib.ecc.der module

Strict ASN.1 DER format for ECDSA signature representation.

The original Bitcoin implementation used OpenSSL to verify ECDSA signatures in ASN.1 DER representation. However, OpenSSL does not do strict validation (e.g. extra padding is ignored) and this changes the transaction hash value, leading to transaction malleability. This was fixed by BIP66, activated on block 363,724.

source: https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki

BIP66 mandates a strict DER format:

Format: [0x30] [data-size][0x02][r-size][r][0x02][s-size][s]

  • 0x30: header byte to indicate compound structure

  • data-size: 1-byte size descriptor of the following data

  • 0x02: header byte indicating an integer

  • r-size: 1-byte size descriptor of the r value that follows

  • r: arbitrary-size big-endian r value.

    It must use the shortest possible encoding for a positive integers: no null bytes at the start, except a single one when the next byte has its highest bit set (to avoid being interpreted as a negative number)

  • 0x02: header byte indicating an integer

  • s-size: 1-byte size descriptor of the s value that follows

  • s: arbitrary-size big-endian s value. Same rules as for r apply

There are 7 bytes of meta-data:

  • compound header, compound size,

  • value header, r-value size,

  • value header, s-value size

The ECDSA signature (r, s) should be 64 bytes, r and s being 32 bytes integers each; however, integers in DER are signed, so if the value being encoded is greater than 2^128, a 33rd byte is added in front. Bitcoin has a “low s” rule for the s value to be below ec.n, but it is only a standardness rule miners are allowed to ignore. Moreover, no such rule exists for r.

class btclib.ecc.der.Sig(r: int, s: int, ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), check_validity: InitVar = True)

Bases: object

ECDSA signature with DER serialization.

  • r is a scalar, 0 < r < ec.n

  • s is a scalar, 0 < s < ec.n

(ec.n is the curve order)

assert_valid() None
check_validity: InitVar = True
ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1)
classmethod parse(data: Union[BytesIO, bytes, str], check_validity: bool = True) Sig

Return a Sig by parsing binary data.

Deserialize a strict ASN.1 DER representation of an ECDSA signature.

r: int
s: int
serialize(check_validity: bool = True) bytes

Serialize an ECDSA signature to strict ASN.1 DER representation

btclib.ecc.dh module

Diffie-Hellman elliptic curve key agreement scheme.

Implementation of the Diffie-Hellman key agreement scheme using elliptic curve cryptography. A key agreement scheme is used by two entities to establish shared keying data, which will be later utilized e.g. in symmetric cryptographic scheme.

The two entities must agree on the elliptic curve and key derivation function to use.

btclib.ecc.dh.ansi_x9_63_kdf(z: bytes, size: int, hf: Callable[[], Any], shared_info: Optional[bytes]) bytes

Return keying data according to ANSI-X9.63-KDF.

Return a keying data octet sequence of the requested size according to ANSI-X9.63-KDF specifications for the key derivation function.

http://www.secg.org/sec1-v2.pdf, section 3.6.1

btclib.ecc.dh.diffie_hellman(dU: int, QV: ~typing.Tuple[int, int], size: int, shared_info: ~typing.Optional[bytes] = None, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bytes

Diffie-Hellman elliptic curve key agreement scheme.

http://www.secg.org/sec1-v2.pdf, section 6.1

btclib.ecc.dsa module

Elliptic Curve Digital Signature Algorithm (ECDSA).

Implementation according to SEC 1 v.2:

http://www.secg.org/sec1-v2.pdf

specialized with bitcoin canonical ‘lower-s’ form to avoid accepting malleable signatures.

btclib.ecc.dsa.assert_as_valid(msg: ~typing.Union[bytes, str], key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], lower_s: bool = True, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) None
btclib.ecc.dsa.assert_as_valid_(msg_hash: ~typing.Union[bytes, str], key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], lower_s: bool = True, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) None
btclib.ecc.dsa.crack_prv_key(msg1: ~typing.Union[bytes, str], sig1: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], msg2: ~typing.Union[bytes, str], sig2: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[int, int]
btclib.ecc.dsa.crack_prv_key_(msg_hash1: ~typing.Union[bytes, str], sig1: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], msg_hash2: ~typing.Union[bytes, str], sig2: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[int, int]
btclib.ecc.dsa.gen_keys(prv_key: Optional[Union[int, bytes, str, BIP32KeyData]] = None, ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1)) Tuple[int, Tuple[int, int]]

Return a private/public (int, Point) key-pair.

btclib.ecc.dsa.recover_pub_key(key_id: int, msg: ~typing.Union[bytes, str], sig: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], lower_s: bool = True, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[int, int]

ECDSA public key recovery (SEC 1 v.2 section 4.1.6).

See also: https://crypto.stackexchange.com/questions/18105/how-does-recovering-the-public-key-from-an-ecdsa-signature-work/18106#18106

btclib.ecc.dsa.recover_pub_key_(key_id: int, msg_hash: ~typing.Union[bytes, str], sig: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], lower_s: bool = True, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[int, int]

ECDSA public key recovery (SEC 1 v.2 section 4.1.6).

See also: https://crypto.stackexchange.com/questions/18105/how-does-recovering-the-public-key-from-an-ecdsa-signature-work/18106#18106

btclib.ecc.dsa.recover_pub_keys(msg: ~typing.Union[bytes, str], sig: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], lower_s: bool = True, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) List[Tuple[int, int]]

ECDSA public key recovery (SEC 1 v.2 section 4.1.6).

See also: https://crypto.stackexchange.com/questions/18105/how-does-recovering-the-public-key-from-an-ecdsa-signature-work/18106#18106

btclib.ecc.dsa.recover_pub_keys_(msg_hash: ~typing.Union[bytes, str], sig: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], lower_s: bool = True, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) List[Tuple[int, int]]

ECDSA public key recovery (SEC 1 v.2 section 4.1.6).

See also: https://crypto.stackexchange.com/questions/18105/how-does-recovering-the-public-key-from-an-ecdsa-signature-work/18106#18106

btclib.ecc.dsa.sign(msg: ~typing.Union[bytes, str], prv_key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData], nonce: ~typing.Optional[~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData]] = None, lower_s: bool = True, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Sig

ECDSA signature with canonical low-s preference.

Implemented according to SEC 1 v.2 The message msg is first processed by hf, yielding the value

msg_hash = hf(msg),

a sequence of bits of length hf_len.

Normally, hf is chosen such that its output length hf_len is roughly equal to nlen, the bit-length of the group order n, since the overall security of the signature scheme will depend on the smallest of hf_len and nlen; however, the ECDSA standard supports all combinations of hf_len and nlen.

RFC6979 is used for deterministic nonce.

See https://tools.ietf.org/html/rfc6979#section-3.2

btclib.ecc.dsa.sign_(msg_hash: ~typing.Union[bytes, str], prv_key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData], nonce: ~typing.Optional[~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData]] = None, lower_s: bool = True, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Sig

Sign a hf_len bytes message according to ECDSA signature algorithm.

If the deterministic nonce is not provided, the RFC6979 specification is used.

btclib.ecc.dsa.verify(msg: ~typing.Union[bytes, str], key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], lower_s: bool = True, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool

ECDSA signature verification (SEC 1 v.2 section 4.1.4).

btclib.ecc.dsa.verify_(msg_hash: ~typing.Union[bytes, str], key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~typing.Union[~btclib.ecc.der.Sig, bytes, str], lower_s: bool = True, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool

ECDSA signature verification (SEC 1 v.2 section 4.1.4).

btclib.ecc.libsecp256k1 module

Helper functions to use the libsecp256k1 python bindings

btclib.ecc.libsecp256k1.disable()
btclib.ecc.libsecp256k1.enable()
btclib.ecc.libsecp256k1.is_enabled()

btclib.ecc.number_theory module

Number theory and modular arithmetic functions.

Implementations originally from https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm and https://codereview.stackexchange.com/questions/43210/tonelli-shanks-algorithm-implementation-of-prime-modular-square-root/43267 with the following modifications:

  • type annotated python3

  • minor improvements

  • added extensive unit test

btclib.ecc.number_theory.legendre_symbol(a: int, p: int) int

Compute the Legendre symbol a|p using Euler’s criterion.

p is a prime, a is relatively prime to p (if p divides a, then a|p = 0). It returns 1 if a has a square root modulo p, -1 otherwise.

https://codereview.stackexchange.com/questions/43210/tonelli-shanks-algorithm-implementation-of-prime-modular-square-root/43267

btclib.ecc.number_theory.mod_inv(a: int, m: int) int

Return the inverse of a (mod m). m does not have to be a prime.

Based on Extended Euclidean Algorithm, see: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

btclib.ecc.number_theory.mod_sqrt(a: int, p: int) int

Return a quadratic residue (mod p) of a; p must be a prime.

Solve the equation:

x^2 = a mod p

and return x. Note that p - x is also a root.

If a simple solution is not available for p, then the Tonelli-Shanks algorithm is used.

https://codereview.stackexchange.com/questions/43210/tonelli-shanks-algorithm-implementation-of-prime-modular-square-root/43267

btclib.ecc.number_theory.tonelli(a: int, p: int) int

Return a quadratic residue (mod p) of a; p must be a prime.

The Tonelli-Shanks algorithm is used.

https://codereview.stackexchange.com/questions/43210/tonelli-shanks-algorithm-implementation-of-prime-modular-square-root/43267

btclib.ecc.number_theory.xgcd(a: int, b: int) Tuple[int, int, int]

Return (g, x, y) such that a*x + b*y = g = gcd(x, y).

based on Extended Euclidean Algorithm, see https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

btclib.ecc.pedersen module

Pedersen commitment functions.

In a commitment scheme the committer:

  • decides (or is given) a secret message v

  • decides a random secret r

  • commits to v by applying the public commitment scheme algorithm and producing a commitment C=Commit(r,v)

  • makes C public

Later, when he reveals r and v, the verifier opens the commitment checking if indeed C=Commit(r,v).

Pedersen commitment uses a public group of large order n in which the discrete logarithm is hard. In the case of an elliptic curve group, the generator G is supplemented with a second random generator H and the commitment algorithm is Commit(r,v)=rG+vH. It is crucial for H to be Nothing-Up-My-Sleeve (NUMS), i.e. the discrete logarithm of H with respect to G must be unknown.

btclib.ecc.pedersen.commit(r: int, v: int, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[int, int]

Commit to r, returning rG+vH.

Commit to r, returning rG+vH. H is the second Nothing-Up-My-Sleeve (NUMS) generator of the curve.

btclib.ecc.pedersen.second_generator(ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[int, int]

Second (with respect to G) elliptic curve generator.

Second (with respect to G) Nothing-Up-My-Sleeve (NUMS) elliptic curve generator.

The hash of G is coerced it to a point (x_H, y_H). If the resulting point is not on the curve, keep on incrementing x_H until a valid curve point (x_H, y_H) is obtained.

idea: https://crypto.stackexchange.com/questions/25581/second-generator-for-secp256k1-curve

source: https://github.com/ElementsProject/secp256k1-zkp/blob/secp256k1-zkp/src/modules/rangeproof/main_impl.h

btclib.ecc.pedersen.verify(r: int, v: int, commitment: ~typing.Tuple[int, int], ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool

Open the commitment and return True if valid.

btclib.ecc.rfc6979 module

Deterministic generation of the ephemeral key following RFC6979.

https://tools.ietf.org/html/rfc6979:

ECDSA and ECSSA need to produce, for each signature generation, a fresh random value (ephemeral key, hereafter designated as nonce). For effective security, nonce must be chosen randomly and uniformly from a set of modular integers, using a cryptographically secure process. Even slight biases in that process may be turned into attacks on the signature schemes.

The need for a cryptographically secure source of randomness proves to be a hindranceand and makes implementations harder to test. Moreover, reusing the same ephemeral key for a different message signed with the same private key reveal the private key!

RFC6979 turns ECDSA into deterministic schemes by using a deterministic process for generating the nonce. The process fulfills the cryptographic characteristics in order to maintain the properties of verifiability and unforgeability expected from signature schemes; namely, for whoever does not know the signature private key, the mapping from input messages to the corresponding nonce values is computationally indistinguishable from what a randomly and uniformly chosen function (from the set of messages to the set of possible nonce values) would return.

btclib.ecc.rfc6979.rfc6979_(msg_hash: ~typing.Union[bytes, str], prv_key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData], ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) int

Return a deterministic ephemeral key following RFC 6979.

see https://tools.ietf.org/html/rfc6979 section 3.2

btclib.ecc.sec_point module

SEC compressed/uncompressed point representation.

btclib.ecc.sec_point.bytes_from_point(Q: Tuple[int, int], ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), compressed: bool = True) bytes

Return a point as compressed/uncompressed octet sequence.

Return a point as compressed (0x02, 0x03) or uncompressed (0x04) octet sequence, according to SEC 1 v.2, section 2.3.3.

btclib.ecc.sec_point.point_from_octets(pub_key: Union[bytes, str], ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1)) Tuple[int, int]

Return a tuple (x_Q, y_Q) that belongs to the curve.

Return a tuple (x_Q, y_Q) that belongs to the curve according to SEC 1 v.2, section 2.3.4.

btclib.ecc.sign_to_contract module

Include a commitment inside an elliptic curve DSA/SSA signature.

Let commit_hash be the commitment value and R a curve point, then

e = hash(R||commit_hash)

is a commitment operation.

When signing, an ephemeral secret key k is generated and its corresponding curve point R = kG is used. Here, instead of using (k, R), compute the commitment to commit_hash

e = hash(R||commit_hash),

tweak k with e and consequently substitute R with W = (k+e)G = R+eG, the proceed signing in the standard way, using (k+e, W).

When the committer/signer will reveal R and commit_hash, the verifier will check that

W.x = (R+eG).x

with e = hash(R||commit_hash)) and W.x being known from the signature.

btclib.ecc.sign_to_contract.dsa_commit_sign(commit: ~typing.Union[bytes, str], msg: ~typing.Union[bytes, str], prv_key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData], nonce: ~typing.Optional[~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData]] = None, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[Sig, Tuple[int, int]]

Include a commitment inside an EC DSA signature.

btclib.ecc.sign_to_contract.dsa_commit_sign_(commit_hash: ~typing.Union[bytes, str], msg_hash: ~typing.Union[bytes, str], prv_key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData], nonce: ~typing.Optional[~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData]] = None, lower_s: bool = True, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[Sig, Tuple[int, int]]

Include a commitment inside an EC DSA signature.

btclib.ecc.sign_to_contract.dsa_verify_commit(commit: ~typing.Union[bytes, str], receipt: ~typing.Tuple[int, int], msg: ~typing.Union[bytes, str], key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~btclib.ecc.der.Sig, lower_s: bool = True, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool

Open the commitment associated to an EC DSA signature.

btclib.ecc.sign_to_contract.dsa_verify_commit_(commit_hash: ~typing.Union[bytes, str], R: ~typing.Tuple[int, int], msg_hash: ~typing.Union[bytes, str], key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~btclib.ecc.der.Sig, lower_s: bool = True, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool

Open the commitment associated to an EC DSA signature.

btclib.ecc.sign_to_contract.ssa_commit_sign(commit: ~typing.Union[bytes, str], msg: ~typing.Union[bytes, str], prv_key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData], nonce: ~typing.Optional[~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData]] = None, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[Sig, Tuple[int, int]]

Include a commitment inside an EC SSA signature.

btclib.ecc.sign_to_contract.ssa_commit_sign_(commit_hash: ~typing.Union[bytes, str], msg_hash: ~typing.Union[bytes, str], prv_key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData], nonce: ~typing.Optional[~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData]] = None, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[Sig, Tuple[int, int]]

Include a commitment inside an EC SSA signature.

btclib.ecc.sign_to_contract.ssa_verify_commit(commit: ~typing.Union[bytes, str], receipt: ~typing.Tuple[int, int], msg: ~typing.Union[bytes, str], pub_key: ~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~btclib.ecc.ssa.Sig, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool

Open the commitment associated to an EC SSA signature.

btclib.ecc.sign_to_contract.ssa_verify_commit_(commit_hash: ~typing.Union[bytes, str], R: ~typing.Tuple[int, int], msg_hash: ~typing.Union[bytes, str], pub_key: ~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~btclib.ecc.ssa.Sig, hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool

Open the commitment associated to an EC SSA signature.

btclib.ecc.ssa module

Elliptic Curve Schnorr Signature Algorithm (ECSSA).

This implementation is according to BIP340-Schnorr:

https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki

Differently from ECDSA, the BIP340-Schnorr scheme supports messages of size hf_size only.

It also uses as public key the x-coordinate (field element) of the curve point associated to the private key 0 < q < n. Therefore, for sepcp256k1 the public key size is 32 bytes. Arguably, the knowledge of q as the discrete logarithm of Q also implies the knowledge of n-q as discrete logarithm of -Q. As such, {q, n-q} can be considered a single private key and {Q, -Q} the associated public key characterized by the shared x_Q.

Also, BIP340 advocates its own SHA256 modification as hash function: TaggedHash(tag, x) = SHA256(SHA256(tag)||SHA256(tag)||x) The rationale is to make BIP340 signatures invalid for anything else but Bitcoin and vice versa.

TaggedHash is used for both the challenge (with tag ‘BIPSchnorr’) and the deterministic nonce (with tag ‘BIPSchnorrDerive’).

To allow for secure batch verification of multiple signatures, BIP340-Schnorr uses a challenge that prevents public key recovery from signature: c = TaggedHash(‘BIPSchnorr’, x_k||x_Q||msg).

A custom deterministic algorithm for the ephemeral key (nonce) is used for signing, instead of the RFC6979 standard: nonce = TaggedHash(‘BIPSchnorrDerive’, q||msg)

Finally, BIP340-Schnorr adopts a robust [r][s] custom serialization format, instead of the loosely specified ASN.1 DER standard. The signature size is p-size*n-size, where p-size is the field element (curve point coordinate) byte size and n-size is the scalar (curve point multiplication coefficient) byte size. For sepcp256k1 the resulting signature size is 64 bytes.

class btclib.ecc.ssa.Sig(r: int, s: int, ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), check_validity: InitVar = True)

Bases: object

BIP340-Schnorr signature.

  • r is an x-coordinate _field_element_, 0 <= r < ec.p

  • s is a scalar, 0 <= s < ec.n (yes, for BIP340-Schnorr it can be zero)

(ec.p is the field prime, ec.n is the curve order)

assert_valid() None
check_validity: InitVar = True
ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1)
classmethod parse(data: Union[BytesIO, bytes, str], check_validity: bool = True) Sig
r: int
s: int
serialize(check_validity: bool = True) bytes
btclib.ecc.ssa.assert_as_valid(msg: ~typing.Union[bytes, str], Q: ~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~typing.Union[~btclib.ecc.ssa.Sig, bytes, str], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) None
btclib.ecc.ssa.assert_as_valid_(msg_hash: ~typing.Union[bytes, str], Q: ~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~typing.Union[~btclib.ecc.ssa.Sig, bytes, str], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) None
btclib.ecc.ssa.assert_batch_as_valid(ms: ~typing.Sequence[~typing.Union[bytes, str]], Qs: ~typing.Sequence[~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]]], sigs: ~typing.Sequence[~btclib.ecc.ssa.Sig], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) None
btclib.ecc.ssa.assert_batch_as_valid_(m_hashes: ~typing.Sequence[~typing.Union[bytes, str]], Qs: ~typing.Sequence[~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]]], sigs: ~typing.Sequence[~btclib.ecc.ssa.Sig], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) None
btclib.ecc.ssa.batch_verify(ms: ~typing.Sequence[~typing.Union[bytes, str]], Qs: ~typing.Sequence[~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]]], sigs: ~typing.Sequence[~btclib.ecc.ssa.Sig], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool

Batch verification of BIP340 signatures.

btclib.ecc.ssa.batch_verify_(m_hashes: ~typing.Sequence[~typing.Union[bytes, str]], Qs: ~typing.Sequence[~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]]], sigs: ~typing.Sequence[~btclib.ecc.ssa.Sig], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool
btclib.ecc.ssa.challenge_(msg_hash: Union[bytes, str], x_Q: int, x_K: int, ec: Curve, hf: Callable[[], Any]) int
btclib.ecc.ssa.crack_prv_key(msg1: ~typing.Union[bytes, str], sig1: ~typing.Union[~btclib.ecc.ssa.Sig, bytes, str], msg2: ~typing.Union[bytes, str], sig2: ~typing.Union[~btclib.ecc.ssa.Sig, bytes, str], Q: ~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[int, int]
btclib.ecc.ssa.crack_prv_key_(msg_hash1: ~typing.Union[bytes, str], sig1: ~typing.Union[~btclib.ecc.ssa.Sig, bytes, str], msg_hash2: ~typing.Union[bytes, str], sig2: ~typing.Union[~btclib.ecc.ssa.Sig, bytes, str], Q: ~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Tuple[int, int]
btclib.ecc.ssa.det_nonce_(msg_hash: ~typing.Union[bytes, str], prv_key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData], aux: ~typing.Optional[~typing.Union[bytes, str]] = None, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) int

Return a BIP340 deterministic ephemeral key (nonce).

btclib.ecc.ssa.gen_keys(prv_key: Optional[Union[int, bytes, str, BIP32KeyData]] = None, ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1)) Tuple[int, int]

Return a BIP340 private/public (int, int) key-pair.

btclib.ecc.ssa.gen_keys_(prv_key: Optional[Union[int, bytes, str, BIP32KeyData]] = None, ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1)) Tuple[int, int, Tuple[int, int, int]]

Return a BIP340 private/public (int, JacPoint) key-pair.

btclib.ecc.ssa.point_from_bip340pub_key(x_Q: Union[bytes, str, int, BIP32KeyData, Tuple[int, int]], ec: Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1)) Tuple[int, int]

Return a verified-as-valid BIP340 public key as Point tuple.

It supports:

  • BIP32 extended keys (bytes, string, or BIP32KeyData)

  • SEC Octets (bytes or hex-string, with 02, 03, or 04 prefix)

  • BIP340 Octets (bytes or hex-string, p-size Point x-coordinate)

  • native tuple

btclib.ecc.ssa.sign(msg: ~typing.Union[bytes, str], prv_key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData], nonce: ~typing.Optional[~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData]] = None, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Sig

Sign message according to BIP340 signature algorithm.

The message msg is first processed by hf, yielding the value

msg_hash = hf(msg),

a sequence of bits of length hf_len.

Normally, hf is chosen such that its output length hf_len is roughly equal to nlen, the bit-length of the group order n, since the overall security of the signature scheme will depend on the smallest of hf_len and nlen; however, ECSSA supports all combinations of hf_len and nlen.

The BIP340 deterministic nonce (not RFC6979) is used.

btclib.ecc.ssa.sign_(msg_hash: ~typing.Union[bytes, str], prv_key: ~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData], nonce: ~typing.Optional[~typing.Union[int, bytes, str, ~btclib.bip32.bip32.BIP32KeyData]] = None, ec: ~btclib.ecc.curve.Curve = Curve('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F', 0, 7, ('79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798', '483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'), 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141', 1), hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) Sig

Sign a hf_len bytes message according to BIP340 signature algorithm.

If the deterministic nonce is not provided, the BIP340 specification (not RFC6979) is used.

btclib.ecc.ssa.verify(msg: ~typing.Union[bytes, str], Q: ~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~typing.Union[~btclib.ecc.ssa.Sig, bytes, str], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool

Verify the BIP340 signature of the provided message.

btclib.ecc.ssa.verify_(msg_hash: ~typing.Union[bytes, str], Q: ~typing.Union[bytes, str, int, ~btclib.bip32.bip32.BIP32KeyData, ~typing.Tuple[int, int]], sig: ~typing.Union[~btclib.ecc.ssa.Sig, bytes, str], hf: ~typing.Callable[[], ~typing.Any] = <built-in function openssl_sha256>) bool

Verify the BIP340 signature of the provided message.

Module contents

btclib.ecc submodule.