elliptic curve public key recovery feature

[SmartLayer]

Thanks to the popularity of Ethereum, most of the libraries working around Ethereum no longer provide public keys, but only the last 20 bit of the hash of the public key. In fact, some libraries (geth-android for example) made it difficult to get public key as it is treated as a secret, making it difficult to use fastecdsa with those. I need to mention that treating public key as a secret is not a secret - it started in Bitcoin though, 9 years ago.

Traditionally, the public key is used to re-generate r, which is checked against signature (r,s). Now a public key is recovered from the message hash and signature (r, s) (plus a sign bit), then hashed, and compared against a known public hash. This allowed a form of "public key" called "address" that is both smaller and more secretive. This way, before the owner signs anything, no one can deduce the public key and leverage any security breaches that depends on the knowledge of the public key; after the owner signs anything, the money is moved and protected by a different set of keys, reducing attack surface by far.

It would be great to see the support of recover() function in order for fastecdsa to be usable in cryptocurrencies. The method is mentioned here: https://crypto.stackexchange.com/questions/18105/how-does-recovering-the-public-key-from-an-ecdsa-signature-work

[AntonKueltz]

I've added the core logic for this in commits 3bcd6be and 601c76c. The method fastecdsa.keys.get_public_keys_from_sig should do the trick -

def get_public_keys_from_sig(sig, msg, curve=P256, hashfunc=sha256):
    """Recover the public keys that can verify a signature / message pair.

    Args:
        |  sig (long, long): A ECDSA signature.
        |  msg (str): The message corresponding to the signature.
        |  curve (fastecdsa.curve.Curve): The curve used to sign the message.
        |  hashfunc (_hashlib.HASH): The hash function used to compress the message.

    Returns:
        (fastecdsa.point.Point, fastecdsa.point.Point): The public keys that can verify the
                                                        signature for the message.
    """

Note that P224 and secp224k1 won't work yet because I haven't implemented modular square roots for curves where the p parameter is not congruent to 3 mod 4 (the 3 mod 4 case is a fast case that's quick to implement, the general case takes a bit more work).

[SmartLayer]

Thanks! It works, and one of the two keys are correct!

I wrote a small script to test its performance:

$ python3 compare_recover_and_verify.py
Signing 2016 times:
2016 signatures, using 3.365245819091797 seconds.
Recovering 2016 times:
2016 signatures, using 25.673808813095093 seconds.
Verifying 2016 times:
2016 signatures, using 1.52587890625e-05 seconds.

[SmartLayer]

By the way, I like the way you use (long, long) for a signature. I hate other libraries taking the longs, converting to bytes to return to the library user, only for a user like me to convert it back to longs for use.

[SmartLayer]

The test script I used:

from fastecdsa import keys, curve, ecdsa
from hashlib import sha256
from time import time

curve = curve.secp256k1

# generate a private key for curve P256
priv_key = keys.gen_private_key(curve)

# get the public key corresponding to the private key we just generated
pub_key = keys.get_public_key(priv_key, curve)

def single_test():
    m = "a message to sign via ECDSA"  # some message
    r, s = ecdsa.sign(m, priv_key, curve=curve)
    keys = keys.get_public_keys_from_sig((r,s), m, curve=curve)

    print(pub_key)
    print(keys[0])
    print(keys[1])

def batch_test():

    messages = [str(i) for i in range(0, 2016)]

    print("Signing 2016 times:")
    start = time()
    signatures = [ecdsa.sign(m, priv_key, curve=curve) for m in messages]
    print("2016 signatures, using {} seconds.".format(time()-start))
    sigm =  zip(signatures, messages)

    print("Recovering 2016 times:")
    start = time()
    [keys.get_public_keys_from_sig(sig, m, curve=curve) for sig, m in sigm]
    print("2016 signatures, using {} seconds.".format(time()-start))

    start = time()
    print("Verifying 2016 times:")
    [ecdsa.verify(sig, m, pub_key, curve=curve) for sig, m in sigm]
    print("2016 signatures, using {} seconds.".format(time()-start))

batch_test()

[SmartLayer]

AntonKueltz, let me know if you accept Bitcoin / Ethereum donations. Thanks for your patch!

[AntonKueltz]

No problem.

I actually don't have wallets / addresses for any cryptocurrencies, but I appreciate the offer. :)

[AntonKueltz]

For reference, changes In release v1.6.2.