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...
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
1 and u
2 because we need to mod the integers by n along the way.
w = s
-1 mod n
u
1 = zw mod n
u
2 = rw mod n
Now we calculate the curve point C
C = u
1*G + u
2*Q
The signature is valid if r = x value of C modded by n, and invalid otherwise.
The reason why C = u
1*G + u
2*Q proves this is:
C = u
1*G + u
2*Q
Since Q = d*G we can replace:
C = u
1*G + u
2*d*G
Grouping like terms:
C = (u
1 + u
2*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.
