By Divya Aikat, Helena Harrison, Annie Qin, and Quinn Shanahan

The definition of cryptography is the art of writing and solving code. However, over the last two weeks, we learned so much more than just this textbook explanation. While working together within our team, we explored many different aspects behind cryptography. By building off our individual strengths, we prepared ourselves for higher level mathematics. The following is a synopsis of the progress we’ve made over the past two weeks.

Modular Arithmetic

The first thing that is essential to RSA Encryption is the knowledge of modular arithmetic. There is a simple reason why modular arithmetic is known as “taking the remainder”. Modular arithmetic revolves around the concepts of division and remainders. For example, 4/2 is equal to 2. Simple, right? What happens when you encounter a remainder? 5/3 is 1, with a remainder of 2. There is a different way to say the same thing, and this way makes it easier to apply to RSA encryption. It can rewritten as 5=1 · 3 + 2. In modular arithmetic, this can be depicted with a ≡ b mod n (this is read as “a is congruent to b mod n”). For example, 5 ≡ 2 mod 3 (look at the above example). The remainder will always be an integer between 0 and n – 1.

Primes

Prime factorization is something crucial to the RSA algorithm. It is the practice of factoring integers into a product of powers of primes.

Relatively prime integers are a little more complicated than just your average prime factorization. Two numbers are “relatively prime” when they have no common factors other than 1. In other words, you cannot evenly divide both by some common value. An example of relatively prime integers are 7 and 20.

Greatest Common Divisor (GCD)

You may have heard of the least common multiple. The greatest common divisor is like its twin. To calculate the GCD of 2 numbers, you need to write out the prime factorization. For example, 12 and 18. The prime factorization of 12 is 2^2 · 3. The prime factorization of 18 is 2 · 3^2. You will take the lowest value that overlaps the two numbers. In this example, 2 and 3 will be multiplied to make 6, GCD of 12 and 18.

Euler’s Phi Theorem

The above picture displays the two different versions of the phi symbol. The φ(N) can be found in a very simple way. N represents any positive integer. For example, if N = 12, then you can write out 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. Then, you can cross out all numbers that are the multiples of all the individual factors in the prime factorization. The prime factorization of 12 is 2^2 · 3. So, you would cross it out like this (the underlined numbers are crossed out) : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. You never cross out 1, even thought it may seem like you should. Then, you count up the remaining amount of numbers. Therefore, the φ(12) is 4.

What if the number is prime? The φ(3) is 2. The φ(5) is 4. The φ(7) is 6. Do you notice a pattern? The φ(N) (if N is prime) is always N – 1.

Euler’s Phi theorem also states that n^φ(p) ≡ 1 mod p. n must be relatively prime to a.

Chinese Remainder Theorem

The Chinese Remainder Theorem is a theorem which states that, if you know the remainders of the division of an integer n by several integers, then you can determine  the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

Proofs

This was a very difficult section of the problem set for our group to complete. However, we powered through with the help of our wonderful team leaders. We will only explain one short proof to spare you difficulty and time.

Using Euler’s phi theorem, we can prove that p|(n^p – 1) – 1. This means that p is a divisor of (n^p – 1) – 1. We start off with Euler’s phi theorem as the first step.

1. n^φ(p) ≡ 1 mod p       1. Euler’s Phi Theorem
2. n^φ(p) ≡ p · x + 1        2. The definition of a mod
3. n^p – 1 = px + 1           3. The definition of the phi of a prime number
4. (n^p – 1) – 1 = px         4. Algebraic manipulation

We have proved p|(n^p – 1) – 1 using Euler’s phi theorem.

Encryption and Decryption

Begin by creating a cipher that both people agree on. For example, a=1, b=2, c=3…. Let’s start with two people that want to transmit a message – Sarah and Lisa. Sarah starts by picking 2 prime numbers, and multiplies them together. This number will equal N. In our example, we can pick 17 · 19 = 323. She finds the phi of N. The φ(323) = 288. Then, she finds s and t. st = 1 mod φ(N) is a formula you can use. 11 · 131 = 1 mod 288 in our example. Sarah sends out (s, N) publicly. (11, 323) will be sent out publicly. When Lisa gets (s, N), she transmits a letter by finding the number in the cipher, and raises it to the s power. 21 to the s power means 21 to the 11th power here. She then calculates it to the s power and into a VERY large number, which is 350277500542221. Lisa calculates the large number to modulo N. 350277500542221 mod 323 = 319. Lisa sends 319 back. Sarah takes the calculation and raises it to the power of t. 319 to the t power means 319 to the 131st power. Sarah calculates it to modulo N, which equals 21. Sarah then deciphers the number as a letter.

This can be worked out easier on paper. So, we have recorded a video about encrypting and decoding messages.

Thoughts

The entire learning process was complicated, and in some sections, we felt like giving up. However, we learned to persevere through the things that challenged us the most. We went through our own little bumps along the way, but we ended up understanding the problem set and each other better. We made many jokes, some funny, some not as funny. The podcast was definitely something we’ll never forget. We proved that you can learn difficult math and have fun doing it.

Annie Qin, Divya Aikat, Helena Harrison, Quinn Shanahan