5.1.3 Decoding (復号)

5.1.3 Decoding (復号)

32 octet の列として与えられた点を復号するのは, やや複雑である.

1. まず, その列を little-endian の整数として解釈する. この数のビット 255 が x 座標の最下位ビットであり, この値を x_0 とする. y 座標はこのビットをクリアするだけで復元できる. 得られた値が >= p なら, 復号は失敗する.

2. x 座標を復元するには, 曲線方程式から x^2 = (y^2 - 1) / (d y^2 + 1) (mod p) が従う. 分母は法 p の下で常に非零である. u = y^2 - 1, v = d y^2 + 1 とする. (u/v) の平方根を計算する第一歩は, 候補根 x = (u/v)^((p+3)/8) を計算することである. 次の技巧により, v の逆元と平方根の両方を単一のモジュラー累乗で行える:

                 (p+3)/8      3        (p-5)/8
        x = (u/v)        = u v  (u v^7)         (mod p)

3. 再び三つの場合がある:

   1. v x^2 = u (mod p) なら, x は平方根である.

   2. v x^2 = -u (mod p) なら, x <-- x * 2^((p-1)/4) と置き換えると平方根になる.

   3. それ以外なら, 法 p の下に平方根は存在せず, 復号は失敗する.

4. 最後に, x_0 ビットで正しい平方根を選ぶ. x = 0 かつ x_0 = 1 なら, 復号は失敗する. それ以外で, x_0 != x mod 2 なら, x <-- p - x とする. 復号された点 (x,y) を返す.