By Mukta Dharmapurikar, Anagha Jandhyala, Savanna Jones, and Ciara Renaud.

Have you ever wondered how your credit card number stays secure after shopping online? Every day millions of people’s personal information is entered online or stored in databases, where it seems like anyone could access it. However, a process called cryptography keeps theft from occurring.

Cryptography is the ancient art of keeping secret messages secure. Elliptic curve cryptography is one type of encryption that we spent the last two weeks learning about. It has some advantages over the more common cryptography method, known as RSA.

RSA relies on the difficulty of factoring very large prime numbers. Despite the current security, it’s feasible that one day a method could be invented that makes factoring large prime numbers realistic. In this blog post, we will be explaining the essential math behind how elliptic curves work and how they are used to encrypt messages.

Modular Arithmetic:

Modular Arithmetic is applied to Elliptic Curve Cryptography in order to provide a smaller set of numbers with certain properties. To do so, modular arithmetic establishes a group of numbers as a “set” in a group modulo n. This group includes all integers from 0 to n-1 and cycles around itself and represents only the values of the elements in that group. Remainders of numbers when divided by n represent their values.

For example, the number 7 in Mod 5 actually represents the value of two, because five goes into seven once with a remainder of two. 12 is also equivalent to two, since five goes into 12 twice with a remainder of two. (5 * 2 = 10; 12 – 2 = 10) So we say that 12 = 2 mod 10. Multiples of five modulo 5 equal 0. For example: five, ten, fifteen, twenty, and so on all equal zero in mod 5, since five is not included in the set of numbers modulo five.

Any number will fit in as a value in the set of modular numbers, so there are only really “n” numbers mod “n”. For example, even large numbers, like 10,001, fit into mod 5. 10,001 equals 1 mod 5, since 10,001/5 equals 2,000 remainder 1. This attributes a certain finiteness to modular numbers, which can make it easier to calculate elliptic curves, as will be explained later.

These properties can also be applied to multiplication and addition. For example, 6 + 8 in mod 5 equals 4, since 6 + 8 equals 14 and 14/5 equals 2 remainder 4. 6 * 8 in mod 5 equals 3, since 6 * 8 = 9 remainder 3.

We can also compute negative numbers in modular arithmetic by traveling backwards in the set. -6 equals 7 modulo 13 because 13 – 6 = 7. Remember: the number thirteen represents the “zero” value in this case. -24 equals 2 modulo 13 because 24/-13 = -2 remainder 2. Think of it like this: 13 * -2= -26; -26 + 2 = -24.

When calculating modular primes, we can find something called the “multiplicative inverse”. The multiplicative inverse of “n” is the number that, when multiplied by n, will produce a value of 1 in a certain mod.

For example, 6 is the multiplicative inverse of 3 (and vice versa) in mod 17, because 6 * 3 = 18 = 1 (6 times 3 equals 18, which equals one in mod 17, since it’s 17 * 1 with a remainder of 1). You can write the multiplicative inverse of a number as itself to the power -1, or as 1 over it. 6^-1 = 3 modulo 17 and 1/6 also equals 3 mod 17. This only works with modular numbers that are prime!

For example, 3 does not have a multiplicative inverse modulo 6, since there isn’t a single number you can multiply by three to get a remainder of one when divided by six. You will always get either a remainder of three, which equals three, or no remainder, which equals zero. (ex. 3 * 4 = 12 = 0, and 3 * 7 = 21 = 3 in mod 6).

Modular arithmetic is a foundational piece of elliptic curve cryptography because it limits the number of variables in a set. This allows us to generate an elliptic curve and assign letters to certain points on that curve possible.

Group Theory:

Group theory can be broadly explained as the study of symmetries.

For example, we can explore the “symmetries” of an equilateral triangle in order to better understand the properties of a group. First, let’s define the “symmetries” of an equilateral triangle as some rigid motion that will place the triangle back on top of itself. We can arrange the order of two symmetries into a series producing a meaningful transformation of our triangle and its vertices. In other words, we can use a specific series of movements to change the order of our labeled vertices on a triangle but maintain the angle the triangle was originally positioned at. In this case, different series can result in differing orders of the equilateral triangles vertices. Each resulting depiction of our transformations is an element in this grouping.

Groups (G) typically abide by the following properties:

1. When “a” and “b” are elements of G, a * b = c. In which case, c is another element of G.
2. There is a special element of G referred to as an “identity”, typically referred to as “e”. The identity has the following unique property: e * a = a * e = a for any element “a”.
3. If “a” is an element of G, then there is a unique element “b” called the “inverse” of “a”. It satisfies the property that a * b = b * a = e. Sometimes this inverse element is written as a^-1.
4. If “a, b, c” are three elements of G, then a * (b * c) = (a * b) * c; that is, the operation is associative.

Some examples of groups that you may already be familiar with include integers, rational numbers, and even the symmetries of equilateral triangles.

Different groups utilize different functions, integers use addition and rational numbers use multiplication. Integers and rational numbers are also considered “Abelian” groups. Named after mathematician Niels Abel, “Abelian” groups possess the property in which a + b = b + a. Real and complex number groups are also considered “Abelian”.

Our example group of the symmetries of an equilateral triangle is not abelian, because the order of our movements within each series matters. In other words, the transformations are not associative.

We can visualize these principles through the use of Cayley tables. If a group is abelian, its Cayley table will be symmetrical along the diagonal. Cayley tables provide evidence for many group observations. For example, if a group possesses a certain “identity” element, the first row and column of a Cayley table will be equivalent to the non-identity element used in conjunction with the identity element. Think along the lines of  1 x 3 = 3.

In addition, if a group’s elements correspond to another group’s, the two are considered isomorphic. This conclusion is typically based off of the formation of both Cayley tables.

In a group, there are certain elements that have the potential to produce the rest of the group.

For example:  5 = 1+1+1+1+1, therefore 1 is a “generator” of 5.

There can be multiple generators within each group; however, groups with only one generator are considered “cyclic”. If a group is cyclic it must be abelian, but an abelian group may not always be cyclic.

Finally, if two groups are both cyclic (one generator) and the same size, they are automatically isomorphic.

 

Elliptic Curves:

Modular Arithmetic and Group Theory begin to come together when dealing with Elliptic Curves over finite fields. So what is a finite field? A finite field is simply a set of a certain amount of numbers, that also includes infinity. These numbers will also correspond to points on the elliptic curve. Elliptic curves follow this equation: y² = x³ + ax + b. The point of solving these equations is to find the exact points of the curve, by only using the numbers in the field. 

For example, let’s look at the equation: y² = x³ +3x + 8 in F13. The field F13, uses mod notation, meaning the numbers in the field would be [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. Using this, we would square every number in the field, because we are solving for y².  To make it easier to see, we put the numbers in a table.

 

As you can see in the table, all the numbers in the field are squared, and then the answer is put into mod 13 notation. If you look at 4^2, the answer would normally be 16, however since we are in mod 13, the remainder is 3, making the answer 3 as well.

Next you make an additional table for the x values, which once again are all the numbers in field 13. You substitute in values in the x spot of the equation y² = x³ +3x + 8. We also put this in a table, to be able to view the values clearly.

 

After working through the two tables, you simply compare the equation side of the x table and the column of y². We want to look and see where the numbers are the same, because our overall goal was to solve y² = x³ + 3x + 8.

When doing this we see that the only x coordinates that match are x = [1], [2], [9], and [12]. Consider the x value [1], which corresponds to the value [12] in the equation column. We then compare the value [12] to the table with the y^2 values.

In that table, we find the [12] in the y^2 column, and match it to the y value that corresponds to it. In this case, the [12] corresponds to the y value [5]. Now you have found the coordinate ([1],[5]), which  is a point on the elliptic curve. In this example the elliptic curve had 9 points, including infinity. This is very important information when using cryptography, because we can assign each point on the curve, a letter value, making writing messages possible!

 

Elliptic Curve Cryptography:

 

Before we can understand cryptography, we first have to understand how to perform operations on points on an elliptic curve.  An elliptic curve is a group, so it possesses all the characteristics of a group mentioned above.

The formula for point addition is as follows:  a₃ = (b₂ – b₁/ a₂ – a₁)² – a₁ – a₂.

All of the previous concepts come together in order to encrypt information.  Each point on an elliptic curve is assigned a corresponding letter. Two parties can send a message to each other without any third parties intercepting and decoding the message through the use of a public key and a private key.  The following are the steps involved in the encryption process:

1. A finite field, F, an elliptic curve, E(F), and a point on the elliptic curve, B, are chosen.  This information is all public and can be accessed by anyone.
2. Each party privately chooses a number between 0 and the size of E(F).  These numbers are known as a and b.
3. The first party adds the point B a times (aB).  The second party does the same with their number b and gets bB.
4. The two parties publicly exchange aB and bB.
5. Each party adds the value they just received from the other party their chosen number of times a(bB) or b(aB).  Now, both parties have abB.  This is known as the private key, P.
6. The two parties can now exchange secure messages by taking their desired points and adding P to each point, sending these values to the other party, and then subtracting P from each value to arrive at the original point, and the decoded message.

Since there are a finite number of point on E(F), it is theoretically possible that a third-party could take the point B and add it to itself every single possible number of times.  For example, if there are only five points on an elliptic curve, it would be fairly easy to add B to itself two, three, four, and five times.  In doing this, a third party would be able to figure out a and b by matching aB and bB to the points they calculated.  However, this becomes unrealistic when the number of points on the elliptic curve becomes very large.  The security of elliptic curve encryption relies upon the idea that it takes an unrealistically long amount of time to calculate all possible aB or bB values when the number of points becomes too large.

 

Conclusion and Reflection:

While the road to understanding Elliptic Curve cryptography was interesting and exciting, there were many twists and turns along the way. Our greatest challenge was that ECC is extremely hard to conceptualize as most of the math differed from our previous understandings and was often very theoretical or abstract.

However, we thoroughly enjoyed learning about topics in math, typically not discussed in school. For example, on the first day, we were learning about modular arithmetic. It was a difficult concept to grasp because it was fundamentally different then what we had learned before. Over time, just by working through the problem set, we became more and more comfortable with the topic, even going as far as being able to explain how it works to other people.

This goes to show, that even when faced with a very difficult problem set, if you keep persevering, eventually you will understand the math. Girls Talk Math has really taught us to never give up, and increased our confidence in learning higher level math.