Crypto Currencyの公開されているソースリポジトリと実装言語をまとめてみました。(2017年12月) ついでに、githubで管理されているものはissueの数を数えて見ました。 ご指摘ありましたら教えていただけると助かります。 Bitcoin(BTC or XBT) 承認時間: 10 …

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…

平方剰余 http://nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2011/11.pdf について簡単に説明しておきます。 整数aと整数pを与えた時に の式を満たす解xは存在する場合と、存在しない場合があります。 解が存在する時、a は p を法…

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

の素体上の有理点の数を調べます。 楕円曲線Eの有理点の数を#Eと書きます。 素数pを3で割って2余る場合は、有理点の数は無限遠点を含み、#E= p + 1 であることが知られています。 の場合の、有理点の数をpythonで調べた結果がこちらです。 p, p mod 3, #E 2,…

素体は体であり、元は{0, 1, ..., p-1}のp個あります。 素体という時、pは素数です。 体なので、加法と乗法について閉じているわけですが、乗法演算の部分のみを取り出した群のことを、 素体の乗法群と呼びと書きます。 この乗法群には加法の単位元0は含まれ…

群論における写像の定義メモ。 準同型写像、同型写像、自己同型写像。 写像というのはプログラムで考えると、引数を一つ入力として持ち、戻り値を一つ返す関数だとイメージすることができますが、 要するに関数f(x)のことです。 準同型写像 関数f(x)が f(x)f…

Bitcoin フルノードを立てるのに必要なものをメモしておきます。 最低限必要なスペック 最新バージョンのWindows, Mac OS X, Linuxが動作するするハードウェア 145GB の空きディスクスペース 2GBメモリ 400Kbpsのアップロードスピードの通信回線 高いアップ…

NSView をvoidに変換するのはObjective-Cですが、これはキャストするだけです。 - (void)convert:(NSView*)view { void* ptr = (void*)view; } void*はswiftではUnsafeMutableRawPointerと表現されます。 func convert(p:UnsafeMutablePointer) { let view:N…

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

楕円関数 の形式の加法公式をメモしておきます。 アフィン座標での加算公式 1) PとQが同一点の場合。 2) の場合 これをアフィン座標(affine coordinate)と呼びます。 素体 上の割り算は掛け算に比べて10倍〜50倍くらいの計算量なので、 割り算の回数を減らす…

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

前回( ed25519をswiftで実装してみる - Pebble Coding )は、swiftでed25519を実装しましたが、愚直なアルゴリズムで遅いので実用に耐えうるものではありませんでした。 今回は、実用に耐えうるアルゴリズムで実装しました。 github.com 実質、SUPERCOP https…

Xcode で Module 'xxx' was not compiled for testing メッセージが出た時の対処法です。 リリースビルドで単体テストを実行しようとすると発生します。 Enable Testability を Yes に変更すればOKです。

ed25519をswiftで実装してみます。 pythonのリファレンス実装 https://ed25519.cr.yp.to/software.html をそのままswiftに置き換えただけのものです。 ソースはこちら。 github.com swiftには標準ライブラリにBigInt実装がありませんので、pure swift で実装…

ed25519のpython実装を紐解く 暗号編 その１(キーペア生成からベリファイまで) - Pebble Coding リファレンス実装では、sign.inputというファイルの中に:区切りでの 秘密鍵,公開鍵,メッセージ,署名+メッセージのセットがhex表示で1024個入っています。 例と…

どうやらビットコインでは署名に楕円曲線暗号が使われているらしいです。 楕円曲線暗号というのはRSA暗号と同じ非対称型の暗号で秘密鍵と公開鍵のペアからなります。 秘密鍵は自分だけが知っている状態にし、公開鍵は他人に公開します。 ビットコインとは何…

前回 ed25519のpython実装を紐解く その１数学編 - Pebble Coding はed25519のpython実装の数学編をやりましたが、今回は暗号編です。 暗号部分の関数を見ていきます。 これらの計算手順は前回と同じRFCに記載されています。 概念図を書いてみました。 b = 2…

ed25519のpythonによるリファレンス実装を解説してみます。 pythonのリファレンス実装はこちらです。 https://ed25519.cr.yp.to/python/ed25519.py 数学的な関数の解説のみ簡単に行います。 詳しくはこのブログの他の記事に記載があります。 使う楕円曲線はe…

Twisted Edward曲線 において、曲線上の２つの点 の加算後の点を次のように定義する。 この点は代数計算によって、Twisted Edward曲線上の点になることを確かめることができる。 が、計算は長く厄介なので、計算方法を記しておく。 計算のコツとしては常にの…

CoreAudio/swift3で録音を行うサンプルです。 iPhoneのマイクから取得した音声データをレベル値に変換して画面に表示します。 import Foundation import AVFoundation import AudioUnit class MyAudioRecorder: NSObject { var level: Float = 0.0 var frame…

iOS11 Audio関連で追加された機能で気になったものをまとめておきます。 内容はここで見ることができます。 今年からApple Developer登録していない方でもVideoが見られるようになったようです。 (WWDC 2017に見た新しい教材のあり方｜MacFan) developer.app…

指定の長さのsin波のWAVファイルを簡単に作る方法をメモしておきます。 Audacityというフリーのアプリケーションを使います。 Audacity ® | Free, open source, cross-platform audio software for multi-track recording and editing. Mac/Windows/Linux版…

Xcodeのデバッガではswiftオブジェクトの中身を表示しても生のデータを表示してくれず、デバッグしづらいです。 (C/C++なら大丈夫ですが。) あらゆるものを16進Hex表示の文字列にしてデバッグに使いましょう。 public protocol HexRepresentable { func hexD…

一つ前の記事 python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Coding で有限体での楕円曲線の群構造をpythonを使って実験的に調べました。 分かったことは、 - 群の位数=群の元の個数=有理点の個数(無限遠点を含む)である。 - 群の位数…

ここでは、有限体 (p=5) 楕円曲線 (a=0,b=1,c=1) の有理点をpythonで調べています。 有理点の数は9です。(無限遠点を含む) 無限遠点はOと出力しています。 加法公式を用いて、有理点{P1, P2, ... P8}を2倍,3倍,...,9倍した点も示しています。 この計算の途中…

matplotlibをインストールします。 ~$ pip install matplotlib %matplotlib inline import numpy as np import matplotlib.pyplot as plt # 乱数を生成 x = np.random.rand(100) y = np.random.rand(100) # 散布図を描画 plt.scatter(x, y) plt.show() うま…

B-smooth と B-power-smooth の概念を押さえておきます。 B-smooth 任意の自然数Nを素因数に分解すると次の形になります。 ここで、はi番目の素数 {2, 3, 5, 7, 11, ...}を表します。 は0以上の整数です。 ここで最も大きい素数として、 NをB-smoothであると…

大きな合成数を素因数分解(factorization in prime numbers)するアルゴリズムの一つにポラードのp-1法があります。 ポラードの (ロー)法とは別モノなので混同しないようにしましょう。 因数分解したい合成数をnとします。 の時、素数pを求めたいです。qはと…