Public Key Recovery Operation

[gianlucafrei]

Given a signature and the corresponding message it's possible to compute multiple public keys for which the signature is valid.

I would like to add a method to the signature class which does this according to http://www.secg.org/sec1-v2.pdf chapter 4.1.6.

[tomato42]

sounds good

a new static or class method in ecdsa.keys.VerifyingKey would likely be a good place to have it

post a design here or prepare a proof-of-concept PR if you want to discuss it further

[gianlucafrei]

Here is a prototype of the maths.
I tested the code below with some examples.

class Signature(object):
  """ECDSA signature.
  """
  def __init__(self, r, s):
    self.r = r
    self.s = s

  def recover_public_keys(self, hash, generator):
    """Returns two public keys for which the signature is valid
    hash is signed hash
    generator is the used generator of the signature
    """
    curve = generator.curve()
    n = generator.order()
    r = self.r
    s = self.s
    e = hash
    x = r

    # Compute the curve point with x as x-coordinate
    alpha = ((x * x * x) + (curve.a() * x) + curve.b()) % curve.p()
    beta = numbertheory.square_root_mod_prime(alpha, curve.p())
    y = beta if beta % 2 == 0 else curve.p() - beta

    # Compute the public key
    R1 = ellipticcurve.Point(curve, x, y, n)
    Q1 = numbertheory.inverse_mod(r, n) * (s * R1 + (-e % n) * generator)
    Pk1 = Public_key(generator, Q1)

    # And the second solution
    R2 = ellipticcurve.Point(curve, x, -y, n)
    Q2 = numbertheory.inverse_mod(r, n) * (s * R2 + (-e % n) * generator)
    Pk2 = Public_key(generator, Q2)

    return [Pk1, Pk2]

[tomato42]

hash is a builtin method, so some other name would be better

(x * x * x)
using pow(x, 3, curve.p()) should yield faster code

looks good otherwise, please add test cases and propose a PR

[gianlucafrei]

hash is a builtin method, so some other name would be better

The sign and verify methods also have a parameter called hash, so I propose to not change it for consistency.