Explaining ECDSA calculations
In this post i assume you know what ECDSA is, and how modular arithmetic works. It also explained why you must never re-use the signing secret.
k = the signing secret G = the generator point x = the private key Y = the public key point m = the message r,s = the signature R = the point corresponding to the r part of the signature n = the curve group order p = the parameter field order
x,y = coordinates a,b = some integer P,Q = some point sign = -1 or +1
x is sometimes a coordinate and sometimes the private key, i think the context will
make it clear which.
y^2 = x^3 + a * x + b ( mod p )
Note that in the rest of the text the a and b don't refer to the curve parameters.
Operations on numbers
+,-,* all modulo `p` a / b `a * modularinverse(b,p)` ^ exponentiation sqrt(a) calculate the square root modulo p
Operations on curve points
P + Q : point addition P * a : scalar multiplication P / a : scalar division = P * modularinverse(a, n) [P] : take the x coordinate of a point <x,sign>: decompress: calculate y coordinate with the given sign (P+Q)*a = P*a+Q*a P*(a+b) = P*a + P*b
Note that the operation
P/Q is very difficult to calculate, this is what the security of ECDSA is based on.
the public key
Y = G * x
point decompression is the operation of calculating the y coordinate given the x and a sign:
y = sign * sqrt(x^3 + a * x + b)
(r,s) = ( [G*k], (m+x*r) / k ) ( mod n )
verify that: R*s == G*m + Y*r
Note that most implementations only verify the x coordinate of R, so in reality the verification
would also appear valid when
Find the public key given a message and signature, and also the private key, given the signing secret
R = <r, sign> Y = (R*s-G*m)/r x = (sign * s*k-m)/r
Note that this can give 2 possible solutions, depending on the sign of R.
Find the public key given 2 signatures for the same message
Y = (R1*s1-R2*s2)/(r1-r2)
Find the private key given 2 signatures with identical signing secret:
k = (m1-m2)/(s1-s2) x = (s1*k-m1)/r
This is the attack on ECDSA because of which you should never reuse the
Similarly, when you know that an implementation used a bad PRNG for generating
you can find other public keys from signatures generated using this same
When implementing ECDSA, read (rfc6979)[https://tools.ietf.org/html/rfc6979] for a solution: basically you derive k from a hash of the message and the private key.
Things to note
Private key x and private key (x+n) both result in the same public key
I can create a signature (r,s) for a message m, using private key x.
then can calculate a privatekey
x' = (-s*k-m)/r
and a publickey Y' using
Y' = (-R*s-G*m)/r
which also verifies that signature.