リカバリーIDについて小さな例を用いて実感する

一つ前の記事では署名のリカバリーIDについて書きました。

Ethereum の署名とBitcoin の署名 - Pebble Coding

が、いまいち分からんと思うので、実感するため、小さい例で考えてみます。
曲線はsecp256k1と同じ、 $y^{2} = x^{3} + 7$ を使いますが、法素数は31=pを使います。
この時、群の位数は、21=nとなります。つまり、Oを含めて有理点の数が21個あるということです。
有理点(P1, P2, ..., P19, P20, O) のうち位数が21の点はいくつかありますが、
ここではP3をベースポイントGとして選びます。
以下、P3の点はx座標が1, y座標が15で(1,15)と書きます。
P3を2倍,3倍した時の点の座標は以下のようになります。
21倍したところで、Oになっていますね。

P3:(1,15)
2*P3:(7,3)
3*P3:(27,6)
4*P3:(5,15)
5*P3:(25,16)
6*P3:(24,6)
7*P3:(0,21)
8*P3:(4,3)
9*P3:(11,25)
10*P3:(20,28)
11*P3:(20,3)
12*P3:(11,6)
13*P3:(4,28)
14*P3:(0,10)
15*P3:(24,25)
16*P3:(25,15)
17*P3:(5,16)
18*P3:(27,25)
19*P3:(7,28)
20*P3:(1,16)
21*P3:O

ここでECDSAをおさらいしておきます。

http://pebble8888.hatenablog.com/entry/2018/03/03/154115

ベースポイントを何倍するかという値がnonceですが、
nonce * P3 のx座標( $R_x = r$ と書きます。) がn(=21)より大きい場合はオーバーフローですから、除外します。
以下を除外することになります。

P3:(1,15)
2*P3:(7,3)
3*P3:(27,6) <- コレ
4*P3:(5,15)
5*P3:(25,16) <- コレ
6*P3:(24,6) <- コレ
7*P3:(0,21)
8*P3:(4,3)
9*P3:(11,25)
10*P3:(20,28)
11*P3:(20,3)
12*P3:(11,6)
13*P3:(4,28)
14*P3:(0,10)
15*P3:(24,25) <- コレ
16*P3:(25,15) <- コレ
17*P3:(5,16)
18*P3:(27,25) <- コレ
19*P3:(7,28)
20*P3:(1,16)
21*P3:O

ここで除外したのものはリカバリIDが2, 3のものです。
Ethreumではこのように、nonce * Gのx座標がnより大きい場合はnonceを取り直す
ということをやっているのだと思います。(すいません。ソースを確認した訳ではありません。)

※1 F31を使った全ての点の計算結果は以下です。

F31
#EC:21

P1:(0,10)
2*P1:(0,21)
3*P1:O
order:3

P2:(0,21)
2*P2:(0,10)
3*P2:O
order:3

P3:(1,15)
2*P3:(7,3)
3*P3:(27,6)
4*P3:(5,15)
5*P3:(25,16)
6*P3:(24,6)
7*P3:(0,21)
8*P3:(4,3)
9*P3:(11,25)
10*P3:(20,28)
11*P3:(20,3)
12*P3:(11,6)
13*P3:(4,28)
14*P3:(0,10)
15*P3:(24,25)
16*P3:(25,15)
17*P3:(5,16)
18*P3:(27,25)
19*P3:(7,28)
20*P3:(1,16)
21*P3:O
order:21

P4:(1,16)
2*P4:(7,28)
3*P4:(27,25)
4*P4:(5,16)
5*P4:(25,15)
6*P4:(24,25)
7*P4:(0,10)
8*P4:(4,28)
9*P4:(11,6)
10*P4:(20,3)
11*P4:(20,28)
12*P4:(11,25)
13*P4:(4,3)
14*P4:(0,21)
15*P4:(24,6)
16*P4:(25,16)
17*P4:(5,15)
18*P4:(27,6)
19*P4:(7,3)
20*P4:(1,15)
21*P4:O
order:21

P5:(4,3)
2*P5:(25,15)
3*P5:(27,6)
4*P5:(20,3)
5*P5:(7,28)
6*P5:(24,6)
7*P5:(0,10)
8*P5:(1,15)
9*P5:(11,25)
10*P5:(5,16)
11*P5:(5,15)
12*P5:(11,6)
13*P5:(1,16)
14*P5:(0,21)
15*P5:(24,25)
16*P5:(7,3)
17*P5:(20,28)
18*P5:(27,25)
19*P5:(25,16)
20*P5:(4,28)
21*P5:O
order:21

P6:(4,28)
2*P6:(25,16)
3*P6:(27,25)
4*P6:(20,28)
5*P6:(7,3)
6*P6:(24,25)
7*P6:(0,21)
8*P6:(1,16)
9*P6:(11,6)
10*P6:(5,15)
11*P6:(5,16)
12*P6:(11,25)
13*P6:(1,15)
14*P6:(0,10)
15*P6:(24,6)
16*P6:(7,28)
17*P6:(20,3)
18*P6:(27,6)
19*P6:(25,15)
20*P6:(4,3)
21*P6:O
order:21

P7:(5,15)
2*P7:(4,3)
3*P7:(11,6)
4*P7:(25,15)
5*P7:(1,16)
6*P7:(27,6)
7*P7:(0,21)
8*P7:(20,3)
9*P7:(24,25)
10*P7:(7,28)
11*P7:(7,3)
12*P7:(24,6)
13*P7:(20,28)
14*P7:(0,10)
15*P7:(27,25)
16*P7:(1,15)
17*P7:(25,16)
18*P7:(11,25)
19*P7:(4,28)
20*P7:(5,16)
21*P7:O
order:21

P8:(5,16)
2*P8:(4,28)
3*P8:(11,25)
4*P8:(25,16)
5*P8:(1,15)
6*P8:(27,25)
7*P8:(0,10)
8*P8:(20,28)
9*P8:(24,6)
10*P8:(7,3)
11*P8:(7,28)
12*P8:(24,25)
13*P8:(20,3)
14*P8:(0,21)
15*P8:(27,6)
16*P8:(1,16)
17*P8:(25,15)
18*P8:(11,6)
19*P8:(4,3)
20*P8:(5,15)
21*P8:O
order:21

P9:(7,3)
2*P9:(5,15)
3*P9:(24,6)
4*P9:(4,3)
5*P9:(20,28)
6*P9:(11,6)
7*P9:(0,10)
8*P9:(25,15)
9*P9:(27,25)
10*P9:(1,16)
11*P9:(1,15)
12*P9:(27,6)
13*P9:(25,16)
14*P9:(0,21)
15*P9:(11,25)
16*P9:(20,3)
17*P9:(4,28)
18*P9:(24,25)
19*P9:(5,16)
20*P9:(7,28)
21*P9:O
order:21

P10:(7,28)
2*P10:(5,16)
3*P10:(24,25)
4*P10:(4,28)
5*P10:(20,3)
6*P10:(11,25)
7*P10:(0,21)
8*P10:(25,16)
9*P10:(27,6)
10*P10:(1,15)
11*P10:(1,16)
12*P10:(27,25)
13*P10:(25,15)
14*P10:(0,10)
15*P10:(11,6)
16*P10:(20,28)
17*P10:(4,3)
18*P10:(24,6)
19*P10:(5,15)
20*P10:(7,3)
21*P10:O
order:21

P11:(11,6)
2*P11:(27,6)
3*P11:(24,25)
4*P11:(24,6)
5*P11:(27,25)
6*P11:(11,25)
7*P11:O
order:7

P12:(11,25)
2*P12:(27,25)
3*P12:(24,6)
4*P12:(24,25)
5*P12:(27,6)
6*P12:(11,6)
7*P12:O
order:7

P13:(20,3)
2*P13:(1,15)
3*P13:(11,6)
4*P13:(7,3)
5*P13:(4,28)
6*P13:(27,6)
7*P13:(0,10)
8*P13:(5,15)
9*P13:(24,25)
10*P13:(25,16)
11*P13:(25,15)
12*P13:(24,6)
13*P13:(5,16)
14*P13:(0,21)
15*P13:(27,25)
16*P13:(4,3)
17*P13:(7,28)
18*P13:(11,25)
19*P13:(1,16)
20*P13:(20,28)
21*P13:O
order:21

P14:(20,28)
2*P14:(1,16)
3*P14:(11,25)
4*P14:(7,28)
5*P14:(4,3)
6*P14:(27,25)
7*P14:(0,21)
8*P14:(5,16)
9*P14:(24,6)
10*P14:(25,15)
11*P14:(25,16)
12*P14:(24,25)
13*P14:(5,15)
14*P14:(0,10)
15*P14:(27,6)
16*P14:(4,28)
17*P14:(7,3)
18*P14:(11,6)
19*P14:(1,15)
20*P14:(20,3)
21*P14:O
order:21

P15:(24,6)
2*P15:(11,6)
3*P15:(27,25)
4*P15:(27,6)
5*P15:(11,25)
6*P15:(24,25)
7*P15:O
order:7

P16:(24,25)
2*P16:(11,25)
3*P16:(27,6)
4*P16:(27,25)
5*P16:(11,6)
6*P16:(24,6)
7*P16:O
order:7

P17:(25,15)
2*P17:(20,3)
3*P17:(24,6)
4*P17:(1,15)
5*P17:(5,16)
6*P17:(11,6)
7*P17:(0,21)
8*P17:(7,3)
9*P17:(27,25)
10*P17:(4,28)
11*P17:(4,3)
12*P17:(27,6)
13*P17:(7,28)
14*P17:(0,10)
15*P17:(11,25)
16*P17:(5,15)
17*P17:(1,16)
18*P17:(24,25)
19*P17:(20,28)
20*P17:(25,16)
21*P17:O

P18:(25,16)
2*P18:(20,28)
3*P18:(24,25)
4*P18:(1,16)
5*P18:(5,15)
6*P18:(11,25)
7*P18:(0,10)
8*P18:(7,28)
9*P18:(27,6)
10*P18:(4,3)
11*P18:(4,28)
12*P18:(27,25)
13*P18:(7,3)
14*P18:(0,21)
15*P18:(11,6)
16*P18:(5,16)
17*P18:(1,15)
18*P18:(24,6)
19*P18:(20,3)
20*P18:(25,15)
21*P18:O

P19:(27,6)
2*P19:(24,6)
3*P19:(11,25)
4*P19:(11,6)
5*P19:(24,25)
6*P19:(27,25)
7*P19:O
order:7

P20:(27,25)
2*P20:(24,25)
3*P20:(11,6)
4*P20:(11,25)
5*P20:(24,6)
6*P20:(27,6)
7*P20:O
order:7