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 Answer 1

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
    Commented Apr 6, 2021 at 11:33
  • 1
    $\begingroup$ Because The most significant bit of the final octet is always zero. $\endgroup$
    – kelalaka
    Commented Apr 6, 2021 at 11:38
  • $\begingroup$ is the "final octet" the most significant one ? $\endgroup$
    – cmdEvo
    Commented Apr 6, 2021 at 19:04
  • $\begingroup$ Does the Little Endian explain this? $\endgroup$
    – kelalaka
    Commented Apr 6, 2021 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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