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

Question

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).

Thank you for your answers :)

(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    

Answer 1

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.