# ECC - ElGamal with Montgomery or Edwards type curves (curve25519, ed25519) - possible?

I know the usual way of using getting shared secrets for encryption with ECC is DH, however, this only works with two keypairs of exactly the same kind, for example two curve25519- or two p256-keypairs.

With ElGamal, one can get a symmetric key for a recipients public key no matter which kind of key they are using themselves. This works great if users don't have the same kinds of keys, and it doesn't use the same shared secret each time. This behaviour makes development and use of an application using ECC for encryption much easier and probably even is more secure (as the shared secret is different each time), so I'd prefer using ElGamal if possible.

However, it only seems to work for Short type curves - NIST, SECG, brainpool and so on. (My javascript implementation (1) is based on SJCL's implementation, but uses "elliptic" as a library, which supports Short, Montgomery and Edwards curves, while SJCL and JSBN only know Short.)

I don't really get this, as the logic behind ElGamal is really simple:

public_key = curve_param_G * secret_key
tag = curve_param_G * random_secret
key = public_key * random_secret = curve_param_G * secret_key * random_secret
key = tag*secret_key = curve_param_G * random_secret * secret_key


The implementation of multiplication for Montgomery and Edwards curves seems to be different from the multiplication function of Short curves. Still, shouldn't it work?

Is there any change to make ElGamal work with Montgomery curves like curve25519, or Edwards type curves like ed25519, and is it just implementations fault?
Or is there any reason this actually isn't possible?

Reasearching on this topic doesn't bring much detailed information(, unless you get the exact math behind Montgomery and Edwards curves, which I don't at the moment, I'm just using the elliptic library for a simple app).

(1) Some pseudocode (simplified):

Get a symmetric key for a known public key (to get a symmetric key only the recipient will be able to find out knowing a public key):

ec = curveobject(curve_the_pubkey_is_on);
secret = random_secret_key();
tag = ec.g.mul(secret); // pass along with the message
key = public_key.mul(secret); // use for symmetric encryption


Get a symmetric key for a known tag (to get the symmetric key knowing the tag and own private key):

key = tag.mul(private_key); // can decrypt message with

• If you don't need the special properties of ElGamal, I recommend using ECIES (or something similar). Easier to implement, and I believe the security reduction is a bit better as well. – CodesInChaos Dec 1 '14 at 8:22
• ECIES and ElGamal seem to use the same kind of shared secret derivation. Luckily I don't need to implement encryption via ElGamal. What didn't work was the secret key exchange. However, it seems to have been an implementation issue only. (Working with different function calls and in another library.) Thank you still :) – namerequired Dec 1 '14 at 16:53
• Slightly related: note that it's possible to convert equations and points from curve25519 or ed25519 to short weierstrass curves. Meaning that you can compute the scalar multiplication using the libraries which doesn't support Montgomery or Twisted Edwards at the expense of an additional cost for converting the resulting point into the original curve. – Ruggero Dec 1 '14 at 17:32
• To clarify for everyone who tries to use the shared key derivation SJCL implements as ElGamal: If you are using JSBN, this will work with "mul"-function, if using elliptic, don't use "mul" directly but construct using DH ("derive") instead. This rather is a programming hint ... but I hope it's useful ;). – namerequired Dec 1 '14 at 21:48

ElGamal works for any group. What is badly specified is the glue between the protocols (some network packets) and the exact implementation variants in the math library.

C25519 use arithmetic over Montgomery curves.

Ed25519 use arithmetic over twisted Edwards curves.

Huff curves implementations can be "faster", but there are not in the repository of curves types http://www.hyperelliptic.org/EFD

Implementations over MIST binary curves can be "faster" than integer curves. http://rt.openssl.org/Ticket/Display.html?id=3117 and even immensely faster than many implementations of c25519.

So you have a plethora of curves available to you. they are all equivalently secure related to "modulus size". Speed, constant time, inter-operability, conformance to standards, and bugs, depend on the library choices and implementation details.

Points from one specific curve (e.g. NIST B283) cannot be used directly in the arithmetic a different curve (e.g. Ed25519).

You have to go to DJ Bernstein original paper for the reasons of his choice for these curves. ECDH can benefit of XZ coordinates and montgomery ladder, assuming the protocol would not require that you transfer the Y coordinate between Bob and Alice. If you need Y coordinate, then c25519 and its XZ ladder is not much of an improvement. EDDSA can benefit of the coordinate system for twisted edwards curves which has a strongly unified point addition which does not requires the implementor to specifically care about P+Q, P+3Q, P-Q, P+P .....

EC encryption, EC decryption, EC-ELGAMAL works with all of these curves. All you need is a standardization of the type of data exchanged between bob and alice. As far as I know, there is nothing approved in the RFCs and NIST standards, where lobbying and who'swho dictates the changes and approvals.

• There is a precise implementation of El-Gamal in this thread crypto.stackexchange.com/questions/9987/…. Your simplified code for encryption and decryption seems to be very far from it. – Pierre Dec 1 '14 at 3:48
• SJCL's ElGamal implementation (which I use) is just the same as what is described in the end of the answer, but with the variables having other names, and using ElGamal for encryption instead of only getting the shared secret (c). However, it seems to be implementations fault, so it makes sense researching further - thanks :). – namerequired Dec 1 '14 at 14:19