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

RHavar

legendary

Activity: 2557

Merit: 1886

Quote from: elda34b on January 31, 2019, 12:39:51 AM

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)

100bitcoin

sr. member

Activity: 858

Merit: 423

Quote from: elda34b on February 01, 2019, 02:49:04 AM

Quote from: 100bitcoin on January 31, 2019, 07:41:27 AM

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.

elda34b

sr. member

Activity: 910

Merit: 351

Quote from: pooya87 on January 31, 2019, 01:00:48 AM

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://bitcointalksearch.org/topic/m.48670739

Thanks, will study it further later.

Quote from: 100bitcoin on January 31, 2019, 07:41:27 AM

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?

HeRetiK

legendary

Activity: 2912

Merit: 2066

Cashback 15%

Quote from: KingZee on January 31, 2019, 01:13:45 AM

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.

100bitcoin

sr. member

Activity: 858

Merit: 423

Quote from: HCP on January 30, 2019, 05:10:25 PM

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

Quote from: elda34b on January 31, 2019, 12:39:51 AM

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/

achow101

staff

Activity: 3374

Merit: 6530

Just writing some code

Quote from: KingZee on January 31, 2019, 01:13:45 AM

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

KingZee

sr. member

Activity: 910

Merit: 452

Check your coin privilege

Quote from: achow101 on January 30, 2019, 05:17:43 PM

Quote from: 100bitcoin on January 30, 2019, 04:41:46 PM

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?

pooya87

legendary

Activity: 3402

Merit: 10424

Quote from: elda34b on January 31, 2019, 12:39:51 AM

Quote from: achow101 on January 30, 2019, 05:17:43 PM

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://bitcointalksearch.org/topic/m.48670739

elda34b

sr. member

Activity: 910

Merit: 351

Quote from: achow101 on January 30, 2019, 05:17:43 PM

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.

achow101

staff

Activity: 3374

Merit: 6530

Just writing some code

Quote from: 100bitcoin on January 30, 2019, 04:41:46 PM

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.

HCP

legendary

Activity: 2086

Merit: 4314

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

100bitcoin

sr. member

Activity: 858

Merit: 423

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?

Topic: Why signing same message with same private key is yielding different signatures? (Read 386 times)