Pebble Coding

プログラマーの作業メモ

secp256k1に関するメモ

secp256k1に関するメモです。 後ろから二番目のkはkoblitzのkらしいです。

曲線

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

素数

 {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桁

ゼロ点は無限遠点となる。

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

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

1) PとQが同一点で y=0の場合、曲線の接線は垂直線になるので、加算結果は無限遠点。
これは計算上、y=0を無限遠点として計算できることを示している。ここでxの値は計算上はなんでもよいが分かりやすく0としておく。

2) 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}

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

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

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

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

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

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

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

f:id:pebble8888:20171014153817p:plain

リリースビルドで単体テストを実行しようとすると発生します。

Enable Testability を Yes に変更すればOKです。

f:id:pebble8888:20171014153823p:plain

ed25519をswiftで実装してみる

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実装を紐解く 暗号編 その2

リファレンス実装では、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を追加した場合、
署名が一致しなくなることを確認しています。
その後、公開鍵が ファイル内の値と一致すること、
署名+メッセージがファイル内の値と一致することを確認しています。

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

どうやらビットコインでは署名に楕円曲線暗号が使われているらしいです。
ビットコイン楕円曲線暗号の勉強を始める何年も前から所有していますが、知らなかった。

ビットコインとは何か? 第3回:ビットコインの仕組み(アドレスの作成から送金まで) - ビットコインの解説 | Bitcoin日本語情報サイト

使われているのはsecp256k1という形式で、
曲線は {y}^{2} = {x}^{3} + 7だそうです。
法とする素数 {2}^{256} - {2}^{32} - {2}^{9} - {2}^{8} - {2}^{7} - {2}^{6} - {2}^{4} - 1 ( = {2}^{256} - {2}^{32} - 977 )
ベースポイント、ベースポイントの位数Lも定義されています。
cofactorは1ですね。

Secp256k1 - Bitcoin Wiki

その他のコインはどうなっているのか調べてみると、
イーサリウムはビットコインと同じsecp256k1のようです。
その他もこれを使っているものが多いようですね。

この調査の過程で、OpenSSHにEd25519が追加された経緯を知りました。

chris blogs: The road to OpenSSH bliss: ED25519 and the IdentityPersist patch

NISTというアメリカのNSA
(暗号学者が多数所属する国家機関、マットデイモンのグッドウィルハンティングにも出てきましたね。)
に関連のある団体が決めた楕円曲線は何か重大なバックドアがあるかもしれない。
心配だからEd25519も追加しようぜってことらしい。どんだけパラノイアなんだって話ですが。

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

前回

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

はed25519のpython実装の数学編をやりましたが、今回は暗号編です。
暗号部分の関数を見ていきます。
これらの計算手順は前回と同じRFCに記載されています。

概念図を書いてみました。

f:id:pebble8888:20171007230121p:plain

b = 256

秘密鍵の長さは256ビットつまり、32バイトのバイト列で表現できます。
公開鍵の長さも同じ32バイトのバイト列です。

秘密鍵は単純にランダムな32バイトのバイト列を生成すればそれで終わりです。(マジか)
公開鍵は秘密鍵から算出します。この手順は後で説明します。

def H(m):
  return hashlib.sha512(m).digest()

H()関数では、任意の長さのバイト列mのsha512を計算します。digest()関数は512ビットつまり、64バイトのバイト列を返します。

def bit(h,i):
  return (ord(h[i/8]) >> (i%8)) & 1

bit()関数ではバイト列hの上位(左側)から数えて(i/8)番目のバイトの、下位から数えて(i%8)ビット目が1か0かを返す関数です。
ordは1文字を整数のコードポイントに変換する関数です。

秘密鍵、公開鍵ペアの生成 (key pair creation)

def publickey(sk):
  h = H(sk)
  a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2))
  A = scalarmult(B,a)
  return encodepoint(A)

publickey()関数は秘密鍵の32バイト列から公開鍵の32バイト列を返す関数です。
STEP1) 32バイト列の秘密鍵のsha512を計算し64バイト列を出力しhとします。
鍵生成にはhの上位32バイトのみを使います。
STEP2) 最上位バイトの最下位3ビットをクリアして8の倍数にします。
最下位(上位から32バイト目)の最上位ビットから2番目をセットします。
これは桁数を保証するためです。
最上位は0です。qより小さい値にするためです。

f:id:pebble8888:20171009002335p:plain:w500

STEP3) 32バイト列をLittleEndianの正の整数(10進数で77桁)としてaとします。
以降LittleEndian整数化するときは常に正の整数とします。
ベースポイントBをスカラーa倍して点Aを計算します。
STEP4) 点Aの点座標を使ってある計算をします。
計算はencodepoint関数で実装します。
戻り値は32バイト列で公開鍵となります。

def encodepoint(P):
  x = P[0]
  y = P[1]
  bits = [(y >> i) & 1 for i in range(b - 1)] + [x & 1]
  return ''.join([chr(sum([bits[i * 8 + j] << j for j in range(8)])) for i in range(b/8)])

encodepoint(P)関数は点Pのx,y値を用いて、32バイト列を返します。
 q={2}^{255}-19なので、点の座標は256ビット未満つまり32文字以内であることを理解しておきます。

点Pのy座標値の整数をLittleEndianの32文字で表現します。
x,y座標は常に0以上、 {2}^{255}-19未満なので、256ビットの最上位ビットは常に0です。
そして256ビットのうちの最下位ビットをx座標値の最下位ビットの値に置き換えます。
こうしてできた0,1の256個の配列がbitsでそれを文字列に変換した32バイト列が戻り値です。

f:id:pebble8888:20171007000258p:plain:w500

def encodeint(y):
  bits = [(y >> i) & 1 for i in range(b)]
  return ''.join([chr(sum([bits[i * 8 + j] << j for j in range(8)])) for i in range(b/8)])

関数encodeint(y)はy座標の整数値(256ビット)をLittleEndianとして32バイト列に変換します。

署名(signing)

def signature(m,sk,pk):
  h = H(sk)
  s = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2))
  r = Hint(''.join([h[i] for i in range(b/8,b/4)]) + m)
  R = encodepoint(scalarmult(B,r))
  k = Hint(R + pk + m)
  S = (r + k * s) % l
  return R + encodeint(S)

signature()関数は、秘密鍵sk、公開鍵pkを使って任意の長さのバイト列mに署名(sign)した64バイト列を返します。

STEP1) 32バイトの秘密鍵のsha512を計算し64バイト列を出力します。これをhとします。
hの前半の半分の32バイトのバイト列に対して、最下位バイトの最下位3ビットをクリアします。
最後のバイト(下位から32バイト目)の最上位ビットをセットします。これをsとします。
STEP2) hの後半の32バイトに任意の長さのバイト列mを加え、sha512を計算して出力した64バイト列をLittleEndianで整数(512bitなので10進数で約155桁)にして、これをrとします。
STEP3) ベースポイントBをrスカラー倍した点のencodepointを計算し、32バイト列を作りRとします。rは10進数で約155桁ほどです。
STEP4) 32バイト列のR、32バイト列の公開鍵、任意のバイト列のmを結合して、sha512を取り、LittleEndianとして64bitの整数にしてkとします。
STEP5) S = (r + k * s) mod Lを計算します。
STEP6) 32バイトのRとSのLittleEndian化した32バイトを結合した64バイト列を署名とします。

def Hint(m):
  h = H(m)
  return sum(2**i * bit(h,i) for i in range(2*b))

Hint()関数は任意長のバイト列のsha512を取って512ビット(=64バイト)の整数を返します。

Verification(署名確認)

def checkvalid(s,m,pk):
  if len(s) != b/4: raise Exception("signature length is wrong")
  if len(pk) != b/8: raise Exception("public-key length is wrong")
  R = decodepoint(s[0:b/8])
  A = decodepoint(pk)
  S = decodeint(s[b/8:b/4])
  k = Hint(encodepoint(R) + pk + m)
  if scalarmult(B,S) != edwards(R,scalarmult(A,k)):
    raise Exception("signature does not pass verification")

64バイト列の署名s、任意長のメッセージm、32バイト列の公開鍵pkを用いて、このメッセージを署名確認し、
確認できない場合は例外を送出します。
STEP1) 署名の前半32バイト列を点Rにデコードします。
公開鍵を点Aにデコードします。
署名の後半32バイト列をLittleEndianで正の整数Sにデコードします。(Sは0以上L未満です。)
STEP2) 点Rをエンコードした32バイト列、32バイト列の公開鍵、任意長のメッセージバイト列を結合し、512ビットの整数kとします。
STEP3) ベースポイントBをSスカラー倍した点と、点Rに、点Aをkスカラー倍した点を加算した点が等しいかどうかを確かめます。

def decodeint(s):
  return sum(2**i * bit(s,i) for i in range(0,b))

decodeint()関数は、encodeint()の逆関数で、32バイト列をLittleEndian整数に変換します。

def decodepoint(s):
  y = sum(2**i * bit(s,i) for i in range(0,b-1))
  x = xrecover(y)
  if x & 1 != bit(s,b-1): x = q-x
  P = [x,y]
  if not isoncurve(P): raise Exception("decoding point that is not on curve")
  return P

decodepoint()関数はencodepoint()関数の逆関数で、
32バイト列sからy座標の値に変換します。256ビットの最上位ビットは常に0なので、無視します。
このy座標の値からx座標の値を求めます。x座標の値の偶奇が一致しない場合は、一致したxの値に置き換えます。
これが点Pの座標となるので関数の戻り値としますが、ここでは念のため、楕円関数上の点であることをさらに確認しています。

秘密鍵を使ってベースポイントをaスカラー倍した点Aの座標は公開するけれども、
どのくらいスカラー倍したかは公開しないとしていることが分かります。
また、ベースポイントをLスカラー倍すると無限遠点になることを用いていることも分かります。

なお、下位3ビットをクリアして8の倍数にしている理由はまだ理解できておりません。
この曲線のcofactorが8なのと関係しているようです。
 8 L = \#E