Sign change conditional fix

[iquerejeta]

Removed the y_sign variable as it was misleading to call y_sign to notsquare. If preferred, we could declare y_sign = notsquare == fe25519_isnegative(y) directly.

The equality check instead of the XOR gate is due to the hash-to-curve standard. The standard defines the following two steps:

6.  If is_square(gx1), set x = x1, y = sqrt(gx1), and sgn0(y) = 1.
7.  Else set x = x2, y = sqrt(gx2), and sgn0(y) = 0.

meaning that we should end up either with gx1 a square and sgn0(y) = 1, or with gx1 a nonsquare and sgn0(y) = 0. However, the current version of the code computes the XOR gate with the nonsquare variable to decide whether we change the sign of y or not, meaning that we end up with either gx1 a nonsquare and sgn0(y) = 1, or with gx1 a square and sgn0(y) = 0.

Surprisingly, all tests still pass, with the exception of the oversized context. How where these test vectors generated?

[jedisct1]

I don't follow.

y_sign is the sign we want y to be, 1 meaning that it's negative, which is the case when gx1 is not a square. The XOR operation looks like the correct one to trigger the sign flip.

The test vectors are the ones from the specification (NU - RO)

[iquerejeta]

I'm also a bit confused myself. But doesn't the standard define that the sign should be 1 if gx1 is a square? However, with what is currently there, the sign is 1 if gx1 is nonsquare, right? I'm assuming that fe25519_notsquare returns 1 if the value is not a square, and 0 if it is a square.

[jedisct1]

Oh, right! Good catch! y should be negative if gx1 is a square.

The failing test is due to x being negative - The test vectors encode coordinates independently.