2018-04-30

シュノア署名を楕円曲線secp256k1を使ってpythonで計算してみる

secp256k1

シュノア署名(Schnorr Signature)

シュノア署名を群の言葉で書きます。

秘密鍵と公開鍵の生成

STEP1
有限体 $F_p$ と素数位数lのベースポイント $g \in F_p$ を生成する。
STEP2
乱数 $x \in {Z_l}^{*}$ を秘密鍵とし、 $Y = {g} ^ {-x} mod p$ を公開鍵とする。
STEP3
H()をハッシュ関数とし公開する。

署名

STEP1
メッセージmに対して
乱数 $r \in {Z_l}^{*}$ を生成し、以下を計算する。
$u = {g}^{r} \mod p$
$e = H(u || m)$
STEP2
$v = r + xe \mod l$
を計算する。v=0の場合はrを取り直す。
(e,v)が署名である。

署名検証

STEP1
e, vが ${Z_l}^{*}$ の要素でなければ、NGとする。
STEP2
$u' = {g}^{v} {y}^{e} \mod p$
$e' = H(u'||m)$ を計算する。
STEP3
e'= e ならOK、異なればNGとする。

pythonで確認する

シュノア署名(Schnorr Signature)を楕円曲線secp256k1を使って計算してみます。
ECDSAのように、ハッシュの取り方など、手続きが決まったRFCはなさそうなので、適当に実装してみました。
ソースと実行結果です。

#!/usr/bin/env python3
#
# secp256k1
# http://www.secg.org/SEC2-Ver-1.0.pdf
#  
import sys
import hashlib

sys.setrecursionlimit(1500)

b = 256
# q is prime
q = 2**256 - 2**32 - 977
# l (order of group) is prime
l = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# no depend q,l
def expmod(v,e,m):
    if e == 0: return 1
    t = expmod(v,e//2,m)**2 % m
    if e & 1: t = (t*v) % m
    return t

# no depend q,l
def inv(x, m):
    return expmod(x,m-2,m)

def double_pt(P):
    x = P[0]
    y = P[1]
    if y == 0: return [0, 0]
    nu = 3*expmod(x,2,q)*inv(2*y,q)
    x3 = expmod(nu,2,q)-2*x
    y3 = nu*(x-x3)-y
    return [x3 % q, y3 % q]

def add_pt(P, Q):
    x1 = P[0]
    y1 = P[1]
    x2 = Q[0]
    y2 = Q[1]
    if x1 == -1 and y1 == -1: return Q
    if x2 == -1 and y2 == -1: return P
    if x1 == x2:
        if (y1 + y2) % q == 0:
            return [-1, -1]
        else:
            return double_pt(P)

    lm = (y1-y2)*inv(x1-x2, q)
    x3 = expmod(lm,2,q)-(x1+x2)
    y3 = lm*(x1-x3)-y1
    return [x3 % q, y3 % q]

def scalarmult(P, e):
    if e == 0: return [-1, -1]
    if e < 0: e = e + l
    Q = scalarmult(P, e//2)
    Q = add_pt(Q, Q)
    if e & 1: Q = add_pt(Q, P)
    return Q

def isoncurve(P):
    x = P[0]
    y = P[1]
    return (y**2 - x**3 - 7) % q == 0

Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G = [Gx, Gy]

# 32 byte array to big endian integer
def decodeint(s):
    assert(len(s) == 32)
    return int.from_bytes(s, 'big')

# big endian integer to 32 byte array
def encodeint(y):
  return y.to_bytes(32, byteorder='big')

print("q  = {}".format(q))
print("l  = {}".format(l))

# string to byte array
msg = str("0000").encode('utf-8')

# -- schnorr sign 
x = 5
print("x = {}".format(x))
Y = scalarmult(G, -x)
print("Y  = ({0}, {1})".format(Y[0], Y[1]))
r = 2
print("r  = {}".format(r))
U = scalarmult(G, r) 
u = U[0]

# int to byte array
u_ba = encodeint(u)
e_digest = hashlib.sha256(u_ba + msg).digest()
e = decodeint(e_digest)
v = (r + x * e) % l

print("e  = {}".format(e))
print("v  = {}".format(v))

# -- verify
UD = add_pt(scalarmult(G, v), scalarmult(Y, e))
ud = UD[0] % l
ud_ba = encodeint(ud)

ed_digest = hashlib.sha256(ud_ba + msg).digest()
ed = decodeint(ed_digest)
print("ed = {}".format(ed))

print("result {}".format(e == ed))

q  = 115792089237316195423570985008687907853269984665640564039457584007908834671663
l  = 115792089237316195423570985008687907852837564279074904382605163141518161494337
x = 5
Y  = (21505829891763648114329055987619236494102133314575206970830385799158076338148, 17788380558553574189887744505607047724243097342766425233927699087598871091545)
r  = 2
e  = 5488091919336943623366459380250002739393051770454284273229695939919413862528
v  = 27440459596684718116832296901250013696965258852271421366148479699597069312642
ed = 5488091919336943623366459380250002739393051770454284273229695939919413862528
result True

eとedが一致しているのが分かります。

余談ですが、python3のバイト列とintを相互変換する組込関数めちゃ便利ですね。

参考:

代数学から学ぶ暗号理論: 整数論の基礎から楕円曲線暗号の実装まで

作者: 宮地充子
出版社/メーカー: 日本評論社
発売日: 2012/03/09
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

2018-04-29

batchTransferでみつかった脆弱性を確かめる

仮想通貨

BeautyChain (BEC)などに実装された batchTransfer に見つかったぜい弱性 CVE-2018-10299

medium.com

について試してみました。

f:id:pebble8888:20180429125640p:plain

remix で検証しました。

この 0x8000...0000 に2を掛けると、solidify のuint256実装では、桁あふれした分が差し引かれ、_amount が0になってしまうというぜい弱性のようです。

solidityの uint256 実装が修正されればいいと思っています。つまりoverflowしたら例外を発生させます。

オーバーフローをきちんと実装している言語としてswift4をあげておきます。
swift4 でUInt64を使ってオーバーフローさせた場合は、EXC_BAD_INSTRUCTION でクラッシュします。

f:id:pebble8888:20180429130321p:plain

swift4 でオーバーフローした分をあえて読み捨てる演算も定義されており、&* を使います。

f:id:pebble8888:20180429131713p:plain

swiftは安全性を第一に考えられているので、デフォルトでオーバーフローしたらクラッシュさせる実装になっているのです。

solidityのような通貨を直に扱うような言語でオーバーフロー例外の実装がされていない演算子がデフォルトになっている
こと自体にびっくりしました。

2018-04-28

secp256k1 秘密鍵と公開鍵の演算

secp256k1

以下の関数の機能を見てみましょう。

func secp256k1_ec_privkey_negate(_ ctx: secp256k1_context, _ seckey: inout [UInt8]) -> Bool
func secp256k1_ec_pubkey_negate(_ ctx: secp256k1_context, _ pubkey: inout secp256k1_pubkey) -> Bool
func secp256k1_ec_privkey_tweak_add(_ ctx: secp256k1_context, _ seckey: inout [UInt8], _ tweak: [UInt8]) -> Bool
func secp256k1_ec_pubkey_tweak_add(_ ctx: secp256k1_context, _ pubkey: inout secp256k1_pubkey, _ tweak: [UInt8]) -> Bool
func secp256k1_ec_privkey_tweak_mul(_ ctx: secp256k1_context, _ seckey: inout [UInt8], _ tweak: [UInt8]) -> Bool
func secp256k1_ec_pubkey_tweak_mul(_ ctx: secp256k1_context, _ pubkey: inout secp256k1_pubkey, _ tweak: [UInt8]) -> Bool

最初の一つは秘密鍵に-1を乗算し、mod L を取る操作を行います。

var seckey: [UInt8] = [0,0,0,0,0,0,0,0,
                       0,0,0,0,0,0,0,0,
                       0,0,0,0,0,0,0,0,
                       0,0,0,0,0,0,0,4]
let result = secp256k1_ec_privkey_negate(ctx, &seckey)
XCTAssert(result)
        
print("\(seckey.hexDescription())")

fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036413d

pythonで確認します。

>>> L = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
>>> print("%x" % ((-4) % L))
fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036413d

次の関数は公開鍵(点P)にマイナスを乗算する(y座標を-1倍する)ものです。

print("\(pubkey)")
let result3 = secp256k1_ec_pubkey_negate(ctx, &pubkey)
XCTAssert(result3)
print("\(pubkey)")

e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13,ae1266c15f2baa48a9bd1df6715aebb7269851cc404201bf30168422b88c630d
e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13,51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922

pythonで確かめます。

>>> p = 2**256 - 2**32 - 977
>>> x = 0xe493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13
>>> y = 0xae1266c15f2baa48a9bd1df6715aebb7269851cc404201bf30168422b88c630d
>>> print("%x" % (-y % p))
51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922

これで、mul や add が何をする関数なのかも分かるでしょう。
ビットコインでの使い方としては、ホットウォレットやコールドウォレット上での、秘密鍵や公開鍵の算出に使います。

2018-04-28

secp256k1 ECDSA 秘密鍵の値の範囲と公開鍵の値の範囲

secp256k1

ECDSA の秘密鍵は1以上、群Gの位数未満です。 secp256k1 の群Gの位数は
L = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
ですが、256bitの正の値skをランダムに取り(0以上 ${2}^{256}-1$ )、値が0だった場合と、L以上だった場合、値を取り直せばよい事になります。
sk=0の場合は、公開鍵が0になってしまい、秘匿性がなさすぎます。
skがLと ${2}^{256}-1$ の間の値でも公開鍵は計算できますが、
同じ公開鍵 $sk \cdot G = A$ に対して、
$(sk - L) \cdot G = A$ が成り立ち、sk - L も秘密鍵となり、１つの公開鍵に対する秘密鍵が２つ出来てしまい、マズイです。

ビットコインのsecp256k1 ライブラリでは、
関数 secp256k1_ec_pubkey_create()にこの範囲外の値を渡すと、戻り値としてエラーを返すようになっています。
公開鍵は当然ながら1以上L未満の値となります。

2018-04-27

secp256k1 署名をs-form にノーマライズする

secp256k1

前回の記事では、secp256k1ライブラリでは署名のsの値は値が小さい方を使うから注意せよと書きました。

ECDSA(secp256k1)での署名と検証をswiftで行う(secp256k1swiftライブラリ使用) - Pebble Coding

関数リストをよくみてみると、
secp256k1_ecdsa_signature_normalize()
という関数があります。

これは、他のecdsaライブラリで作られた(r,s)でsが群のオーダーの半分より大きい場合、それを小さくした値(lower-S form)に置き換える関数です。
Bitcoinでは、署名とハッシュ結果に一意性が求められるので、sとしては lower-S form を採用しています。
実際に、計算してみましょう。

guard var ctx: secp256k1_context = secp256k1_context_create([.SECP256K1_CONTEXT_SIGN, .SECP256K1_CONTEXT_VERIFY]) else { fatalError() }
let seckey: [UInt8] = [0,0,0,0,0,0,0,0,
                               0,0,0,0,0,0,0,0,
                               0,0,0,0,0,0,0,0,
                               0,0,0,0,0,0,0,3]
var pubkey = secp256k1_pubkey()
let result = secp256k1_ec_pubkey_create(ctx, &pubkey, seckey)
XCTAssert(result)
        
let msg32:[UInt8] = [0x9a, 0xf1, 0x5b, 0x33, 0x6e, 0x6a, 0x96, 0x19,
                     0x92, 0x85, 0x37, 0xdf, 0x30, 0xb2, 0xe6, 0xa2,
                     0x37, 0x65, 0x69, 0xfc, 0xf9, 0xd7, 0xe7, 0x73,
                     0xec, 0xce, 0xde, 0x65, 0x60, 0x65, 0x29, 0xa0]

// python で生成した署名
var sig = secp256k1_ecdsa_signature()
sig.data = [0xc6, 0x04, 0x7f, 0x94, 0x41, 0xed, 0x7d, 0x6d, // r
            0x30, 0x45, 0x40, 0x6e, 0x95, 0xc0, 0x7c, 0xd8,
            0x5c, 0x77, 0x8e, 0x4b, 0x8c, 0xef, 0x3c, 0xa7,
            0xab, 0xac, 0x09, 0xb9, 0x5c, 0x70, 0x9e, 0xe5,
            0xf6, 0x7f, 0x6c, 0xf8, 0x1a, 0x19, 0x87, 0x30, // s
            0x91, 0xaa, 0x7c, 0x95, 0x78, 0xfa, 0x2e, 0x96,
            0x49, 0x0e, 0x9b, 0xfc, 0x78, 0xae, 0x7e, 0x97,
            0x98, 0x00, 0x4e, 0x82, 0x52, 0xc0, 0x62, 0x87]

// s-formではないのでverifyに失敗します        
let ret3 = secp256k1_ecdsa_verify(ctx, sig, msg32, pubkey)
// confirm to fail
XCTAssert(!ret3)
        
var sig_sform = secp256k1_ecdsa_signature()
// s-form にノーマライズされていない署名を指定した場合、戻りはtrue
let ret4 = secp256k1_ecdsa_signature_normalize(ctx, &sig_sform, sig)
XCTAssert(ret4)
print("\(sig_sform)")

secp256k1_context_destroy(&ctx)

secp256k1_ecdsa_sign()で生成したものと同じ署名が得られました。

c6 04 7f 94 41 ed 7d 6d 30 45 40 6e 95 c0 7c d8 5c 77 8e 4b 8c ef 3c a7 ab ac 09 b9 5c 70 9e e5 09 80 93 07 e5 e6 78 cf 6e 55 83 6a 87 05 d1 68 71 a0 40 ea 36 9a 21 a4 27 d2 10 0a 7d 75 de ba