# Overview

```
"If you can't explain it simply, you don't understand it well enough"
Albert Einstein
```

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[0], 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[0], 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 keep reading if you want line by line explanations and a few elliptic curve graphs.

# Basics

- What the heck is an elliptic curve?
- It is just a simple equation of this form `y2 = x3 + ax + b`.
- Why it is so special?
- Because it has one interesting operation: addition. Adding two points on the curve will result a third point also on the curve (aka closure). Multiplication is particular case of addition, adding the same point to itself `k` times.
- And how does it looks like?
- Well, I am afraid you won’t like the graph because elliptic curves defined over finite fields get cut off and are not intelligible to humans eye

But here it is anyway: `a = 0; b = 7` and prime number is `103`.

```
E = EllipticCurve(FiniteField(103), [0, 7])
E.plot()
```

Not pretty huh? lets define the same elliptic curve over real numbers and the graph starts to make little sense.

```
E = EllipticCurve([0, 7])
E.plot()
```

# 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[0], 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[0], 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:

- start with the equation of signature verification and substitute public key `P`
- substitute `u` and `v`
- multiplication is commutative and we can put `r` and `k` together
- extract `G` and `s` as factors
- substitute `s`
- 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[0] == (int((m + r*k)*t/(m + r*k)) * G)[0] else "ERROR"
MAGIC
```