Pebble Coding

プログラマーの作業メモ

数学英単語

数学書に出てくる英単語がわかりずらいので、リストしておく。 homomorphism 準同型 endomorphism 自己準同型 isomorphism 同型 automorphism 自己同型 injective 単射 (行き先が被らない関数) surjective 全射 (行き先を全て埋め尽くす関数) closure 閉包 a…

swiftとアセンブラ

swiftコードがどのようにアセンブラに出力されているのかをみてみましょう。 Xcodeのプロジェクトで、コマンドラインプロジェクトを生成し、以下のソースをmain.swiftに書き込みます。 import Foundation func plus(_ a: Int64, _ b: Int64) -> (Int64) { re…

ラグランジュの定理

ラグランジュの定理を解説します。 ここでは有限群のみを考慮対象とします。 まず、群の定義です。 有限個の元からなる集合Gを考えます。 集合Gから2つの元を選び、に対してを作用させて結果rを得るという操作(演算)を定義します。 この演算をここではで表…

準同型写像に関する元の数についての定理

準同型写像に関する元の数についての定理を直観的に理解したいと思います。 G,Yを有限群とする。 群Gから群Yへの準同型写像(Homomorphism)を とする。 すなわち、 をGの任意の元として、 が成りたちます。 ここで左辺のプラスは群Gでの演算,右辺のプラスは群…

楕円曲線の有理点の数の求め方 schoof アルゴリズムその1

上の楕円曲線 の有理点個数の求め方です。 ここではSchoofアルゴリズムの理解を目的とし、少しづつ理解を進みます。 まず使うのはHasseの定理です。 Hasse-Weilの定理(楕円関数限定版) - Pebble Coding 有理点の数を#Eで表すと、 が成り立ちます。 tはある範…

素体を拡大する

素体 を拡大してみます。 を拡大して、拡大体 を作ることにします。 体の拡大には既約多項式を使います。 ここでは、規約多項式を使います。 を作る場合は素数3で割った余りを使うというルールでした。 の元は{0, 1, 2}の3つですが、加法の単位元が0で乗法の…

BabyStep GiantStep法(BSGS法)

DLP問題を解くアルゴリズムの一つとしてBabyStep GiantStep法があります。 DLP問題とは、対称群の位数nに対して、生成元をg、群のある元をaとして、 を満たすxを求める問題です。 ここで、解はただ一つのみ必ず存在することは前提とします。 なので、解が存…

ネットワークハッシュレート

ビットコインの現在のネットワークハッシュレートはこちらによると https://blockchain.info/charts/hash-rate 30G * GHash/sec ビットコインキャッシュ BitcoinCash Network Hashrate Chart and Network Hashrate History Chart - CoinWarz 4G * GHash/sec …

Hasseの定理から導き出される補題

楕円曲線に限定した Hasse の定理 上の任意の楕円曲線の有理点の個数 の範囲は以下となる。 補題 楕円曲線 E () に含まれる点Pで、 となる m が Hasse の定理により定まる曲線の位数の区間 に唯一存在する時、 となる。 この補題は Hasse の定理から導かれま…

256bitの暗号化はどの程度強固なのか

256bit(=32バイト)の暗号化はどの程度強固なのかというのを説明したYouTubeの動画が面白かったのでリンクを貼っておきます。 www.youtube.com 内容としては、まず、8つの大きさに分解します。 それぞれ、M1, M2, M3, ..., M8と表すことにします。 そして、 …

リカバリーIDについて小さな例を用いて実感する

一つ前の記事では署名のリカバリーIDについて書きました。 Ethereum の署名とBitcoin の署名 - Pebble Coding が、いまいち分からんと思うので、実感するため、小さい例で考えてみます。 曲線はsecp256k1と同じ、 を使いますが、法素数は31=pを使います。 こ…

Ethereum の署名とBitcoin の署名

Ethereum の署名の仕様はイエローペーパー https://ethereum.github.io/yellowpaper/paper.pdf に記載されています。 n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 Rは点でx座標とy座標を持ちます。 n は secp256k1…

base58checkフォーマット出力の先頭文字が決まる理由

base58checkフォーマット出力の先頭の文字が何になるかって教科書にはよく書かれていますが、 どうやって算出しているのか気になったので、確かめてみました。 取りうる最小値と最大値を与えれば出力値の範囲が分かるという理屈です。 ここでは最小値を0x0、…

python bytesメモ

>>> a = bytes([0xff] * 8) >>> print(a) b'\xff\xff\xff\xff\xff\xff\xff\xff' >>> int.from_bytes(a, 'big') 18446744073709551615 >>> (18446744073709551614).to_bytes(9, 'big') b'\x00\xff\xff\xff\xff\xff\xff\xff\xfe'

base58check フォーマットとビットコインアドレス

bitcoinでは色々なところでbase58checkフォーマットが使われています。 base58checkフォーマットを行う関数をb58checkとして実装してみたのが以下です。 ここでは、公開鍵から、メインネットのビットコインアドレスを計算しています。 ビットコインアドレス…

macOS に bitcoin explorer をインストールする

$ brew install bx 秘密鍵を生成しファイルに出力(32バイトhex) $ bx seed | bx ec-new > private_key $ cat private_key 4a1bdbb5164f0b096ab56ec74399222e44d13b2a93d5ad7fe8a341bbfa197c46 秘密鍵から公開鍵を計算しファイルに出力(33バイトhex) 先頭が0x…

ripemd160をpythonで試す

ripemd160は160ビット(=20バイト)の値を返すハッシュ関数です。 pythonでは以下で計算できます。 #!/usr/bin/env python import hashlib h = hashlib.new('ripemd160') h.update(b"abc") r1 = h.hexdigest() print(r1) print("len "+str(len(r1))) 8eb208f7e…

base58をpythonで試す

base58は大まかに言ってbase64を改良したものです。 base64は64個の文字とパディングに=(イコール)を使うものです。WEBプログラマなら説明は不要でしょう。 base58はbase64から小文字のl(エル),大文字のI(アイ),大文字のO(オー),0(数字のゼロ),+(プラス),/(…

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

シュノア署名(Schnorr Signature) シュノア署名を群の言葉で書きます。 秘密鍵と公開鍵の生成 STEP1 有限体 と素数位数lのベースポイントを生成する。 STEP2 乱数を秘密鍵とし、 を公開鍵とする。 STEP3 H()をハッシュ関数とし公開する。 署名 STEP1 メッセ…

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

BeautyChain (BEC)などに実装された batchTransfer に見つかったぜい弱性 CVE-2018-10299 medium.com について試してみました。 remix で検証しました。 この 0x8000...0000 に2を掛けると、solidify のuint256実装では、桁あふれした分が差し引かれ、_amoun…

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 secp256…

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

ECDSA の秘密鍵は1以上、群Gの位数未満です。 secp256k1 の群Gの位数は L = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 ですが、256bitの正の値skをランダムに取り(0以上)、値が0だった場合と、L以上だった場合、値を取り…

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

前回の記事では、secp256k1ライブラリでは署名のsの値は値が小さい方を使うから注意せよと書きました。 ECDSA(secp256k1)での署名と検証をswiftで行う(secp256k1swiftライブラリ使用) - Pebble Coding 関数リストをよくみてみると、 secp256k1_ecdsa_signatu…

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

前回、pythonで行なったECDSA(secp256k1)での署名と検証をswiftで行なってみます。 拙作 secp256k1swift GitHub - pebble8888/secp256k1swift: secp256k1 by pure swift を用いてみます。 ちなみに、このライブラリはbitcoinのC言語で書かれたライブラリ Git…

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…

python メモ

pythonメモ range range(5) -> [0, 1, 2, 3, 4] ord ordは1文字を整数のコードポイントに変換する関数 ord('0') -> 48 (=0x30)

python3 で hmac-sha512を計算する

python3.6.4を用いています。 import hmac import hashlib sk = str("secret").encode('utf-8') msg = str("message").encode('utf-8') sig = hmac.new(sk, msg, hashlib.sha512).hexdigest() print(sig) print(len(sig)) 1bba587c730eedba31f53abb0b6ca589e…

bitcoin-cli コマンドまとめ その2

ウォレットのダンプ $ bitcoin-cli dumpwallet a.txt { "filename": "/Users/pebble8888/Library/a.txt" } 第2引数には出力先のファイル名をいれます。 約4000行のファイル名が出力されました。先頭を少し加工して見てみます。 (ちなみにtestnet環境のもので…

postgres インストール後に行うセットアップ for rails

$ pg_ctl -D /usr/local/var/postgres start && brew services start postgresql $ psql postgres # create role myuser with login password mypass; # alter role myuser createdb; # \q; ruby用の環境変数 DATABASE_URL=postgres://myuser:mypass@{hostna…