An elliptic curve cryptosystem based on factoring

In an elliptic curve E 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 P,Qin E with Q=nP it is in general very difficult to determine n.

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 p=2pmod{3}, then the elliptic curve E defined by

y^2=x^3+bpmod{p}

has exactly p+1 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 p=2pmod{3}, then there exists t for which 3t=1pmod{p-1}. Let r be a primitive root of p. Since t is relatively prime to p-1, it follows that s=r^t is also a primitive root. Then if x=s^kpmod{p}, it follows that x^3=r^kpmod{p}; in other words, the set of all cubes forms a complete residue set modulo p. Since adding b just cyclically permutes the residue set, the set x^3+bpmod{p} is also a complete residue set modulo p. Now, the number of non-zero quadratic residues of p is (p-1)/2. These quadratic residues provide 2(p-1)/2=p-1 solutions to

y^2=x^3+bpmod{p}.

The other two solutions are (x_0,0) where x_0^3+b=0, and the point at infinity, giving p+1 points in total.

Let p,q be two primes both equal to 2 modulo 3, and let N=pq. Then we can define the elliptic curve E by

y^2=x^3+bpmod{N}

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 (x,y)in E then by the Chinese remainder theorem we can represent this point by the two points

(x_p,y_p) and (x_q,y_q)

where we use the abbreviation x_n to mean xpmod{n}. So, for example, if p,q=17,23, so that N=pq=391, and E is the curve

y^2=x^3+1pmod{391}

then the point

(x,y)=(150,209)

corresponds to the points

(x_p,y_p)=(14,5) and (x_q,y_q)=(12,2)

This means that the number of points on E can be obtained by

|E|=|E_p| |E_q|

where E_p is the curve

y^2=x^3+bpmod{p}

and similarly for E_q; so that |E|=(p+1)(q+1).

Alice picks a number e<mbox{lcm}(p+1,q+1) and relatively prime to it to be her public key, and uses it to produce her private key

d=e^{-1}pmod{mbox{lcm}(p+1,q+1)}.

She publishes (N,e). Messages M are pairs (m_1,m_2) with 0le m_1,m_2le N-1. The ciphertext is obtained by

C=e(m_1,m_2)

with (m_1,m_2) being considered as a point in the elliptic curve

y^2=x^3+bpmod{N}

where

b=m_2^2-m_1^3pmod{N}. Decryption is obtained by m=dC.

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

(p+1)M=inftypmod{p} and (q+1)M=inftypmod{q}.

Now by definition de=1+k(mbox{lcm}(p+1,q+1)) for some k, and in particular we can write

de=1+K(p+1) for some K. This means that

dC=deM=(1+K(p+1))M=M+k(p+1)M=M+infty=Mpmod{p}

and similarly for q. This shows that dC=M, 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)

One thought on “An elliptic curve cryptosystem based on factoring

Leave a Reply

Your email address will not be published. Required fields are marked *