Pebble Coding

プログラマーの作業メモ

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

前回は、swiftでed25519を実装しましたが、愚直なアルゴリズムで遅いので実用に耐えうるものではありませんでした。
今回は、実用に耐えうるアルゴリズムで実装しました。

github.com

実質、SUPERCOP https://bench.cr.yp.to/supercop.html によるC言語実装をswiftにポーティングしたものになります。

ちなみに、
opensslでのC言語実装
openssl/curve25519.c at master · openssl/openssl · GitHub

rustでの実装
https://github.com/isislovecruft/curve25519-dalek

goでの実装
GitHub - agl/ed25519: ed25519 for Go

などがgithubにありますが、全て、このあたりの実装をポーティングしたものになっているようです。

アルゴリズムの理論は、こちらの2つの論文を用いています。

https://ed25519.cr.yp.to/ed25519-20110926.pdf

https://eprint.iacr.org/2008/522.pdf

内容を詳しく紹介したいところですが、数式がたくさん出てきて、texでブログを書くのはなかなかしんどいので、概要だけつまみます。

  • キャリーを効率的に扱うため、255ビットを4 * 64bitではなく、 5* 51bitで扱う。
  • ベースポイントのスカラー倍関連の値を事前計算し、テーブルに持っておく。
  • 楕円関数の加法をx,yではなく、x,y,z,tの4つの変数を使う形のものを用いる。

パフォーマンス結果は、1024個の署名確認にかかった時間が、

Debugビルド: 558sec
Releaseビルド: 10sec

となりました。
これなら実用に耐えられそうです。