5.1.3 Decoding

5.1.3 Decoding

Decoding a point, given as a 32-octet string, is a little more complicated.

1. First, interpret the string as an integer in little-endian representation. Bit 255 of this number is the least significant bit of the x-coordinate and denote this value x_0. The y-coordinate is recovered simply by clearing this bit. If the resulting value is >= p, decoding fails.

2. To recover the x-coordinate, the curve equation implies x^2 = (y^2 - 1) / (d y^2 + 1) (mod p). The denominator is always non-zero mod p. Let u = y^2 - 1 and v = d y^2 + 1. To compute the square root of (u/v), the first step is to compute the candidate root x = (u/v)^((p+3)/8). This can be done with the following trick, using a single modular powering for both the inversion of v and the square root:

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

3. Again, there are three cases:

   1. If v x^2 = u (mod p), x is a square root.

   2. If v x^2 = -u (mod p), set x <-- x * 2^((p-1)/4), which is a square root.

   3. Otherwise, no square root exists for modulo p, and decoding fails.

4. Finally, use the x_0 bit to select the right square root. If x = 0, and x_0 = 1, decoding fails. Otherwise, if x_0 != x mod 2, set x <-- p - x. Return the decoded point (x,y).