Pebble Coding

プログラマーの作業メモ

secp256k1

ECDSA(secp256k1)での署名と検証をpythonで行う(外部ライブラリ使用なし)

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(secp256k1)での署名と検証をrubyで行う(ecdsaライブラリ使用)

ECDSAでの署名と検証をrubyで行います。 ECDSAの仕様はこちらです。 ECDSA(楕円曲線デジタル署名アルゴリズム)の概要 - Pebble Coding それではコードです。 #!/usr/bin/env ruby require 'ecdsa' require 'securerandom' require 'digest' def bin_to_hex(s…

ruby rcdsa gemを用いたsecp256k1の鍵ペア生成

$ 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における体演算の最適化

secp256k1の体演算の最適化手法として、x,yが法素数q未満であることと256bit値の範囲内であることを用いて、 256bitサイズの値を9個の26bit値と1つの22bitの値(9*26+22=256bit)に分割する手法があります。 法素数q=0x FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF F…

secp256k1における逆数計算

secp256k1における逆数つまり1/aの計算方法を解説します。 法素数qに対して、が1/aとなります。 なぜなら 最後の等号は、フェルマーの小定理を使っています。 やることはaをq-2回ベキ乗することです。 pythonでq-2を2進表現してみましょう。 >>> q = 2 ** 25…

secp256k1における平方剰余計算

secp256k1における平方剰余計算を考えてみます。 secp256k1の法素数 はこの形をみてわかる通り、なので、 この記事mod p での平方剰余を計算する(p mod 4 = 3の場合) - Pebble Coding で示したように、解は と書けます。 コンピュータで計算する場合は、次の…

ビットコインで使われている楕円暗号 secp256k1 をpythonで実装してopensslで確認してみる

ビットコインで使われている楕円暗号 secp256k1 をpythonで実装してみます。 なお、動作確認にはopensslを用います。 こちら secp256k1仕様 - Pebble Coding で示したように、計算効率を考えなければpythonで実装するのは割と容易です。 #!/usr/bin/env pyth…

secp256k1仕様

secp256k1に関するメモです。 後ろから二番目のkは数学者Neal Koblitzのkらしいです。 曲線 法素数 = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 11579208923731619542357098500868790785326998466564056403945758400790…

ビットコインでは楕円曲線暗号secp256k1が使われている

どうやらビットコインでは署名に楕円曲線暗号が使われているらしいです。 ビットコインは楕円曲線暗号の勉強を始める何年も前から所有していますが、知らなかった。 楕円曲線暗号というのはRSA暗号と同じ非対称型の暗号で秘密鍵と公開鍵のペアからなります。…