core/java: ECP compression

[sytansy]

I am using ED25519 from core/java.
When an ECP point P = (x,y) is encoded into bytes (toBytes(byte[] b, boolean compress)) with compress set to true, it does not always decompress into an ECP with the same y value, i.e., it gives P' = (x, y'). A sample of ECP compression/decompression I have:

Original P: 
(40ccd876746fb401023a49469c0b7f52725ec08e2b6e3ed15af0a90f445dc129,6e313f6097112eefbeeefc4ab187e32f0a00a963332a695540be983cd4798e92)

Compressed and decompressed P: 
(40ccd876746fb401023a49469c0b7f52725ec08e2b6e3ed15af0a90f445dc129,ee313f6097112eefbeeefc4ab187e32f0a00a963332a695540be983cd4798e7f)

where only the first byte and the last byte of y and y' are different.

However, I noticed the point multiplication for both gives the same R = rP = rP'.
My workaround is to call mul(new BIG(1)) so the decompressed ECP always returns the same P.

May I know if is this the supposed way to perform point compression/decompression?
Clarification is appreciated, thanks!

[mcarrickscott]

Hello, On examination of the decompressed point it seems that the y coordinate instead of being displayed as x mod p, is actually displayed as x+p. That is, it is too big by 2^255-19, affecting one bit (2^255) of the first byte and the last byte is too big by 19. This is a consequence of the redundant internal representation. However x and x+p are the same modulo p so everything still works OK. But you are right, the displayed output should be fully reduced before being output - we will fix this on the next update. Mike

…

On Tue, Aug 15, 2023 at 2:49 AM sytansy ***@***.***> wrote: I am using ED25519 from core/java. When an ECP point P = (x,y) is encoded into bytes (toBytes(byte[] b, boolean compress)) with compress set to true, it does not always decompress into an ECP with the same y value, i.e., it gives P' = (x, y'). A sample of ECP compression/decompression I have: Original P: (40ccd876746fb401023a49469c0b7f52725ec08e2b6e3ed15af0a90f445dc129,6e313f6097112eefbeeefc4ab187e32f0a00a963332a695540be983cd4798e92) Compressed and decompressed P: (40ccd876746fb401023a49469c0b7f52725ec08e2b6e3ed15af0a90f445dc129,ee313f6097112eefbeeefc4ab187e32f0a00a963332a695540be983cd4798e7f) where only the first byte and the last byte of y and y' are different. However, I noticed the point multiplication for both gives the same R = rP = rP'. My workaround is to call mul(new BIG(1)) so the decompressed ECP always returns the same P. May I know if is this the supposed way to perform point compression/decompression? Clarification is appreciated, thanks! — Reply to this email directly, view it on GitHub <#69>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAU3ZDVJ5L4BCVKVUOA4OSTXVLISXANCNFSM6AAAAAA3QO7H3E> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[sytansy]

Hi Mike,

I see now, thanks for the detailed explanation.

Cheers,
Tan