Week 2: There’s Always More Trap Doors

Madeline S -

Hello and welcome back! This week, I spent most of my time searching for and trying out new resources. As I mentioned in my last post, one of the initial struggles I am facing is the process of building up some of the mathematical background information that I lack. After scouring the internet for online courses, I enrolled in a fundamentals of quantum computing course and found a great series of lectures on linear algebra through MIT’s OpenCourseWare website. I hope that by following along with these courses while working on my project, I will be more familiar with some of the notations and computations that arise in my own research.

Aside from finding new resources, I have continued to study RSA encryption and have begun delving into elliptic curve cryptography (ECC) with Dr. Ismert. Both ECC and RSA are similar in that they are trap-door algorithms, public key algorithms, and rely heavily on modular arithmetic. That was a lot of fancy jargon I threw at you, so let me explain each of these similarities a little further. First off, a trap-door algorithm means that cryptography works by utilizing a simple computation to encrypt data and a difficult computation to decrypt data. Last week, I briefly discussed that RSA uses multiplication (an easy process) to encrypt data, but the prime factorization of huge numbers (a hard process) to decrypt data. Similarly, ECC encrypts data by adding points together on a curve to get to a new point (an easy process) and then determining how one arrived at a final point (a hard process).  This article describes ECC as a game of billiards. It is an easy process for someone to hit a ball over and over and watch as it moves from point to point. It is very hard for someone who just walked into the room and saw where the ball currently is to decipher how many hits it took to get the ball into that exact place. 

 

x
Three funky elliptic curves

 

Now, a new term! ECC and RSA are also both public key algorithms, meaning that there are two keys necessary to decrypt the data, one of which is accessible to the general public. This is the key that “Eve” has access to that, along with “Bob” and “Alice’s” private keys, and is critical to the decryption process, but without the private keys, it doesn’t give enough information to an outsider to decrypt the data. Finally, what is modular arithmetic? In both RSA and ECC, calculations are done over a finite set of numbers which “wrap around” after reaching the largest value in the set. Think of it as the remainders when doing division. If the largest number in my set is four, my set of numbers is made up of 0, 1, 2, 3, 4, which in total is a collection of five numbers. Let’s try to get the number 6 in the set. 6 divided by 5 has a remainder of 1, so in this set, 6 would be represented by a 1. Similarly, 5 divided by 5 has remainder 0, so it is represented by a 0.  7 divided by 5 has remainder 2, 8 divided by 5 has remainder 3, and so forth. Another way to think about it is in terms of clocks! Rather than counting every hour of every day, we “reset” at twelve. The thirteenth hour is one o’clock (13 divided by 12 has remainder 1) and the twentieth hour is eight o’clock! In both RSA and ECC, modular arithmetic, specifically with a prime modulus, makes the trap-door function even harder to decrypt, and therefore makes both of these forms of cryptography more secure. Modular arithmetic also ensures that arithmetic is being done over a finite field which generally makes operations “nicer.”

x
The red graph mod 13
x
The black graph mod 13
x
The green graph mod 13

 

Needless to say, there are many similarities between RSA and ECC, another of which is that neither of them are quantum safe. The most notable difference between the two, however, is that ECC’s trap-door function is much harder to solve than RSA’s. ECC is also more computationally efficient in that it requires much less computing power to create the same level of security as the equivalent form of RSA encryption. A fun fact from the same article I linked above is that in order to break a 228-bit RSA key (a string of 228 zeros and ones) it would take less energy than boiling a teaspoon of water. In order to break an equivalent 228-bit ECC key, it would require the amount of energy it would take to boil all of the water on the planet. That’s a pretty big difference! 

 

That completes the summary of my week two. Thank you for reading!

 

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.

    Taylor Phelan
    Wow, Maddie! I’m so impressed with that you are able to do. Are you finding it difficult to conduct online research, or is there a lot of data based on your topic?
    zoey_c
    Hi Maddie! Your research is so impressive! What are you going to end up using all this research and mathematical knowledge for? What is your end game? I am loving your finds!
    madeline_s
    Hi Taylor! Thank you so much. I have found that while there are a fair amount of resources online, they are mostly for students who are already experienced in the field of study. It’s definitely been difficult to find lectures and papers that are in-depth but also for an audience of my limited background.
    madeline_s
    Thank you Zoey! That’s a great question, and one that I have been thinking about these last couple of weeks. My end goal is to take the public on a journey through the evolution of encryption. I’m thinking about possibly doing this with a tri-fold presentation or through an interactive pamphlet with activities and fun facts that explains the basic points of the encryption methods I have been studying. I will make sure to write about any updates in my upcoming blogs!
    gianna_f
    Wow Maddie! This is such a cool project! I really appreciate you providing visuals and simplified explanations :). I am wondering though, as there have been such big advancements in encryption, has there been more people who are able to decrypt? Is this why we are emphasizing quantum encryption? Also, is that first graph the alien??
    payton_b
    Hi Maddie! This is so cool! Your explanations are so clear and concise. I almost feel that I could do my own project on this topic using this as a guide. It seems super interesting. I can't wait for next week!
    madeline_s
    Hi Gianna! I’m so glad that the visualizations are useful. Yes, there are continuously more advancements in the decryption processes as technology advances. As you mentioned, with the efficiency of quantum computing, processes that may take years and years to decrypt with a classical computer can be decrypted in exponentially less time using quantum computers. Although quantum computers are not yet stable, there are people who are storing valuable information now in hopes of being able to decrypt this information when quantum computers are stabilized. Additionally, researchers are always looking for better decryption algorithms so that, in turn, we can better our encryption processes. This is exactly why there is a race right now to create efficient, quantum safe forms of encryption. Haha, yes that first graph of elliptic curves is what I refer to as looking like an alien head. :)
    madeline_s
    Hi Payton! I’m so glad you enjoyed the post! :))

Leave a Reply