Category: Bitcoin

楕円曲線暗号の公開鍵は(x,y)形式の一つの座標
ECDSA公開鍵をシリアライズする方法はSECフォーマットと呼ばれている
非圧縮と圧縮がある

1.プレフィックス0x04
2.32バイトのビッグエンディアン整数をx座標に追加
2.32バイトのビッグエンディアン整数をy座標に追加

### 非圧縮

class S256Point(Point):
	// 省略
	def sec(self):
		return b'\x04' + self.x.num.to_bytes(32, 'big')\
			+ self.y.num.to_bytes(32, 'big')

priv = PrivateKey(5002)
print(priv.point.sec(compressed=False).hex())
priv = PrivateKey(2018**5)
print(priv.point.sec(compressed=False).hex())
priv = PrivateKey(0xdeadbeef12345)
print(priv.point.sec(compressed=False).hex())

$ python3 app.py
040f85cb0c917647fadfd31e641231d3a01ac9d3d8a680aab2457e0036bf34d37e6949b302843a33cdf068589c8330bb5c09c1739420d65b7b33cfab6d10118d97
04027f3da1918455e03c46f659266a1bb5204e959db7364d2f473bdf8f0a13cc9dff87647fd023c13b4a4994f17691895806e1b40b57f4fd22581a4f46851f3b06
04d90cd625ee87dd38656dd95cf79f65f60f7273b67d3096e68

### 圧縮

class S256Field(FieldElement):

	def __init__(self, num, prime=None):
		super().__init__(num=num, prime=P)

	def __repr__(self):
		return '{:x}'.format(self.num).zfill(64)

	def sqrt(self):
		return self**((P + 1) // 4)

	@classmethod
	def parse(self, sec_bin):
		if sec_bin[0] == 4:
			x = int.from_bytes(sec_bin[1:33], 'big')
			y = int.from_bytes(sec_bin[33:65], 'big')
			return S256Point(x=x, y=y)
		is_even = sec_bin[0] == 2
		x = S256Field(int.from_bytes(sec_bin[1:], 'big'))
		alpha = x**3 + S256Field(B)
		beta = alpha.sqrt()
		if beta.num % 2 == 0:
			even_beta = beta
			odd_beta = S256Field(P - beta.num)
		else:
			even_beta = S256Field(P - beta.num)
			odd_beta = beta
		if is_even:
			return S256Point(x, even_beta)
		else:
			return S256Point(x, odd_beta)

priv = PrivateKey(5001)
print(priv.point.sec(compressed=True).hex())
priv = PrivateKey(2019**5)
print(priv.point.sec(compressed=True).hex())
priv = PrivateKey(0xdeadbeef54321)
print(priv.point.sec(compressed=True).hex())

$ python3 app.py
0357a4f368868a8a6d572991e484e664810ff14c05c0fa023275251151fe0e53d1
02933ec2d2b111b92737ec12f1c5d20f3233a0ad21cd8b36d0bca7a0cfa5cb8701
0296be5b1292f6c856b3c5654e886fc13511462059089cdf9c479623bfcbe77690

### 署名の作成

e = int.from_bytes(hash256(b'my secret'), 'big') 
z = int.from_bytes(hash256(b'my message'), 'big') # 署名しようとしているメッセージ
k = 1234567890 
r = (k*G).x.num # x座標のみ取り出す
k_inv = pow(k, N-2, N)
s = (z+r*e) * k_inv % N # モジュロ演算
point = e*G # 公開点は知らせる必要がある
print(point)

print(hex(z))
print(hex(r))
print(hex(s))

$ python3 app.py
Point(1153752822844410451703720272380683670327470420405725541447346968941621636178,4935740600172189071191766981850281297554521083605982627869195587800421042658)_0_7 FieldElement(115792089237316195423570985008687907853269984665640564039457584007908834671663)
0x231c6f3d980a6b0fb7152f85cee7eb52bf92433d9919b9c5218cb08e79cce78
0x2b698a0f0a4041b77e63488ad48c23e8e8838dd1fb7520408b121697b782ef22
0xbb14e602ef9e3f872e25fad328466b34e6734b7a0fcd58b1eb635447ffae8cb9

e = 12345
z = int.from_bytes(hash256(b'programming bitcoin'), 'big')
k = 1234567890
r = (k*G).x.num
k_inv = pow(k, N-2, N)
s = (z+r*e) * k_inv % N
point = e*G
print(point)

print(hex(z))
print(hex(r))
print(hex(s))

$ python3 app.py
Point(108607064596551879580190606910245687803607295064141551927605737287325610911759,6661302038839728943522144359728938428925407345457796456954441906546235843221)_0_7 FieldElement(115792089237316195423570985008687907853269984665640564039457584007908834671663)
0x6aac771a641117f22150921737c72c77e73150945342f7a490b77332abaac5c
0x2b698a0f0a4041b77e63488ad48c23e8e8838dd1fb7520408b121697b782ef22
0xd6f075528e124345b4b81029288861d9c33ddc49f8327005dfb203b3e9c1ee9c

### メッセージ署名

from random import randint

class PrivateKey:

	def __init__(self, secret):
		self.secret = secret
		self.point = secret * G

	def hex(self):
		return '{:x}'.format(self.secret).zfill(64)

	def sign(self, z):
		k = randint(0, N-1)
		r = (k*G).x.num
		k_inv = pow(k, N-2, N)
		s = (z + r*self.secret) * k_inv % N
		if s > N/2:
			s = N - s
		return Signature(r, s)

k は署名ごとに一意である必要がある。
RFC6979

	def sign(self, z):
		k = self.deterministic_k(z)
		r = (k*G).x.num
		k_inv = pow(k, N-2, N)
		s = (z + r*self.secret) * k_inv % N
		if s > N/2:
			s = N - s
		return Signature(r, s)

	def deterministic_k(self, z):
		k = b'\x00' * 32
        v = b'\x01' * 32
        if z > N:
            z -= N
        z_bytes = z.to_bytes(32, 'big')
        secret_bytes = self.secret.to_bytes(32, 'big')
        s256 = hashlib.sha256
        k = hmac.new(k, v + b'\x00' + secret_bytes + z_bytes, s256).digest()
        v = hmac.new(k, v, s256).digest()
        k = hmac.new(k, v + b'\x01' + secret_bytes + z_bytes, s256).digest()
        v = hmac.new(k, v, s256).digest()
        while True:
            v = hmac.new(k, v, s256).digest()
            candidate = int.from_bytes(v, 'big')
            if candidate >= 1 and candidate < N:
                return candidate  
            k = hmac.new(k, v + b'\x00', s256).digest()
            v = hmac.new(k, v, s256).digest()

これが基本要素なのか
なんか凄いな

P = eG
eは秘密鍵(256ビット)、Pは公開鍵(x, y座標256ビット)

署名アルゴリズムは楕円曲線署名アルゴリズム(Elliptic Curve Digital Signature Algorithm) ECDSA

eG = P
ランダムな256ビットの数字をkとして
kG = R
uG + vP = kG
u,vは0ではない値を署名者が選ぶ　GPは既知の数値

-署名ハッシュ
任意のデータを固定サイズのデータにする決定関数
kはランダムな数値を用いて明かさない

ビットこんんはハッシュ関数はhash256(sha256を2回繰り返す)
s = (z + re)/k

### 署名のアルゴリズム
1.署名を(r, s)、署名対称のハッシュをz、署名者の公開鍵をP
2. u = z/s, v = r/s
3. uG + vP = R
4. 点Rのx座標がrと同じであれば署名は有効

z = 0xbc62d4b80d9e36da29c16c5d4d9f11731f36052c72401a76c23c0fb5a9b74423
r = 0x37206a0610995c58074999cb9767b87af4c4978db68c06e8e6e81d282047a7c6
s = 0x8ca63759c1157ebeaec0d03cecca119fc9a75bf8e6d0fa65c841c8e2738cdaec
px = 0x04519fac3d910ca7e7138f7013706f619fa8f033e6ec6e09370ea38cee6a7574
py = 0x82b51eab8c27c66e26c858a079bcdf4f1ada34cec420cafc7eac1a42216fb6c4
point = S256Point(px, py)
s_inv = pow(s, N-2, N) # フェルマー小定理
u = z * s_inv % N # u = z/s
v = r * s_inv % N # v = r /s
print((u*G + v*point).x.num == r) # 点Rのx座標がrと同じであれば署名は有効 

$ python3 app.py
True

point = S256Point(
	0x887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c,
	0x61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34)

z = 0xec208baa0fc1c19f708a9ca96fdeff3ac3f230bb4a7ba4aede4942ad003c0f60
r = 0xac8d1c87e51d0d441be8b3dd5b05c8795b48875dffe00b7ffcfac23010d3a395
s = 0x68342ceff8935ededd102dd876ffd6ba72d6a427a3edb13d26eb0781cb423c4
s_inv = pow(s, N-2, N) 
u = z * s_inv % N 
v = r * s_inv % N
print((u*G + v*point).x.num == r)

point = S256Point(
	0x887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c,
	0x61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34)

z = 0x7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d
r = 0xeff69ef2b1bd93a66ed5219add4fb51e11a840f404876325a1e8ffe0529a2c
s = 0xc7207fee197d27c618aea621406f6bf5ef6fca38681d82b2f06fddbdce6feab6

s_inv = pow(s, N-2, N) 
u = z * s_inv % N 
v = r * s_inv % N
print((u*G + v*point).x.num == r)

class S256Point(Point):

	def __init__(self, x, y, a=None, b=None):
		a, b = S256Field(A), S256Field(B)
		if type(x) == int:
			super().__init__(x=S256Field(x), y=S256Field(y), a=a, b=b)
		else:
			super().__init__(x=x, y=y, a=a, b=b)

	def __rmul__(self, coefficient):
		coef = coefficient % N
		return super().__rmul__(coef)

	def verify(self, z, sig):
		s_inv = pow(sig.s, N - 2, N)
		u = z * s_inv % N
		v = sig.r * s_inv % N
		total = u * G + v * self
		return total.x.num == sig.r


class Signature:

	def __init__(self, r, s):
		self.r = r
		self.s = s

	def __repr__(self):
		return 'Signature({:x},{:x})'.format(self.r, self.s)

1. zが与えられており、eG=Pを満たすeが分かっている
2. ランダムにkを選ぶ
3. R = kGとrを算出
4. s = (z+re)/kを算出
5. 署名は(r,s)となる

publickeyは誰にも転送されなければならず、zは検証者が必ず知る必要がある

なんか凄いんだなBitcoinって…

### Bitcoinのsecp256k1
a = 0, b = 7 つまり y^2 = x^3 + 7
p = 2^256 – 2^32 ^ 077
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
(x座標・16進数)
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
(y座標)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
– 256ビットで表す
– ビットコインの秘密鍵は途方もない

secp256k1の計算

gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
p = 2**256 - 2**32 - 977
print(gy**2 % p == (gx**3 + 7) % p)

gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
p = 2**256 - 2**32 - 977
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
x = FieldElement(gx, p)
y = FieldElement(gy, p)
seven = FieldElement(7, p)
zero = FieldElement(0, p)
G = Point(x, y, zero, seven)
print(n*G)

class S256Field(FieldElement):

	def __init__(self, num, prime=None):
		super().__init__(num=num, prime=P)

	def __repr__(self):
		return '{:x}'.format(self.num).zfill(64)


class S256Point(Point):

	def __init__(self, x, y, a=None, b=None):
		a, b = S256Field(A), S256Field(B)
		if type(x) == int:
			super().__init__(x=S256Field(x), y=S256Field(y), a=a, b=b)
		else:
			super().__init__(x=x, y=y, a=a, b=b)

	def __rmul__(self, coefficient):
		coef = coefficient % N
		return super().__rmul__(coef)

P = 2**256 - 2**32 - 977
A = 0
B = 7
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
G = S256Point(
	0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
	0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)


print(N*G)

なんか一気に来たな

同じ点を加算することができるため、次のような表記になる
(170,142)+(170,142) = 2(170,142)

この加算は何度も繰り返し行うことができ、スカラー倍算と呼ぶ
計算をせずに予測することが非常に難しい

prime = 223
a = FieldElement(num=0, prime=prime)
b = FieldElement(num=7, prime=prime)
x1 = FieldElement(num=192, prime=prime)
y1 = FieldElement(num=105, prime=prime)
p = Point(x1, y1, a, b)
print(p+p)
x1 = FieldElement(num=143, prime=prime)
y1 = FieldElement(num=98, prime=prime)
p = Point(x1, y1, a, b)
print(p+p)
x1 = FieldElement(num=47, prime=prime)
y1 = FieldElement(num=71, prime=prime)
p = Point(x1, y1, a, b)
print(p+p)
print(p+p+p+p)
print(p+p+p+p+p+p+p+p)
print(p+p+p+p+p+p+p+p+p+p+p+p+p+p+p+p+p+p+p+p+p)

for s in range(1, 21):
	result = s*p
	print('{}*(47,71)=({},{})'.format(s,result.x.num, result.y.num))

スカラー倍数ははっきりとしたパターンがないため、逆の離散対数は難しい

## 数学の群

prime = 223
a = FieldElement(num=0, prime=prime)
b = FieldElement(num=7, prime=prime)
x = FieldElement(num=15, prime=prime)
y = FieldElement(num=86, prime=prime)
p = Point(x, y, a, b)
inf = Point(None, None, a, b)
product = p
count = 1
while product != inf:
	product += p
	count += 1
print(count)

    def __rmul__(self, coefficient):
        coef = coefficient
        current = self
        result = self.__class__(None, None, self.a, self.b)
        while coef:
            if coef & 1:
                result += current
            current += current
            coef >>= 1
        return result

楕円曲線暗号: メッセージの署名と検証

– 実数上の楕円曲線
実数は有理数、無理数を含む数(π, sqrt(2), e +7√19 など)

### 有限体上の楕円曲線
F103 でのy^2 = x^3 + 7
y^2 = 64^2 % 103 = 79
x^3 + 7 = (17^3 + 7) % 103 = 79

有限体に負が存在しないと、y^2の項によって真ん中の線に対して対称になる

a = FieldElement(num=0, prime=223)
b = FieldElement(num=7, prime=223)
x = FieldElement(num=192, prime=223)
y = FieldElement(num=105, prime=223)
p1 = Point(x, y, a, b)
print(p1)

$ python3 app.py
<__main__.Point object at 0x7f1a3ceef2b0>

### 有限体における点の加算

prime = 223
a = FieldElement(num=0, prime=prime)
b = FieldElement(num=7, prime=prime)
x1 = FieldElement(num=192, prime=prime)
y1 = FieldElement(num=105, prime=prime)
x2 = FieldElement(num=17, prime=prime)
y2 = FieldElement(num=56, prime=prime)
p1 = Point(x1, y1, a, b)
p2 = Point(x2, y2, a, b)
print(p1+p2)

prime = 223
a = FieldElement(num=0, prime=prime)
b = FieldElement(num=7, prime=prime)
p1 = Point(FieldElement(170, prime), FieldElement(142, prime), a, b)
p2 = Point(FieldElement(60, prime), FieldElement(139, prime), a, b)
print(p1+p2)
p1 = Point(FieldElement(47, prime), FieldElement(71, prime), a, b)
p2 = Point(FieldElement(17, prime), FieldElement(56, prime), a, b)
print(p1+p2)
p1 = Point(FieldElement(143, prime), FieldElement(98, prime), a, b)
p2 = Point(FieldElement(76, prime), FieldElement(66, prime), a, b)
print(p1+p2)

ほう、なるほどー

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 __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 == other.x and self.y != other.y:
			return self.__class__(None, None, self.a, self.b)

		if self.x is None:
			return other
		if other.x is None:
			return self

	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)

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)

$ python3 app.py
<__main__.Point object at 0x7f014fc2fbb0>
<__main__.Point object at 0x7f014fbf07f0>
None

### x1 != x2 の点の加算
P1 = (x1,y1), P2 = (x2, y2), P3 = (x3, y3)
s = (y2 – y1)/(x2 – x1)
x3 = s^2 – x1 – x2
y3 = s(x1 – x3) – y1

x1, y1 = 2, 5
x2, y2 = -1, -1
s = (y2 - y1) / (x2 - x1)
x3 = s**2 - x1 - x2
y3 = s * (x1 - x3) - y1
print(x3, y3)

		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 の時の点の加算
x3 = s^2 – 2×1
y3 = s(x1 – x3) – y1

a, x1, y1 = 5, -1, -1
s = (3 * x1**2 + a) / (2 * y1)
x3 = s**2 - 2*x1
y3 = s * (x1 - x3) - y1
print(x3, y3)

		if self == other:
			s = (3 * self.x**2 + self.a) / (2 * self.y)
			x = s**2 - 2 * self.x
			y = s * (self.x - x) - self.y
			return self.__class__(x, y, self.a, self.b)

		if self == other and self.y == 0 * self.x:
			return self.__class__(None, None, self.a, self.b)

なるほどー

### 楕円曲線 定義
y^2 = x^3 + ax + b

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

	def __ne__(self, other):
		return not (self == other)

p1 = Point(-1, -1, 5, 7)
p1 = Point(-1, -2, 5, 7)

一次方程式
y = ax^2 + bx + c

二次方程式
y = ax^3 + bx^2 + cx + d

楕円曲線は左辺がy^2となっている　
x軸に対して対称のグラフ

ビットコインに用いられる楕円曲線はsecp256k1と呼ばれる
y^2 = x^3 + 7

def on_curve(x, y):
	return y**2 == x**3 + 5*x + 7

print(on_curve(2,4))
print(on_curve(-1,-1))
print(on_curve(18,77))
print(on_curve(5,7))

### 点の加算
曲線上の二つの点を演算して、三つ目の点を得る
第三の点をx軸に対して対称にした点が点の加算の解になる
　L 点の加算は容易に予測できない(同一性、可換性、結合性、可逆性)

なるほど、こういうことをやっとるんか

四則演算(加算、減算、乗算、除算)について閉じている有限体を作るために利用できる道具がモジュロ演算
モジュロ演算：1つの数を別の数で割った余りの数を求めること
(3 – 16) % 12 = 11
(12 + 843) % 60 = 15
(23 + 97) % 60 = 0

pythonのモジュロ演算

print(7 % 3)
print(-27 % 13) 

$ python3 app.py
1
12

有限体上の加算が閉じていることを確認する必要がある
F19 = {0, 1, 2…18}

F57

prime = 57
print((44+33)%prime)
print((9-29)%prime)
print((17+42+49)%prime)
print((52-30-38)%prime)

### 加算と減算

// 省略
	def __add__(self, other):
		if self.prime != other.prime:
			raise TypeError('Cannot add two numbers in different Fields')
		num = (self.num + other.num) % self.prime
		return self.__class__(num, self.prime)

	def __sub__(self, other):
		if self.prime != other.prime:
			raise TypeError('Cannot subtract two numbers in different Fields')
		num = (self.num - other.num) % self.prime
		return self.__class__(num, self.prime)		

a = FieldElement(7, 13)
b = FieldElement(12, 13)
c = FieldElement(6, 13)
print(a+b==c)

### 乗算とべき乗
べき乗は乗算を繰り返し

prime = 97
print(95*45*31 % prime)
print(17*13*19*44 % prime)
print(17**7 * 77**49 % prime)

乗算

	def __mul__(self, other):
		if self.prime != other.prime:
			raise TypeError('Cannot multiply two numbers in different Fields')
		num = (self.num * other.num) % self.prime
		return self.__class__(num, self.prime)

a = FieldElement(3, 13)
b = FieldElement(12, 13)
c = FieldElement(10, 13)
print(a*b==c)

べき乗

	def __pow__(self, exponent):
		num = (self.num ** exponent) % self.prime
		return self.__class__(num, self.prime)

a = FieldElement(3, 13)
b = FieldElement(1, 13)
print(a**3==b)

for prime in (7, 11, 17, 31):
	print([pow(i, prime-1, prime) for i in range(1, prime)])

### 有限体上の除算

prime = 31
print(3*pow(24, prime-2, prime) % prime)
print(pow(17, prime-4, prime))
print(pow(4, prime-5, prime)*11 % prime)

	def __truediv__(self, other):
		if self.prime != other.prime:
			raise TypeError('Cannot divide two numbers in different Fields')
		num = self.num * pow(other.num, self.prime - 2, self.prime) % self.prime
		return self.__class__(num, self.prime)

いきなり難しいな

$ sudo apt install python3-virtualenv
$ virtualenv -p python3 .venv
$ .venv/vin/activate
$ . .venv/bin/activate
$ pip3 install -r requirements.txt

// vagrant上でjupyter notebookを起動する
$ jupyter notebook –no-browser –ip=0.0.0.0

ビットコインは相互に依存するコンポーネントが多数存在する
楕円曲線暗号(ECC)が基礎となる
L 署名アルゴリズム、検証アルゴリズム　… トランザクションの仕組みの中心
　　L シェノア署名、秘匿トランザクションなどの技術

### 有限体
有限の個数からなる集合と演算
集合が閉じている、加法単位元、乗法単位元、加法逆元、乗法逆元

### 有限集合
Fp = {0,1,2,…p-1}
体の位数は素数のべき乗となる

class FieldElement:

	def __init__(self, num, prime):
		if num >= prime or num < 0:
			error = 'Num {} not in field range 0 to {}'.format(
				num, prime - 1)
			raise ValueError(error)
		self.num = num
		self.prime = prime

	def __repr__(self):
		return 'FieldElement_{}({})'.format(self.prime, self.num)

	def __eq__(self, other):
		if other is None:
			return False
		return self.num == other.num and self.prime == other.prime

a = FieldElement(7, 13)
b = FieldElement(6, 13)
print(a==b)
print(a==a)

$ python3 app.py
False
True