Montgomery curvesを用いたECDSAでの射影座標の扱い

[mathjax]y座標が必要って話.

検証者が知る情報のなかに,ベースポイント\(P\)と公開鍵\(P_B\)がある.今回はこの2つの点を公開する際に,射影座標\((X:Z)\)が使用可能か考えてみる.
署名の検証には\(V=dH(m)P+duP_B\)を行う必要がある.つまり,点の加算が必要となる.以下に射影座標での点の加算を示す.
$$ X_{m+n}=Z_{m-n}((X_m-Z_m)(X_n+Z_n)+(X_m+Z_m)(X_n-Z_n))^2 $$
$$ Z_{m+n}=X_{m-n}((X_m-Z_m)(X_n+Z_n)-(X_m+Z_m)(X_n-Z_n))^2 $$
上記の式ではある点を基準として\(n\)倍した点を\((X_n,Z_n)\)として表現している.ここで,\(P_B=d_BP\)なので\(V=dH(m)P+dud_BP\)となる.つまり,上記の式では\(m=dH(m),n=dud_B\)となる.ただし,このときに\(X_{m-n},Z_{m-n}\),つまり\(dH(m)P-dud_BP\)が必要となる.しかし\(dH(m)P-dud_BP\)は不明なため計算できない.
そのため,加算についてはアフィン座標で行う必要がある.アフィン座標での加算の式を以下に示す.
$$x_3=\frac{B(y_2-y_1)^2}{(x_2-x_1)^2}-A-x_1-x_2$$
$$y_3=\frac{(2x_1+x_2+A)(y_2-y_1)}{x_2-x_1}-\frac{B(y_2-y_1)^3}{(x_2-x_1)^3}-y_1$$
加算にはアフィン座標でy座標を復元する必要がある.y座標の復元には以下の式を用いる.
$$y_n = \frac{(x_1 x_n +1)(x_1 + x_n +2A)-2A-(x_1-x_n)^2x_{n+1}}{2By_1}$$
上記の式では\(x_1,y_1,x_n,x_{n+1}\)が必要となる.\(x_1,y_1\)はスカラー倍する前のアフィン座標での点である.つまり\(P,P_B\)が射影座標で公開された場合,\(P\)のy座標が必要となる(x座標は\(X,Z)\)から計算可能).また,その上で\(x_{n+1}\)が必要となる.\(x_{n+1}\)が公開されない場合,検証者が自ら\(P_B+P\)を計算する必要があり,手間である.(なお,署名者の場合はMontgomery ladderの結果として\(P_n,P_{n+1}\)が手に入るため,手間は減る.)
以上のことから,ベースポイント\(P\)と公開鍵\(P_B\)についてはアフィン座標での公開が望ましいと考える.