2
$\begingroup$

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

To sign a transaction (message) in the 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 ($ \rightarrow \operatorname{hash}(M) $) without check; obviously that is not possible, there is roughly a 50% chance that a random 256 bit string doesn't correspond to a point of the curve. I can't find out how/if the ECDSA library checks if $\operatorname{hash}(M)$ is on the curve or not and especially what it does if the $\operatorname{hash}(M)$ is not on the curve.

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

$\endgroup$
5
$\begingroup$

In ECDSA, the message is never encoded as a point in the elliptic curve. Signing in ECDSA loosely works like this:

$$ \begin{align*} k &= \text{random}(0, n) \\ (x, \_) &= k \cdot G \\ r &= x \bmod n \\ s &= k^{-1}(H(m) + r \alpha) \bmod n \end{align*} $$

$r$ and $s$ are the signature, and as you can see $H(m)$ is only ever used as an element of the integers modulo $n$, the order of the generator point $G$ (and $\alpha$ is the private key). Therefore, $H(m)$ is never treated as a point, and thus never needs to be encoded into one.

$\endgroup$
  • $\begingroup$ You're right! I thought that "r" was a curve point, but it isn't! Thank you very much! $\endgroup$ – arulbero May 8 '15 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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