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

and

where we use the abbreviation to mean . So, for example, if , so that , and is the curve

then the point

corresponds to the points

and

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

where

. Decryption is obtained by .

To show that this works, note that by the orders or and :

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)

Very Nice ! …… is that your ‘discovery’ ?