Bitcoin Forum

How does a private key prove it owns the private key for a public key?

Pseudocode or simple real code... I just can't seem to google it...

It's called a Trapdoor Function: http://en.wikipedia.org/wiki/Trapdoor_function

Bitcoin uses ECDSA: https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm

It's specific to CRYPTOGRAPHY, not just Bitcoin...

Proving ownership of a private key is typically done by signing a message with that private key. Bitcoin uses ECDSA (Elliptic Curve Digital Signature Algorithm) for this. For starters, you can have a look at http://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm which outlines the algorithm, or simply dive headfirst into the Bitcoin Core code (on GitHub)

Yeah, so much I could google myself, but how it is done in simple pseudocode or just textbook explanation would be good to have... hm, actually think I'm starting to get it... thanks to the trapdoor wiki... How can A prove to B that he has the private key of his public key without giving away his private key. Hm, I still don't get it...

Something like this? (I'm not positive this is what you are asking):
https://github.com/nanotube/supybot-bitcoin-marketmonitor/blob/master/GPG/local/bitcoinsig.py
or
https://github.com/bitcoin/bitcoin/blob/9af3c3c8249785a0106c14bce1cb72b3afc536e8/src/bitcoinrpc.cpp#L661

or (this is how to do it with bitcoin-cli):
https://bitcoin.org/en/developer-reference#signmessage


They aren't just a few lines because it is complicated.  Did you want less detail?

A 'message' (usually a hash) is signed with the private key - this gives you the ECDSA signature.

The message, ECDSA signature and public key are published, this is enough to verify that the person who created the signature has the private key.

Ok, thanks for all the help, I'm getting there, didn't get you had to have 3 parts...

Now I just need to understand this source:

http://grepcode.com/file/repo1.maven.org/maven2/com.madgag/scprov-jdk15/1.46.99.3-UNOFFICIAL-ROBERTO-RELEASE/org/spongycastle/crypto/signers/ECDSASigner.java

I always found the paint analogy helpful for explaining private key public key.

1.  Bob and Alice agree on a base (Blue), Eve eves drops and knows it.
2.  Both Alice and Bob choose a private key (Red and Green)
3.  The mix with the base, to form a public key (Purple and another green).  Its a good example of a one way function, mixing is easy,
trying to "unmix" is hard.

4.  They swap public keys (Purple and another green) and Eve intercepts these.
5.  Alice and Bob now mix their private keys (Red and Blue), which is a blend of all 3 colours and see they are the same colour. However, Eve cannot compute the final colour.

To answer your question, the final colour would be different, thus proving by contradiction.

http://aleph.straylight.co.uk/cryptcol.png

If you feel confused by ECDSA, it's worth keeping in mind that it had to avoid Schnorr's patent.

No need for pseudo code, the actual formulas only require simple algebra to show.

A signature is made using the private key 'd' and a unique private number generated just for the signature which is called 'k'.
These are used to generate 2 values, r and s. A signature is simply an r value and an s value, and it can be combined with the PUBLIC key to verify the private key was actually used to generate r and s.
(G = generator point of the curve (constant);
 n = order of the curve;
 z = digest of the message (aka the message being signed's hash turned into an integer))
 [All capitol letters represent points on the Elliptic curve and lower case letters are big integers]

R = k*G
r = x value of point R modded by n
    (now we have r)

s = k^-1(z + dr) mod n


So now we have r and s.

Now given the public key corresponding to d which we will say is Q.
We will calculate intemediate values w, u₁ and u₂ because we need to mod the integers by n along the way.

w = s^-1 mod n
u₁ = zw mod n
u₂ = rw mod n

Now we calculate the curve point C

C = u₁*G + u₂*Q
The signature is valid if r = x value of C modded by n, and invalid otherwise.

The reason why C = u₁*G + u₂*Q proves this is:

C = u₁*G + u₂*Q

Since Q = d*G we can replace:

C = u₁*G + u₂*d*G

Grouping like terms:

C = (u₁ + u₂*d)*G

Expand the u values to their components that we calculated earlier:

C = (z*s^-1 + r*d*s^-1)*G

grouping the s^-1 and remove from the parenthesis:

C = (z + rd)*s^-1*G

Insert the definition of s (remembering it is to the power of -1:

C = (z + rd)*(z + rd)^-1*(k^-1)^-1*G

(z + rd) crosses out and k flips to power of 1:

C = k*G

Since R also is k*G, you can be certain that if the C point has the same x value as the R point, that the private key was used to generate that s value.


Simple algebra, crossing like terms, grouping things... only tricky parts are when you ACTUALLY TRY TO COMPUTE IT, and include modular arithmetic and EC math.

But tbh as long as you understand that EC addition and multiplication are distributive, so they can be grouped like normal variables and you understand that modular arithmetic is a one way function, then it should be intuitive to anyone who understands algebra.

That is really nice - do you have one to explain signature verification as well?

Although my math isn't up to par from this pictorial my guess (from just looking at this visually) is that a signature would be the combination of a published private key and the public key of the secret private key. Is that at all close?

The picture explains Diffie Hellman key exchange but it doesn't fit the signature algorithm well. Because you can 'unmix' the private color but not after you mix to the base color. Nonetheless, very roughly, the idea is for Alice to do the following:
- she picks a random secret color.
- she adds the base color to it to make it the public color.
- Then she gives out the public color but she doesn't give out the secret color.
- Instead, she adjusts it with a combination of her private key and message content and sends out the result.

Bob performs the adjustments in reverse and verifies that he gets the public color. The main trick is that he can do these adjustments using the public color so Alice never revealed her secret.

I wrote a longer explanation here: https://gist.github.com/hhanh00/b9a3afc0bd17027b45ab
It's about Schnorr signatures though. ECDSA is similar but more complicated.