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があるのは古いバージョンだけなのだ。


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