Pebble Coding

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

secp256k1仕様

secp256k1

secp256k1に関するメモです。 後ろから二番目のkは数学者Neal Koblitzのkらしいです。

曲線

{y}^2 = {x}^3 + 7

法素数

p = {2}^{256} - {2}^{32} - 977
= 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
= 115792089237316195423570985008687907853269984665640564039457584007908834671663
256ビット、10進で78桁

ベースポイント:

Bx = 0x79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
= 55066263022277343669578718895168534326250603453777594175500187360389116729240
256ビット、10進で77桁

By = 0x483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
= 32670510020758816978083085130507043184471273380659243275938904335757337482424
256ビット、10進で77桁

ベースポイントの位数(=素数)

L = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
= 115792089237316195423570985008687907852837564279074904382605163141518161494337
256ビット、10進で78桁

ゼロ点は無限遠点(O)となる。
python実装上は、無限遠点はx=0, y=0で表現する。

BをL倍すると最初に無限遠点になる。
L * G = O
コファクターは1なので、Lがこの曲線上の有理点の数(無限遠点を含む)であり、巡回群の位数である。

点P( x_1, y_1)と点Q(x_2, y_2)の加法公式

1) PとQのどちらかが無限遠点の場合、加算結果はもう片方の点。

2) Qが-Pと等しい、つまり x_1 = x_2, y_1 = -y_2の場合、加算結果は無限遠点。

3) PとQが同一点で y=0の場合、曲線の接線は垂直線になるので、加算結果は無限遠点。

4) PとQが同一点でy \ne 0の場合、次の2倍公式。
x_3 = {\nu}^{2} - 2 x_1
y_3 = {\nu} ( x_1 - x_3 ) - y_1
{\nu} = \frac {3 {x_1}^{2} } {2 y_1}

5) 上記以外( x_1 \ne x_2)は次式。
x_3 = {\lambda}^{2} - (x_1 + x_2)
y_3 = {\lambda} (x_1 - x_3) - y_1
{\lambda} = \frac {y_1 - y_2} {x_1 - x_2}

参考

Recommended Elliptic Curve Domain Parameters
http://www.secg.org/SEC2-Ver-1.0.pdf

X9.62-1998 Draft
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.202.2977&rep=rep1&type=pdf

python implementation
https://github.com/warner/python-ecdsa

[asin:4061538314:detail]

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

ed25519

前回( ed25519をswiftで実装してみる - Pebble Coding )は、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にありますが、全て、このあたりの実装をポーティングしたものになっているようです。

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

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の４つの変数を使う形のものを用いる。

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

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

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

ed25519をswiftで実装してみる

ed25519

ed25519をswiftで実装してみます。

pythonのリファレンス実装

https://ed25519.cr.yp.to/software.html

をそのままswiftに置き換えただけのものです。
ソースはこちら。

github.com

swiftには標準ライブラリにBigInt実装がありませんので、pure swift で実装されたこちら

github.com

を使いました。
注意する点は、このBigIntライブラリは除算と余りの計算で負の値が指定された時の結果が、
Java系統の方式を採用しています。
整数論を使ったアルゴリズムを使う場合、python,ruby系統の値になってくれないと困るので、
そこだけ独自に実装しました。

swfit 負数の除法 - Pebble Coding

MacBook Pro 2017でベンチマークをとった結果は、以下のようになりました。

python swift4 (Release Build)
スカラー倍 1 sec 3 sec
秘密鍵から公開鍵生成、署名、署名確認 7 sec 33 sec

python実装に比べてもだいぶ遅いので実用では使えそうにないですね。
実は、Ed25519の実装には、まだ最適化の余地がありますが、かなり面倒なので、この記事はここまでとします。

余談ですが、テストする際はここをReleaseにビルドにしましょう。
デバッグビルドではめちゃくちゃ遅くなり、16分とかかかります。

f:id:pebble8888:20171008211732p:plain

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

ed25519

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

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

c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025  
:fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025  
:af82  
:6291d657deec24024827e69c3abe01a30ce548a284743a445e3680d7db5ac3ac18ff9b538d16f290ae67f760984dc6594a7c15e9716ed28dc027beceea1ec40aaf82  
:

1列目が秘密鍵32バイト+公開鍵32バイトです。
c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025

2列目が公開鍵32バイトです。
fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025

3列目がメッセージです。
1行目が0バイト,2行目が1バイト,...,1024行目が1023バイトとなっているようです。
ここでは2バイトです。
af82

4列目が署名64バイト+元のメッセージです。 ここでは64バイト+2バイトです。 6291d657deec24024827e69c3abe01a30ce548a284743a445e3680d7db5ac3ac18ff9b538d16f290ae67f760984dc6594a7c15e9716ed28dc027beceea1ec40aaf82

以下のコマンドで1024のセットに対して検証が行われます。

$ sign.py < ./sign.input

MacBookPro 2017で試すと、1つの行の処理に7秒ほどかかります。

検証プログラムの中身を見ていきましょう。

import sys
import binascii
import ed25519

# examples of inputs: see sign.input
# should produce no output: python sign.py < sign.input

# warning: currently 37 seconds/line on a fast machine

# fields on each input line: sk, pk, m, sm
# each field hex
# each field colon-terminated
# sk includes pk at end
# sm includes m at end

while 1:
  line = sys.stdin.readline()
  if not line: break
  x = line.split(':')
  sk = binascii.unhexlify(x[0][0:64])
  pk = ed25519.publickey(sk)
  m = binascii.unhexlify(x[2])
  s = ed25519.signature(m,sk,pk)
  ed25519.checkvalid(s,m,pk)
  forgedsuccess = 0
  try:
    if len(m) == 0:
      forgedm = "x"
    else:
      forgedmlen = len(m)
      forgedm = ''.join([chr(ord(m[i])+(i==forgedmlen-1)) for i in range(forgedmlen)])
    ed25519.checkvalid(s,forgedm,pk)
    forgedsuccess = 1
  except:
    pass
  assert not forgedsuccess
  assert x[0] == binascii.hexlify(sk + pk)
  assert x[1] == binascii.hexlify(pk)
  assert x[3] == binascii.hexlify(s + m)

pk = ed25519.publickey(sk)
で秘密鍵から公開鍵を計算し、メッセージの署名を計算しています。
ed25519.checkvalidで計算した署名が正しいかを確認しています。
そのあと実施しているforgedでは、メッセージバイト列の最後のバイトに1を追加した場合、
署名が一致しなくなることを確認しています。
その後、公開鍵が ファイル内の値と一致すること、
署名+メッセージがファイル内の値と一致することを確認しています。