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回で少し調べた。
n¹～n^p-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の中に入っているので悩んでしまうのだ。