I taught a class on elliptic curves and cryptography to high school students. Here are some things that I wrote.

**Elliptic Curves**

Definition:An elliptic curve over a field is a curve defined by an equation like where and , along with a “point at infinity” denoted .

This “point at infinity” is obtained by considering the projectivization of to get . Then our elliptic curve sits on the plane . What if ? Then . But now, , because is not a point in projective space. And since we’re considering things up to scaling anyway, we can set . The point at infinity is then the point .

Some of you may recognize as the discriminant of the cubic . Its nonvanishing ensures that is not singular, i.e., there’s no point where there aren’t tangents.

Let’s write . A very important result is the following.

Theorem(Hasse):If is an elliptic curve over , then: .

Elliptic curves are rather special, because there is a method of adding points on such curves that makes into an abelian group. This means that they are “one-dimensional abelian varieties”.

For us, a field will typically mean , or for some prime . Also, a line in is defined by pairs such that . Note that this is the same thing as a line in or , but where we’ve added the condition.

Construction:Let . Define as follows. Consider the line through and , and let be the point where the line intersects . Say that , so that is ““. Define , i.e., let be the identity element, and let .

It’s simpler to imagine the case , because then is the reflection of across the axis. You can try to imagine what happens when , i.e., what is. More interestingly, suppose the line from to doesn’t intersect anywhere else. Then the line is tangent to either or . If the line is tangent to , then , as you can see by drawing this out, and likewise, if the line is tangent to , then .

Over , given the point (i.e., the point through which the line between and intersects ), define as the point with coordinates . There still are some problems when working in — for example, what does “tangent line” mean? To resolve this, one needs algebraic methods.

Proposition:Over not of characteristic (for us, this means ), given and , it turns out that: is if , and is if .

Here and .

*Proof.* If , then is the slope of the line between and . If , then is the first derivative of evaluated at . This follows because:

Let’s write to denote or (depending on the context). This means that , i.e.: . Expanding gives:

We already know that and are solutions to this polynomial. This polynomial has three distinct roots, so write . Then , i.e., , and consequently . QED.

If you’re working in , the same result holds, but and .

If or , then this doesn’t work. They have to be treated differently. We’ll therefore just assume that . The reason these primes are weird is the following. I lied a bit before when defining elliptic curves. The actual definition is the following.

Definition:An elliptic curve over a field is of the form where .

If is not of characteristic , then we can make the change of coordinates and , to get an equation of the form . If is in addition not of characteristic , then we can coordinate change again: and . This gives an equation of the form .

**Exercise: **Check these claims. Compute what should be in terms of .

**Remark: **For more on this, see any standard book on elliptic curves. Also see http://math.rice.edu/~friedl/papers/AAELLIPTIC.PDF. This studies the formal group law of the elliptic curve.

Let . Define as , added times. How many operations should you perform? It might seem like quite a bit, but this can actually be made simpler. Consider the binary expansion where . Given , first find for all such that (by doubling ), and then add them all together. This is faster than adding up by making additions.

Suppose . Suppose also that is finite (for us, this means that for some prime ). Let denote the cyclic group generated by under this operation of addition. This means that .

**Exercise: **Show that is finite. (Use the fact that is finite.)

Definition:The order of is the smallest integer such that . This is also referred to as the order of the subgroup generated by .

**Exercise: **Show that the order of is the same as the order (size) of .

**Exercise (Lagrange’s theorem): **This is a hard exercise. If , and if denotes the order (size) of (and similarly for ), then , i.e., is a multiple of . The quotient is denoted , and is called the index of the subgroup in .

As a corollary, the order of (which is the order of ) divides . This suggests that one way to compute the order of is the following:

Algorithm:Find , and compute all of its divisors. Compute for every . The smallest such that is the desired order of .

How do we find the order ? There is something called Schoof’s algorithm. I won’t go into this, mostly because I’m still learning it, and also because it is pretty complicated and involves invoking more technology than I think is appropriate for SPLASH. See Wikipedia for more.

**The discrete logarithm problem and cryptography**

Problem (discrete logarithm):Let be finite. Suppose . What is a such that ?

This is called the discrete *logarithm* problem because this problem can be stated for a general finite group as well: given , what is a such that ? There are no known efficient algorithms for solving this problem on a classical computer. Using quantum computers, however, this problem can be solved.

Let’s now describe the way you can use the discrete logarithm problem in cryptography. First I want to recall the Diffie-Hellman key exchange algorithm.

Algorithm (Diffie-Hellman):Let be a finite cylic group, say of order . Let be the generator of . Alice considers some such that , and sends to Bob. Then Bob chooses some , and sends to Alice. Alice computes , and Bob computes . These are the same thing, so they now have a shared key.

**Remark: **This is secure if there’s no efficient algorithm to find if you’re given . The most efficient way to do this (that’s known to date) is to try the stupidest thing possible: find and by solving the discrete logarithm problem for .

You might be more accustomed to thinking of this in the case for a prime , in which case is a primitive root modulo .

Let be a prime, and let . Let . Pick some . This is your \emph{private key}. The point is the \emph{public key}. The reason is private is because given and , finding is hard because this means that you have to solve the discrete logarithm problem.

Elliptic Curve Diffie-Hellman (ECDH):Let Alice pick , and let be Alice’s public key. Let Bob pick , and let be Bob’s public key. Then Alice and Bob exchange and . Alice computes , and Bob computes the RHS. Thus is now the shared secret.

Note that in Diffie-Hellman and in ECDH, you don’t get to choose what you’re encrypting. This is good when you want key exchange.

**Cracking the discrete logarithm problem**

The first algorithm I want to talk about is the baby-step/giant-step algorithm. Suppose . Suppose for some . Write for some integers . Then , i.e., .

Let be of order , and let .

Baby-Step/Giant-Step:Let . Compute for every , and store in a table. For every , compute . Then consider . If there some point our list of such that , then , so we’ve solved the discrete logarithm problem.

What use is this without knowing how efficient this is? We are performing operations when doing the additions: steps in computing the , and at most steps in computing . For every , we are comparing with all points between and . To compare the with the , you want to use the most efficient table lookup. Now, it is apparently true that lookup in a hash table is . This means that the time complexity is , better than brute force, which has .

The problem is, this algorithm requires a lot of storage. In fact, it has space complexity.

The Pohlig-Hellman Algorithm:Suppose , and let . Suppose has order , i.e., . Let us factorize as where the are pairwise coprime. For each , define . (A pretty trivial exercise is to show that the order of each is .) Suppose . Using baby-step/giant-step, we can find such that . But also: . This means that for each (the reason it’s modulo is because the order of is ). Now we have a system of congruences modulo relatively prime integers, so we can use the Chinese remainder theorem to find .

This is more effective than just applying baby-step/giant-step, because each , so each baby-step/giant-step (for every ) runs faster. There are other kinds of attacks on elliptic curve cryptography, but we’ll end here.