1
$\begingroup$

The RFC 8032 describes the point encoding like this :

A curve point (x,y), with coordinates in the range 0 <= x,y < p, is coded as follows. First, encode the y-coordinate as a little-endian string of 32 octets. The most significant bit of the final octet is always zero. To form the encoding of the point, copy the least significant bit of the x-coordinate to the most significant bit of the final octet.

And implements it like this :

def point_compress(P):
    zinv = modp_inv(P[2])
    x = P[0] * zinv % p
    y = P[1] * zinv % p
    return int.to_bytes(y | ((x & 1) << 255), 32, "little")

Could you explain the meaning of the word "copy" in this sentence "copy the least significant bit of the x-coordinate to the most significant bit of the final octet" ? Why isn't the bit copied in the code ? Why is it just a bitwise OR ?

$\endgroup$
1
$\begingroup$

Could you explain the meaning of the word "copy" in this sentence "copy the least significant bit of the x-coordinate to the most significant bit of the final octet" ? Why isn't the bit copied in the code ? Why is it just a bitwise OR ?

First of all note that;

# Points are represented as tuples (X, Y, Z, T) of extended
# coordinates, with x = X/Z, y = Y/Z, x*y = T/Z

So the zinv comes from there and

x = P[0] * zinv % p
y = P[1] * zinv % p

Uses to find x and y

Now the last line does what the RFC describes in a simple way.

int.to_bytes(y | ((x & 1) << 255), 32, "little")

The code is just a demonstration of the result. In your programming environment, you can use copy bit by bit, and it will be way slower.

A bitwise or operation is much faster than bit by bit copy. Also, as you can see there are no range check or if to check boundaries. Since the formula is fixed you can use whatever optimization is needed as longs as your code doesn't leak information.

Final note: you restrict yourself with the bit-by-bit copy. Doesn't the result copy the values into the return value?

$\endgroup$
4
  • $\begingroup$ if the most significant bit is 1 and the least significant bit of x is 0, the resulting bit will be 1. not 0 as I expected while reading the word "copy" $\endgroup$ – cmdEvo Apr 6 at 11:33
  • 1
    $\begingroup$ Because The most significant bit of the final octet is always zero. $\endgroup$ – kelalaka Apr 6 at 11:38
  • $\begingroup$ is the "final octet" the most significant one ? $\endgroup$ – cmdEvo Apr 6 at 19:04
  • $\begingroup$ Does the Little Endian explain this? $\endgroup$ – kelalaka Apr 6 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.