The 21 Crypto Library (two1.crypto)

Posted by Nigel Drego

The 21 Crypto Library (two1.crypto)

The crypto module within the 21 Bitcoin Library (two1.crypto) provides an interface to the low-level cryptographic functions used in Bitcoin to create public keys and signatures using the Elliptic Curve Digital Signature Algorithm (ECDSA) on the secp256k1 curve.

Two modules are provided:

  1. two1.crypto.ecdsa_openssl: An OpenSSL-using module that's available if OpenSSL is available on the system.

  2. two1.crypto.ecdsa: A pure Python module that's always available and is very portable, but which does not contain as many performance optimizations and which has not been as well audited as the Bitcoin-related parts of OpenSSL.

We will illustrate the use of the two1.crypto module by going through a simple example:

Generate an ECDSA key pair

Start our simple example by importing the library and loading the secp256k1 elliptical curve Bitcoin uses for cryptography:

>>> from two1.crypto import ecdsa
>>> ec = ecdsa.secp256k1()

Generate an ECDSA key pair from random data, which is the way all non-HD wallets generate keys:

>>> priv, pub = ec.gen_key_pair()

Show the private key:

>>> priv
3847872623548319391455692167473247674183946521467832802482786839851919968799

Public keys are points on the secp256k1 curve; they're represented by x,y coordinates on a 256-bit by 256-bit prime number field.

>>> pub.x
2415082117413395476165664856824912483567021584059887816816320242542362529060
>>> pub.y
10353152122150796736951723708916428234072509795738767586951937235484200709278

The construction of the secp256k1 and other Koblitz-style curves means that the curve never backtracks itself, so each x coordinate only has two possible y coordinates (the inverse of each other). This allows us to "compress" the y coordinate down to a single bit: whether the coordinate is on the "high" half of the curve or the "low" half of the curve. Let's get the compressed public key for the same key above:

>>> pub.compressed_bytes
b'\x02\xf4\xf5\xbc\x9d{\x91+c\xb2\xffO;\x14)\xed3E\x11\xad+\xab\xc3\x1c\x1b\xe7\xd5\xc2%\x1b\xc8\xe9\x8b'

Just in case you lose that extra bit of information telling you which y coordinate is correct, you can recover both possible y coordinates for any x coordinate on the curve:

>>> ec.y_from_x(pub.x)
[10353152122150796736951723708916428234072509795738767586951937235484200709278,
105438937115165398686619261299771479619197474869901796452505646772424633962385]

How to sign a message

Generally we use these keys for signing and verifying things within Bitcoin. Let's sign a message:

>>> signature = ec.sign(b'21', priv)
>>> signature
(Point(x=48170274459291977398620592594153137413292379572661653951252377159885526334606,
y=25099180716939036749527356364397603957892864939606910246337660310599408353076),
1)

How to verify a signature

The signature gives us a new point on the secp256k1 curve. Now let's verify that signature::

>>> ec.verify(b'21', signature.__getitem__(0), pub)
True

two1.crypto: module contents

The two1.crypto module is organized into the following submodules:

two1.crypto.ecdsa

For the vast majority of use cases, importing either EllipticCurve or secp256k1 from two1.crypto.ecdsa should be sufficient. The module will automatically use ecdsa_openssl if OpenSSL is installed and usable on the system. If it is not installed/usable, ecdsa_python will be used instead.

To directly select one or the other, import specifically from two1.crypto.ecdsa_openssl or two1.crypto.ecdsa_python.

class two1.crypto.ecdsa_openssl.ECPointAffine(curve, x, y, infinity=False)

Bases: object

An affine (2D) representation of an elliptic curve point.

In this implementation, only the minimum functionality required for bitcoin crypto-API compatibility is provided. All math operations make use of OpenSSL primitives.

Parameters:
  • curve (EllipticCurve) – The curve the point is on.
  • x (int) – x component of point.
  • y (int) – y component of point.
  • infinity (bool) – Whether or not this point is at infinity.
Returns:

the point formed by (x, y) on curve.

Return type:

ECPointAffine

compressed_bytes

Returns the compressed bytes for this point.

If pt.y is odd, 0x03 is pre-pended to pt.x. If pt.y is even, 0x02 is pre-pended to pt.x.

Returns:Compressed byte representation.
Return type:bytes
class two1.crypto.ecdsa_openssl.EllipticCurve(hash_function)

Bases: two1.crypto.ecdsa_base.EllipticCurveBase

A generic class for elliptic curves and operations on them.

The curves must be of the form: y^2 = x^3 + ax + b.

Parameters:hash_function (function) – The function to use for hashing messages.
curve_name = None
gen_key_pair(random_generator=<random.SystemRandom object at 0x28f8488>)

Generates a public/private key pair.

Parameters:random_generator (generator) – The random generator to use.
Returns:A private key in the range of 1 to self.n - 1 and an ECPointAffine containing the public key point.
Return type:tuple
is_on_curve(p)

Checks whether a point is on the curve.

Parameters:p (ECPointAffine) – Point to be checked
Returns:True if p is on the curve, False otherwise.
Return type:bool
public_key(private_key)

Returns the public (verifying) key for a given private key.

Parameters:private_key (int) – the private key to derive the public key for.
Returns:The point representing the public key.
Return type:ECPointAffine
recover_public_key(message, signature, recovery_id=None)

Recovers possibilities for the public key associated with the private key used to sign message and generate signature.

Since there are multiple possibilities (two for curves with co-factor = 1), each possibility that successfully verifies the signature is returned.

Parameters:
  • message (bytes) – The message that was signed.
  • signature (ECPointAffine) – The point representing the signature.
  • recovery_id (int) – If provided, limits the valid x and y point to only that described by the recovery_id.
Returns:

list – List of points representing valid public keys that verify signature.

Return type:

ECPointAffine

verify(message, signature, public_key, do_hash=True)

Verifies that signature was generated with a private key corresponding to public key, operating on message.

Parameters:
  • message (bytes) – The message to be signed
  • signature (Point) – (r, s) representing the signature
  • public_key (ECPointAffine) – ECPointAffine of the public key
  • do_hash (bool) – True if the message should be hashed prior to signing, False if not. This should always be left as True except in special situations which require doing the hash outside (e.g. handling Bitcoin bugs).
Returns:

True if the signature is verified, False otherwise.

Return type:

bool

y_from_x(x)

Computes the y component corresponding to x.

Since elliptic curves are symmetric about the x-axis, the x component (and sign) is all that is required to determine a point on the curve.

Parameters:x (int) – x component of the point.
Returns:both possible y components of the point.
Return type:tuple
class two1.crypto.ecdsa_openssl.p256

Bases: two1.crypto.ecdsa_openssl.EllipticCurve

curve_name = 415
class two1.crypto.ecdsa_openssl.secp256k1

Bases: two1.crypto.ecdsa_openssl.EllipticCurve

curve_name = 714
class two1.crypto.ecdsa_python.ECPoint(curve, x, y, z=0, infinity=False)

Bases: object

Base class for any elliptic curve point implementations.

Currently there are two implementations provided: 1) ECPointAffine which is the standard affine coordinate system, and 2) ECPointJacobian which is a 3-dimensional projected coordinate system.

The EllipticCurve class currently utilizes ECPointJacobian for efficiency reasons. However, switching to the affine implementation is trivial.

Parameters:
  • curve (EllipticCurve) – The curve the point is on.
  • x (int) – x component of point.
  • y (int) – y component of point.
  • z (int) – z component of point (only used in Jacobian)
  • infinity (bool) – Whether this is the point-at-infinity.
Returns:

the point formed by (x, y, z) on curve.

Return type:

ECPoint

double()

Implements a doubling of this point (i.e. 2P)

static from_affine()

Converts from an Affine representation to a Jacobian.

from_jacobian()

Converts from a Jacobian representation to an Affine.

to_affine()

If not affine, converts to affine. Otherwise should return self.

to_jacobian()

If not affine, converts to affine. Otherwise should return self.

class two1.crypto.ecdsa_python.ECPointAffine(curve, x, y, infinity=False)

Bases: two1.crypto.ecdsa_python.ECPoint

Encapsulates a point on an elliptic curve.

This class provides an affine representation of a point on an elliptic curve. It presents the standard addition and scalar multiplication operations between two points as overloaded ‘+’ and ‘’ Python operators. Scalar multiplications are computed via the Montgomery Ladder technique.

Parameters:
  • curve (EllipticCurve) – The curve the point is on.
  • x (int) – x component of point.
  • y (int) – y component of point.
Returns:

the point formed by (x, y) on curve.

Return type:

ECPointAffine

compressed_bytes

Returns the compressed bytes for this point.

If pt.y is odd, 0x03 is pre-pended to pt.x. If pt.y is even, 0x02 is pre-pended to pt.x.

Returns:Compressed byte representation.
Return type:bytes
double()

Doubles this point.

Returns:The point corresponding to 2self.
Return type:ECPointAffine
static from_affine(affine_point)

A no-op since the point is already affine.

Parameters:affine_point (ECPointAffine) – A Affine point
Returns:Returns the input arg.
Return type:ECPointAffine
static from_int(curve, i)

Creates a point from an integer.

Assumes that pt.y is the lower bits of i and pt.x is the upper bits of i.

Parameters:
  • curve (EllipticCurve) – The curve to which the point belongs.
  • i (int) – integer representing the point.
Returns:

point on curve.

Return type:

ECPointAffine

static from_jacobian(jacobian_point)

Converts from a Jacobian point to an affine representation.

Parameters:jacobian_point (ECPointJacobian) – The Jacobian point to convert.
Returns:The affine representation.
Return type:ECPointAffine
to_affine()

No-op since this is already a Affine point.

Returns:Just returns this point.
Return type:ECPointAffine
to_jacobian()

Converts this point to an jacobian representation.

Returns:The jacobian representation.
Return type:ECPointJacobian
class two1.crypto.ecdsa_python.ECPointJacobian(curve, x, y, z, infinity=False)

Bases: two1.crypto.ecdsa_python.ECPoint

Encapsulates a point on an elliptic curve.

This class provides a Jacobian representation of a point on an elliptic curve. It presents the standard addition and scalar multiplication operations between two points as overloaded ‘+’ and ‘’ Python operators. Scalar multiplications are computed via the Montgomery Ladder technique (same as OpenSSL).

All math operations from: https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates

Parameters:
  • curve (EllipticCurve) – The curve the point is on.
  • x (int) – x component of point.
  • y (int) – y component of point.
  • z (int) – z component of point.
  • infinity (bool) – Whether this is the point-at-infinity.
Returns:

the point formed by (x, y) on curve.

Return type:

ECPointAffine

double()

Optimized point doubling operation that results in 2self.

Returns:The point corresponding to 2self.
Return type:ECPointJacobian
static from_affine(affine_point)

Converts from an affine point to a Jacobian representation. This is simplisticly done by using Z = 1.

Parameters:affine_point (ECPointAffine) – The affine point to convert.
Returns:The jacobian representation.
Return type:ECPointJacobian
static from_int(curve, i)

Creates a point from an integer.

Assumes that pt.y is the lower bits of i and pt.x is the upper bits of i.

Parameters:
  • curve (EllipticCurve) – The curve to which the point belongs.
  • i (int) – integer representing the point.
Returns:

point on curve.

Return type:

ECPointJacobian

static from_jacobian(jacobian_point)

A no-op since the point is already jacobian.

Parameters:jacobian_point (ECPointJacobian) – A Jacobian point
Returns:Returns the input arg.
Return type:ECPointJacobian
to_affine()

Converts this point to an affine representation.

Returns:The affine representation.
Return type:ECPointAffine
to_jacobian()

No-op since this is already a Jacobian point.

Returns:Just returns this point.
Return type:ECPointJacobian
class two1.crypto.ecdsa_python.EllipticCurve(p, a, b, n, G, h, hash_function)

Bases: two1.crypto.ecdsa_base.EllipticCurveBase

A generic class for elliptic curves and operations on them.

The curves must be of the form: y^2 = x^3 + ax + b.

Parameters:
  • p (int) – Prime that defines the field.
  • a (int) – linear coefficient of the curve.
  • b (int) – constant of the curve.
  • n (int) – order of G (smallest prime) such that nG = infinity.
  • G (Point) – generator (base point) of the curve.
  • h (int) – The curve co-factor.
  • hash_function (function) – The function to use for hashing messages.
base_point

Returns the base point for this curve.

Returns:the base point
Return type:ECPointJacobian
gen_key_pair(random_generator=<random.SystemRandom object at 0x2f5e488>)

Generates a public/private key pair.

Parameters:random_generator (generator) – The random generator to use.
Returns:A private key in the range of 1 to self.n - 1 and an ECPointAffine containing the public key point.
Return type:tuple
is_on_curve(p)

Checks whether a point is on the curve.

Parameters:p (ECPointAffine) – Point to be checked
Returns:True if p is on the curve, False otherwise.
Return type:bool
static modinv(a, n)

Provides the modular inverse of a wrt n.

This uses the extended Euclidean algorithm to compute the the GCD of a, n.

Parameters:
  • a (int) – number to find modular inverse of
  • n (int) – modulus
static modsqrt(a, n)
public_key(private_key)

Returns the public (verifying) key for a given private key.

Parameters:private_key (int) – the private key to derive the public key for.
Returns:The point representing the public key.
Return type:ECPointAffine
recover_public_key(message, signature, recovery_id=None)

Recovers possibilities for the public key associated with the private key used to sign message and generate signature.

Since there are multiple possibilities (two for curves with co-factor = 1), each possibility that successfully verifies the signature is returned.

Parameters:
  • message (bytes) – The message that was signed.
  • signature (ECPointAffine) – The point representing the signature.
  • recovery_id (int) – If provided, limits the valid x and y point to only that described by the recovery_id.
Returns:

list – List of points representing valid public keys that verify signature.

Return type:

ECPointAffine

verify(message, signature, public_key, do_hash=True)

Verifies that signature was generated with a private key corresponding to public key, operating on message.

Parameters:
  • message (bytes) – The message to be signed
  • signature (Point) – (r, s) representing the signature
  • public_key (ECPointAffine) – ECPointAffine of the public key
  • do_hash (bool) – True if the message should be hashed prior to signing, False if not. This should always be left as True except in special situations which require doing the hash outside (e.g. handling Bitcoin bugs).
Returns:

True if the signature is verified, False otherwise.

Return type:

bool

y_from_x(x)

Computes the y component corresponding to x.

Since elliptic curves are symmetric about the x-axis, the x component (and sign) is all that is required to determine a point on the curve.

Parameters:x (int) – x component of the point.
Returns:both possible y components of the point.
Return type:tuple
class two1.crypto.ecdsa_python.Point(x, y)

Bases: tuple

x

Alias for field number 0

y

Alias for field number 1

two1.crypto.ecdsa_python.montgomery_ladder(k, p)

Implements scalar multiplication via the Montgomery ladder technique.

This technique is used to prevent against simple side-channel attacks as well as certain kinds of cache attacks.

Parameters:
  • k (int) – The scalar to multiply by.
  • p (ECPoint) – The point to multiply by k.
Returns:

p k

Return type:

ECPoint

class two1.crypto.ecdsa_python.p256

Bases: two1.crypto.ecdsa_python.EllipticCurve

P-256 NIST-defined curve

A = 115792089210356248762697446949407573530086143415290314195533631308867097853948
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286
Gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109
H = 1
N = 115792089210356248762697446949407573529996955224135760342422259061068512044369
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
class two1.crypto.ecdsa_python.secp256k1

Bases: two1.crypto.ecdsa_python.EllipticCurve

Elliptic curve used in Bitcoin.

A = 0
B = 7
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
H = 1
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337
P = 115792089237316195423570985008687907853269984665640564039457584007908834671663