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