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, and sends $g^a$ to Bob. Then Bob chooses some $1\leq b, 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, 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.