Pebble Coding

プログラマーの作業メモ

はてなブログをproにして独自ドメインに変更する

はてなブログの無料版はサブドメインのため、GoogleAdsenseを導入することができません。 そのため、はてなブログをproにして独自ドメインに変更した時の手順です。 まず、元のURLはこのようになっています。 http://pebble8888.hatenablog.com hatenablog.c…

twisted edwards curve でのaffine加算公式とprojective加算公式

Twisted Edward Curveでのコンピュータでの計算の最適化手法はいくつかありますが、 この記事では、projective座標系を使って、わり算の数をへらし計算量を押さえる手法を紹介します。 twisted edwards curve のaffine座標での加算公式その1は以下です。 式…

ed25519におけるcofactor=8

こちらの記事 ed25519のpython実装を紐解く その2 暗号編キーペア生成からベリファイまで - Pebble Coding で、ed25519の署名のロジックを検証しました。 8の倍数を使う意味が分かった気がしたので、それについて書きます。 結論からいうと、small subgroup…

iOSウォレットアプリ外部ライブラリ依存関係

外部ライブラリ依存関係 breadwallet/breadwallet-ios | |-- breadwallet/breadwallet-core | |- bitcoin-core/secp256k1 MIT | |-- breadwallet/nettle GNU nettle | crypt library sha1,sha2,sha3,sha256,sha512,twofish,salsa20, | rsa,pkcs1,hmac,ecdsa,…

素体上の楕円曲線の等分点をpythonで計算してみる

楕円曲線においてとなる点Pの集まりを等分点と呼びます。 左辺は点をn倍することを表し、右辺は無限遠点を表します。 python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Coding 以前使ったpythonスクリプトをちょっといじって計算してみま…

楕円曲線の点の2倍公式

楕円曲線の点の2倍公式を楕円曲線を簡単にして計算してみよう。 楕円関数の加法公式 - Pebble Coding で計算を簡単にするためa=0とする。2倍公式を得るにはP=Qとすれば良い。 すると、 が得られる。 3倍公式、4倍公式を求めていくと、xの有理式の次数が上が…

体論

定義 1 Kを体とする。任意の定数でない1変数多項式]に対し がありとなるとき、Kを代数閉体(algebraically closed field)という。 定理 1 Kが代数閉体で、fが の形である場合、 が存在し、である。 拡大体のゆるい定義 2 体Kにいくつかの元を添加して得られた…

楕円曲線の自己準同型

有限体 上の楕円曲線 上の有理点(x, y)を考える。 x座標,y座標はともに0以上p(素数)未満の整数。 2つの点に対する加法を以下で定義すると、この点と加法は群をなすことが知られている。 これを点の加法と呼ぶことにする。 楕円関数の加法公式 - Pebble Codi…

数学英単語

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

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以上だった場合、値を取り…