Encryption using elliptic curves

In my first post, we’ve seen that elliptic curves cryptography (ECC) was first introduced as a better alternative to public-key cryptography based on multiplicative groups of finite fields. In fact, ECC requires smaller keys compared to its finite field analog to provide equivalent security. Finite fields cryptosystems rely on the “hardness” of the discrete logarithm problem (DLP) to build cryptographic tools such as encryption (ElGamal), key exchange (Diffie-Hellman DH) and digital signature algorithms(DSA). Analogously, one expects to have ElGamal, DH and DSA counterparts thanks to the “hardness” of the equivalent elliptic curves discrete logarithm problem (ECDLP). However, it seems that only ECDH and ECDSA are popular. So, is there an ElGamal version for elliptic curves? Is direct encryption even possible with elliptic curves?

The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S. Miller in 1985. The main reason was that previous asymmetric approaches were subject to subexponential-time index calculus algorithms that solve the underlying hard problems, whereas no subexponential-time algorithms are known for the discrete logarithm problem in a (suitably chosen) elliptic curve. Moreover, for the most part the best available algorithms are ones that have nothing to do with the specific structure of the elliptic curve group, but rather would work with essentially the same running time on any group. Such algorithms are said to be “generic”. In his paper, Koblitz suggested an encryption algorithm similar to ElGamal but it needed an invertible function to map plaintexts to points on an elliptic curve which made the scheme a bit impractical. The algorithm works as follows:

• We set up an elliptic curve $E$ over a finite field $\mathbb{F}_p$ and a point $P$ of order $N$.
• We need a public known invertible function $f$ that maps messages $m$ to points $P_m$ on $E$.
• We choose a random secret key $x \in [1,N-1]$ and publish the point $Y=xP$ as public key.
• Encryption: We choose a random integer $k \in [1,N-1]$, then calculate $C_1=kP$, $C_2=kY$ and $P_m=f(m)$. The ciphertext is the tuple $(C_1, C_2+P_m)$.
• Decryption: From the ciphertext $(C, D)$ we calculate $C'=xC$ and retrieve the point $P_m$ with $P_m=D-C'$ ($=k(xP)+P_m-x(kP)$). Finally, we recover the message $m$ with $f^{-1}(P_m)$.

Basically, this is how we can do encryption on the elliptic curve but for real-world encryption this is somehow impractical because of the required invertible point mapping. One way to do it is interpreting the message as the $X$ coordinate of a curve point and computing a matching $Y$ coordinate. This has two drawbacks:

• First, only about half of the $X$ values can be the first coordinate of a curve point and
• second, one needs to compute a modular quadratic residue ($Y^2=X^3+aX+b$) to find the $Y$. This is not trivial and requires using Tonelli-Shanks algorithm.

So, for things to work, some variability (some bits which can be adjusted until a possible $X$ is reached) would be needed and since the size of the message would be severely limited (no bigger than $p$) this is hardly worthwhile.

For these reasons, direct encryption using elliptic curve is not practical but one can use hybrid encryption instead. That is, using ECDH to produce a shared secret value that will be used as a secret for some symmetric encryption algorithm (e.g. AES). This is called Elliptic Curve Integrated Encryption Scheme (ECIES).