 # Elliptic Curve Cryptography

by Alana Drumgold*, Lauren Flowers, Emily Huang, Tamarr Moore*, and Ashleigh Sico.

*Alana and Tamarr helped the group work through the problem set but were unfortunately unable to attend camp during the blog writing.

For years, people have been trying to find a way to send secret messages. This may have been easy to do in the ancient times of the Roman Empire, where you could write a message, and then hand-deliver it to your recipient.  This way, you could be certain that nobody else could intercept it. However, this becomes a lot more difficult in today’s online tech-driven world. People no longer hand-deliver letters; rather, we email or text our friends.  So how do we make sure that nobody else can intercept your text message as it travels the internet before finally landing on your friend’s cell-phone? The answer is found in cryptography, a technology that is becoming more and more important in today’s world.  Today, we are going to focus on one particular form of cryptography: elliptic curve cryptography.

Elliptic curve cryptography has its foundations in a type of math called modular arithmetic.  When you first learned how to divide, you probably learned that 7/3 = 2 R 1. In modular arithmetic, you would write your answer as 7 ≡ 1 mod 3.  If we take another number, such as 16, and divide it by three, we get 16 ≡ 1 mod 3, because when it is divided by three, 16 has a remainder of 1. This makes 16 and 7 equal in mod 3, with can also be written as ℤ3.  ℤ3 is the set of remainders when a number is divided by three.  Every number can be written as either , , or . As 16 and 7 both have a remainder of 1, they can both be written as .  Numbers greater than 2 can be simplified by dividing by three. For example,  =  because the remainder is 0 when 12 is divided by 3.

An elliptic curve is a curve of the equation y^2 = x^3+ax+b that is drawn over a finite field, Fp.  Fp contains all the elements of the group ℤp, and thus follows modular arithmetic.  To find the points on an elliptic curve, we first must square all of the numbers in ℤp, next we plug the numbers into x^3+ax+b, anything that does not produce a perfect square does not fall in the domain of the curve.  The y values are then solved for.

Example of an Elliptic Curve: 