<blockquote>
  <p>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</p>
</blockquote>

<p>Perhaps you're thinking of <a href="https://en.wikipedia.org/wiki/ElGamal_encryption" rel="nofollow">ElGamal <em>encryption</em></a>, whereby you <em>do</em> need to select a point on the curve which represents your plaintext.</p>

<p>However for <em>signing</em>, Bitcoin uses <a href="https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Signature_generation_algorithm" rel="nofollow">ECDSA</a>, and this has no such requirement.</p>

<p>If you're interested, the code which implements ECDSA signing is in secp256k1_ecdsa_sig_sign(). For example, <a href="https://github.com/bitcoin/bitcoin/blob/fec5c0ea05ec22e12313ce3ec575786f5c52039f/src/secp256k1/src/ecdsa_impl.h#L244-L247" rel="nofollow">this is the code</a> which implements step 6 from the Wikipedia link above.</p>

CC BY-SA 3.0
2015-05-07T17:49:37.867Z
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
CC BY-SA 3.0
2015-05-07T17:55:24.857Z
@arulbero Why does z need to be a curve point? It's added to rd<sub>a</sub>, which is a scalar.
Nick ODell
CC BY-SA 3.0
2015-05-07T18:25:23.380Z
You're right!  I thought that "r" was a curve point, but it isn't!  Thank you very much!
arulbero
CC BY-SA 3.0
2015-05-07T17:36:40.610Z
2015-05-07T17:36:40.610Z
Christopher Gurnee
<p>Where should I look at in <a href="https://github.com/bitcoin/bitcoin/tree/master/src/secp256k1/src" rel="nofollow noreferrer">Bitcoin Core source code</a> to figure out how the signature process trasform a message in a curve point?</p>

<p>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 <a href="http://math.boisestate.edu/~liljanab/MATH508/KoblitzEmbedding.pdf" rel="nofollow noreferrer">Koblitz's paper</a>. There are three encoding schemes. I read <a href="https://crypto.stackexchange.com/questions/24240/koblitz-encoding-a-message-to-a-point-what-is-the-associated-auxiliary-base-pa">this question</a> too.</p>

<p>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. </p>

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

<p>Thanks and sorry for my English.</p>

<p>EDIT:</p>

<p>Bitcoin: Signature generation (ECDSA)</p>

<p>Given a message m to be signed and the private key d,</p>

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

<p><strong>Why SHA1(m) should be a curve point?</strong> There is only a 50% chance. </p>

CC BY-SA 3.0
2015-05-07T17:13:26.797Z
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
CC BY-SA 3.0
2015-05-07T17:56:44.443Z
arulbero, are you having trouble pasting something in?
Nick ODell
<signature><ecdsa><encoding>
Signature: encoding a message - transaction to a point of curve y^2=x^3+7 and Bitcoin Core
arulbero
# Signature: encoding a message - transaction to a point of curve y^2=x^3+7 and Bitcoin Core

(Asked by: username_0 on 2015-05-07)

Where should I look at in [Bitcoin Core source code](https://github.com/bitcoin/bitcoin/tree/master/src/secp256k1/src) 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](http://math.boisestate.edu/~liljanab/MATH508/KoblitzEmbedding.pdf). There are three encoding schemes. I read [this question](https://crypto.stackexchange.com/questions/24240/koblitz-encoding-a-message-to-a-point-what-is-the-associated-auxiliary-base-pa) 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.

**Tags:** signature, ecdsa, encoding

> **Comments:**
> **username_1**: I assume you're talking about section 3. These look like ways of encrypting something using ECDSA, not ways of signing a message.  
> **username_1**: username_0, are you having trouble pasting something in?  

---

## 1 answers

### Answer by username_2 on 2015-05-07. Score: 2 | Accepted answer

> 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*](https://en.wikipedia.org/wiki/ElGamal_encryption), whereby you *do* need to select a point on the curve which represents your plaintext.

However for *signing*, Bitcoin uses [ECDSA](https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Signature_generation_algorithm), 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](https://github.com/bitcoin/bitcoin/blob/fec5c0ea05ec22e12313ce3ec575786f5c52039f/src/secp256k1/src/ecdsa_impl.h#L244-L247) which implements step 6 from the Wikipedia link above.

> **Comments:**
> **username_0**: 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.  
> **username_1**: @username_0 Why does z need to be a curve point? It's added to rd<sub>a</sub>, which is a scalar.  
> **username_0**: You're right!  I thought that "r" was a curve point, but it isn't!  Thank you very much!  

---

