Explaining ECDSA calculations

In this post I assume you know what ECDSA is, and how modular arithmetic works. I will also explained why you must never re-use the signing secret.

Notation

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

variables

x,y = coordinates
a,b = some integer
P,Q = some point
sign = -1 or +1

Note that x is sometimes a coordinate and sometimes the private key, I think the context will make it clear which.

The Curve

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.

Calculations

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)

Signing

(r,s) = ( [G*k],  (m+x*r) / k )     ( mod n )

Verification

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 -R*s==G*m+Y*r

Find pubkey

Find the public key given a message and signature, and also the private key, given the signing secret k:

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 privkey

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 k value.

Similarly, when you know that an implementation used a bad PRNG for generating k, you can find other public keys from signatures generated using this same k value.

When implementing ECDSA, read 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.