Digital signature misunderstanding

[BlackHatCoiner]

Today I watched this video called Bitcoin 101 - Elliptic Curve Cryptography - Part 5 - The Magic of Signing & Verifying that explains the magic of signing & verifying using elliptic curve cryptography. I'm focusing on signing at the moment. Once I'm okay with this I'll make my question on verifying too. It says that, besides your private key and your message's hash, you also need a random number.

(x1, y1) = RandNum * GenPoint
r = x1(mod n)
s = (HashOfMsg + r * PrivKey) * RandNum^-1(mod n)

The signature is (r, s)

So here's my question.

How can it be random? Once I try to sign a message on electrum (for example), I always get the same signature using the same message. Since we deal with an integer that is constantly random, I should be getting different signatures every time I sign the same message.

[NotATether]

The randomness comes from RandNum in this expression:

(x1, y1) = RandNum * GenPoint

The random number is selected between 1 and the order of the generator point - 1. It's used in such a way that you don't need to know the random number's value when verifying the message.

Wikipedia has this for the last stage of the signing algorithm:

Select a cryptographically secure random integer k from [1,n-1].
Calculate the curve point (x1 , y1) = k × G
Calculate r = x₁ mod n. If r = 0, go back to step 3.
Calculate s = k⁻¹(z + r d_A) mod n. If s=0, go back to step 3.
The signature is the pair (r, s). (And (r , −s mod n) is also a valid signature.)

To verify the signature:

Calculate u₁ = z s⁻¹ mod n and u₂ = r s⁻¹ mod n.
Calculate the curve point (x₁ , y₁) = u₁ × G + u₂ × Q A . If (x₁ , y₁) = O then the signature is invalid.
The signature is valid if r ≡ x₁ (mod n), invalid otherwise.

z is the left bits of a hash of the message.

k⁻¹(z + r d_A) mod n is not a reversible operation, because of the mod. That's why the verification algorithm can't rely on the value of k and it has to take a detour by calculating s⁻¹ mod n using the r and z values.

[ranochigo]

So here's my question.

How can it be random? Once I try to sign a message on electrum (for example), I always get the same signature using the same message. Since we deal with an integer that is constantly random, I should be getting different signatures every time I sign the same message.

That used to be the case and you'll get a different signature for every try.

However, due to the concerns arising from the system having a flawed RNG and generating insecure signatures, we've started implementing RFC6979[1] in our wallets. Having a deterministic k and it's nonce that is obtained from a function of both the private key and the message and thus having a unique nonce that is never reused. This also entails that for a specific message signed with a specific private key and a message, the signature is always the same.

In this case, the nonce doesn't have to be completely random, just to the extent that each of the signature has to be unique. There were plenty of incidents involving reusing nonce, especially with Blockchain.com(Blockchain.info in the past).

[1] https://tools.ietf.org/html/rfc6979

[pooya87]

It is basically the same concept as BIP32, the underlying cryptography is similar too. You already have a random entropy and you derive another random entropy from that "master key". In your HD wallet the "master key" is the initial entropy you use and in your ECDSA the master key is your private key. Both use HMAC-SHA.

That used to be the case and you'll get a different signature for every try.

This should not happen, if the message or the transaction remain the same the signature must be the same too.

[ranochigo]

This should not happen, if the message or the transaction remain the same the signature must be the same too.

Wasn't that the case after most wallets implemented the RFC? I'm pretty sure that was the case in earlier versions of Bitcoin Core, before they implemented the deterministic nonce?

[pooya87]

Wasn't that the case after most wallets implemented the RFC? I'm pretty sure that was the case in earlier versions of Bitcoin Core, before they implemented the deterministic nonce?

I'm assuming by "that" in your first comment you are referring to you "I always get the same signature using the same message". Now I'm thinking I may have been wrong.

In early versions the ephemeral key was chosen randomly in every client and they were generating a different signature on each try, then as the risks became apparent and some issues happened it was replaced by RFC6979. Nowadays you get the same signature as long as you don't change the input in all popular wallets.