Ethereumの署名の$,v,$を作っていたら$,recid,$というのが出てきたので調べたら、署名からの公開鍵の復元に使われる値だった。

署名から直接にはその値はわからないが、署名作成時に作った一時的な公開鍵$,kG,$がわかれば、署名$,(r,s),$から、$,r^{−1}(skG−H(m)G),$を使って、公開鍵$,xG,$を復元できる。

$s = k^{-1}(H(m) + rx) \bmod n$なので、

r^{−1}(skG−H(m)G)\\
= r^{−1}(k^{-1}(H(m) + rx)\cdot kG-H(m)G)\\
= r^{−1}((H(m) + rx)\cdot G-H(m)G)\\
= r^{−1}G(H(m) + rx -H(m))\\
= r^{−1}Grx\\
= xG

$,kG,$を署名から導き出してみる。

$secp256k1,$曲線の式は

y^2 = (x^3 + 7) \bmod p

で、曲線上の点の座標には$0$から$p-1$の数値が使われている。

一方、カーブオーダー(曲線上の点の数)は$,n,$で、$,p,$よりもかなり小さい。
$p \approx ,2^{256} - 2^{32},$
$n \approx ,2^{256} - 2^{128},$

署名の$,r,$は$,kG,$の$,x,$座標を$\bmod n,$したものなので、$kG,$の$,x,$座標は、$,n,$以上$,p,$未満である可能性もある。$,n,$の大きさを考えると、$,r,$は、$,kG.x,$か、$kG.x-n$のどちらかになる。

更に、曲線の式は$,y^2=...,$で、それぞれの$x$の候補で$,y,$について解くと、$+$と$-$の２通りの解が存在する。結果として、$,kG,$はその４通りのうちのいずれかの点になる。

$,r,$が$,kG.x-n,$になる可能性はとても小さくて、$0.000000000000000000000000000000000000373$%ということらしい。

$,kG.y,$は、奇数か偶数かというところで、$+$と$-$と紐づくらしい。
どちらがどちらなのかは未確認。

$,s,$が$,\frac{n}{2},$を超えた場合には、$,recid,$の最下位ビットを反転させる必要があるという書き込みもあった。曲線がうねっていった結果、$,y,$座標の正負がそこで逆転するのだろうか。こちらも未確認。

４つケースそれぞれについて、以下のように$,recid,$が割り当てられる。