Elliptic curves and cryptography

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 E over a field k is a curve defined by an equation like y^2=x^3+ax+b where a,b\in k and 4a^3+27b^2\neq 0, along with a “point at infinity” denoted \mathscr{O}.

This “point at infinity” is obtained by considering the projectivization of E to get y^2z=x^3+axz^2+bz^3. Then our elliptic curve E sits on the plane (x:y:1). What if z=0? Then x=0. But now, y\neq 0, because (x:y:z)=(0:0:0) is not a point in projective space. And since we’re considering things up to scaling anyway, we can set y=1. The point at infinity is then the point (0:1:0).

Some of you may recognize 4a^3+27b^2 as the discriminant of the cubic x^3+ax+b. Its nonvanishing ensures that E is not singular, i.e., there’s no point where there aren’t tangents.

Let’s write E(k)=\{(x,y)\in k\times k | y^2=x^3+ax+b\}\cup\{\mathscr{O}\}. A very important result is the following.

Theorem (Hasse): If E is an elliptic curve over \mathbf{F}_p, then: |p+1-\# E(\mathbf{F}_p)|\leq 2\sqrt{p}.

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

For us, a field k will typically mean k=\mathbf{R},\mathbf{C}, or \mathbf{F}_p for some prime p. Also, a line in \mathbf{F}_p is defined by pairs (x,y)\in\mathbf{F}_p such that ax+by+c\equiv 0\bmod p. Note that this is the same thing as a line in \mathbf{R} or \mathbf{C}, but where we’ve added the \bmod p condition.

Construction: Let P,Q\in E(k). Define P+Q as follows. Consider the line through P and Q, and let R be the point where the line intersects E(k). Say that P+Q+R=0, so that P+Q is “-R“. Define P+\mathscr{O}=P, i.e., let \mathscr{O} be the identity element, and let P+(-P)=\mathscr{O}.

It’s simpler to imagine the case k=\mathbf{R}, because then P+Q is the reflection of R across the x axis. You can try to imagine what happens when P=Q, i.e., what P+P=:2P is. More interestingly, suppose the line from P to Q doesn’t intersect E(k) anywhere else. Then the line is tangent to either P or Q. If the line is tangent to P, then P+Q=-P, as you can see by drawing this out, and likewise, if the line is tangent to Q, then P+Q=-Q.

Over \mathbf{F}_p, given the point R=(x,y) (i.e., the point through which the line between P and Q intersects E(\mathbf{F}_p)), define -R=P+Q as the point with coordinates (x,-y\bmod p). There still are some problems when working in \mathbf{F}_p — for example, what does “tangent line” mean? To resolve this, one needs algebraic methods.

Proposition: Over k not of characteristic p (for us, this means k=\mathbf{R},\mathbf{C}), given P=(x_P,y_P) and Q=(x_Q,y_Q), it turns out that: R=(x_R,y_R) is \left(\lambda^2-x_P-x_Q,y_P+\lambda\left(\lambda^2-x_Q-x_P\right)\right) if P\neq Q, and is \left(\rho^2-x_P-x_Q,y_P+\rho\left(\rho^2-x_Q-x_P\right)\right) if P=Q.

Here \displaystyle\lambda=\frac{x_P-x_Q}{y_P-y_Q} and \displaystyle\rho=\frac{3x_P^2+a}{2y_P}.

Proof. If P\neq Q, then \displaystyle\lambda=\frac{x_P-x_Q}{y_P-y_Q} is the slope of the line between P and Q. If P=Q, then \displaystyle\rho=\frac{3x_P^2+a}{2y_P} is the first derivative of y=\pm\sqrt{x^3+ax+b} evaluated at (x_P,y_P). This follows because:

\displaystyle\left.\frac{\mathrm{d}y}{\mathrm{d}x}\right|_{(x,y)=(x_P,y_P)}=\left.\frac{1}{2y}(3x^2+a)\right|_{(x,y)=(x_P,y_P)}=\frac{3x_P^2+a}{2y_P}=\rho

Let’s write m to denote \lambda or \rho (depending on the context). This means that y=m(x-x_P)+y_P, i.e.: (m(x-x_P)+y_P)^2 = x^3+ax+b. Expanding gives:

f(x):=x^3-m^2x^2-m^2x_P^2+2m^2xx_P-y_P^2-2y_Pmx+2y_Pmx_P+ax+b = 0

We already know that x_P and x_Q are solutions to this polynomial. This polynomial has three distinct roots, so write f(x)=\prod_{i=P,Q,R}(x-x_i). Then x_P+x_Q+x_R=m^2, i.e., x_R=m^2-x_P-x_Q, and consequently y=y_P+m\left(m^2-x_Q-x_P\right). QED.

If you’re working in \mathbf{F}_p, the same result holds, but \displaystyle\lambda=\frac{x_P-x_Q}{y_P-y_Q}\bmod p and \displaystyle\rho=\frac{3x_P^2+a}{2y_P}\bmod p.

If p=2 or 3, then this doesn’t work. They have to be treated differently. We’ll therefore just assume that p>2,3. 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 k is of the form y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 where a_1,\cdots,a_6\in k.

If k is not of characteristic 2, then we can make the change of coordinates \widetilde{x}=x and \widetilde{y}=y+\frac{1}{2}(a_1x+a_3), to get an equation of the form y^2=x^3+\widetilde{a_2}x^2+\widetilde{a_4}x+\widetilde{a_6}. If k is in addition not of characteristic 3, then we can coordinate change again: x_\alpha=x+\frac{1}{3}\widetilde{a_2}+x and y_\alpha=y. This gives an equation of the form y^2=x^3+\overline{a_4}x+\overline{a_6}.

Exercise: Check these claims. Compute what \widetilde{a_2},\widetilde{a_4},\widetilde{a_6},\overline{a_4},\overline{a_6} should be in terms of a_1,\cdots,a_6.

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 P\in E(k). Define nP as P+\cdots+P, added n 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 n=\sum_{k=0} \alpha_k2^k where \alpha_k\in\mathbf{Z}/2\mathbf{Z}. Given P, first find 2^kP for all k such that \alpha_k\neq 0 (by doubling 2^{k-1}P), and then add them all together. This is faster than adding up P+\cdots+P by making n additions.

Suppose P\in E(k). Suppose also that k is finite (for us, this means that k=\mathbf{F}_p for some prime p). Let \langle P\rangle denote the cyclic group generated by P under this operation of addition. This means that \langle P\rangle=\{nP|n\in\mathbf{Z}\}.

Exercise: Show that \langle P\rangle is finite. (Use the fact that k is finite.)

Definition: The order of P\in E(k) is the smallest integer n such that nP=0. This is also referred to as the order of the subgroup generated by P.

Exercise: Show that the order of P is the same as the order (size) of \langle P\rangle.

Exercise (Lagrange’s theorem): This is a hard exercise. If H\subseteq G, and if \# H denotes the order (size) of H (and similarly for \# G), then \# G\equiv 0\bmod \# H, i.e., \# G is a multiple of \# H. The quotient \# G/\# H is denoted [G:H], and is called the index of the subgroup H in G.

As a corollary, the order of P (which is the order of \langle P\rangle) divides \# E(k). This suggests that one way to compute the order of P is the following:

Algorithm: Find \# E(k), and compute all of its divisors. Compute nP for every n|\# E(k). The smallest n such that nP=0 is the desired order of P.

How do we find the order \# E(k)? 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 k be finite. Suppose P,Q\in E(k). What is a n such that Q=nP?

This is called the discrete logarithm problem because this problem can be stated for a general finite group as well: given a,b\in G, what is a n such that a=b^n? 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 G be a finite cylic group, say of order n. Let g\in G be the generator of G. Alice considers some k\in\mathbf{Z}_{>0} such that 1\leq k<n, and sends g^a to Bob. Then Bob chooses some 1\leq b<n, and sends g^b to Alice. Alice computes g^{ab}, and Bob computes g^{ba}. These are the same thing, so they now have a shared key.

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

You might be more accustomed to thinking of this in the case G=\mathbf{Z}/p\mathbf{Z} for a prime p, in which case g is a primitive root modulo p.

Let p be a prime, and let P\in E(\mathbf{F}_p). Let \#\langle P\rangle=n. Pick some k\in\mathbf{Z}/n\mathbf{Z}. This is your \emph{private key}. The point Q:=kP is the \emph{public key}. The reason k is private is because given P and Q, finding k is hard because this means that you have to solve the discrete logarithm problem.

Elliptic Curve Diffie-Hellman (ECDH): Let Alice pick k_A\in\mathbf{Z}/n\mathbf{Z}, and let Q_A=k_A P be Alice’s public key. Let Bob pick k_B\in\mathbf{Z}/n\mathbf{Z}, and let Q_B=k_B P be Bob’s public key. Then Alice and Bob exchange Q_A and Q_B. Alice computes k_AQ_B=k_BQ_A=:M, and Bob computes the RHS. Thus M 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 P\in E(\mathbf{F}_p). Suppose Q=kP for some k. Write k=\ell i+j for some integers \ell,i,j. Then Q=(\ell i + j)P, i.e., Q-\ell i P = jP.

Let P\in E(\mathbf{F}_p) be of order n, and let Q\in \langle P\rangle\subseteq E(\mathbf{F}_p).

Baby-Step/Giant-Step: Let m=\left\lfloor{\sqrt{n}}\right\rfloor. Compute kP for every k\in\{0,\cdots,m\}, and store (k,kP) in a table. For every \ell\in\{0,\cdots,m-1\}, compute \ell mP. Then consider Q-\ell mP. If there some point our list of kP such that Q-\ell mP=kP, then Q=(\ell m+k)P, so we’ve solved the discrete logarithm problem.

What use is this without knowing how efficient this is? We are performing 2m operations when doing the additions: m steps in computing the kP, and at most m steps in computing \ell mP. For every \ell\in\{0,\cdots,m-1\}, we are comparing Q with all points between \ell mP and (\ell+1)mP. To compare the \ell m P with the kP, you want to use the most efficient table lookup. Now, it is apparently true that lookup in a hash table is O(1). This means that the time complexity is O(\sqrt{n}), better than brute force, which has O(n).

The problem is, this algorithm requires a lot of storage. In fact, it has O(\sqrt{n}) space complexity.

The Pohlig-Hellman Algorithm: Suppose P\in E(\mathbf{F}_p), and let Q\in\langle P\rangle. Suppose P has order n, i.e., \#\langle P\rangle=n. Let us factorize n as \prod_{i}q_i^{n_q} where the q_i are pairwise coprime. For each i, define P_i=\frac{n}{q_i}P. (A pretty trivial exercise is to show that the order of each P_i is q_i.) Suppose Q=kP. Using baby-step/giant-step, we can find k_i such that k_iP_i=\frac{n}{q_i}Q. But also: kP_i=k\frac{n}{q_i}P=\frac{n}{q_i}(kP)=\frac{n}{q_i}Q. This means that k\equiv k_i\bmod q_i for each i (the reason it’s modulo q_i is because the order of P_i is q_i). Now we have a system of congruences modulo relatively prime integers, so we can use the Chinese remainder theorem to find k.

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

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s