2

Where should I look at in Bitcoin Core source code to figure out how the signature process trasform a message in a curve point?

To sign a transaction (message) in Bitcoin system, you need to encode the message to a point of the curve y^2=x^3+7. I read this Koblitz's paper. There are three encoding schemes. I read this question too.

If I look at in Bitcoin Core source code I can't see any of these encoding schemes, it seems to me that message M is directly encoded in a point m=hash(M) without check; obviously that is not possible, there is roughly a 50% chance that a random 256 bit string don't correspond to a point of the curve. I can't find out how/if the ECDSA library checks if hash(M) is on the curve or not and especially what it does if the hash(M) is not on the curve.

What encoding scheme does Bitcoin-ECDSA implement and where is it in the source code?

Thanks and sorry for my English.

EDIT:

Bitcoin: Signature generation (ECDSA)

Given a message m to be signed and the private key d,

  1. Choose a random integer k in [1,n-1].
  2. Compute (x1,y1)=kP, convert x1 into integer and r = x1 mod n.(Return to step1 if r = 0)
  3. Computes=(k^-1)*(SHA1(m)+ dr). (Return to step 1 if s= 0)
  4. Signature is (r, s) pair.

Why SHA1(m) should be a curve point? There is only a 50% chance.

2
  • I assume you're talking about section 3. These look like ways of encrypting something using ECDSA, not ways of signing a message.
    – Nick ODell
    May 7, 2015 at 17:13
  • arulbero, are you having trouble pasting something in?
    – Nick ODell
    May 7, 2015 at 17:56

1 Answer 1

2

To sign a transaction (message) in Bitcoin system, you need to encode the message to a point of the curve y^2=x^3+7

Perhaps you're thinking of ElGamal encryption, whereby you do need to select a point on the curve which represents your plaintext.

However for signing, Bitcoin uses ECDSA, and this has no such requirement.

If you're interested, the code which implements ECDSA signing is in secp256k1_ecdsa_sig_sign(). For example, this is the code which implements step 6 from the Wikipedia link above.

3
  • Why "Bitcoin uses ECDSA and this has no such requirement" ? In the Wikipedia link, at step 6 you use "z = HASH(m)", and then z must be a curve point.
    – arulbero
    May 7, 2015 at 17:49
  • 2
    @arulbero Why does z need to be a curve point? It's added to rd<sub>a</sub>, which is a scalar.
    – Nick ODell
    May 7, 2015 at 17:55
  • You're right! I thought that "r" was a curve point, but it isn't! Thank you very much!
    – arulbero
    May 7, 2015 at 18:25

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.