[밑바닥비트코인] 3. 타원곡선

비트코인에서 쓰이는 암호화 기법을 알아보기 전에 타원곡선의 정의와, 타원곡선 위에서 연산이 

 

어떻게 이뤄지는지에 대해서 살펴보도록하자.

 

 

 

타원곡선

---

타원곡선은 다음과 같은 형태의 방정식을 갖는다.

 

비트코인은 secp256k1이라는 타원곡선을 사용하며, 여기서 a의 값은 0, b의 값은 7이다. 

secp256k1

그러면 타원곡선에서 점 간의 연산은 어떻게 하는 것일까? 그에 대한 해답은 아래에 있다.

 

출처 : https://stackoverflow.com/questions/19800518/python-matplotlib-for-elliptic-curve-with-sympy-solve

 

더하고자 하는 두 점(P, Q)을 연장한 선이 타원곡선과 만나는 점(R)을 x축 대칭한 점이 P+Q가 된다. 

 

타원곡선에서 한 점 A를 x축 대칭하면 -A가 된다. 이처럼 타원곡선에서의 덧셈 연산을 점 덧셈이라고 한다. 

 

좀 더 다양한 사례를 만나보자. 

 

출처 : https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

 

한 점(P)이 곡선 위에 있고, 나머지 한점이 곡선과의 접점(Q)이라고 하면, 이를 점 덧셈하면 -Q가 된다. (역원 존재)

 

그리고 두 점이 서로 x축 대칭이라면 이들을 점덧셈하면 무한원점(I)이 된다. (항등원 존재)

 

마지막으로 점 P에서의 접선이 x축과 수직이라면 이 점 P를 자기자신과 더하면 이는 무한원점이된다. 

 

출처 : https://crypto.stackexchange.com/questions/48657/how-does-ecc-go-from-decimals-to-integers

 

점덧셈도 일반 덧셈연산과 마찬가지로 교환법칙, 결합법칙이 성립한다. 

 

타원곡선에서의 점을 코드로 구현해보자. 

class Point:

    def __init__(self, x, y, a, b):
        self.x = x
        self.y = y
        self.a = a
        self.b = b
        if x is None and y is None:
            return
        if self.y**2 != self.x**3 + self.a*self.x + self.b:
            raise ValueError('({},{}) is not on the curve'.format(x,y))

x값, y값, 그리고 타원곡선에서의 매개변수 a, b를 인자로 받는다.

 

무한원점은 x, y값을 None으로 표현한다. x, y값이 타원곡선에서 성립하지 않으면 ValueError를 반환한다. 

    def __repr__(self):
        return 'Point({},{})_{}_{}'.format(self.x, self.y, self.a, self.b)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y and self.a == other.a and self.b == other.b

    def __ne__(self, other):
        return self.x != other.x or self.y != other.y or self.a != other.a or self.b != other.b

타원곡선의 점을 표현하는 함수와, 동치(==), 비동치(!=)를 검사하는 함수이다. 

    def __add__(self, other):
        if self.a != other.a or self.b != other.b:
            raise TypeError('Points {}, {} are not on the same curve'.format(self, other))
        if self.x is None:
            return other
        elif other.x is None:
            return self
        if self.x == other.x and self.y == -(other.y):
            return self.__class__(None,None,self.a,self.b)

덧셈연산을 재정의하는 __add__함수에서는 먼저 두 점(self, other)이 같은 곡선에 있는지 검사하고, 

 

어느 한쪽이 무한원점이라면 나머지 한 점을 반환한다. 

 

그리고 점들이 서로 x축에 대칭(y값이 다른 부호)이면 무한원점을 반환한다. 

 

항등원의 덧셈, 역원의 덧셈을 살펴보았다. 그러면 이제 x값이 서로 다른 점끼리의 점덧셈을 구하는 법을 알아보자. 

 

P1 = (x1, y1), P2 = (x2, y2)이면 P1 + P2 = P3일 것이다. (P3 = (x3, y3))

 

두 점 (P1, P2)의 기울기 s = (y1-y2) / (x1-x2) 이다. 

 

그렇다면 결과값인 P3의 x값은 s^2 - x1 - x2 이고, y값은 s(x1 - x3) - y1 이다.

        if self.x != other.x:
            slope = (self.y - other.y)/(self.x - other.x)
            x3 = slope ** 2 - self.x - other.x
            y3 = slope * (self.x - x3) - self.y
            return self.__class__(x3, y3, self.a, self.b)

마지막으로 서로 같은 점끼리의 덧셈을 살펴보자. 같은 점끼리의 점덧셈은 일단 해당 점에서의 접점의 기울기를 

 

구해야한다. 

위 식을 x에 대해서 미분하면 2y dy/dx = 3x^2 + a

 

우항으로 2y를 넘기면 dy/dx = (3x^2 + a) / 2y 이고 dy/dx가 접선의 기울기 s이므로

 

s = (3 * x1^2 + a) / (2 * y1) 이고

 

x3 = s^2 - 2*x1  그리고  y3 = s*(x1 - x3) - y1 이다.

        elif self == other:
            if self.y == 0 and other.y==0:
                return self.__class__(None,None,self.a,self.b)
            slope = (3*self.x**2 + self.a)/(2*self.y)
            x3 = slope**2 - 2*self.x
            y3 = slope*(self.x - x3) - self.y
            return self.__class__(x3,y3, self.a, self.b)

여기서 y값이 0인 경우, 더했을 때 무한원점이 반환되도록 예외처리를 해준다.

    p1 = Point(-1,-1,5,7)
    p2 = Point(-1,-1,5,7)
    print(p1+p2)
    
    결과값>>>
    Point(18.0,77.0)_5_7