Don't send y coordinate with elliptic curve public keys

[ryco117]

In place of the y-coordinate, a single toggle bit may be sent from which the y may be derived. For speed, y coordinates should still be stored in the database, however, over transmission it makes sense to send the compressed version with only the x coordinate and toggle

EDIT: Confused which coordinate can be compressed.

[ryco117]

The curve for secp256k1 is y² ≡ x³ + 7. Let z = y².

EDIT: It turns out that the resulting number from adding the prime the curve is over to 1 is not divisible by 4, making the previous algorithm not usable. The algorithm required is Tonelli-Shanks

[init-js]

Not sure If I'm reading this correctly. But just in case,

We used to pack the y coordinate as 1 or 0. 0 for the even root, 1 for the odd one. There's code for that buried in the bitpacking code, and an sjcl addition to perform the square root.

JS

On Sat, Jul 20, 2019 at 8:34 PM Ryan Andersen notifications@github.com wrote:

In place of the x-coordinate, a single toggle bit may be sent from which the x may be derived. For speed, x coordinates should still be stored in the database, however, over transmission it makes sense to send the compressed version with only the y and toggle

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/ryco117/distort-server/issues/20?email_source=notifications&email_token=AAIPFX23M45B6WOGQA7UFD3QAPKMTA5CNFSM4IFQMORKYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HAO4NWA, or mute the thread https://github.com/notifications/unsubscribe-auth/AAIPFX7CPJWGKVYVYKK3FPTQAPKMTANCNFSM4IFQMORA .

[ryco117]

@init-js Thanks for the reply! Since the start, I had remembered that we were able to compress the curve points but avoided doing so for simplicity. However, now that things are very stable this seems like a worth-while efficiency improvement

I'll check out the sjcl addition if I get stuck on the implementation side. Thanks!

[init-js]

It makes a lot of sense to save space, but the main reason we switched back is that it was more work to decrypt a message than send one -- and all this to save a few bits.

The bernstein curve is overall a better fix for space savings. I don't remember the details exactly, but the Y was super easy to derive (or could be omitted altogether).

On Mon, Jul 22, 2019 at 2:52 PM Ryan Andersen notifications@github.com wrote:

@init-js https://github.com/init-js Thanks for the reply! Since the start, I had remembered that we were able to compress the curve points but avoided doing so for simplicity. However, now that things are very stable this seems like a worth-while efficiency improvement

I'll check out the sjcl addition if I get stuck on the implementation side. Thanks!

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/ryco117/distort-server/issues/20?email_source=notifications&email_token=AAIPFX6DYRAFMGT3KCWUOETQAYT3DA5CNFSM4IFQMORKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD2RIY2I#issuecomment-513969257, or mute the thread https://github.com/notifications/unsubscribe-auth/AAIPFX7USVIV6ABWDYJ5BVDQAYT3DANCNFSM4IFQMORA .

[ryco117]

@init-js I don't intend to store it compressed in the database (for the reason you just described), only over transmission, of which certificates make a small percent anyways. And I would like to use curve25519 but sjcl doesn't seem to have a full implementation for it

Edit: If you look through the sjcl source code, you'll see they have a sjcl.bn constant for the curve25519 prime, but they don't have it under their list of pre-defined curves