ちょっとしたツールを作っている。
そのツールでは、自分が作った他のライブラリを使っている。
いま、そのライブラリはデバッグ中で、stderrにログをいろいろ吐き出している。
作っているツールではそのライブラリを何度も呼び出すため、おびただしいログが出てしまい、困っている。
やりたいのは、こう。
考えたのは、ファイルディスクリプタ2を別の番号にしてしまおう、というもの。
2の方をcloseして、自分のコマンドは別の番号の方に出力させればよいはず。
int fd_err = dup(2);
FILE *fp_err = fdopen(fd_err, "w");
close(2);
fprintf(stderr, "ERR LOG\n");
fprintf(fp_err, "err log\n");
よしよし。
fdopen()で"r"と書いていて10分ほど悩んでいたのは秘密だ。。。
このシリーズも、早8回目。
すぐにあきらめて終わるだろうと思ったのだが、意外と粘り強いようだ。
粘り強いというか、粘着質というか・・・。
Bitcoinなどで使っている楕円曲線暗号の計算は、楕円曲線のグラフそのままではなく、剰余で範囲を制限した値空間になるということと、その空間ではX座標に対してY座標が正負にあるのではなく、なんだかわからないが偶数/奇数になる、ということが前回分かった。
分かったというか、分からないところも多かったので、そのまま受け入れたというところだ。
では、前回0x02と0x03が逆になったのは、それに関して何か間違っていたのではないかと思うだろう。
よって、今回はY座標の値も見てみた。
・・・偶数/奇数と0x02/0x03の関係は間違っていない。
よく考えたら、非圧縮公開鍵を圧縮公開鍵に変換するのはAPIを使っているから、そこは間違えないのだった。
なのに。。。なぜ。。。
移植元になったjavascriptのライブラリを動かしてみようとしたのだが、さっっっぱりわからん。
動かないということはわかったのだけど、何をして良いのかわからんのだ。
https://stackoverflow.com/questions/28400459/referenceerror-describe-is-not-defined-nodejs
ここにならって、npmでmochaをインストールし、`mocha` とやってみたのだが無いと怒られたので、sudo apt install npmでインストール。。。しようとしたら、404 Not Foundでインストールできず。
たいがいにしとけや、きさーん！と思ったが、こちらにもインストールの方法が載っていた。
https://qiita.com/TsutomuNakamura/items/0eb50bf7622a3906e101
npmにsudoして、-gもやってやらんといかんのか。
このディレクトリだけ動けばいいから-gをつけてないのがいかんかったか。。
そして、一番上のディレクトリで「mocha」を実行すると、何か進んだ。
よかったよかった。
。。。よくない。
ソースはいじってないのに、見たいところがピンポイントでエラーになっているではないか。
1) ecdsa
recoverPubKey
throws on Invalid i value (> 3) (Expected UInt2, got Number 4):
Error: Expected property "2" of type UInt2, got Number 4
at tfSubError (node_modules/typeforce/errors.js:93:9)
at node_modules/typeforce/index.js:159:17
at Array.every (<anonymous>)
at _tuple (node_modules/typeforce/index.js:155:20)
at typeforce (node_modules/typeforce/index.js:196:9)
at Object.recoverPubKey (src/ecdsa.js:166:3)
at test/ecdsa.js:129:17
at tryBlock (assert.js:619:5)
at innerThrows (assert.js:638:18)
at Function.throws (assert.js:662:3)
at Context.<anonymous> (test/ecdsa.js:128:16)
UInt2を期待したけど4が来た？
うーん、UInt2って書いてあると、0～65535までOKのような気がしたが、javascriptは違うんだろうか。
2がbitの2だったら、0～3というのは納得できるが、そもそもこのtestをがんばって意味があるのか。。。
最新版のbitcoinjs-libだったら、書いてあるとおりにやればよいのかもしれんが、recovery pubkeyがあるのは古いバージョンだけなのだ。
残念だが、思考が定まらんし、今回はここまでだ。
今日、会社に行ったので、日本語のMastering Bitcoinを読んでいた。
そうすると、気になる記述が。
「0x02は偶数で、0x03は奇数」と。
もちろん、2は偶数で3は奇数なのだが、そうではなく、Y座標が偶数の場合は0x02を、奇数の場合は0x03を、ということだ。
えー、楕円曲線のグラフと関係ないやん！
http://chimera.labs.oreilly.com/books/1234000001802/ch04.html#pubkey_compression
When calculating the elliptic curve in binary arithmetic on the finite field of prime order p, the y coordinate is either even or odd, which corresponds to the positive/negative sign as explained earlier.
わざわざ「in binary arithmetic on the finite field of prime order p」と書いてあるので、グラフ空間とは違うんだよ、といいたいのだろう。
で、このよくわからない空間は何だろうか？
調べても理解できないような気がするのだが、やっておかねばなるまい。
Mastering Bitcoinの日本語PDFでは「素数位数pの有限体上で二進数演算を用いて」(p.81)と書かれていたが、もちろん意味が分からない。
prime order p : 素数位数p
on the finite field : 有限体上
in binary arithmetic : 2進数演算を用いて
なのだろうが、分解したところでわからないものはわからない。
素数がprimeで、位数がorderらしい。
困ったときのwikipediaなのだけど、数学関係のwikipediaって、書いてあることが難しいよね...
湯桶読みかどうかすらわからんかったのだが、変換するときは「いすう」でよかった。
う、うーん・・・。
よく出てくる「mod p」が現れたので安心しそうになったが、わからん。。。
こっちを先に見ましょう、というリンク先の方がよいか。
https://mathtrain.jp/primitive
これなら、例も載っているのでわかる(気になれる)。
n乗する数(r)と、剰余を求める法(p)の3つが登場人物で、rnのnをインクリメントしながらpの剰余を求めていき、剰余が1になるときのnが「法pに対するrの位数はn」という書き方をするようだ。
何の役に立つのかわからんが、重要らしい。
「法」というのがなんかわかりづらかったのだが、moduloのことらしい。
A mod n = Bだと、「法nに対する」みたいな感じらしい。
http://www.maitou.gr.jp/rsa/rsa09.php
言葉の使い方としては、こっちを読むとわかった気がする。
「10を法とする世界」みたいな、数字の世界観＝世界を表す法、のような感じ方でよさそうだ。
10を法とする場合、その世界には0～9の数字しかないので、9の次は0になってしまうのだ。
マリオブラザーズで、画面の右端を突き抜けると左端に出てくるのと同じだ(古い。。。)。
pを法としているので、この世界は0～p-1の範囲ですべてを表すことになる。
そういう世界になるように、mod pするのだ。
そして、たぶんpはprimeのpで、素数なのだろう。
mod pして、その結果が1になるということは、たとえばpが10なら、11とか21とか、そういう数字だ。
(X - 1) / p = k(kは整数)になり、X = rnのはずだから、(rn - 1) / p = k。
例では、p=7, r=2, n=3だから、(23 - 1) / 7 = (8 - 1) / 7 = 7/7 = 1。
原始根というものも関係するようだから、見ておこう。
さっきの結果から、pとnだけ使うようだ。
今度は、n1～np-1を求めていく。
31 ---> 3 mod 7 = 3
32 ---> 9 mod 7 = 2
33 ---> 27 mod 7 = 6
34 ---> 81 mod 7 = 4
35 ---> 243 mod 7 = 5
36 ---> 729 mod 7 = 1
このように、1～p-1が重複せずに現れることを「一巡する」と呼ぶようだ。
ここで思ったのは「さっきのr=2はどこに出てくるの？？」だ。
rは原始根ということになると思ったのだが、「3は7に対する原始根」と書かれている。
でも、法7に対する2の位数は3、ともある。
うぅ。。。
Y軸の正負が偶数/奇数に置き換えられるのは、このmod pすると重複しない値が出てくるということと関係していそうな気がする。
が、違うような気もする。
もっと心に余裕ができたら調べることにして、今回は「正負と偶数/奇数は対応してるんだよ」にとどめておこう。
前回は、sec1-v2.pdfとJavaScriptの実装を見ながらmbedTLSでやってみたところ、公開鍵の算出がいいところまでできたものの、先頭の0x02 / 0x03が一致しなかった、というところまでだった。
やはりもう少し理論を把握せねばならんか・・・と思っていたが、先にmbedTLSのecpについて確認しておこう。
Bitcoinで楕円曲線の計算をする場合、secp256k1を使っている。
256、だから、バイト数にすると32。
秘密鍵は32byteだし、圧縮公開鍵はプレフィクス1byteがあるので33byte。
と思っているのだが、まずそこを確認したい。
secp256k1の「256」は、なにがどう256なんだろう？
https://en.bitcoin.it/wiki/Secp256k1
グラフを見ると、X座標はマイナスも取り得るし、形としてはX軸に対して線対称だ。
Gについては圧縮と非圧縮の両方で書かれているが、0x02なのでY座標は正。
0x79BE....がX座標で、0x483A....がY座標のはず。
これは正の数であるはずだが、0x03だった場合はY座標をどう表現しているのだろうか？
なじみのある2の補数なのか、たまにBitcoinで出てくる1の補数なのか。
mbedTLSで大きい数字を扱う場合、mbedtls_mpi型を使うのだが、これは符号ビットを持っている。
前回、Y座標を符号反転させる計算として「0 - R.y」という計算をしたのだが、これをmbedTLSの持つ文字列変換APIを使うと、先頭にマイナスがついた座標になっていたのだ。
R.x = 047C1B1111BBE0FC09CF2ED28DD1ABD613C02B747AF8EDD1274886654259BBFB
+R.y = 01E00EF18DE0BE1695CEA5700152D1BD765AA23814DD52843C227A82F0BC60E4
-R.y = -01E00EF18DE0BE1695CEA5700152D1BD765AA23814DD52843C227A82F0BC60E4
そして、mbedtls_ecp_check_pubkey()でチェックすると、-R.yの方がNGになるのである。
でも、公開鍵として正当かどうかは指定した座標がグラフ上にあるかどうかだけだろうし（チェックAPIに秘密鍵は与えない）、グラフの形状からすると、+R.yがグラフ上にあるなら、-R.yもグラフ上にないとおかしいと思うのだ。
チェックAPIは、こちら。
https://github.com/ARMmbed/mbedtls/blob/d4d60579e4550d034a884d1a413942fbe36a8625/library/ecp.c#L1862-L1880
そして、-R.yでチェックに引っかかっていたのは、ここ。
https://github.com/ARMmbed/mbedtls/blob/d4d60579e4550d034a884d1a413942fbe36a8625/library/ecp.c#L1732-L1736
どのチェックがNGだったのかは見ていないが、まあ「mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0」だろう。
負の数はダメなんだ。
こうなってしまうと、グラフの形状だけがすべてじゃないんだ、ということになる。
なるのだが、ではどうしたらよいのだろうか？
sec1-v2.pdfの「2.3 Data Types and Conversions」を見ればよいかと思ったが、これの「整数から16進数変換」のInput条件が"non-negative integer"だったので、違うところを探さねばならぬのか。
そこで、以前参考にした、圧縮公開鍵を展開するgistを見ることにした。
https://gist.github.com/flying-fury/6bc42c8bb60e5ea26631
元の式である、y^2 = x^3 + Bを計算して、y^2の平方根を取り、最上位ビットが期待する値([0]が0x02なら0、0x03なら1)と不一致であれば符号反転のために「0 - Y」するのではなく、「P - Y」としている。
PはmbedTLSでは「prime modulus of the base field」という変数名になっている。
secp256k1では「p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F」らしい。
理解はできないのだが、そうやると確かに-Rは楕円曲線上にあるという判定になったし、-Rを作るときに「0x03」を付けて圧縮公開鍵を展開したときの結果と同じになった。
だからといって、0x02 / 0x03の問題が解決されたわけではない。。。
署名から公開鍵を算出する計算についても、sec-1-v2.pdfに載っていた。
「4.1.6 Public Key Recovery Operation」だ。
まだ読んでないけど「4.1.7 Self-Signing Operation」は署名するときにrecovery idを求める方なんじゃなかろうか。
また、どこで見つけたか忘れたが、JavaScriptで実装されているところもあった。
https://github.com/cryptocoinjs/ecdsa/blob/master/lib/ecdsa.js#L165
両方あれば、何かわかるんじゃなかろうか。
README.mdにdeprecatedと書いてあってリンク先が書いてあったので、こちらかもしれん(コードは同じか)。
masterにはrecoveryする関数ごと残っていなかったので、v3になるときに消されたのかもしれん。
https://github.com/bitcoinjs/bitcoinjs-lib/blob/v2.1.4/src/ecdsa.js#L165
JavaScriptの方は、先ほどの関数の呼び元もあって、こっちは4回ループしているのだ。
https://github.com/cryptocoinjs/ecdsa/blob/master/lib/ecdsa.js#L228
前回、私が考えていた「rec_idは0～3だから、ぐるぐる回せばいいんじゃないの？」なのかもしれん。
引数Qが「正解の公開鍵」で、戻り値のQprimeと比較しているから、署名をした方が使う関数なのかな。
ソースでは4回ループしているが、PDFの方を見ると、
でループするようで、secp256k1のhは1だから、0と1の2回、Rと-Rの2回で、あわせて4回ということなのか。
rec_idに相当する引数がiのようで、b0がRの正負、b1がhの0と1になっているのかな？
気になるのは、Rと-Rだ。
PDFでは、まずRで計算して出てきた値でverifyし、ダメだったら1.6.3で-Rにしているのだ。
だから、1.6のループ内でRか-Rかにしていると思うのだが、JavaScriptの方は最初にRを作る段階でRか-Rを分けているのだが、大丈夫なんだろうか。
まあ、その段階ではnRが無限遠になることの確認だけだから、それならnRだろうと-nRだろうと結果は同じか。
では、mbedTLSでやってみよう、と作っているのだが、これがうまくいかない。。。
今詰まっているのは、-Rの計算だ。
これを mbedtls_ecp_mul()で「-1 * R」という求め方にしているのだが、エラーMBEDTLS_ERR_ECP_INVALID_KEYが返ってきてしまう。
よく考えれば、これって秘密鍵から公開鍵を求めるときの「Q=aG」と同じようなものだから、-1だとダメなんだろう。
JavaScriptでは、secp256k1.pointFromX()を使ってて、第1引数に奇数かどうか突っ込んでいる。
奇数＝0x03だろうから、Y座標だけ負の数になれば良いのかな？
・・・ダメだ。
-Yにしても楕円曲線上に載ってないように見られてしまう。
計算方法自体が良くないのか？？
自作している圧縮公開鍵を非圧縮に戻す関数があるのだが、そのときに先頭を0x02から0x03にすると大丈夫だった。
うーん、理論的なところがわかっていないので、それでいいのかどうか判断できん。。。
そして、そうやってやると、4回回すと1つだけ公開鍵が期待値とほぼ一致した！
「ほぼ」なのは、先頭の0x02/0x03が逆になったからだ。
私の認識では、楕円曲線はX軸に対して線対称だから、特定のXに対して、+Yと-Yがあり、+Yが0x02～、-Yが0x03～、だ。
だから、X座標はちゃんと復元できていて、Y座標の正負だけが間違っているのだと思う。
じゃあ、それはなんで？ということになると、ちゃんとPDFを読んで、JavaScriptのソースが何をしているのかを把握せねばなるまい。
場当たり的に「0x02を0x03にする」などとやってしまうと、値のパターンによってうまくいかないという将来が見えてしまうではないか。。。
今日は疲れたので、軽い話題を。
TechCrunchに、記事が出ていた。
Google Assistantで何ができるか…そのアクションを検索できるディレクトリページができた | TechCrunch Japan
http://jp.techcrunch.com/2018/01/10/2018-01-08-google-launches-a-new-directory-to-help-you-find-assistant-action/
こちらだ。
https://assistant.google.com/explore/
おお、日本語になってるじゃないか！
TechCrunchの記事に書いてあるように、Google Homeというか、Google Assistantは何ができるのかを確認するのが難しい。
画面があれば、一覧を出すとか、メニューにしておくとか、何かしら方法はあるだろう。
しかし音声となると、一覧を知りたいとなると、しゃべってもらうしかない。
が、しゃべってもらっても、なんだかわからない、ということになりかねない。
もっとできることはあるのだろうが、実例がわかるだけでも助かるというものだ。
よくあるのだが、Google Homeに音楽を掛けてもらうような指示をしたつもりなのに、何かを検索して結果を話し始めることがある。
しかし、何の結果を話しているのかわからないし、合成された音声だと強調しているかしょがわからないので、何を言いたいのかさっぱりわからん、ということがあるのだ。
かといって、検索前に「XXXについて検索した結果をお伝えします」などとやると、まだるっこしいかもしれない。
あるいは、そんなのはもうすぐ解決するんじゃー、という意思の表れかもしれない。
あとは、あれですな。
こいつは一体、何をGoogleに送っているんだろう？というところか。
その気になれば、音声をすべて送ることも可能なはずだ。
たぶん、そんなことをしても企業としてデメリットが多いからやらないのだろうが、特定の条件を満たしたデバイスでしかそういうことをしない、ということになっていると、ソフトウェアの作りを調べないことにはわからんかもしれん。
まあ、そんなきわどいことをしなくても、Google Homeに話す＝話をGoogleに送る、になるから、ユーザは喜んで送っているのと同じことになってしまうのだろう。
戦略通りといえばそれまでなんだけど、複雑な気持ちになりますな。
今まで、署名計算の時にrecovery idを求めるためのやり方を探っていたのだが、署名から公開鍵を得る方法を先に調べた方がいいんじゃないかと思うようになった。
recidがどういう値かはわからないものの、代入される値は0～3の整数しかない。
たった4つだ。
だったら、4回計算してみて、得られた公開鍵らしきものを使って署名をverifyさせて、成功したものが公開鍵だ！というやり方ができるかもしれない。
邪道だとは思うのだけど、あーだこーだ悩むよりは早いと思う。
少なくとも「それでもいいんじゃないの？」という好奇心は満たせる。
もしかしたら、2つ以上verifyが成功して「やっぱりダメやん」という結果に終わるかもしれないが、それならそれでよい。
ダメだと分かりたいのだ。
というわけで、次回はタイトル通りの調査をやっていこう。
では、今回は楕円曲線の署名がどういう計算をしているか見てみよう。
途中で挫折する可能性は大きいが、まずは見てみるのだ。
mbedTLSでは、この辺りになる。
https://github.com/ARMmbed/mbedtls/blob/development/library/ecdsa.c#L68
コメントに書いてあるSEC1は、これだろう(pdf)。
http://www.secg.org/sec1-v2.pdf
SEC1 4.1.3は、p.44の「4.1.3 Signing Operation」と思われる。
ここの1～7を実装しているということだろう。
Step4は、ハッシュを求める部分だが、これはAPIの引数でハッシュを求めた後の値を渡すようになっているので、それ以外を実装していることになる。
PDFとソースは一致してるんだろう、という前提で読むと、何をしているのかは分からないが、順番にやっているだけのようだ。
mbedtls_ecp_gen_keypair()でephemeral keypairの(k, R)が得られているのだが、f_rng()とp_rng()で変化を付けているのだろうか？
BitcoinではDeterministic signatureが推奨されているので、mbedtls_ecdsa_sign_det()を使っているのだが、f_rng()としてmbedtls_hmac_drbg_random()を使っているようだ。
だからまあ、うまいことやってくれているのだろう。
これとlibsecp256k1の署名処理を見比べると、何をやっているのかわかりやすくなるだろう。
まず、nonceは、kに当たるようだ。
rpがRで、それをbにして、sigrになっているようだ。
secp256k1_fe_normalize()がmod nで正規化する部分に相当しているのか。
で、このbからsigrにしているところでoverflowしているか取得して、それとr.yが奇数かどうかを判定してrecidを決定しているようだ。
最後は、署名がis_high()だったらrecidを1でxorしている。
ということは、何をやっているかはやはりわからなかったものの、最後のxorする材料はis_high()がTRUEのときの処理をする前じゃないと取得できないことになる。
PDFには、is_high()のようなチェックをすることは書かれていないので、sを求めるときのmod nが必要かどうかという判定になるのだろうか？
しかし、やっているのはsecp256k1_scalar_negate()だから、反転をしているのだと思うのだ。
参考にするのは別のライブラリがよいのかもしれんが、当てがないのよねぇ。
前回は、EXHAUSTIVE_TEST_ORDERの値がわからんというところで終わった。
bitcoindのソースをgrepしたが、やはり「13」のしか出てこない。
「tests_」とファイル名に付いているから、さすがに違うだろう。
少し戻って、secp256k1_scalar_set_b32()をgrepした。
githubで検索したときには出てこなかったのだが、「scalar_low_impl.h」だけでなく「scalar_4x64_impl.h」「scalar_8x32_impl.h」にも同じAPIが出てきている。
ああ、そうか。。。
ここを見逃していたのか。
https://github.com/bitcoin/bitcoin/blob/9ccafb1d7bdd172a9b963444072a844da379c4f7/src/secp256k1/src/scalar_impl.h#L17-L25
テスト時にはEXHAUSTIVE_TEST_ORDERが定義されているが、通常はUSE_SCALAR_4X64かUSE_SCALAR_8X32が使われるということだ。
config.logにマクロ名が出てきているので、configureとかで決まるのだろう。
CPUが64bitか32bitかで使い分けているのかと思ったが、uint64_tが使えるかどうかなのかもしれない。
改めて4x64の方を見てみよう。
単に、エンディアンに考慮しながら32byteの配列をsecp256k1_scalar型に詰めているだけように見える。
overflowは・・・Gの値と見比べているのか。
楕円曲線に詳しくないのだが、Gより大きかったらGで剰余を取るという処理を作った記憶がある。
では、secp256k1_ecdsa_sign_recoverable()がやっているのはこういうことか。
意外とあっさりしているが、署名を取るときにrecovery idなるものが返ってきている。
これは、通常の署名にはない値だ。
署名を取っているsecp256k1_ecdsa_sig_sign()はこちら。
geとかfeとか、よくわからん文字が出てくる。
group elementと、field elementかもしれんが、助けにならん。。
関数名からすると、これはrecovery専用というわけではなく、署名のsigrとsigsを求めるのだろう。
recidは、おまけだ。
ということは、これを実装したいとして、recidだけを別途求められるのか、あるいは署名の計算中じゃないと求められないのかがポイントとなる。
見た感じでは、sigr, sigsの処理前にも後にもrecidに代入する箇所があるので、うまいことやればrecidは自分で計算できるかもしれん。
しかし・・・それには署名計算自体を多少は理解しないと、できるかどうかもわからん。
遠い道のりだ。。。
前回の続きになる。
ECDSAの署名＋αで公開鍵が算出できるらしい
まず、私が見たPythonのライブラリを見てみよう。
https://github.com/ludbb/secp256k1-py/blob/master/secp256k1/__init__.py#L396-L407
ハッシュを計算して、secp256k1_ecdsa_sign_recoverable()を呼び出しているだけのようだ。
呼び出しているライブラリは、これか。
Pythonのsecp256k1が入っているフォルダを見ても、_libsecp256k1.cpython-35m-x86_64-linux-gnu.soというファイルがあるだけだ。
上記のリンクはbitcoindの一部なのだけど、ライブラリとして独立しているようだから、たぶんビルドしたんだろう。
実装は、こちら。
見てみれば何かわかるんじゃなかろうかと期待したのだが・・・わからんね。
処理自体は、多くない。
直接関係している関数は、これらだけだ。
secp256k1_scalar_is_zero()もあるが、これは値がゼロかどうかをチェックしているだけだろう。
うしろの2つは最後に1回だけ実行している。
つまり、secp256k1_scalar_set_b32()とsecp256k1_nonce_function_default()を繰り返して条件に合うnonceを探し、署名するときにR, S, recidを取得しているようだ。
nonce計算する関数は、nonce_function_rfc6979()のようだ。
https://github.com/bitcoin/bitcoin/blob/00d369239612c75548187d4da853bf6878a6f91f/src/secp256k1/src/secp256k1.c#L343
データを固めてSHA256しているようだ。
よく出てくるsecp256k1_scalar_set_b32()は、これ。
何をしているのだろう・・・。
overflowが非NULLであれば0を設定している、というのはわかるが、途中で抜けるルートはないので、!overflowは常に真だ。
しかし、EXHAUSTIVE_TEST_ORDERが出てこない。。。
テストで13という値を使っているところがあったが、これがそのまま使われているかどうかはわからん。
ビルドしてみれば分かるのだろうが、今日はやめておこう。