Fixes Curve25519/Ed25519 and adds Brainpool curves for use in OpenPGP.js

[mahrud]

This pull request fixes point encoding problems for X25519 curves, fixes key generation for Curve25519, and adds a key generation function for Ed25519. These are necessary fixes needed for adding ECC support to OpenPGP.js in this pull request: https://github.com/openpgpjs/openpgpjs/pull/618 .

[coveralls]

Coverage increased (+1.0%) to 90.07% when pulling 75637c76678e83c31682fd967c2fa9ff4761b3fc on mahrud:master into ee7970b92f388e981d694be0436c4c8036b5d36c on indutny:master.

[mahrud]

@indutny have you had a chance to review this? I didn't add any tests here since it still doesn't produce test vectors from #142, but there are new tests in the ecc_nist branch of OpenPGP.js that incorporate changes this PR.

[dkg]

what's the status on this pull request? it'd be nice to get it included so that openpgp.js doesn't use a fork :)

[mahrud]

@dkg sorry about the delay. I think it's ready.

[mahrud]

Is there anything else I should do here?

[chjj]

Been looking at some other code and it made me think of this PR and a possible change: are all montgomery points supposed to be the X coordinate in little endian? OpenSSL[1], libsodium[2], and ed25519-donna's X25519 serialization[3] make it seem so.

Also, a lot of these implementations seem to have a nice helper function for converting edwards points to montgomery points[4]. This is useful (though maybe discouraged) for using ed25519 keys for an X25519 ECDH. I have a very particular use case which requires this, which is why I ended up digging through this code.

The point conversion seems to be something like:

// From ed25519-donna:
// x = ((y + z) * inverse(z - y)) % p
const y = ed25519Point.y;
const z = ed25519Point.z;

// curve25519_add(yplusz, p.y, p.z);
const yplusz = y.redAdd(z);

// curve25519_sub(zminusy, p.z, p.y);
const zminusy = z.redSub(y);

// curve25519_recip(zminusy, zminusy);
const zinv = zminusy.redInvm();

// curve25519_mul(yplusz, yplusz, zminusy);
const zmul = yplusz.redMul(zinv);

// curve25519_contract(pk, yplusz);
const x = zmul.fromRed();

return curve25519.point(x, 1);

Adding a Edwards#toMontgomery(curve) method might be nice.

cc @mahrud @indutny

[1] https://github.com/openssl/openssl/blob/master/crypto/ec/curve25519.c#L852 [2] https://github.com/jedisct1/libsodium/blob/master/src/libsodium/crypto_core/ed25519/ref10/fe_51/fe.h#L102 [3] https://github.com/floodyberry/ed25519-donna/blob/master/curve25519-donna-32bit.h#L449 [4] https://github.com/jedisct1/libsodium/blob/master/src/libsodium/crypto_scalarmult/curve25519/ref10/x25519_ref10.c#L143

[chesnokovilya]

@indutny Hey! So what prevents this PR from merging? Is it order of parameters in the line? KeyPair.prototype.getPublic = function getPublic(enc, compact) I think, in general, brainpool curves and better curve25519 support could be good for this library!

[mahrud]

@chjj, I haven't used or followed the changes to this repository since last April, so I'm not confident I can add the conversion method you requested. I do remember a lot of pain dealing with conflicting endian-ness in different RFCs, and I kept that in mind when making this PR and added notes or references to relevant RFCs when necessary.

With regards to the order of enc and compact, my opinion is that checking the type of the first input and switching the order of inputs if it is a string, as it is currently, should be avoided. https://github.com/indutny/elliptic/blob/ee7970b92f388e981d694be0436c4c8036b5d36c/lib/elliptic/ec/key.js#L53-L58 That said, if it is the only thing keeping this PR from being merged, then please feel free to amend the PR as you see fit.

I rebased the PR and brought it up to date with the version that openpgp.js uses. All tests are green.

[mahrud]

Should I close this PR? Not sure why it's still open, despite being approved. If the changes have already been applied elsewhere, please feel free to close it.

[francois4224]

Hi, is this PR dead? I'm interested about pure js Brainpool curves support

[mahrud]

I don't think so. It just was never merged...