Why signing same message with same private key is yielding different signatures?

[Silas]

Private Key (WIF): Kyi31gE1dprUuRANxxa8CVBFnDjcUQAsMo5U7ZA8JHCgpsphuWi4

Message to Sign: Sample message to sign

Signature 1: HxQn9USB+UEmGyaWz9MAboy3AswGiD6grQ/h1jUyB7IEBG3VbIKwevFu8keOTkvCKOpNbe24PJyuRqfbNqLtmNM=

Signature 2: ILAEHEorCkMT7jukaNHE1HtP+deUP4LXf3KqE7lfOcRHOV820yuK3mzj0PoZubwnIiOisu0mHmhggYiy4k5im+s=

Signature 3: H7PZ1HDZrd6XULmCyT2DriJdpHX9ZnmE+UWc5i0n6kRYf+jJaDQjQqnqBPqLN1LzpSrb/0Qw5AdQkUObzl2kdKg=

Signature 4: IIiltHihG3A92WX4CpE2g3PCKQVa7zz7fJZdBzPT27bOSQ7E8sLQFhkIvopAteNTOUxZakweJ73brFz 0dNuX3a0=

Signature 5: H6d0jouZvZ36onGDn1Mpm9wmdnbS2I54SCksni1VPnDaKN+y38BkMTsCgR8lSjrUfmne+vOqNaIZPcNGycfo2Do=

How many such combinations are possible?

 

[Jesus]

What method/wallet are you using for creating your signed message?

 

[Kaiden]

How many such combinations are possible?

Infinitely many.

The signature algorithm used in Bitcoin is called ECDSA. One part of creating a signature with ECDSA is generating a random number (known as a nonce) and combining it with the private key. Every time you make a signature, you generate a new random number. This nonce is very important and cannot be known to anyone else or be used in different signatures. Otherwise the private key can be derived from the signature. This is what you are observing here.

However some software will, instead generate the random number by hashing the private key and the message being signed. This will make a number that is random enough, secret (because the private key is also secret), and extremely unlikely to be seen in different signatures. This will result in the same signature when you signing the same message multiple times.

 

[Maxwell]

However some software will, instead generate the random number by hashing the private key and the message being signed. This will make a number that is random enough, secret (because the private key is also secret), and extremely unlikely to be seen in different signatures. This will result in the same signature when you signing the same message multiple times.

CMIIW, does this mean it's better to use a wallet that can produce the same signature for the same message?
I'm also curious what wallet has been used by OP, would be great if he can answer it.

 

[Juan]

However some software will, instead generate the random number by hashing the private key and the message being signed. This will make a number that is random enough, secret (because the private key is also secret), and extremely unlikely to be seen in different signatures. This will result in the same signature when you signing the same message multiple times.

CMIIW, does this mean it's better to use a wallet that can produce the same signature for the same message?
I'm also curious what wallet has been used by OP, would be great if he can answer it.

a wallet that is implementing RFC6979 (which is what people are talking about here, a deterministic k) is slightly better but i don't think we can really call anyone that doesn't "unsafe" or "less good" than those that do implement it.
read this reply for a better understanding of why it is better to have it than not: https://bitcointalk.org/index.php?topic=5084787.msg48670739#msg48670739

 

[Kingston]

How many such combinations are possible?

Infinitely many.

The signature algorithm used in Bitcoin is called ECDSA. One part of creating a signature with ECDSA is generating a random number (known as a nonce) and combining it with the private key. Every time you make a signature, you generate a new random number. This nonce is very important and cannot be known to anyone else or be used in different signatures. Otherwise the private key can be derived from the signature. This is what you are observing here.

However some software will, instead generate the random number by hashing the private key and the message being signed. This will make a number that is random enough, secret (because the private key is also secret), and extremely unlikely to be seen in different signatures. This will result in the same signature when you signing the same message multiple times.

That's really interesting actually. But for OP's case, if the random number wasn't generated using the message itself (which I assume is the most common way nowadays as each unique message will have its own number), how do verification algorithms verify all the signatures above?

 

[Ashton]

That's really interesting actually. But for OP's case, if the random number wasn't generated using the message itself (which I assume is the most common way nowadays as each unique message will have its own number), how do verification algorithms verify all the signatures above?

If you are interested in seeing how ECDSA works and understand the equations, have a read of the Wikipedia page

 

[Rowan]

What method/wallet are you using for creating your signed message?

I'm also curious what wallet has been used by OP, would be great if he can answer it.

Code: https://github.com/OrdinaryDude/offline-bitcoin-signer

Implementation: https://ordinarydude.github.io/offline-bitcoin-signer/

 

[Ivan]

That's really interesting actually. But for OP's case, if the random number wasn't generated using the message itself (which I assume is the most common way nowadays as each unique message will have its own number), how do verification algorithms verify all the signatures above?

In short, you don't need to know k to verify the signature. I personally find old school DSA easier to wrap my head around, so maybe this will point you in the right direction:
https://en.wikipedia.org/wiki/Digital_Signature_Algorithm

While ECDSA works slightly different, the problem with k is essentially the same.

 

[Diego]

a wallet that is implementing RFC6979 (which is what people are talking about here, a deterministic k) is slightly better but i don't think we can really call anyone that doesn't "unsafe" or "less good" than those that do implement it.
read this reply for a better understanding of why it is better to have it than not: https://bitcointalk.org/index.php?topic=5084787.msg48670739#msg48670739

Thanks, will study it further later.

Code: https://github.com/OrdinaryDude/offline-bitcoin-signer

Implementation: https://ordinarydude.github.io/offline-bitcoin-signer/

My first time knowing about this, and it seems very old. Hmm. Why did you choose to use this btw? Why not use popular wallet like Core/Electrum?

 

[Camden]

Code: https://github.com/OrdinaryDude/offline-bitcoin-signer

Implementation: https://ordinarydude.github.io/offline-bitcoin-signer/

My first time knowing about this, and it seems very old. Hmm. Why did you choose to use this btw? Why not use popular wallet like Core/Electrum?

I prefer JS based lightweight implementations. For example, for address generation, I use BitAddress.org source code, for transaction, I use Coinb.in source code. And regarding being old, I dont think cryptographic output should change, just because its old.

 

[Calvin]

CMIIW, does this mean it's better to use a wallet that can produce the same signature for the same message?

I would generally prefer wallets that do that. If a wallet screws up the picking of k (most classically: using the same k, for different messages) it leaks your private key. A wallet that uses a deterministic k is far less likely to screw it up (as it's so much easier to test, and has no dependency on a good random-number-generator).

What I do like about random k's though, is that by generating a different signature every time -- it helps developers realize there's no canonical signature. (although using a deterministic k does generate a canonical signature, it's not possible for someone to verify that it is in fact the canonical one, without leaking the private key)