4.3.1 ElGamal Cryptosystem on Elliptic Curves

Let E be an elliptic curve over Z_p (p prime, p > 3). The computing of the number of point on E, which we denotes by #E, is quite difficult, but there is an efficient algorithm to do this, due to Schoof. Knowing #E, we further want to find a cyclic subgroup of E in which te discrete log problem is intractible. This subgroup can be used as a setting for the ElGamal Cryptosystem (see 4.2).

4.3.1 ElGamal Cryptosystem on Elliptic Curves: Sample applet for small numbers


source

There are some practical difficulties in implementing an ElGamal Cryptosystem on an elliptic curve:

• message expansion factor of (about) four, since each ciphertext consists of four elements
• plaintext space consists of the points on the curve E and there is no convenient method known of deterministically generating points on E.

4.4 Menezes-Vanstone Elliptic Curve Cryptosystem