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()

img

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()

img

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:

  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[0] == (int((m + r*k)*t/(m + r*k)) * G)[0] else "ERROR"

MAGIC