2018/01/29

[tool]jqの出力をリダイレクトしたいときはドットをつける

したいのだ・・・。


私はUbuntu16.04を使っているが、例えばこういうことになる。

$ cat test.json | jq > ok.json
jq - commandline JSON processor [version 1.5-1-a5b5cbe]
Usage: jq [options] <jq filter> [file...]
(ヘルプが続く)

違う、違うのだ。。。


ネットで検索したら、どこで見つけたか分からないけど、jqの引数にドットを付ければよさそうだった。
ありがとう、ブログを書いてくれた人たち!

$ cat test.json | jq . > ok.json


jqは多機能で使いこなせていないのだけど、私の使い方だとこれだけ知っておけばなんとかなるのだった。

2018/01/24

[c/c++]popen()で実行した結果はpclose()の戻り値で判定する

コマンドの結果が標準出力で出てくるので、それを別のプログラムで呼び出して、結果を加工しようとした。

そういうときは、popen()で取ってくると良いようである。

https://linuxjm.osdn.jp/html/LDP_man-pages/man3/popen.3.html


これを"r"で開いた場合、戻り値のFILE*で標準出力に吐き出された内容が取ってこれる。
バッファにためてやらないといかんが、まあよかろう。


さて、そのコマンドはエラーを返すこともある。
エラーはreturnで返しているので、コンソールから実行すると「echo $?」などすれば見える。
しかし、popen()の場合はどうしたらよいのだろうか?


結果としては、pclose()の戻り値を、wait()を使ったときの要領で判定していくようだ。


        int ret = pclose(fp);
         if (WIFEXITED(ret)) {
             printf("WIFEXITED\n");
             printf("WEXITSTATUS=%d\n", WEXITSTATUS(ret));
         }
         if (WIFSIGNALED(ret)) {
             printf("WIFSIGNALED\n");
             printf("WTERMSIG=%d\n", WTERMSIG(ret));
#ifdef WCOREDUMP
             if (WCOREDUMP(ret)) {
                 printf("WCOREDUMP\n");
             }
#else
             printf("WCOREDUMP not defined\n");
#endif
         }
         if (WIFSTOPPED(ret)) {
             printf("WIFSTOPPED\n");
             printf("WSTOPSIG=%d\n", WSTOPSIG(ret));
         }
         if (WIFCONTINUED(ret)) {
             printf("WIFCONTINUED\n");
         }

これを調べる前だったので、実装は呼び出すコマンドの方を加工して、エラーの時は何も出力しない、ということにした。
そうすれば、strlen()でわかるからいいや、と思ったのだ。

が、pclose()の戻り値を見るようにした方がまっとうですな。

2018/01/22

[c/c++]strtoull()はマイナスでもエラーにならない

ならないんだ・・・。

errno = 0
uint64_t val = strtoull("-1234", NULL, 10);
if (errno == 0) {
    printf(val = %" PRIu64 "\n");
}

val=18446744073709550382


まあ、そう書いてあるから、そうなんだろう。

https://linuxjm.osdn.jp/html/LDP_man-pages/man3/strtoul.3.html


せっかく、文字の先頭に空白文字があっても判断してくれるのに、マイナスを許容するんだったら文字列のチェックを事前にやらんと行かんじゃないか。。。

2018/01/21

ECDSAの署名+αから公開鍵を算出したい (10) - 完

まず、前回の修正から。


ハッシュ値のマイナスである-eを求めるとき、(0 - e)は不一致で、(N - e)で一致した、ということを書いた。
あれは、実装を間違えていた。
(0 - e)まではよくて、最後にmodするとき、mod Pでやってしまっていたのだ。
mod Nでやると、ちゃんと期待した値になった。
まあ、そうじゃないとbitcoinlib-jsでの計算がe.negate().mod(n)でうまくいくはずはないわな。


https://qiita.com/sh-miyoshi/items/7479f6e647a324638b9a
ここを読み、Nを法とした世界での-e値は、Nからのマイナス方向でe進んだところになるということがわかった。
つまり (N - e) となるので、最初の計算も間違いではないし、eがmod Nされた値であれば、N - eであればmodする必要はないということになる。


うーん、今までeの値そのものについてはハッシュ計算するだけで深く考えていなかったのだが、楕円曲線で使う場合にはmod Nしないといけないのだろうか?
心配になってきたので、実装としては (0 - e) mod Nにしておこう。


なお、mod Pしてしまった理由だが、mbedTLSは大きい数字のmod APIも持っているが、楕円曲線の場合はmod Pを高速に計算するAPIが別途用意されている。
https://github.com/ARMmbed/mbedtls/blob/mbedtls-2.6/include/mbedtls/ecp.h#L149

なので、なんか楕円曲線ではmodP()を使うものだと思い込んでしまったのだ。


では、mod Pだったりmod Nだったりする使い分けは何なのだろうか?

https://en.bitcoin.it/wiki/Secp256k1

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

桁数は同じ。
書き方としては、field pで、order nとなっている。

https://btcnews.jp/elliptc-curve-diy/

よって、楕円曲線の計算をする場合、整数の計算はNで限り、平面の座標を指す場合はPで限ります。

なにが「よって」なのかはわからないが、整数はmod N、座標はmod Pということらしい。

値としては、P > Nになるから、座標にした方が広く表されるようだ。
もしかしたら、基点GとNの乗算によって表される座標のXかYがPくらいになるということか?


sec1-v2.pdfを見てみた。

field p = { 0, 1, ..., p-1 }

h = #E(field p) / n

#E(field p)は、Eがfield pで定義されるならその曲線上の点、「order of the curve E」と呼ぶ

order n of Gなので、nは位数

位数nは、第7回で少し調べた。
n1~np-1で、mod pした値は重複しないという関係か。
order n of Gだから、mod pじゃなくてmod G?
でも、pは数字だけど、Gは楕円曲線上の点だ。
#E(field p)がorder of the curve Eだから、ここだと#G(field n)と表すのか?


うーん、mod Nとmod Pの使い分け根拠を知りたいだけなのだが。。。

x = r + jNは数字だけど、それをRのX座標にするので、mod P。
r-1は数字だから、mod N。
-RはRのY座標を反転させるのだが、座標だからmod P。

第6回で-Rを求めるのにP - R.Yを使ったのだが、これは最初に書いた-eと同じ話だ。
こちらはちゃんとmod Pとしていたのだが、使っている関数が高速なmodp()だった。
どうも、modp()は正の数じゃないと処理ができないようで、mbedtls_mpi_mod_mpi()を使うと0 - R.Yで計算できる。
R.YはPを法としているので、P - R.Yで値を外れることはないことになる(modp()しても変化しないのでうまくいってる)。


長くなったが、このシリーズはここで終わろう。

できれば、自作したくないところではあるのだが、APIが存在しないなら作るしかなかろう。
secp256k1ライブラリだけ独立しているなら使ってもよいのだが、bitcoindの中に入っているので悩んでしまうのだ。

2018/01/20

ECDSAの署名+αから公開鍵を算出したい (9)

自作の公開鍵復元が動かないので、先生を動かすことにした。

https://github.com/bitcoinjs/bitcoinjs-lib/tree/v2.1.4


recoverPubKeyを持つのがv2なので、この辺りを使った。
こんな感じで書くと、動くことが分かった。


var ecdsa = require('./src/ecdsa')
var BigInteger = require('bigi')
var ECSignature = require('./src/ecsignature')


//pubkey= 03becec41f68d77fde9e972c79aa0e6e4e818bd3046276969e79374ec0561ba459
//hash=b881ab3c470b9398adb5ea6cb360d145df702fa0bc0a6c012219fa93e709adad
//  r=047c1b1111bbe0fc09cf2ed28dd1abd613c02b747af8edd1274886654259bbfb
//  s=1d00ca3fc10a111a5a3ea0669992e4ad9a2f1c402ec5fd29d9e1348ab0584fa2

var e = BigInteger.fromHex('b881ab3c470b9398adb5ea6cb360d145df702fa0bc0a6c012219fa93e709adad')
var r = BigInteger.fromHex('047c1b1111bbe0fc09cf2ed28dd1abd613c02b747af8edd1274886654259bbfb')
var s = BigInteger.fromHex('1d00ca3fc10a111a5a3ea0669992e4ad9a2f1c402ec5fd29d9e1348ab0584fa2')
var signature = new ECSignature(r, s)
var i = 0

var Qprime = ecdsa.recoverPubKey(e, signature, i)
var QprimeHex = Qprime.getEncoded().toString('hex')
console.log('Qprime=', QprimeHex)

$ node recover_pub.js
Qprime= 03becec41f68d77fde9e972c79aa0e6e4e818bd3046276969e79374ec0561ba459

さすが先生ですわ・・・。
自分の結果と比較するために、データを残しておこう。

i=0
03becec41f68d77fde9e972c79aa0e6e4e818bd3046276969e79374ec0561ba459

i=1
0383a8ef00cdbdc68b4176c72be1b2173b522633ba525f7a89334e4bab6cec89b4

i=2
03ccb2ec2eca77c75955cd5334e9f0248adf51dcb37744fef36a9152dd468cbe37

i=3
02082151f0695b3b98128e4326e7ddd1f44264448d39723b10ba56976c44fe5dba

i=4
例外発生

うちの子はこうだ。

i=0
0283a8ef00cdbdc68b4176c72be1b2173b522633ba525f7a89334e4bab6cec89b4

i=1
02becec41f68d77fde9e972c79aa0e6e4e818bd3046276969e79374ec0561ba459

i=2
03f23664e578b9cc1f8eb81e47ce3eb037043a5a92f0a3fc09ebd2ca121f862e05

i=3
03b06c50b0579e2142f56756c29445d7762539368be48918db2d6bd4f2f562b51d

i=0とi=1の結果が逆のような形になっている。
i=2と3は共通点がない。

この辺りに突破口がないだろうか。


うーん、-eの値が違う。

先生
e   = b881ab3c470b9398adb5ea6cb360d145df702fa0bc0a6c012219fa93e709adad
eNeg= 477e54c3b8f46c67524a15934c9f2eb8db3ead45f33e343a9db863f8e92c9394



e    = B881AB3C470B9398ADB5EA6CB360D145DF702FA0BC0A6C012219FA93E709ADAD
eNeg = 477E54C3B8F46C67524A15934C9F2EBA208FD05F43F593FEDDE6056B18F64E82

実は、前回まで私は (0 - e) % Pを計算していたのだが、ログに出してみるとeと同じ値だったのだ。。。
Y座標の符号を逆にするときの反省を生かして(P - e) % Pにしたのが今回。
それでも、微妙に値が違っている。


先生は、e.negate().mod(n)で計算している。
だいたい、一番最後の桁を足しても、0xD + 0x4は0じゃないやん。。。

やけになって、PではなくNでやってみた。


e    = B881AB3C470B9398ADB5EA6CB360D145DF702FA0BC0A6C012219FA93E709ADAD
eNeg = 477E54C3B8F46C67524A15934C9F2EB8DB3EAD45F33E343A9DB863F8E92C9394

理屈はわからんが、値が一致してしまったではないか。

i=0
03becec41f68d77fde9e972c79aa0e6e4e818bd3046276969e79374ec0561ba459

i=1
0383a8ef00cdbdc68b4176c72be1b2173b522633ba525f7a89334e4bab6cec89b4

i=2
02b06c50b0579e2142f56756c29445d7762539368be48918db2d6bd4f2f562b51d

i=3
02f23664e578b9cc1f8eb81e47ce3eb037043a5a92f0a3fc09ebd2ca121f862e05

うーん、i=2と3がまだ不一致だ。


これは、Rが不一致なためのようだ。

先生(i=2)
x= 01047c1b1111bbe0fc09cf2ed28dd1abd4ce6f085b2a418e0ce71ae4f2128ffd3c
R= 02047c1b1111bbe0fc09cf2ed28dd1abd4ce6f085b2a418e0ce71ae4f31290010d


x = 01047C1B1111BBE0FC09CF2ED28DD1ABD4CE6F085B2A418E0CE71AE4F2128FFD3C
R.x = 01047C1B1111BBE0FC09CF2ED28DD1ABD4CE6F085B2A418E0CE71AE4F2128FFD
R.y = 7F6ACBA2D227DCA73DDC17A895454F00A97F34A87967BECB6535287E0E5C436C

xは同じ値で、Rはxの先頭に0x02を付けたもののはずだが、先生はそうしていない。
そして、私もそうなっていないのだが、なんでだ??

あ、表示桁が足りてない・・・。
xにNを足したとき、33byteになってしまったのだ。
単純なバグだな。

i=2
03ccb2ec2eca77c75955cd5334e9f0248adf51dcb37744fef36a9152dd468cbe37

i=3
02082151f0695b3b98128e4326e7ddd1f44264448d39723b10ba56976c44fe5dba

一致した。


で、だ。

ハッシュ値eに対する-eを求めるとき、N - eして値が一致したけど、それでよいのだろうか?
secp256k1の法に従うことにはなるのだろうけど、そこが感覚的に分かっていない。

(sR - eG)を求めるとき、APIとしては (a * P + b * Q)しかないためにbをマイナスにしようとしただけなのだ。
だから、単純に(0 - e)を求めたのだが、これは当然負の数で、それは0~N-1の世界にいないからダメなのか?


module 負」で検索すると、そういう計算自体が微妙なところらしい。
言語間で違うということは、ライブラリだと言語に関係なく違いが生じるということか。

うーん、難しいことはやらずにAPIだけ使い回して完了させる予定だったのに、最後に悩みが残る結果になってしまった。
楕円曲線の簡単な説明をしてくれるサイトでも読むか。

[c/c++]fd 2を閉じて、別のFILE*に割り当てたい

ちょっとしたツールを作っている。
そのツールでは、自分が作った他のライブラリを使っている。
いま、そのライブラリはデバッグ中で、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分ほど悩んでいたのは秘密だ。。。

2018/01/18

ECDSAの署名+αから公開鍵を算出したい (8)

このシリーズも、早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があるのは古いバージョンだけなのだ。


残念だが、思考が定まらんし、今回はここまでだ。

2018/01/16

ECDSAの署名+αから公開鍵を算出したい (7)

今日、会社に行ったので、日本語の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って、書いてあることが難しいよね...
湯桶読みかどうかすらわからんかったのだが、変換するときは「いすう」でよかった。

https://mathtrain.jp/isuu

う、うーん・・・。
よく出てくる「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すると重複しない値が出てくるということと関係していそうな気がする。
が、違うような気もする。

もっと心に余裕ができたら調べることにして、今回は「正負と偶数/奇数は対応してるんだよ」にとどめておこう。

2018/01/14

ECDSAの署名+αから公開鍵を算出したい (6)

前回は、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の問題が解決されたわけではない。。。

ECDSAの署名+αから公開鍵を算出したい (5)

署名から公開鍵を算出する計算についても、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の方を見ると、

  • 楕円曲線のh
  • Rと-R

でループするようで、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にする」などとやってしまうと、値のパターンによってうまくいかないという将来が見えてしまうではないか。。。

2018/01/11

[googlehome]Actionsでできることの紹介サイトができた

今日は疲れたので、軽い話題を。


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に送る、になるから、ユーザは喜んで送っているのと同じことになってしまうのだろう。
戦略通りといえばそれまでなんだけど、複雑な気持ちになりますな。

2018/01/10

ECDSAの署名+αから公開鍵を算出したい (4)

今まで、署名計算の時にrecovery idを求めるためのやり方を探っていたのだが、署名から公開鍵を得る方法を先に調べた方がいいんじゃないかと思うようになった。

recidがどういう値かはわからないものの、代入される値は0~3の整数しかない。
たった4つだ。
だったら、4回計算してみて、得られた公開鍵らしきものを使って署名をverifyさせて、成功したものが公開鍵だ!というやり方ができるかもしれない。

邪道だとは思うのだけど、あーだこーだ悩むよりは早いと思う。
少なくとも「それでもいいんじゃないの?」という好奇心は満たせる。
もしかしたら、2つ以上verifyが成功して「やっぱりダメやん」という結果に終わるかもしれないが、それならそれでよい。
ダメだと分かりたいのだ。


というわけで、次回はタイトル通りの調査をやっていこう。

2018/01/08

ECDSAの署名+αから公開鍵を算出したい (3)

では、今回は楕円曲線の署名がどういう計算をしているか見てみよう。
途中で挫折する可能性は大きいが、まずは見てみるのだ。


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()だから、反転をしているのだと思うのだ。


参考にするのは別のライブラリがよいのかもしれんが、当てがないのよねぇ。

ECDSAの署名+αから公開鍵を算出したい (2)

前回は、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の方を見てみよう。

https://github.com/bitcoin/bitcoin/blob/9ccafb1d7bdd172a9b963444072a844da379c4f7/src/secp256k1/src/scalar_4x64_impl.h#L117-L127

単に、エンディアンに考慮しながら32byteの配列をsecp256k1_scalar型に詰めているだけように見える。
overflowは・・・Gの値と見比べているのか。
楕円曲線に詳しくないのだが、Gより大きかったらGで剰余を取るという処理を作った記憶がある。



では、secp256k1_ecdsa_sign_recoverable()がやっているのはこういうことか。

  1. messageとsecretとのハッシュを取ってnonceとする(順に連結して、SHA256をcounter回実施?)
  2. nonceに値が入っていてオーバーフローもしていなければ、署名をとって4へ
  3. counterをインクリメントして、1へ
  4. 署名のr, s、recovery idを連結

意外とあっさりしているが、署名を取るときにrecovery idなるものが返ってきている。
これは、通常の署名にはない値だ。


署名を取っているsecp256k1_ecdsa_sig_sign()はこちら。

https://github.com/bitcoin/bitcoin/blob/9ccafb1d7bdd172a9b963444072a844da379c4f7/src/secp256k1/src/ecdsa_impl.h#L271-L311

geとかfeとか、よくわからん文字が出てくる。
group elementと、field elementかもしれんが、助けにならん。。


関数名からすると、これはrecovery専用というわけではなく、署名のsigrとsigsを求めるのだろう。
recidは、おまけだ。
ということは、これを実装したいとして、recidだけを別途求められるのか、あるいは署名の計算中じゃないと求められないのかがポイントとなる。

見た感じでは、sigr, sigsの処理前にも後にもrecidに代入する箇所があるので、うまいことやればrecidは自分で計算できるかもしれん。
しかし・・・それには署名計算自体を多少は理解しないと、できるかどうかもわからん。

遠い道のりだ。。。

2018/01/07

ECDSAの署名+αから公開鍵を算出したい (1)

前回の続きになる。
ECDSAの署名+αで公開鍵が算出できるらしい


まず、私が見たPythonのライブラリを見てみよう。
https://github.com/ludbb/secp256k1-py/blob/master/secp256k1/__init__.py#L396-L407

ハッシュを計算して、secp256k1_ecdsa_sign_recoverable()を呼び出しているだけのようだ。
呼び出しているライブラリは、これか。

https://github.com/bitcoin/bitcoin/blob/9ccafb1d7bdd172a9b963444072a844da379c4f7/src/secp256k1/include/secp256k1_recovery.h#L81-L88

Pythonのsecp256k1が入っているフォルダを見ても、_libsecp256k1.cpython-35m-x86_64-linux-gnu.soというファイルがあるだけだ。
上記のリンクはbitcoindの一部なのだけど、ライブラリとして独立しているようだから、たぶんビルドしたんだろう。


実装は、こちら。

https://github.com/bitcoin/bitcoin/blob/9ccafb1d7bdd172a9b963444072a844da379c4f7/src/secp256k1/src/modules/recovery/main_impl.h#L123-L168

見てみれば何かわかるんじゃなかろうかと期待したのだが・・・わからんね。
処理自体は、多くない。
直接関係している関数は、これらだけだ。

  • secp256k1_nonce_function_default()
  • secp256k1_scalar_set_b32()
  • secp256k1_ecdsa_sig_sign()
  • secp256k1_ecdsa_recoverable_signature_save()

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

https://github.com/bitcoin/bitcoin/blob/00d369239612c75548187d4da853bf6878a6f91f/src/secp256k1/src/secp256k1.c#L310-L340

データを固めてSHA256しているようだ。



よく出てくるsecp256k1_scalar_set_b32()は、これ。

https://github.com/bitcoin/bitcoin/blob/9ccafb1d7bdd172a9b963444072a844da379c4f7/src/secp256k1/src/scalar_low_impl.h#L47-L56

何をしているのだろう・・・。
overflowが非NULLであれば0を設定している、というのはわかるが、途中で抜けるルートはないので、!overflowは常に真だ。


しかし、EXHAUSTIVE_TEST_ORDERが出てこない。。。
テストで13という値を使っているところがあったが、これがそのまま使われているかどうかはわからん。
ビルドしてみれば分かるのだろうが、今日はやめておこう。