Pebble Coding

プログラマーの作業メモ

secp256k1に関するメモ

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

swift で 実用に耐えうる ed25519 を実装してみる

前回は、swiftでed25519を実装しましたが、愚直なアルゴリズムで遅いので実用に耐えうるものではありませんでした。 今回は、実用に耐えうるアルゴリズムで実装しました。 github.com 実質、SUPERCOP https://bench.cr.yp.to/supercop.html によるC言語実装…

Xcode で Module 'xxx' was not compiled for testing メッセージが出た時の対処法

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

ed25519をswiftで実装してみる

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

ed25519のpython実装を紐解く 暗号編 その2

リファレンス実装では、sign.inputというファイルの中に:区切りでの 秘密鍵,公開鍵,メッセージ,署名+メッセージのセットがhex表示で1024個入っています。 例として3行目のデータを取り出します。 c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0…

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

どうやらビットコインでは署名に楕円曲線暗号が使われているらしいです。 ビットコインは楕円曲線暗号の勉強を始める何年も前から所有していますが、知らなかった。 ビットコインとは何か? 第3回:ビットコインの仕組み(アドレスの作成から送金まで) - ビット…

ed25519のpython実装を紐解く 暗号編 その1

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

ed25519のpython実装を紐解く 数学編

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

Twisted Edward曲線における加法

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

swift3でCoreAudioを使う 録音編

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

iOS11 Audio関連機能(2017)

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

指定の長さのsin波のWAVファイルの作り方(モノラル、ステレオ)

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

swift であらゆるデータをHex表示してデバッグする

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

楕円曲線上の離散対数問題(ECDLP)

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

python で有限体Fpでの楕円曲線上の有理点の群構造を調べる

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

macOS 10.12 jupyer notebook でグラフを描画する(Fpにおける楕円曲線の解の個数)

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

ポラードのp-1因数分解法

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

体の標数(characteristic)

体Kにおいて、n個の1の和 1+1+…+1 が0となるような整数が存在するとき、その最小値を体Kの標数といい、ch(K)と表します。 いくつ加えても0にならない時は標数が0と定めます。 標数は0か素数です。 有理数体Qの標数は0です。 有限体の標数はpです。

体の拡大

拡大体 体とは大雑把に言って、加法と乗法に対して演算が閉じている数の集合のことを指します。 有理数Q, 実数体R, 複素数体Cは全て加法と乗法において演算が閉じているので体と呼べます。 これらは数の集合としては数の存在の密度が高すぎますね。 整数Zと…

メモリ破壊系バグの潰し方 その2

ヒープアロケートしていない領域に書き込む 初期化していないポインタに対して、ヒープアロケートせずデータを書き込もうとしています。 #include <stdio.h> #include <string.h> typedef struct { int x1; char* x2; } Data; static int f(){ Data d; d.x1 = 1; memset(d.x2, 0</string.h></stdio.h>…

巡回群

巡回群とはただ一つの元だけを使い、繰り返し演算することにより、全ての元を生成できる群のことである。

約数記号

整数 a が 整数 b を割り切るとき と書きます。 例: 整数 a が整数 b を割り切らないとき と書きます。 例: であるとき、b は a の倍数であり、a は b の約数であるといいます。

macOS sierra 10.12 で Jupyter Notebook を立ち上げるまで

macOS sierra 10.12 に Jupiter Notebook をインストールする。 ~$ brew install python ~$ brew link python ~$ python --version Python 2.7.10 ~$ which python /usr/bin/python ~$ ls -l /usr/bin/python -rwxr-xr-x 1 root wheel 66576 4 29 08:36 /usr…

Hasse-Weilの定理(楕円関数限定版)

Hasse-Weilの定理を楕円関数に限定した形で書くと、 Cが有限体 上定義された非特異な楕円曲線であるとき、 C上の に座標を持つ点の数をと定義すると、 不等式だが、任意の楕円曲線に関するものだというのがすごい。 これを実感するために、pをくらいの数とす…

Mordellの定理(位数2の有理点をもつ曲線の場合)

Cを で与えられる3次曲線とする。ここでa,bは整数。 このとき曲線上の有理点のなす群C(Q)は有限生成アーベル群である。 解(x,y)が無限個、有限個どちらの場合でも、有限個の元から出発し、群演算によって、全ての元を作り出せるといっている。

有限アーベル群と有限生成アーベル群

有限アーベル群と有限生成アーベル群の違いを直感的に説明する。 アーベル群の正確な定義は述べないが、一つの演算(加法や乗法と呼ぶ)が定義された数の集合としておく。 有限アーベル群とは元の数が有限であるアーベル群である。 例えば、加法として2つの整…

Nagell-Lutzの定理

Nagell-Lutzの定理 を整数係数a,b,cを持つ非特異3次曲線とする。 P=(x,y)を有限位数の有理点とする時 x,yは整数である。 これは、整数ではない有理点が存在するときは、無限位数となるということも同時に示している。 例えば、 (a=0, b=0, c=2)の場合を考え…

楕円曲線暗号 情報リンクまとめ

EdDSAのWiki EdDSA - Wikipedia EdDSAアルゴリズムのRFC 8032 RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA) Ed25519のpythonによるサンプル実装、主要論文のリンク https://ed25519.cr.yp.to/software.html SUPERCOPによる様々な暗号のC言…

RSA暗号化方式を紐解く その(2)

前回からの続きです。 暗号化は の式によって行い、 復号化は の式によって行います。 これがうまく動作する仕組みを知るにはどうやってe, d, nを選ぶかということを知る必要があります。 理論の根幹をなす定理がフェルマーの小定理を一般の整数に拡張したオ…