In an elliptic curve over a field, the points form a group with respect to the standard addition of points on such curves. This means that most elliptic curve cryptosystems are analogues of discrete logarithm systems (such as the Elgamal system), with modular powers being replaced with multiplication of points. Then the security of the system comes from the difficulty of the discrete logarithm problem on an elliptic curve: given with it is in general very difficult to determine .
However, it is possible to have an elliptic curve cryptosystem whose security depends on factoring; one was developed by Kenji Koyama, Ueli M. Maurer, Tatsuaki Okamoto and Scott A. Vanstone in 1991. You can read the article here.
The starting point is the observation that if a prime , then the elliptic curve defined by
has exactly points. (In general determining the number of points on an Elliptic curve is not easy; the best current method is the Schoof-Elkies-Atkin algorithm; have a look at this article for a discussion.) To show this, note that if , then there exists for which . Let be a primitive root of . Since is relatively prime to , it follows that is also a primitive root. Then if , it follows that ; in other words, the set of all cubes forms a complete residue set modulo . Since adding just cyclically permutes the residue set, the set is also a complete residue set modulo . Now, the number of non-zero quadratic residues of is . These quadratic residues provide solutions to
The other two solutions are where , and the point at infinity, giving points in total.
Let be two primes both equal to 2 modulo 3, and let . Then we can define the elliptic curve by
Since this curve is defined over a ring and not a field, addition will not always be possible. However, it is the starting point for the cryptosystem of Koyama et al. We start by observing that if then by the Chinese remainder theorem we can represent this point by the two points
where we use the abbreviation to mean . So, for example, if , so that , and is the curve
then the point
corresponds to the points
This means that the number of points on can be obtained by
where is the curve
and similarly for ; so that .
Alice picks a number and relatively prime to it to be her public key, and uses it to produce her private key
She publishes . Messages are pairs with . The ciphertext is obtained by
with being considered as a point in the elliptic curve
. Decryption is obtained by .
To show that this works, note that by the orders or and :
Now by definition for some , and in particular we can write
for some . This means that
and similarly for . This shows that , as required. For more details see “Elliptic curves: number theory and cryptography” by Lawrence C. Washington.
Here’s an example in Sage:
sage: p=next_prime(randint(500,1000));p%3 2 sage: q=next_prime(randint(500,1000));q%3 2 sage: N=p*q sage: [x,y]=[randint(1,N),randint(1,N)] sage: b=(y^2-x^3)%N sage: E=EllipticCurve(Zmod(N),[0,b]) sage: m=E(x,y) sage: l=lcm(p+1,q+1) sage: e=randint(1,l);gcd(e,l) 1 sage: d=inverse_mod(e,l) sage: c=e*m;c (33738 : 431045 : 1) sage: d*c (13161 : 338751 : 1) sage: m (13161 : 338751 : 1)