y^2 = x^3 + ax + b
-> yが2乗となっているため、x軸に対して対象となる。
-> ビットコインは y^2 = x^3 + 7 で表されている(secp256k1)
2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 -1を 有限体上で定義された楕円曲線
曲線 y^2 = x^3 + ax + bをclassで表現すると
class Point:
def __init__(self, x, y, a, b):
self.a = a
self.b = b
self.x = x
self.y = y
if self.y**2 != self.x**3 + a * x + b:
raise ValueError('({}, {}) is not on the curve'.format(x, y))
def __eq__(self, other):
return self.x == other.x and self.y == other.y and self.a == other.a and self.b == other.b
from ecc import Point
p1 = Point(-1, -1, 5, 7)
p1 = Point(-1, -2, 5, 7)
楕円曲線上にあるかの判定
d = {2:4, -1:-1, 18:77, 5:7}
for x, y in d.items():
try:
Point(x, y, 5, 7)
print(x, y)
except ValueError:
pass
$ python3 main.py
-1 -1
18 77
### 点の加算
2つの点を演算して、同じ曲線上に3つ目の点を得ることを加算と呼ぶ
垂直、接線の場合は、直線が2点で交差する
無限遠点とは、限りなく遠いところ（無限遠）にある点のこと
点Aに換算すると点Aになる A + I = A
Pythonでは無限遠点をNoneで表現する
from ecc import Point
p1 = Point(-1, -1, 5, 7)
p2 = Point(-1, 1, 5, 7)
inf = Point(None, None, 5, 7)
print(p1 + inf)
print(inf + p2)
print(p1 + p2)
__init__を修正してaddをoverloadする
class Point:
def __init__(self, x, y, a, b):
self.a = a
self.b = b
self.x = x
self.y = y
if self.x is None and self.y is None:
return
if self.y**2 != self.x**3 + a * x + b:
raise ValueError('({}, {}) is not on the curve'.format(x, y))
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 not (self == other)
def __add__(self, other):
if self.a != other.a or self.b != other.b:
raise TypeError('Point {}, {} are not on the same curve'.format(self, other))
if self.x is None:
return other
if other.x is None:
return self
x1 != x2 の時の加算コーディング
if self.x != other.x:
s = (other.y - self.y) / (other.x - self.x)
x = s**2 - self.x - other.x
y = s(self.x - x) - self.y
return self.__class__(x, y, self.a, self.b)
P1 = P2(x座標が同じでy座標が異なる時)