By Noa Bearman, Kimberly Cruz Lopez, Tina Lin, Xintong Xiang, and Maria Neri Otero*

*Maria helped the group work through the problem set but was unfortunately unable to attend camp during the blog writing.

Introduction

Have you ever tried to send a secret message to a friend? Did it work? Was it secure? Well, one way to do so in a more secure way is by using Elliptic Curve Cryptography (ECC). Most people have never heard of ECC before, and two weeks ago, neither did we. However, in the past two weeks, we have been learning how to use this exciting application of the techniques of algebraic geometry and abstract algebra applied to the ancient art of keeping messages secure. ECC was first introduced by Victor Miller and Neal Koblitz in 1985. It was proposed as an alternative to other forms of cryptography with public-key systems such as DSA and RSA. Public-key systems involve the use of two different kinds of keys: a public key that is available to the public and a private key in which only the owner knows. The applications of ECC has been growing and has recently gained a lot of attention in industry and academia. The following information below will go more in-depth on what ECC is, how it works, its advantages, its disadvantages, and our progression throughout this course.

Importance of Cryptography in Real World Applications

Cryptography is used everywhere, from keeping credit card information secret to the authentication of digital signatures, to securing classified government information. Elliptic Curve cryptography is a fairly new version of cryptography, but it is quickly becoming the cryptographic method of the future. It has many advantages over RSA cryptography, the most common form that is used worldwide. Since it is based on sets of points on an elliptic curve rather than exceedingly large prime numbers, much shorter and compact keys for ECC are at the same level of security as a huge RSA key. Because of this, it also has lower CPU (Central Processing Unit) consumption and takes up less memory storage. This means that messages in ECC can be encoded and decoded faster and more efficiently while being as or more secure than the same messages in RSA. Why is cryptography so important and complex? This is due to the fact that it is almost impossible to keep lines of communication secure. Phone calls, emails, and other methods of sending information can be hacked quite easily or bugged quite easily, and if the company that provides those services wanted to share that information, they could certainly do so. Once a line of communication is breached, the information is defenseless. The purpose of cryptography is to ensure that even if the message falls into the wrong hands, it will be secure because the message itself was encoded, only able to be decrypted by whom it was sent to.

There are also disadvantages to ECC when compared to other forms of cryptography. One main disadvantage of ECC is the size of the encrypted message. It is significantly bigger in size when compared to the most commonly used form of cryptography, RSA. Another disadvantage of ECC is the complexity of the algorithms involved along with the difficulties of implementing them, which can increase the likelihood of implementation errors.

How It Works

Elliptic Curve Cryptography (ECC) is a complex system of coding that is based on the points of an elliptic curve within a set region, in which the points are in modular. Modular basically means remainder, (brackets [] are the notation for modular) so in F5 [8]=[3] because both 8 and 3 have remainders of 3 when divided by 5. Throughout this course, we have worked through problems preparing us for what we need to know before we attempt ECC.  We began with understanding how to use modular and continued on to learn about sets, fields, and generators, all of which led to our understanding of ECC. ECC is a public key cryptography system, so there’s a public key that allows anyone to encrypt information. However, there is also a private key that only the sender and receiver know in order to decrypt information. The field, equation for the curve, and generator point (called “B”) are all public information.  Then individually each party chooses one number from the data set (which remain private), which we will call a and b, and multiplies it by the generator, B.  Then each party multiplies their number by B (so one person will have aB and one will have bB). This is then sent to the other person.  Now person A has bB, and person B has aB. They then each multiply this by their original number, so they each end up with “abB”. This is considered point P.  This point is used for encrypting the code. Point P is added to each point when it is being sent, and the receiver then subtracts P from the point sent, ending with the original point sent.  The original point being sent is aligned with a letter or symbol on a public key which the receiver can refer to get the message. Notice that throughout this process, person B does not ever get to know person A’s number, or a, and vice versa. This is very useful when sending multiple messages, make it easier on the computation when the number/point chosen at the beginning does not ever have to be changed.

If this is confusing, you can refer to this video which offers a great visualization of the process:

Here’s an example:

Public Key	Private Key
The field is F13, which means that only the numbers 0-12 are used in the points. The Elliptic Curve function E(F): y2=x3+3x+8 The point B ([1],[5]), which is a generator of this group The key for how points are associated with letters, as shown above	Person A has their own number a and the point P that results from abB. Person B has their own number b and the same point P that results from baB.

For example, if Person A chooses the number 8, he/she would add the generator point B to itself 8 times, and end up with the point ([1],[8]) (this will make sense once you go into how modular works). Person B chooses an arbitrary number 3, and he/she adds the point B to itself 3 times, ending up with point ([9],[7]). Then they send these points to each other and multiply their numbers by these points. So person A would do 8 x ([9],[7]), and person B would do 3 x ([1],[8]), and end up with the same point ([2],[10]). If Person A wants to send the letter T to person B, she would choose the point that corresponds to the letter T, which is ([1],[5]). Then she would encrypt the point ([1],[5]) by adding to it the point that she and person B have in common, which is ([2],[10]), ending up with the point ([9],[7]). She sends this point to person B, who then subtracts ([2],[10]) from ([9],[7]), since that is their private key, and arrives with the point ([1],[5]), which he knows corresponds to the letter T through the public key. This cryptography method works because even if someone intercepted the information while they were sending it, they would not be able to figure out the message, because even if you know aBand bB, in this case ([1],[8]) and ([9],[7]), you would not be able to solve for abB, or point ([2],[10]), which they used to encrypt the message.

• • How to add points when P=([a1],[b1]) is a point on the elliptic curve (E) and Q=([a2],[b2]) is another point of E such thatQP. P+Q=([a3],[b3])
    • [a3]=(([b2]-[b1])/([a2]-[a1]))2-[a1]-[a2]
    • [b3]=(([b2]-[b1])/([a2]-[a1]))([a1]-[a3]) -[b1]
  • How to add a point to itself (Point doubling) when P=([a1],[b1]) is a point on E, where P-P. 2P=([a3],[b3])
    • [a3]=((3[a1]2+a)/2[b1])2-2[a1]

• [b3]=((3[a1]2+a)/2[b1])([a1]-[a3])-[b1]

Conclusions and Reflections

Although Elliptic Curve Cryptography can be slow when done by hand, the process is considerably faster when using computers to send information. We did all of our calculations by hand so as to better understand the process and also because those were the tools available to us, but if this was done professionally it would be slightly different. The fields of numbers would also be much larger as it would not be difficult for a computer to solve them.

While we were attempting to understand ECC we ran into some difficulties along the way. We had some trouble understanding how ECC was private and how it wouldn’t be possible for a third party to decode the information.  By going through the practice example given, we were able to better understand this but ran into an issue when we realized we would have to subtract P, and weren’t given an equation to do so.  We quickly realized that this had a simple fix by using -P ([x],[-y]), or (a2,-b2) using the same addition formula but replacing b2with -b2 to solve for the point being sent (a3,b3).  After these few difficulties, we were able to better understand ECC and are now able to send codes to each other. Exploring ECC also exposed us to many aspects of math that we were not familiar with, like modular arithmetic, groups (group theory), fields and their extensions, and projective geometry.

Through the Girls Talk Math Program, we have been able to develop new ways of thinking and learning while gaining general knowledge on all topics covered as well as a more in-depth knowledge on elliptic curve cryptography. There were many fun activities to partake in to expand on that knowledge, making topics all the more enjoyable.