secp256k1
ベースポイントを2倍した点,3倍した点は以下で求めます。 sage: E = EllipticCurve(GF(2 ** 256 - 2 ** 32 - 977), [0, 7]) sage: G = E([55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507…
ビットコインのgenesis blockつまり、最初のブロックの情報を見てみます。 まず、0番めつまり、genesis block のブロックハッシュを取得します。 $ bitcoin-cli getblockhash 0 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f 指定ブロ…
secp256k1_zkpライブラリの関数概要のメモです。 スカラー値は小文字、楕円曲線上の点は大文字で表現します。 未調査の部分は?としてあります。 /// seedを指定してハッシュ関数を通した点を返す // 同じseedを指定した場合、いつも同じ点が返されることが保…
secp256k1のC89実装のライブラリの関数のメモです。 GitHub - bitcoin-core/secp256k1: Optimized C library for EC operations on curve secp256k1 秘密鍵はスカラー値であり、sと表現することにします。 sは1以上secp256k1の群位数N未満である必要がありま…
SageMathを使います。 計算の都合上x一つに付きy一つの点のみとしています。(※1) q = 2**256 - 2**32 - 977 K = GF(q) i = 1 for x in range(0, 1000): try: n = (x ** 3 + 7) % q y = K(n).nth_root(2) print("P"+str(i)+": ("+str(x)+","+str(y)+")") if i…
secp256k1のベースポイントの性質をみていきます。 有理点(x, y)はおよそ256ビットの範囲内で均等に値がばらけていると考えられます。 ベースポイントGの倍数 を計算したときのx, yの値はおよそ256ビットの値がランダムに並んだようになりますが、たまたま端…
secp256k1は素体で、 群位数は L = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 = 115792089237316195423570985008687907852837564279074904382605163141518161494337 であり素数ですから、巡回群(cyclic group)です。 つま…
シュノア署名(Schnorr Signature) シュノア署名を群の言葉で書きます。 秘密鍵と公開鍵の生成 STEP1 有限体 と素数位数lのベースポイントを生成する。 STEP2 乱数を秘密鍵とし、 を公開鍵とする。 STEP3 H()をハッシュ関数とし公開する。 署名 STEP1 メッセ…
以下の関数の機能を見てみましょう。 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 secp256…
ECDSA の秘密鍵は1以上、群Gの位数未満です。 secp256k1 の群Gの位数は L = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 ですが、256bitの正の値skをランダムに取り(0以上)、値が0だった場合と、L以上だった場合、値を取り…
前回の記事では、secp256k1ライブラリでは署名のsの値は値が小さい方を使うから注意せよと書きました。 ECDSA(secp256k1)での署名と検証をswiftで行う(secp256k1swiftライブラリ使用) - Pebble Coding 関数リストをよくみてみると、 secp256k1_ecdsa_signatu…
前回、pythonで行なったECDSA(secp256k1)での署名と検証をswiftで行なってみます。 拙作 secp256k1swift GitHub - pebble8888/secp256k1swift: secp256k1 by pure swift を用いてみます。 ちなみに、このライブラリはbitcoinのC言語で書かれたライブラリ Git…
ECDSA(secp256k1)での署名と検証をpythonで行ってみます。 まずコードです。 ちなみにpython3です。 #!/usr/bin/env python # # secp256k1 # http://www.secg.org/SEC2-Ver-1.0.pdf # import sys import hashlib sys.setrecursionlimit(1500) b = 256 # q is…
ECDSAでの署名と検証をrubyで行います。 ECDSAの仕様はこちらです。 ECDSA(楕円曲線デジタル署名アルゴリズム)の概要 - Pebble Coding それではコードです。 #!/usr/bin/env ruby require 'ecdsa' require 'securerandom' require 'digest' def bin_to_hex(s…
$ irb irb(main):001:0> require 'ecdsa' => true irb(main):002:0> require 'securerandom' => true irb(main):003:0> group = ECDSA::Group::Secp256k1 => #<ECDSA::Group:secp256k1> 法素数 irb(main):005:0> group.field.prime => 115792089237316195423570985008687907853269984</ecdsa::group:secp256k1>…
secp256k1の体演算の最適化手法として、x,yが法素数q未満であることと256bit値の範囲内であることを用いて、 256bitサイズの値を9個の26bit値と1つの22bitの値(9*26+22=256bit)に分割する手法があります。 法素数q=0x FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF F…
secp256k1における逆数つまり1/aの計算方法を解説します。 法素数qに対して、が1/aとなります。 なぜなら 最後の等号は、フェルマーの小定理を使っています。 やることはaをq-2回ベキ乗することです。 pythonでq-2を2進表現してみましょう。 >>> q = 2 ** 25…
secp256k1における平方剰余計算を考えてみます。 secp256k1の法素数 はこの形をみてわかる通り、なので、 この記事mod p での平方剰余を計算する(p mod 4 = 3の場合) - Pebble Coding で示したように、解は(存在する場合は) と書けます。 コンピュータで計算…
ビットコインで使われている楕円暗号 secp256k1 をpythonで実装してみます。 なお、動作確認にはopensslを用います。 こちら secp256k1仕様 - Pebble Coding で示したように、計算効率を考えなければpythonで実装するのは割と容易です。 #!/usr/bin/env pyth…
secp256k1に関するメモです。 後ろから二番目のkは数学者Neal Koblitzのkらしいです。 曲線 法素数 = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 11579208923731619542357098500868790785326998466564056403945758400790…
どうやらビットコインでは署名に楕円曲線暗号が使われているらしいです。 楕円曲線暗号というのはRSA暗号と同じ非対称型の暗号で秘密鍵と公開鍵のペアからなります。 秘密鍵は自分だけが知っている状態にし、公開鍵は他人に公開します。 ビットコインとは何…
