# ECDSA

## Cryptography

Elliptic curve cryptography (ECC) and digital signature algorithm (ECDSA) are more complex than RSA or ElGamal but I will try my best to hide the hairy math and the implementation details.

Here is the ELI5 version in 18 lines of SageMath / Python code. I use Sage because it provides elliptic curves as first-class citizens (FiniteField and EllipticCurve) and we can take multiplication operation for granted.

 1  p = 103
2  F = FiniteField(p)
3  E = EllipticCurve(F, [0, 7])
4  G = E([97, 10])
5  n = G.order()
6  k = randint(2, n)
7  P = k * G
8  m = 6
9  t = randint(2, n)
10  R = t * G
11  r = mod(R, n)
12  s = mod(inverse_mod(t, n) * (m + r * k), n)
13  inv_s = inverse_mod(int(s), n)
14  u = mod(m * inv_s, n)
15  v = mod(r * inv_s, n)
16  F = int(u) * G + int(v) * P
17  f = mod(F, n)
18  print "YOU ARE A CRYPTOSTAR!" if r == f else "YOU SUCK!"

YOU ARE A CRYPTOSTAR!


Besides lines #7, #10 and #16 that involves multiplication between a scalar and a point on elliptic curve, everything else is just modular arithmetic and two multiplicative inverse calculations (line #12 and #13)

Please have a look at Elliptic curves post for an introduction to elliptic curves then keep reading if you want line by line explanations and a few elliptic curve graphs.

# Elliptic curve multiplication trapdoor

First thing first, let's define the elliptic curve parameters and notations:

1  p = 103
2  F = FiniteField(p)
3  E = EllipticCurve(F, [0, 7])
4  G = E([97, 10])
5  n = G.order()


Variable notations:

• uppercase letter - elements of the elliptic curve like finite fields (F), elliptic curve itself (E) or point on elliptic curve (G)
• lowercase letter - scalar value like the secret key (k)

Domain parameters:

• p - prime number
• F - finite field
• 0,7 - coefficients for elliptic curve
• E - elliptic curve
• G - point generator
• n - order (the number of points) of the cyclic subgroup generated by G

Now, it's time to generate the secret key k and calculate the public key P using the trapdoor function called Elliptic Curve Discrete Logarithm Problem (ECDLP).

This is the bread and the butter of elliptic curve cryptography, given the generator G and public key P’ it is infeasible to calculate the secret key k, hence the trapdoor

6  k = randint(2, n)
7  P = k * G


If you are curious how elliptic curve point P looks like then it is nothing than a Cartesian (x,y) coordinate:

P

(65 : 31 : 1)


# Signature

Let's sign the message m and for this we need to generate a random integer t of order n and calculate the R point on elliptic curve.

 8  m = 6
9  t = randint(2, n)
10  R = t * G
11  r = mod(R, n)
12  s = mod(inverse_mod(t, n) * (m + r * k), n)


The signature itself has two numbers r and s that are sent to third-party for verification:

• r - the x coordinate of point R
• s - is calculated with s = (m + r*k) / t but we use multiplication with inverse instead of division.

And this is how our signature looks like:

[r, s]

[66, 51]


# Verification

Given the signature r, s above and G, P, r and n that are public information we need to calculate the equation F = u*G + v*P where u = m/s and v = r/s.

The signature is valid if R.x == F.x is true, in other words the x coordinates are the same.

13  inv_s = inverse_mod(int(s), n)
14  u = mod(m * inv_s, n)
15  v = mod(r * inv_s, n)
16  F = int(u) * G + int(v) * P
17  f = mod(F, n)
18  print "YOU ARE A CRYPTOSTAR!" if r == f else "YOU SUCK!"

YOU ARE A CRYPTOSTAR!


# Intuition

Remember that uppercase letters are points on elliptic curve, lowercase are scalars:

1  R == u*G + v*P
2  R == u*G + v*k*P
3  R == m/s * G + r/s * k*G
4  R == m/s * G + r*k/s * G
5  R == (m + r*k)/s * G
6  R == (m + r*k)/((m + r*k)/t) * G


As always we will do the math backwards:

1. start with the equation of signature verification and substitute public key P
2. substitute u and v
3. multiplication is commutative and we can put r and k together
4. extract G and s as factors
5. substitute s
6. after reduction we are left with t*G

And the intuition is valid if the x coordinates on both sides of the equation are equal.

print "MAGIC" if R == (int((m + r*k)*t/(m + r*k)) * G) else "ERROR"

MAGIC
`