# "ECDSA calculations"

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.

## 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)[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.

## Comments

Comments powered by Disqus