Aug 16, 2019

T H I C C_C U R V E S pt. 1

I’m back with small series where I explain the math behind elliptical curve cryptography and write my own implementation in python. As usual this is nothing new or super exciting.

I’ve recently ordered some Arduino boards and CAN-buses, so soon I will be taking a deep dive into CAN and car hacking! Making myself ready for our big move to Gothenburg :)

What’s an Elliptical curve then?

From Wikipedia -

In mathematics, an elliptic curve is a plane algebraic curve defined by an equation of the form

y^2=x^3+ax+b

which is non-singular; that is, the curve has no cusps or self-intersections.

Which means that it is non-singular, i.e it has no singular points on the curve. As Wikipedia says - it has no intersection nor cusps.

A cusp is a point where both the tangent of x and y is zero. You can also say that you can decide two tangents in a singular point, where in a non-singular you can only decide one.

Quick maths

Take P(x1,y1) and Q(x2,y2) where the intersection is non-vertical, the line which intersects P and Q is

(kx+m)^2 = x^3+ax+b

Which also is a point on the curve.

BUt WhAt iF tHE iNteRsECtiOn iS VerTIcAl

That can happen. Therefore we introduce a point to represent infinity (Since the third point on the line doesn’t exist). This will be proven to come in handy later :)

Group theory as fields

So, we actually do implement Elliptical curves as fields. This requires some rules -

  • Associative: (ab)*c = a*(bc)
  • Identity element: There exists an element, e, which a*e=a
  • Inverse: a*a^-1=e

(This is a really basic explaination)

We already defined an identify element (the one to represent infinity, 0). Nice!

So for our nice elliptical curve, the rules follows as such -

  • (P+Q)+R = P+(Q+R)
  • P+0 = 0
  • P+P’ = 0
  • P'+P’ = P

Addition of two points on the curve

So the proof for the addition algorithm is a bit tricky (Read: I’m to lazy :D) But it looks like this -

(P+Q) % p

  1. If P=0 (i.e P+0) return Q
  2. If Q=0 (i.e 0+Q) return P
  3. (remember that addition is third point of intersection on the curve between P and Q
x = delta^2-x1-x2
y = delta*(x1-x)-y1

delta = 
	if p1=p2: # This means that the point of intersection is the derivative, f'(x) of f(x)
		delta = (3*x1^2+A)  / 2*y1
	else:
		delta = (y2-y1) / (x2-x1)


*omitted*

def add(self,p1, p2):
        if p1 == self.id:
            return p2

        if p2 == self.id:
            return p1
        
        if p1 == p2.invert(self.p):
            return self.id

        if p1 == p2:
            delta = (3*pow(p1.x,2)+self.A)*gmpy2.invert(2*p1.y, self.p)
        else:
            delta = (p2.y - p1.y)*gmpy2.invert(p2.x - p1.x, self.p)
        
        x = pow(delta, 2)- p1.x - p2.x
        y = delta*(p1.x-x)-p1.y 

        return Point(x % self.p, y % self.p)

*omitted*

Point is a simple class

class Point():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    
    def __str__(self):
        return "{"+str(self.x)+", "+str(self.y)+"}"

    def __eq__(self, p2):
        return True if self.x == p2.x and self.y == p2.y else False
    
    def __mod__(self,p):
        return Point(self.x%p, self.y%p)
    
    def invert(self, p):
        return Point(self.x, p-self.y)

Multiplication

I have actually written the multiplication algorithm for fields already. Check out galois fields

So we end up with

*omitted*

def multiply(self,n,p):
        q = self.id
        while n > 0:
            if n&1:
                q = self.add(q,p)
            p = self.add(p,p)
            n = n >> 1
        return q % self.p

*omitted*

Where n is an integer for the multiplication nP = Q

Done for today

Now we have everything to set up Elliptical curve cryptography, which I will cover in the next post. Until next time!