1

When verifying the signature in bitcoin, we calculate S^(-1) * hash(m) * G + S^(-1) * R * pub_key and verify that this is equal to the temporary public key. Given the same logic, why can't we use it to calculate private key from public key?

for example: pub_key = priv_key * G. Modify it to: priv_key^(-1) = pub_key^(-1)*G and then take get the priv_key by taking inverse of LHS.

I just want to understand the math that makes us calculate S^(-1) in the first case, but does not allow us to do it in the second case.

Improve this question

1 Answer 1

Reset to default
3

The semantics of multiplication are different in your two equations.

As for the first equation. The s-part of a signature is an element in a group (represented by a number) so the inverse exists and is easy to compute (or even well known)

In the second case you take the numerical value of the private key and compute the multiple of this with a base point. With that notation the "inverse" becomes equivalent to finding the discrete logarithm in this additive group. In ecc it is not known how to compute the discrete log efficiently

I guess this answer is somewhat frustrating. I recommend learning about Groupe theory to understand the differences in notation.

Improve this answer
5
  • Thanks for the answer. I was hoping that was the case, but just wanted to confirm. But say given a signature, how do you calculate the inverse of it?
    – Ugam Kamat
    Mar 7, 2019 at 14:52
  • 3
    A signature doesn't really have an inverse. It consists of two distinct elements, r and s. r is a point on the curve so finding it's inverse would mean solving the elliptic curve discrete log problem. However s is just an integer in the group. Finding the inverse of this is easy, as stated in this answer.
    – Andrew Chow ♦
    Mar 7, 2019 at 18:07
  • Thanks Andrew I fixed my answer. Since the question was about S^(-1) I was sloppy naming that the signature. I know you know that but for the other readers I want to emphasize that r and s are both elements of groups. Just very different ones. While s comes from a prime field r comes from the elliptic curve.
    – Rene Pickhardt
    Mar 7, 2019 at 20:19
  • 1
    That's a good point. It was my bad to call the signature as S. I'll update the question to reflect S component of the signature. Thanks guys. Looks like I have some reading I need to do.
    – Ugam Kamat
    Mar 7, 2019 at 20:38
  • Note we write points in uppercase (G, Q) but numbers (or for F_2^m field elements) in lowercase (a, b, n, h, d, k, r, s) to help keep this distinction clear. @AndrewChow: in ECDSA r is actually the x-coordinate of a point (kG) mod n. But a given r corresponds to usually 2 and very rarely 4 points, and yes inverting those is equivalent to DLP.
    – dave_thompson_085
    Mar 8, 2019 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.