RSA Algorithm – Baiting

Image result for rsa encryption

https://www.boxcryptor.com/en/encryption/

In this blog, I would like to provide updates on the M3 Challenge and my research project in Abstract Algebra for Chester County Science Fair. Then, I will introduce the RSA Algorithm, the most used information encryption algorithm in the world and how it relates to my project.

M3 Challenge was certainly a successful experience, despite the fact that we messed up several places in our math model. If you still remember, M3 Challenge this year is about drug overdoses. In Question 2, we were asked to predict the drug overdose of nicotine, alcohol, marijuana, and non-prescribed opioids. In the math model, I was trying to find the percentage of people who misuse drugs in a specific population group whereas some of my teammates were finding among all “misusers” of the drug, how many belong to each population group. We didn’t have enough effort or communication to figure out this mistake during the competition, which leads us to the incorrect results.

During the start of Spring Break, three Westtown students including me participated in the Chester County Science Fair in different subjects. This year, I was the only participant in 12th Grade Mathematics so I automatically won first place and advanced into the Delaware Valley Science Fair. During the competition, I introduced my project to two judges, and I am quite sure that neither of them had a strong understanding of Abstract Algebra. However, our conversation was still meaningful. They asked me about the application of my project, which I wasn’t ready to explain at the time. Many times, one or two math theorems don’t mean anything in real life, so I just explained maybe scientists could use these theorems to solve equations. It turned out to be a dumb response. During Spring Break, however, I discovered the RSA Algorithm, which closely relates to Fermat’s Little Theorem, which I am going to explain right here.

Image result for rsa encryption

http://demonstrations.wolfram.com/RSAEncryptionAndDecryption/

Open the URL above, you will find a RSA simulator so that you can play with it and see what happens!

Let’s look at an example.

  1. Normally, we would pick two very large prime numbers that are hundreds or thousands digits long. However, in this example, say we pick p = 13 and q = 17.
  2. Then n = 21, and phi(n) = 192.
  3. Say we pick u=7, and we confirm that gcd (7, 192) = 1
  4. Then we want to find v such that 7v==1 (mod 192). This implies 7v – 1 = 192m for an integer m. We then find m = 2 and v = 55.
  5. n = 21 and u = 7 are the public keys. v = 55 is the private key.
  6. For instance, the message we want to encrypt is x = 12. Use the public key u = 7, then the encrypted message becomes y = 12^7 = 35,831,808.
  7. Send 4,782,969 to your friend. To decrypt it, they need to use the private key v = 55.

How does the RSA Algorithm relate to Fermat’s Little Theorem? Here, I am providing a quick proof.


This part proves why our encryption and decryption method works. However, it is not a strict proof. To strictly prove the RSA Algorithm, we need to prove each detail in the process. Say in Step 4 above, we need to prove that such a v always exist and is always unique. If you are interested in learning more, please visit here. Finally, I would like to share a fun fact to conclude the RSA section. You may have seen companies advertising their to be 256-bit, 512-bit, etc. and didn’t understand what that number means. In fact, if the chip uses RSA Algorithm, it is highly likely that those numbers represent the length of u, v, or n. Wow, mind blooming, right? Obviously, to find the original text without knowing the private key would take hundreds, if not millions of years. This is why RSA is widely used and so safe!

In the very end of my blog, I would like to share my plan for Independent Seminar after spring break. I will keep working and preparing for the Delaware Valley Science Fair. After that, I will shift focus toward Intro Computer Science. Even though I don’t have any background in this field yet, I believe the journey will be fun.

Works Cited

AES and RSA Encryption. http://www.boxcryptor.com/en/encryption/. Accessed 1 Apr. 2019.

Blinder, S. M. RSA Encryption and Decryption. Mar. 2011, demonstrations.wolfram.com/RSAEncryptionAndDecryption/. Accessed 1 Apr. 2019.

Milanov, Evgeny. “The RSA Algorithm.” University of Washington, 3 June 2009, sites.math.washington.edu/~morrow/336_09/papers/Yevgeny.pdf. Accessed 1 Apr. 2019.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.