Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

ECDSA署名とECSchnorr署名の概略メモ

ECDSA署名とECSchnorr署名の概略メモです。 群や体の演算など、些細な部分は省略し、核となるロジックだけを記載しています。 楕円曲線上の点は大文字、スカラー値は小文字で表現します。 点Aのx,y座標はと表現します。 ECDSA署名 <共有情報> G:ベースポイン…

grin のトランザクションフローのメモ

こちらにgrinのトランザクションフローについての図が上がっていたので、テキストに落としておく。 まだソースを追っているところだったが、このフロー図で理解が進みやすくなる気がする。 この図はどこから入手したんだろ。 MimblewimbleとGrinのトランザク…

rust ?(question mark)演算子

rustでの?演算子はResultの処理を簡略化した機能を持つ。 戻り値としてResultを持つ関数内で利用することができ、 Resultを生成する式の後ろにつけることができる。 ?をつけた場合は式の結果がSuccessだった場合はその値をunwrapして処理を継続する。 Error…

grin の外部依存 crate

grin はかなりの数の外部 crate を利用しています。 セキュリティ上重要な部分は当然自前実装かつセキュリティ監査をしたらしいです。 rust は脆弱性が入り込みにくいとはいえ、何らかの不備が見つからないとも限らないので、まさに実験的プロジェクトです。…

rust の trait

rust の trait は大雑把に言って、swift の protocol に相当する。 以下サンプルを見てみよう。 fn main() { let mut bicycle = Bicycle { pos: 0 }; bicycle.forward(); } struct Bicycle { pub pos: i32 } trait Movable { fn forward(&mut self); } // Bi…

rust をios用にビルドする

ios の target を追加してからビルドします。 $ rustup target add x86_64-apple-ios $ cargo build --target x86_64-apple-ios cargo.toml [lib] name = "blake2rustios" crate-type = ["staticlib"] これでstatic libraryが生成されるようです。 他、細か…

secp256k1_zkpライブラリの関数

secp256k1_zkpライブラリの関数概要のメモです。 スカラー値は小文字、楕円曲線上の点は大文字で表現します。 未調査の部分は?としてあります。 /// seedを指定してハッシュ関数を通した点を返す // 同じseedを指定した場合、いつも同じ点が返されることが保…

secp256k1 ライブラリの関数

secp256k1のC89実装のライブラリの関数のメモです。 GitHub - bitcoin-core/secp256k1: Optimized C library for EC operations on curve secp256k1 秘密鍵はスカラー値であり、sと表現することにします。 sは1以上secp256k1の群位数N未満である必要がありま…

MimbleWimbleプロトコル情報リンク

MimbleWinbleペーパー 2016年 http://diyhpl.us/~bryan/papers2/bitcoin/mimblewimble.txt Block Stream社のAndrew Poelstra氏によるMimbleWimble解説の日本語訳 btcnews.jp GrinのMimbleWinble概要解説 grin/intro_JP.md at master · mimblewimble/grin · G…

macOS にrust(stable版, nightly版)をインストールする

現在の最新バージョンは1.32です。 stableな機能のみしか使わない場合は、brew でインストールしてもよいです。 $ brew install rust nightly の機能を使う場合は rustup を使います。 まずは、brew でインストールしたrustをアンインストールします。 $ bre…

rust 定数の2次元配列宣言方法

C言語とは配列長部分の定義順序が逆になります。 3 x 2の2次元配列 const A: [[u8; 2]; 3] = [ [0x01, 0x02], [0x03, 0x04], [0x05, 0x06] ]; プログラミングRust作者: Jim Blandy,Jason Orendorff,中田秀基出版社/メーカー: オライリージャパン発売日: 2018…

rust で並列処理

rust は並列処理が作りやすい言語である。言語レベルで完全にスレッド安全性が担保されていると言って良いだろう。 以下は0から15の値の合計を4つのスレッドを使って計算するrustのソースである。 extern crate crossbeam; fn main() { let mut sum0: u64 = …

macOS で grin のCPUマイニングを試みる

macOS grin-miner でCPUマイニングを試したときの手順メモです。 結果的にハッシュパワーが足りずマイニングはできませんでした。 ビルド grin 本体とgrin-minerをクローンしてビルドします。 $ git clone https://github.com/mimblewimble/grin.git $ cargo…

bitcoin ウォレットダンプの値をpythonで計算してみる

ウォレットをテキストファイルに出力する。 $ bitcoin-cli dumpwallet pebble8888wallet.txt { "filename": "/Users/pebble8888/Library/Application Support/Bitcoin/pebble8888wallet.txt" } $ cat pebble8888wallet.txt # Wallet dump created by Bitcoin…

secp256k1 の有理点のxの小さい方から100個の点の座標を求める

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のベースポイントの謎

secp256k1のベースポイントの性質をみていきます。 有理点(x, y)はおよそ256ビットの範囲内で均等に値がばらけていると考えられます。 ベースポイントGの倍数 を計算したときのx, yの値はおよそ256ビットの値がランダムに並んだようになりますが、たまたま端…

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

macOS 10.14.2 mojave に bitcoin core をインストールしてみます。 testnet で550MBのプルーンモードで起動させるので、ディスク容量の空き容量はは2GBあればよさそうです。 (550MBを指定しても2GBのサイズになる理由は分かっていません。) mainnet で起動…

SageMath 入門

ほぼpythonと同じ構文と考えておけばよいです。 100未満の素数を出力する sage: x = 1 sage: while x < 100: ....: if x.is_prime(): ....: print(x) ....: x = x + 1 ....: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 プログ…

SageMath のインストール方法と使い方

数学の研究に便利な SageMath のインストール方法と使い方です。 macOSの場合です。 こちらのページから以下のファイルをダウンロードします。 http://ftp.yz.yamagata-u.ac.jp/pub/math/sage/osx/intel/index.html sage-8.5-OSX_10.14.2-x86_64.tar.bz2 解…

楕円曲線における離散対数問題

例として、 を考えます。 有理点の数(群位数)は31で素数です。 点の加法群の位数が31ということは部分群が存在せず、巡回群つまり一つの元を足し合わせることで全ての元が表現できるということです。 全ての点が位数31となります。 ちなみに、無限遠点O以外…

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

y'についてもみていきます。 を使うと、 残りのフロベニウス写像部分は したがって、 分母を揃え、分子だけ取り出したものがで割り切れるかどうかを調べます。 コンピュータ計算上は分母にyが含まれるか否かの分岐が面倒なので、 分子だけの計算結果にyが含…

macOS mojave にmysql8ではなくmysql5.7をインストールする

普通に $ brew install mysql とするとmysql8がインストールされてしまいます。 mysql5のデータベースを8にマイグレートする余裕などありません。 mysql5.7をインストールするには以下のようにします。 $ brew install mysql@5.7 コマンドパスを通すため、.b…

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

アルゴリズムの実際の計算をもう少し詳しくみていきます。 が成り立つかどうかの計算をみていきます。 まず、この式はがreductionの最終結果がxのみの多項式で分母と分子があるということを意味します。 lは奇数なのでにはyは入らないです。 そして、で割り…

macOS の git gc で warning: unable to unlink '.git/objects/ff/xxx': Operation not permitted

macOS で git gcしたときに、warning: unable to unlink '.git/objects/ff/xxx': Operation not permitted というメッセージが表示される現象の対応方法です。 .git ディレクトリに移動して、以下のコマンドを打ちます。 chflags -R nouchg * error: failed …

楕円曲線のn等倍点の多項式

楕円曲線の点(x, y)をn倍した点(n torsion point)はx,yの具体的な多項式で表せます。 としたとき、n倍点の座標(X, Y)は以下となります。 はdivision polynomialと呼ばれており、以下の漸化式で定義されます。 はmが奇数のとき、xの任意次数の関数。 mが偶数…

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

楕円曲線の有理点の数の求め方 schoof アルゴリズムその1 - Pebble Coding の続きです。 を素数 l=2, 3, 5, ...について計算するアルゴリズムは以下の通りです。 素体, 楕円曲線とします。 まず、l=2の場合は、の値が1かどうか調べます。 ここでgcdはxの素…

中国剰余定理で2式の場合の解を求める

中国剰余定理とは、2式の場合を互いに素とするとき、 を満たす整数xがの範囲内にただ一つ存在するというものです。 xの求め方はこうです。 まずを満たす(p, q)のセットを一つ求めます。 以下のアルゴリズムを用います。 37x+10y = 1 を拡張されたユークリッ…

37x+10y = 1 を拡張されたユークリッドの互除法で解いてみる

37と10は違いに素なので、は整数解(x, y)を持ちます。 この解を求める方法を拡張されたユークリッドの互除法と呼ぶようです。 具体的には、の形でaをbで割った余りをaに置き換える操作を余りが0になるまで繰り返します。 とおきます。 とおきます。 とおきま…

素体上の1変数多項式の商と余り

こちら 多項式の割り算、商と余り - Pebble Coding の1変数多項式の商と余りを拡張し、素体上での計算をみてみます。 (nがxの最大次数)を、 (mがxの最大次数)() で割ることが考えるとき、以下のようにしてxの最大次数を下げていけばよさそうです。 例えば、 …

xcode address sanitizerでヒープ破壊箇所を検出する

xcode address sanitizerでヒープ破壊箇所を検出してみます。 - (void)viewDidLoad { [super viewDidLoad]; uint8_t* a = malloc(16); memset(a, 0, 17); } 普通に実行してみると、 どこで破壊されているのか分かりませんね。 これをソースの行レベルで検出…

プライバシーポリシー

お問い合わせ

スポンサーリンク