Class 19: Elliptic Curves!

Overview: In this lesson we show you how elliptic curve cryptography (ECC) works. Starting off with showing you that it has a role in the crypto eco-system that RSA doesn't fill. In this part pay attention to the key sizes.

OK, so the security of RSA becomes more and more expensive as our needs grow. As devices get smaller while adversaries get stronger the following table lets us know that that RSA is not the future of crypto.

Encryption	80	128	192	256
RSA/DH/DSA/ElGamal	1024	3072	7680	15360
Elliptic Curve Crypto	160	256	384	512
AES/3DES	80	128	192	256

There are several candidates for the future of public-key crypto, but the current crown-prince is elliptic curve crypto. It is much further along than lattice-based crypto /LWE and the new HE schemes. In fact let's see it in action:

Visit a secure site: use chrome to visit: https://staff.eecis.udel.edu/ . Go to the Three Dots Menu -> More Tools -> Developer Tools, then click on the Security Tab. This will give you a Security Overview with a View Certificate Button. Look for the Key Exchange mechanism and the encryption scheme. Feel good that you are learning useful stuff. Take a look at the same tabs for wikipedia, facebook, google, and any other https site you can think of.

Mechanics of Elliptic Curves

Overview: This part shows you the workings of Elliptic curves which really act as an interesting cyclic group.

So in some ways the math of elliptic curves is unusual and takes a bit to wrap your head around. BUT it is also a really great pitch for my first love, abstract algebra, because as soon as you squint the right way we can just see it all as our old-friend discrete log in a cyclic subgroup generated by an element. I love to see the same rules that I learned in an environment I feel comfy with used to build intuition in a new and unfamiliar territory. That is part of why math makes you such a flexible problem solver. </algebraPitch>

You probably remember old-school analytic geometry along the lines of $y = x^2$ describing the basic upward parabola.

The magic leap that helped you in Algebra 2 was that this equation has $(x,y)$ points that satisfy this equation. The locus of points which satisfy the equation make the picture we see. The picture allows us to have intuition which we can convert back to the equation world and vice-versa.

For instance. The equation $y=x^2$ convinces me that every real point on its locus must have a positive $y$ coordinate if I restrict myself to Real numbers. Also every non-zero value of $x$ leads to one point only and it must have a mirror-image on the other side of the y-axis (since $\sqrt{y}$ and $-\sqrt{y}$ are both answers for $x$).

Likewise we can make it more complex by having an equation of the form:

$$y^2 + x^2 = r^2 $$

Which traces out a perfect circle of radius $r$. Now I can imagine that any non-zero solution must have 3-mirror images out there, once around the x-axis, once around the y-axis.

The elliptic curves

These curves come from computing arclengths of ellipses, but they've been generalized enough to form their own family. The fully generic Elliptic curves we explore have the form $y^2 = x^3 + a\cdot x + b $

Wikimedia Image

I know it feels like we're in a vastly different world, but we're almost back to computation. First some observations:

Every $(x,y)$ that satisfies our equation has another point at $(x,-y)$ which is also on the curve.
Draw a line through any two points and you either hit a third point on the curve or hit infinity.

Wikimedia Lines ECC

Plot some: Head to the SAGE cloud, and try the following lines: E=EllipticCurve([-1, 1]) and plot(E)

Finding the Cyclic Group

There is a group hidden in these curves which works under the following "addition" operation:

Given $P,Q \in E$ we want to calculate $P+Q$ also in $E$
Find the line between $P$ and $Q$
There is a third point on that line (or infinity), whenever we touch at a tangent that point counts twice.
The summation is the mirror of that third point (flip around the x-axis).

Addition

Try it: Define P=E(1,1) and Q=E(0,1) . Then do P+Q and even E.is_on_curve(*(P+Q).xy()) . What are the coordinates of P+Q+P+Q ? Look back at the plot and see if these coordinates make sense.

If we define the negative of $P=(x,y)$ as $-P=(x,-y)$ then $P+-P$ is the point at infinity. That would make the infinty point our identity.

Prove Groupiness: Convince yourself that the solutions to an elliptic curve and this version of addition together form a group (identity, inverses, associativity, closure). Is this group commutative ($A + B = B + A$)?

Changing the domain and our computations:

So the Real number interpretation helps us visualize but our elliptic curves will be defined over $\mathbb{Z}_p$.

This adds one constraint to the ellipic curves so that they aren't singular: $4\cdot a^3 + 27 \cdot b^2 \neq 0$

Diophantine Systems: Visualize how elliptic curves look over the integers by plotting the same curve over a finite field. Do FE = EllipticCurve(GF(101), [-1, 1]) then plot(FE) in SAGE. How is that plot different?

Here are the rules to get $x_3, y_3$ from adding $P=(x_1, y_1)$ and $Q=(x_2, y_2)$:

$s := \frac{(y_2 - y_1)}{(x_2 - x_1)}$ when $P \neq Q$
$s := \frac{(3\cdot x_1^2 + a)}{2 y_1}$ when $P = Q$
$x_3 = s^2 -x_1 -x_2 \mod{p}$
$y_3 = s(x_1 -x_3) -y_1 \mod{p}$

Implement these rules: make your own addition function and confirm them with the elliptic curves on SAGE.

Here are some videos of me tooling around with ECC:

ECC in the trenches

Overview: Finally we actually pull off an encryption/decryption with a real elliptic curve system. It's not easy but also not so bad when you think modularly.

Right now we have seen the group structure of Elliptic Curves and started to explore their behavior over $\mathbb{Z}_p$. If we want to use all of the insights we learned from exploring Diffie-Hellman in this new group then we should think about the following questions:

How do we pick a curve and prime modulus?
What is the order of the largest cyclic group we work in?
How do we find points on the curve? (This wasn't a diffie-hellman concern really)
How do we pick a generator of that group?
How do we do fast exponentiation? (Multiplication in the ECC case.)

Once we have a suitable curve with a generator then the rest should be pretty easy. Let's say that our modulus is $p$, our curve is given by $y^2 = x^3 + Ax + B$, we have a generator $P$, and the number of elements on the curve is $q$. Then to share a secret:

Alice picks a secret key $a \in \mathbb{Z}_q \setminus {0} $.
Alice computes her (ephemeral) public key $aP$ which she sends to Bob.
Bob picks a secret key $b \in \mathbb{Z}_q \setminus {0}$.
Bob computes his (ephemeral) public key $bP$ which he sends to Alice.
Bob computes $b \cdot aP$, Alice computes $a \cdot bP$, now they both know the shared secret.
Probably hash that and switch to AES

Answering Our Questions

Just like the original DH key exchange, if we can work in a group of prime order then everything else becomes simple. Most of our questions are answered by finding curves with a prime number of elements on the curve. That means that counting points on an elliptic curve is a fundamental problem for ECC.

So if we want to make secure Elliptic Curves of our own we need some work. Namely we must be able to count the number of points $(x,y) \in \mathbb{Z}_p \times \mathbb{Z}_p$ that satisfy the equation. Writing that algorithm is complex and beyond the scope of this course. But, of course, we've been using the SAGE cloud so we can actually answer the question:

Finding the answer is easy as E=EllipticCurve(Zmod(p), [A, B]) E.cardinality()

Using pre-analyzed curves

So the standard in ECC is to use curves that have been recommended by NIST. The idea of that makes me nervous, frankly. There are alternative community made curves out there ( like https://cr.yp.to/ecdh.html ).

But for now let's do it to get us kick-started.

Look at the approved curves: use the command openssl ecparam -list_curves to look at the curves which have been approved. Typically these are curves with good properties like generalized-Mersenne prime-order groups.

Generate some ECC parameters: use the command openssl ecparam -name brainpoolP512t1 -out brainpoolP512t1.pem -param_enc explicit

Read your parameters: use the command openssl ecparam -in brainpoolP512t1.pem -text -noout

I feel like we waste a lot of time reading in hex-based numbers and getting integers, so here is a param reader script I hacked together:

Use parameters: Here is how you can use that script. Save it into a file named read_params.py and put your parameters in a file named parameters with a command like this: openssl ecparam -in brainpoolP512t1.pem -text -noout > parameters Then run python -i read_params.py and you'll have an object named params to get values out, like params["Prime"] or params["A"] . Note that I had to split the generator and that the "04" prefix is to be tossed out. It comes out at a tuple.

Confirm the generator: confirm that the generator is on the curve by computing $x*x*x + a*x + b$ and $y*y$ modulo $p$.