5.1.3 Decoding (解码)

5.1.3 Decoding (解码)

对给定的 32 个 octet 串表示的点做 decoding, 要略复杂一些.

1. 首先将该串按小端解释为一个整数. 该数的第 255 位是 x 坐标的最低位, 记为 x_0. y 坐标通过清除该位即可恢复. 若所得值 >= p, 则 decoding 失败.

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 下不存在平方根, decoding 失败.

4. 最后, 用 x_0 选取正确的平方根. 若 x = 0 且 x_0 = 1, decoding 失败. 否则, 若 x_0 != x mod 2, 令 x <-- p - x. 返回解码得到的点 (x,y).