Week 3: Again and Again and Again

Madeline S -

Hello everybody! This week I explored some more great resources on elliptic curve encryption (ECC) and got a better handle on how exactly data can be encrypted using these funky graphs. One of these resources is actually a series of lectures by Professor Christof Paar, a German mathematician who teaches in, well, Germany. It turns out his lectures are *almost* entirely in English, and who knows, maybe I’ll also pick up on some of the scattered German phrases by the end of this project. On another note, his lectures are incredibly clear and have helped me grasp many of the terms I had previously been struggling to understand from articles and textbooks alone.

 

One of the most important terms I learned this week is “cyclic group.” Cyclic groups are necessary in order for ECC to be hard to decrypt, but in order for me to define a cyclic group, I must first define a group. Fundamentally, a group needs both a set of elements (which in this case is the points on the elliptic curve) and an operation (in this case, addition).  Last week, I mentioned that the encryption process is based on adding points together to get new ones on the curve. I’ll start off this post by briefly explaining a little bit more about how addition actually works on elliptic curves. From a geometric point of view, when you add two points (P and Q) together, a secant line is drawn through the corresponding points. The third, new, point at which the secant line crosses the elliptic curve is then reflected across the x-axis to give the final point (P + Q). When “doubling” points, or adding P + P to get 2P, the same process is completed, except a tangent line is drawn through point P, and then the second point at which the line crosses the elliptic curve is reflected across the x-axis. That is all wildly confusing when written down, so I’ve drawn a diagram below that shows these processes more clearly. 

X

X

One of the reasons that ECC is so important is its efficiency, as I have mentioned before. Thus, ECC is very common in the technology we use day-to-day, such as when we send messages on our phones. While point addition is necessary for ECC to occur, our phones do not use geometry when adding points. Rather, they use algebraic formulas based on the equations of secant lines and the two points being added, similar to finding the intersection of two linear equations. These formulas are not pretty, however, which is why I chose to explain the additive process geometrically. Additionally, you may remember that the arithmetic of ECC is done modularly, as seen in the odd dot graphs from last week’s post. So, how exactly does adding points work when there isn’t a physical elliptic curve for a line to intersect? Interestingly, it works similarly to the game Asteroids, in which the line connecting two points simply continues bouncing from top to bottom of the graph until it intersects one of the modular points. In other words, like in Asteroids, when the line reaches the top of the “screen,” or in this case the top limit of the modular set, it teleports to the bottom of the “screen,” or the bottom limit of the modular set, and continues on until intersecting a point, which is then reflected across the x-axis as before (elliptic curves are still symmetrical even modularly).

X

Now, back to defining a “cyclic group.” In order for a group to fall under the “cyclic” category, there must be a primitive element. This primitive element is important in that it can generate all of the other elements within a group. For ECC, the primitive element is the point P, which, when added to itself again and again and again, eventually creates all of the other points on the elliptic curve until it generates itself and the process repeats…again and again and again. That’s pretty wild! Under certain conditions, the points of an elliptic curve form a cyclic group, meaning that all points are some multiple of a generator point P. This idea is the basis of how ECC works. 

 

Think of it this way: if I pick the point T on an elliptic curve, it is part of the cyclic group and thus was generated by the primitive element P. This means that T is a multiple of P, but which exact multiple of P is unknown. For example, T could be 3P, 7P, or 32P; the number of times P was added to itself to get to the point T is unknown. This number is the private key for ECC, and the primitive element itself is the public key. ECC works very similarly to RSA in terms of the encryption process; this time, when modeling the process, however, I am using points rather than colors. 

X
Welcome back Alice & Bob 🙂

 

This unique property of some elliptic curves, in which all points form a cyclic group, makes it difficult for cryptographers to randomly choose their own curves that have a primitive element and therefore are viable for ECC to occur. To address this problem, the National Institute of Standards and Technology (NIST) created a list of standard elliptic curves and their primitive points for the use of the public. Because primitive elements alone are not enough to decrypt ECC, Bob and Alice can still choose their private keys, which determine how many times the primitive element is added to itself to arrive at a brand new point. The number of “hops” the primitive element makes can still be a secret, and therefore, the NIST elliptic curves are very convenient as they are already known to meet the criteria of a cyclic group.

 

Other than researching elliptic curves this week, I also learned a fun fact from my mentor: Wikipedia is actually a very reliable resource in the math field. After so many years of avoiding Wikipedia for any sort of research, it feels wrong to intentionally search for pages on the cryptography I am researching. Next week, I hope to continue watching Professor Paar’s lectures, look into the early beginnings of cryptography (thank you for the idea, Mr. Smith!), and brainstorm activities to put in the interactive pamphlet I plan to include in my final project. I hope you enjoyed this week’s post! Until next time. 

 

More Posts

Comments:

All viewpoints are welcome but profane, threatening, disrespectful, or harassing comments will not be tolerated and are subject to moderation up to, and including, full deletion.

    zoey_c
    Hi Maddie! I hope to hear some of your scattered German sometime! It is super interesting that Wikipedia is actually a credible source for math, but it makes me wonder what the difference is. Why is it that mathematics is credible on the infamous noncredible site? Do only professors and well-educated people add to Wikipedia in the math section? I can't wait to see the pamphlet!
    Josh Smith
    I think that's essentially it. After going through undergraduate and grad school as a physics major, I never found any issues with wikipedia. It was extremely helpful while I was in college. I'd be interested to know if this phenomenon is purely for math, and other math intensive fields, or if it has more to do with the specificity of a concept or how abstract a concept is.
    Taylor Phelan
    Hi, Maddie! Wow—I am impressed by what you are learning every week. At the end of your post, you mentioned making an interactive pamphlet with your final product. I was wondering what will be your overall final product?
    madeline_s
    Hi Zoey! I will definitely ask Dr. Ismert more about the credibility of Wikipedia this week, but I would say that most of the more advanced mathematical topics on the site are written by mathematicians who are knowledgeable in the field. Because math isn’t generally a very contested subject, there isn’t much of a motivation for non-experts to add opinionated statements to the web pages. Also, because Wikipedia has linked sources, it makes it very valuable for research purposes as it is sometimes hard to just google articles and papers!
    madeline_s
    Hi Taylor! I am planning to create a tri-fold presentation that explores a journey through the evolution of encryption. Right now, I am hoping that by also having pamphlets, my audience will be able to interact with a resource that is both fun and informative.
    madeline_s
    Hi Mr. Smith! I will definitely have to look more into the reliability of Wikipedia. I believe it has something to do with if the article is covering contentious issues. As these are fairly rare in the more abstract fields of science, which aren’t easily understood by someone without a fair amount of background on the topic, I believe these articles tend to be more reliable sources.
    gianna_f
    Oh my goodness Maddie! Math is so interesting and it is super cool how you are learning to understand how it's used in our everyday life! All this stuff is extremely complicated, are you finding it difficult to understand some of these concepts?
    payton_b
    Hi Maddie! This is so interesting! It's cool to watch Alice and Bob continue to keep their code private.
    madeline_s
    Hey Gianna! Yes, I am definitely finding certain topics difficult to understand and even more difficult to explain. I am always on a hunt for more resources, and whenever I get stuck, Dr. Ismert has been my rock in explaining complex ideas!

Leave a Reply