ELLIPTIC CURVE CRYPTOSYSTEMS

SCOTT BURLINGTON MCGILL–SCHOOL OF COMPUTER SCIENCE

                 SCOTTYB@CS.MCGILL.CA

Abstract. This is a partial presentation of Mugino Saeki’s MSc. thesis entitled Elliptic Curve Cryptosystems. Also the ElGamal and Disrete Logarithm over Z_{p} will be reviewed and introduced in a more general setting.

Date: December 2, 1996.

1. Background

We have seen the ElGamal Cryptosystem over the finite field of integers, Z_{p}. This cryptosystem relies on the intractibility of the Discrete Logarithm problem over Z_{p} to prevent decryption.

Definition 1 (Discrete Logarithm Problem). Given α, β ∈ Z_{p}, where p is a prime, find the unique a, 0 ≤ a ≤ p − 2, such that

α^{a} = β mod p

We will denote this by a = log_{α} β

Now recall the ElGamal scheme that we looked at to see how the discrete logarithm can be used to decrypt a message sent using such a system by some opponent.

Definition 2 (The ElGamal Cryptosystem). Let α ∈ Z_{p} a primitive element, β = α^{a} mod p, β ∈ Z_{p} and take P = Z_{p}, C = Z_{p}^{∗} × Z_{p}^{∗}, where the values α, β, and p are public, and a, k ∈ Z_{p−1} are secret, define

e_{K}(x, k) = (y_{1}, y_{2}), where
y_{1} = α^{k} mod p
y_{2} = xβ^{k} mod p

With the decryption, being, for y_{1}, y_{2} ∈ Z_{p}^{∗}

d_{K}(y_{1}, y_{2}) = y_{2}(y_{1}^{a})^{−1} mod p

Since α, β are both public then we can simply solve for a by,

log_{α} β = a

if the logarithm problem is tractable, and then performing the decryption in exactly the same manner as Bob.

In order to ensure the intractibility of the discrete logarithm problem over Z_{p} it is necessary to choose p with at least 150 digits and such that p − 1 has at least one “large” prime factor (to thwart a Pohlig-Hellman type attack). Primes with such attributes may be computationally difficult to determine, and we would desire access to a wide variety of such numbers, so that security from storage-based attacks is ensured. Not to mention the sheer bulk of numbers containing 150 digits may be undesirable in certain implementations such as “smart-cards”.

The point here is that there is motivation to look for groups other than Z_{p}^{∗} where the discrete logarithm is intractible, but in groups that may have some more appealing properties to us. Let’s first rephrase the discrete logarithm problem over a general group before seeing the most convincing argument of all for leaving Z_{p}^{∗}

2. Some Algebraic Definitions

The following are some definitions from group and field theory that will be helpful in the more general settings that we are going to be considering.

Definition 3 (Group). A set, G, and a binary operation, · (often addition, +, or multiplication, ×) such that

i [Associativity] a · (b · c) = (a · b) · c ∀ a, b, c ∈ G ii [Identity] ∃ e ∈ G such that e · a = a · e = a ∀ a ∈ G iii [Inverse] ∀ a ∈ G ∃ b ∈ G such that a · b = b · a = e and b is

defined as “a-inverse”, b = a^{−1}.

Definition 4 (Abelian Group). The group, G, is called Abelian if the operation is commutative for all the elements in the group.

Definition 5 (Order of a Group). The order of a group is the number of elements in the group.

Definition 6 (Order of an Element). The order of an element a ∈ G is the smallest integer, n, such that a^{n} = e (exponentiation defined by repeated application of ·).

Definition 7 (Cyclic Group). The group is cyclic if there exists an element a ∈ G that has order equal to the order of the group. If so a is a generator of G and we write ⟨a⟩ = G, the orbit of a is G.

Remark: Every element in a group has an orbit, and that orbit defines a cyclic subgroup of G and the order of that subgroup divides the order of G.

Definition 8 (Group Isomorphism). An isomorphism ϕ from a group G to a group \overline{G} is a one-to-one, onto mapping (or function) that preserves the group operation. That is,

ϕ(a · b) = ϕ(a) · ϕ(b), ∀ a, b ∈ G

If there is an isomorphism ϕ : G → \overline{G} then the groups are isomorphic and G ≈ \overline{G}

3. Generalized Discrete Logarithm

There is nothing special about Z_{p}^{∗}, in terms of it being one of many finite groups, which makes the discrete logarithm intractable. In fact, using our new definitions, we see that the problem defined over a general group, is almost identical to case over Z_{p}, as one might expect.

Definition 9 (Discrete Logarithm Problem). Let ⟨G, ·⟩ be a finite group and let α ∈ G β ∈ H where ⟨a⟩ = H. Define exponentiation as repeated application of ’·’. The unique integer a, 0 ≤ a ≤ |H| − 1, that relates α, β by,

α^{a} = β

is the discrete (because G is finite) logarithm.

We will denote this by a = log_{α} β

Any cryptosystem that was defined over Z_{p} can easily be seen to apply over ⟨G, ·⟩ by a simple change in perspective. However, for the discrete logarithm consider what has transpired with this change of perspective.

Consider ⟨Z_{n}, +⟩ and suppose that gcd (α)(n) = 1. The logarithm in this case is not a problem, with the addition operation we end up with exponentiation being simple modular multiplication, hence the logarithm problem is that of modular division, which is solved for us already using the Extended Euclidean Algorithm. The logarithm problem in this setting doesn’t seem so difficult.

In our previous setting of ⟨Z_{p}^{∗}, ×⟩, a cyclic group of order p − 1, the discrete logarithm seemed to be difficult to compute. We are not safe here however, since Z_{p}^{∗} ≈ Z_{p−1}, as indeed, all finite cyclic groups are isomorphic to the additive group of the appropriate order. An isomorphism, ϕ which gives us this result, is clear: for any generator of the cyclic group, α, define

ϕ(1) = 0 and ϕ(α^{k}) = k, k ≠ 0

This shows that solving the logarithm problem over Z_{p}^{∗} reduces to computing the exact isomorphism for the particular groups at hand, and then simply computing in Z_{p−1}. So the discrete logarithm for Z_{p} is as difficult as computing that isomorphism. This is, as it turns out, also apparently difficult to do when p is large, although it gives us another approach to breaking the logarithm problem. This is of course true in all groups G, but perhaps the particular representation of the group G may make it more or less difficult to compute this isomorphism. So we desire other groups where the discrete logarithm looks to be intractable, but may have less obvious representations. A fruitful direction to look in is the topic of the rest of this paper.

4. Elliptic Curves

disclaimer: Forgive the “magical” nature of some of the following results, but I will try to define the concepts appropriate to our particular setting as thoroughly as possible, and hopefully develop an example to clarify matters a little. The reason being that there is a significant amount of work going on “in the background”, refer to any text on elliptic curve theory for more details (such as [Sliverman, J.:The Arithmetic of Elliptic Curves, 1986]).

We begin with the definition of an elliptic curve.

Definition 10 (Elliptic Curve). An Elliptic Curve over G, E(G) can be seen as the set of points (x, y) x, y ∈ G together with O which are solutions to the cubic Weierstrass Equation over {R^{∈} ∪ O}, where O is the point at infinity [which is a beleivable concept in projective geometry!].

aside: I believe that R^{∈} will do here since G ⊊ R, but we may have to go up to C if my guess is wrong …

Let us assume, for technical reasons, that we are working over G such that characteristic(G) ≠ 2, 3 (which will server our purposes fine). By “completing the square” we then arrive at a simplified version of the cubic Weierstrass Equation defined as,

Definition 11 (The Weierstrass Equation). Let a, b ∈ G, then the cubic Weierstrass Equation is:

E : y^{2} = x^{3} + ax + b

4.1. Rules for Addition. An elliptic curve, E(G) or simply E, can be made into an abelian group with an appropriate binary relation on E.

Let P = (x_{1}, y_{1}), Q = (x_{2}, y_{2}) ∈ E and let the inverse of P, −P = (x_{1}, −y_{1})

Definition 12 (Addition in E). Let P + Q = (x_{3}, y_{3}), where

x_{3} = λ^{2} − x_{1} − x_{2}
y_{3} = λ(x_{1} − x_{3}) − y_{1}

with λ defined by

λ = \begin{cases}\frac{y_{2}−y_{1}}{x_{2}−x_{1}} , & P ≠ Q \\ \frac{3x_{1}^{2}+a}{2y_{1}}, & P = Q \end{cases}  (1)

Finally, define

P + O = O + P = P

So that O is the identity element for all P ∈ G

With “addition” defined thus, we now have a valid abelian group, ready for us to do our arithmetic in. It’s time now for an example of an elliptic curve so that we can go ahead and embed our cryptosystem in this new group.

\begin{matrix}x & F (x) & y \\ 0 & 6 & ∅ \\ 1 & 8 & ∅ \\ 2 & 5 & 4,7 \\ 3 & 3 & 5.6 \\ 4 & 8 & ∅ \\ 5 & 4 & 2,9 \\ 6 & 8 & ∅ \\ 7 & 4 & 2,9 \\ 8 & 9 & 3,8 \\ 9 & 7 & ∅ \\ 10 & 4 & 2,9 \end{matrix}

Table 1. Points on y^{2} = x^{3} + x + 6 over Z_{11}

5. An Elliptic Curve

A small example from [Stinson: Cryptography …] will suffice for introductory purposes.

Let E be the elliptic curve y^{2} = x^{3} + x + 6 over Z_{1}1. The points of E are calculated by taking the quadratic residues (read: modular square roots) of every point x from Z_{1}1. (Euler’s criterion is used for this calculation). Let F (x) = x^{3} + x + 6 mod 11, and the results are tabulated in Table 1.

Every (x, y) pair corresponds to one point on our elliptic curve. We can count and we will find that there are 13 points on our curve. By choosing a generator, α = (2, 7) for instance, we can compute the orbit of α on E. To compute 2α = (2, 7) + (2, 7) we first must find λ,

λ = (3 × 2^{2} + 1)(2 × 7)^{−1} mod 11

= 2 × 3^{−1} mod 11 = 2 × 4 mod 11 = 8

Giving us

x_{3} = 8^{2} − 2 − 2 mod 11 = 5

and

y_{3} = 8(2 − 5) − 7 mod 11 = 2

so 2α = (5, 2). We continue on with addends of α to compute λ and hence the new point on E until we reach 12α = (2, 4). Since there are 13 points on our elliptic curve, we affirm our hunch that α is indeed a primitive element in E(Z_{11}). These results are tabulated as follows:

α = (2, 7)  2α = (5, 2)  3α = (8, 3)
4α = (10, 2)  5α = (3, 6)  6α = (7, 9)
7α = (7, 2)  8α = (3, 5)  9α = (10, 9)
10α = (8, 8)  11α = (5, 9) 12α = (2, 4)

5.1. The ElGamal Cryptosystem over E. Now that we can “see” our group, let’s take a look at passing a message (insecurely here) from Alice to Bob. We have chosen α = (2, 7) already, so suppose that Bob’s secret exponent is a = 7. Thus Alice looks up Bob’s published β,

β = 7α = (7, 2).

The encryption takes place, for x = (10, 9)inE, k = 3 ∈ Z_{12}, as

e_{K}(x, k) = e_{K}((10, 9), 3) = (kα, x + kβ)
= (3(2, 7), (10, 9) + 3(7, 2))
= ((8, 3), (10, 2))

So, Bob receives the ciphertext y = ((8, 3), (10, 2)) and decrypts it as follows:

x = y_{3} − ax_{3} = (10, 2) − 7(8, 3)
= (10, 2) − (3, 5)
= (10, 2) + (3, 6)
= (10, 9)

Which is the message that Alice sent. And any observer would have to calculate a = log_{α}β = (7, 2)(2, 7)^{−1} where the inverse here would require a search on the space of #E, the number of points in E. Since #E ≈ p we can assume that this calculation is computationally infeasible if p is taken to be roughly 40 digits.