ecc package

Subpackages

Submodules

ecc.alias module

The type aliases of the public API, and the input conventions they name.

Octets and String below are the same union, so mypy cannot tell one from the other: passing a text string where a hex-string is expected is a type error this file names but no checker can catch. The distinction is enforced at run time instead, by the converter each function calls on its way in – bytes_from_octets for Octets, str_from_string for String – and it is documented here because that is the only place it can be read as one piece.

Making Octets and String NewTypes would let mypy separate them, at the cost of every caller having to wrap its literals: Octets(“deadbeef”) instead of “deadbeef”, throughout a public API whose whole style is to accept whatever is convertible. For those two that is a different package, not a fix to this one. Public below is a NewType because there the wrap is the point: it is where a caller declares a value public.

class ecc.alias.HashObject(*args, **kwargs)[source]

Bases: Protocol

The slice of a hashlib object this package reads, as a Protocol.

Structural: anything hashlib.new returns satisfies it, and the members carry hashlib’s own meanings.

property block_size: int

Return the internal block length in bytes.

copy() → HashObject[source]

Return a clone that can absorb independently.

digest() → bytes[source]

Return the digest of everything absorbed so far.

property digest_size: int

Return the digest length in bytes.

hexdigest() → str[source]

Return the digest as a hex string.

property name: str

Return the name hashlib.new would accept.

update(data: Any, /) → None[source]

Absorb more data, as hashlib’s update does.

ecc.alias.Octets = bytes | str | bytearray | memoryview

Bytes, or the hex-string that decodes to them, wherever raw bytes are asked for.

class ecc.alias.Public

An integer the caller declares public, for a variable-time parameter.

alias of int

ecc.exceptions module

Exception classes.

These exist only to tell an exception raised by ecc from one raised by any other code: each derives from the built-in that says what kind of failure it is, and adds nothing to it.

EccException is what makes that telling apart a single except rather than a tuple of three a caller has to keep in step with this hierarchy. It is inherited beside the built-in and not instead of it, which is the half that matters: EccValueError is a ValueError, so code catching the built-in catches it, and json.JSONDecodeError is the standard library doing the same.

It is caught and never raised: every raise below is one of the three, and which one answers a question the base cannot carry – whether the value was wrong, the type was, or neither was and a check failed anyway. A caller with something to do about that difference names the specific class; except EccException is for the caller who only needs to know it came from here.

The two classes carrying a field hand every constructor argument to BaseException.__init__ and compose their message in __str__, which is what subprocess.CalledProcessError and UnicodeDecodeError do, and what makes them picklable: BaseException.__reduce__ returns (cls, self.args), so a class whose args is the composed message alone is rebuilt by calling it with one argument, and one argument is not what it takes. That is a TypeError out of pickle, out of copy.copy and out of copy.deepcopy – and out of a ProcessPoolExecutor, which cannot send the exception back and reports a broken pool instead of the failure the worker died of.

exception ecc.exceptions.BorromeanRingError(message: str, ring: int | None, position: int | None)[source]

Bases: EccRuntimeError

A borromean ring signature check failed, and where names it.

ring is the index into pubk_rings and position the index within that ring: an e-value landing on zero, and the point at infinity its one-in-n neighbour lands a ring’s nonce or its r on instead, each happen at one ring and one position, and ecc.ecc.borromean.sign and assert_as_valid already have both in hand at every one of their raises. Naming them is what tells a caller building on this primitive which key rejected the signature rather than only that the whole thing did.

Both are None for the one failure with no ring of its own: the final e0 not matching what every ring converges on is a property of the whole signature, not of any single ring in it.

An EccRuntimeError and not InvalidContributionError: that class names a party to an interactive multi-round protocol – MuSig2 – and which of its contributions was wrong, where a borromean ring signature is not interactive and has no parties to accuse, only positions in a signature that either close their ring or do not. An EccRuntimeError still, so code catching that keeps catching this, as verify already does.

exception ecc.exceptions.EccException[source]

Bases: Exception

Anything ecc raised, whatever kind of failure it is.

The one name to catch for a caller who handles the standard library’s exceptions anyway and needs to know which came from here. Never raised: the three below it are, and each says which kind of failure it was.

exception ecc.exceptions.EccRuntimeError[source]

Bases: EccException, RuntimeError

A check that failed on valid inputs, e.g. a failed verification.

exception ecc.exceptions.EccTypeError[source]

Bases: EccException, TypeError

An input of a type no conversion accepts: a caller error.

exception ecc.exceptions.EccValueError[source]

Bases: EccException, ValueError

A value no valid input could carry; the package’s usual refusal.

exception ecc.exceptions.InvalidContributionError(signer: int | None, contrib: str)[source]

Bases: EccRuntimeError

A party to an interactive protocol sent a value that does not check out.

Which party, and which of its contributions: signer is the index in the list the caller passed, None for the aggregator – who has no index, having no key – and contrib names what was wrong, one of “pubkey”, “pubnonce”, “aggnonce”, “aggothernonce”, “psig” or “adaptor”. That is the whole point of the class: a multi-round protocol that merely fails leaves every participant a suspect, and the answer a caller needs is who to hold accountable and to exclude from the next attempt.

An EccRuntimeError and not an EccValueError, which is the other obvious base and the one BIP327 keeps separate: its reference implementation raises ValueError for an argument that breaks a precondition – the caller’s own mistake, a 33-byte tweak – and this for a peer misbehaving, and the MuSig2 test vectors distinguish the two case by case. Sharing a base would put the two beyond telling apart by except, and would let every except ValueError in the package swallow an accusation.

ecc.hashes module

The hashing ecc.ecc’s schemes do.

BIP340’s tagged hash, SEC 1’s reduction of a message to one digest, and the check that a hash function is a constructor. Each is hashlib and nothing else.

ecc.hashes.reduce_to_hlen(msg: bytes | str | bytearray | memoryview, hf: Callable[[], ~ecc.alias.HashObject]=<built-in function openssl_sha256>) → bytes[source]

Return the message digested by hf, one digest long.

Step 4 of SEC 1 v.2 section 4.1.3: what the un-underscored signing and verifying spellings do to a message before handing it to their trailing-underscore twins.

ecc.hashes.tagged_hash(tag: bytes, m: bytes, hf: Callable[[], ~ecc.alias.HashObject]=<built-in function openssl_sha256>) → bytes[source]

Return BIP340’s tagged hash: hf(hf(tag) || hf(tag) || m).

The doubled tag digest is what makes a hash under one tag invalid under every other.

tag and m are bytes and not Octets: unlike every octets parameter this package converts through bytes_from_octets, neither is ever meant to be read as a hex-string, so assert_type is what refuses a caller’s mistake here rather than a coercion (issue btclib-org/ecc#11).

ecc.kdf module

Key derivation functions: SEC 1’s ANSI-X9.63-KDF and RFC 5869’s HKDF.

A KDF stretches one secret into keying data of the length a protocol asks for, under a hash function the caller chooses. ansi_x9_63_kdf is SEC 1’s, one hash per block over a four-octet counter, and ecc.ecc.dh.diffie_hellman is the agreement built on it. hkdf is RFC 5869’s, extract then expand, and it is the one piece of BIP324’s key schedule this package implements: a construction over a hash rather than over a cipher, which is the near side of the line ecc.ecc.ellswift draws and ecc.ecc.ecies argues.

Both are hashlib and hmac and nothing else: no elliptic curve, and no bitcoin.

Why they are here rather than beside the agreement that uses one (issue btclib-org/btclib#1080). SEC 1 defines ANSI-X9.63-KDF in section 3.6.1 for the agreement of section 6.1, so ecc.ecc.dh is where it reads naturally, and with one KDF in the tree that costs nothing. HKDF has no such tie – RFC 5869 has no Diffie-Hellman in it, and nothing that wants HKDF here holds a public key – so a drawer under ecc.ecc leaves either a KDF reached through a package of signature schemes or two KDFs in two places for the next one to have to choose between. One drawer, at the layer its contents belong to, is the answer to both; btclib-org/btclib’s RELEASE_NOTES.md has the spellings it costs.

ecc.kdf.ansi_x9_63_kdf(z: bytes, size: int, hf: Callable[[], HashObject], shared_info: bytes | None) → bytes[source]

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.

size is a positive number of octets, SEC 1’s keydatalen: an EccTypeError if it is no integer, an EccValueError if it is zero, negative, or above what the hash function can derive.

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

z and shared_info are bytes and not Octets: assert_type is what refuses a caller’s mistake here, hf never reaching a bare hf() on something that is not callable (issue btclib-org/ecc#11).

ecc.kdf.hkdf(ikm: bytes, size: int, hf: Callable[[], HashObject], salt: bytes | None, info: bytes | None) → bytes[source]

Return keying data according to HKDF, extract then expand.

The composition of the two steps above, which is how RFC 5869 is used unless the caller already holds a uniformly random key: extract concentrates the entropy of ikm under salt, expand stretches the result to size octets under info.

https://www.rfc-editor.org/rfc/rfc5869.html, section 2

ecc.kdf.hkdf_expand(prk: bytes, size: int, hf: Callable[[], HashObject], info: bytes | None) → bytes[source]

Return output keying material of the requested size.

prk is a pseudorandom key, hkdf_extract’s answer or a uniformly random key of at least a digest’s length. info is optional context – a protocol label, a party’s identity – which binds the output to an application, so that one prk yields independent keys.

size is a positive number of octets, RFC 5869’s L: an EccTypeError if it is no integer, an EccValueError if it is zero, negative, or above 255 digests. A prk below a digest is an EccValueError too.

https://www.rfc-editor.org/rfc/rfc5869.html, section 2.3

prk and info are bytes and not Octets, for the reason ansi_x9_63_kdf’s docstring gives (issue btclib-org/ecc#11).

ecc.kdf.hkdf_extract(ikm: bytes, salt: bytes | None, hf: Callable[[], HashObject]) → bytes[source]

Return the pseudorandom key of HKDF’s extract step.

ikm is the input keying material, which need not be uniformly distributed – concentrating whatever entropy it has into one digest is what this step is for. salt is an optional non-secret value, which may be reused. The answer is one digest of hf, and is what hkdf_expand takes as its prk.

https://www.rfc-editor.org/rfc/rfc5869.html, section 2.2

An ikm that is already a uniformly random key of full length does not need this step: RFC 5869 section 3.3 says to skip it and expand that key directly, which hkdf_expand is separately public for.

ikm and salt are bytes and not Octets, for the reason ansi_x9_63_kdf’s docstring gives (issue btclib-org/ecc#11).

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_var-shanks-algorithm-implementation-of-prime-modular-square-root/43267 with the following modifications:

  • type annotated Python3

  • minor improvements

  • added extensive unit test

ecc.number_theory.legendre_symbol_var(a: Public, p: int) → int[source]

Compute the Legendre symbol a|p, as a binary Jacobi symbol.

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. The Jacobi symbol is what is computed, and for a prime modulus the two are the same number.

By the reciprocity recursion rather than by Euler’s criterion, which is pow(a, (p - 1) // 2, p) – an exponentiation the size of the square root the caller is asking about, where this is a gcd. The factors of two come out all at once, a & -a being the lowest set bit, which is libsecp256k1’s secp256k1_ctz64_var; asking a gcd rather than an exponent is what its secp256k1_fe_is_square_var does, through secp256k1_jacobi64_maybe_var and never through a power. Its own recursion is the safegcd one, which in bytecode loses as every safegcd does – curves.curve_group_2 keeps the list.

The loop’s length follows a, where an exponentiation’s did not. SECURITY.md publishes the Python path as variable-time, and nothing in the tree asks this about a value that has to stay hidden. curves.curve._is_x_coordinate_var reaches it for a signature’s r, the x-coordinate of a serialized xpub, or the -x-u that an ElligatorSwift encoding is tested against, and ecc.ecc.ellswift reaches it directly for the fractions and radicands its map and its inverse test, each of them public and on secp256k1 each answered by the bindings before this is reached; ecc.ecc.pedersen and ecc.ecc.rangeproof reach it for the residuosity octet of a point they are about to write down.

ecc.number_theory.mod_inv(a: int, m: int) → int[source]

Return the inverse of a (mod m), timed on a random value instead.

What mod_inv_var is for an operand that is public, this is for one that is secret. The extended Euclid under that one takes the iterations its input asks for, and for an operand drawn uniformly below m what its duration carries is the operand’s bit-length: on secp256k1’s order a 256-bit scalar takes longer than a 128-bit one, falling at every step between them. That correlation is what the Minerva attack collects – an ECDSA nonce is such a scalar, and a few thousand signing times sorted by it are a lattice away from the private key.

(b*a)^-1 * b is a^-1 for every b invertible mod m, so drawing b at random leaves an inverse whose iteration count follows b and tells an observer nothing about a. What it adds is two multiplications, two reductions and a draw from secrets. Fermat’s pow(a, m - 2, m) is the alternative and is flat for a different reason, its ladder running on the fixed exponent rather than on a random operand; it is not the one chosen.

The draw is what costs, so a small modulus pays proportionally more: on an order of 11 the Euclid is a few iterations and secrets is the same syscall. Nothing signs with such an order outside the test suite.

Not a constant-time inverse, and no more claiming to be one than curve_group._blinded_jac does: the duration is still an extended Euclid’s and still visible, and what the blinding changes is whose it is. SECURITY.md publishes the Python path as variable-time, and CONTRIBUTING.md has what a name in this library does and does not promise about duration.

m does not have to be a prime, and the blinding holds for any m. The factor’s gcd with m, a second Euclid timed on the secret factor, is taken only when the product has no inverse: a factor that is not a unit, which only a composite m draws, is then redrawn, and an operand with no inverse raises. The expected number of draws is (m - 1) / phi(m). mod_inv_var is never handed the operand itself.

ecc.number_theory.mod_inv_batch(a: Sequence[int], m: int) → list[int][source]

Return every inverse, each timed on a random value instead.

What mod_inv is to mod_inv_var, this is to mod_inv_batch_var: the twin a secret may be handed. Montgomery’s trick inverts one running product for the whole sequence, so the single extended Euclid it spends is timed on a value every element went into – which is the channel, the same one and no smaller for being shared.

Each element is blinded with a factor of its own rather than the sequence with one: inv(a_i * b_i) * b_i is inv(a_i), and the product the batch forms is then a product of blinded values. One factor for all of them would blind that product and leave the ratios a_i / a_j in the peeled-back inverses, which is what the running products are made of.

So it costs n draws from secrets and 2n multiplications on top of the trick.

It is still the trick, which is the point of it being a batch at all: one extended Euclid for the whole sequence, where mod_inv on each element spends one each.

On a composite modulus a factor can be a zero divisor, and an element can have no inverse: either fails the batch, which is then answered by mod_inv on each element in turn, so the cost is at worst n independent calls.

Not constant-time, for the reasons mod_inv gives at length. The empty sequence is not an error here either.

ecc.number_theory.mod_inv_batch_var(a: Sequence[Public], m: int) → list[int][source]

Return the inverse of every element of a (mod m), in its order.

m does not have to be a prime, and every element has to be invertible modulo it, as mod_inv_var requires of its one operand.

Montgomery’s trick, which libsecp256k1 runs inside secp256k1_ge_set_all_gej_var: the running products a[0], a[0]*a[1], …, a[0]*…*a[n-1] are formed, the last of them is inverted once, and the individual inverses are peeled back off it. So n inverses cost one inverse and 3(n-1) products, where n calls to mod_inv_var are n extended Euclids – an inverse modulo a 256-bit prime being, on an int, some thirty times a product.

An empty sequence has no inverses and is not an error: it is what a caller that filtered its own input is left with.

ecc.number_theory.mod_inv_var(a: Public, m: int) → int[source]

Return the inverse of a (mod m).

m does not have to be a prime.

pow(a, -1, m) is an Extended Euclidean Algorithm too: on an int, CPython’s long_invmod, which is the loop xgcd_var runs with the second cofactor dropped; on gmpy2’s mpz, GMP’s mpz_invert. Either way it delegates the algorithm to C rather than interpreting it, and that is the whole of why it is called. It is not a constant-time inverse and neither was the bytecode one; SECURITY.md publishes the Python path as variable-time.

Its duration follows the operand, so a secret one goes to mod_inv instead: what that duration carries is described there, and it is enough to recover a private key from a signature.

What pow does not carry is this module’s contract, so the checks stay above it and the message below it: a non-invertible operand leaves pow as a bare ValueError naming neither operand, and rebuilding the message says more than chaining that one would.

ecc.number_theory.mod_sqrt_var(a: Public, p: int) → int[source]

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

Solve the equation:

x^2 = a mod p

and return x; 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_var-shanks-algorithm-implementation-of-prime-modular-square-root/43267

ecc.number_theory.tonelli_var(a: Public, p: int) → int[source]

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_var-shanks-algorithm-implementation-of-prime-modular-square-root/43267

ecc.number_theory.xgcd_var(a: Public, b: Public) → tuple[int, int, int][source]

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

Module contents

The ecc package: what it publishes, and the version metadata.

Elliptic curve arithmetic and the signature, commitment and key-agreement schemes built on it, over any curve in short Weierstrass form, with libsecp256k1 accelerating secp256k1 where the optional btclib-secp256k1 bindings are installed.

__all__ here is the root of the package’s public tree: the packages and top-level modules a caller reaches from this name. Each of those, and each module below them, declares its own __all__, so a walk that starts here has a declared surface at every node – which is why the list is not pkgutil.iter_modules: discovery would answer the file tree, and a module added to the directory would publish itself rather than being published.

name is not in it, nor are the metadata dunders. name is the distribution’s name and not a member of the tree, __version__ bound by a star import would overwrite the importing module’s own, and each is still an attribute here: ecc.__version__ is how a caller reads the version and ecc.name how it reads the name.

Nothing is imported eagerly. A module is imported when it is first asked for, through the __getattr__ at the bottom of this file, so import ecc is the metadata lookup below and nothing else, and the import graph keeps its shape: importing every module here would put the whole package in sys.modules before any single module of it could be imported first, which is the situation tests/imports_test.py exists to make impossible.

What that costs is worth stating: mypy reads a module-level __getattr__ as a promise that any attribute may exist, so ecc.cruves is Any to it and a misspelling on this package is a runtime AttributeError rather than a reported error. The spellings a caller actually writes – from ecc import curves, import ecc.curves, from ecc.curves import mult – resolve against the real modules and stay checked.