Pebble Coding

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

ed25519

go言語実装のed25519のベンチマークを測定してみる

go言語によるed25519実装は2種類あるようですが、こちらにあるもので調べてみました。 GitHub - Bytom/bytom: Official Go implementation of the Bytom protocol go言語では単体テストにベンチマーク機能が組み込まれており、簡単にベンチマークが取れるよ…

mod pでの平方剰余を計算する(p mod 8 = 5) その2

www.pebblewind.com こちらの記事で、平方剰余を計算しましたが、ed25519 においては、aは u/v という形になっています。 u,vの計算量は少ないので、計算効率をあげるため、u,vを用いた掛け算になるように変形します。 (フェルマーの小定理) (余分な項が8の…

go 言語 でed25519ライブラリを使う

go の標準ライブラリにはed25519は含まれない($ go list std | grep cryptoで確認できます。)ため、 以下のライブラリを使います。 github.com 以下のコマンドでインストールします。 $ go get -u golang.org/x/crypto/ed25519 a.goというファイル名で以下を…

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…

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

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

ed25519をswiftで実装してみる

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

ed25519のpython実装を紐解く その3 暗号編テスト

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

ed25519のpython実装を紐解く その2 暗号編キーペア生成からベリファイまで

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

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

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

Twisted Edward曲線における加法

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

curve25519とed25519の同等性

curve25519とは、 のことであり、 ed25519とは、 のことである。 これは単純な変数の置き換えで同等性が示せる。 ただし、ed25519の方が加法定義で場合分けをする必要がなく、扱いやすい。 とし、 とする。 を代入して計算すると、 となる。 xをで置き換える…

edward曲線における加法

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

エドワード曲線とツイストエドワード曲線の形

2007年のエドワードさんの論文(http://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf) から、エドワード曲線と名付けられた がどのような形をしているのか見てみましょう。 まずはa=1.0 2本の直線になってしまいま…