By: Jourdan Moore, Emma Holzbach, Nicole Godwin, Naa Aryee, and Athalya Wakonyo
Have you ever made a secret language or code with your friend so that only you two would know what’s being said? You’re in luck! With the help of RSA Encryption Cryptography at Girls Talk Math we’ve learned about the world of mathematics, more specifically RSA, as well as Modular Arithmetic, Greatest Common Divisor and related theorems.
RSA is one of the first public-key cryptosystems created by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977, and is now the most widely used cryptography algorithm in the world.
Now what exactly does one do in math camp? We chose RSA so obviously we’d start with the simplest topic ever: modulo n.
Modular arithmetic (or modulo n) is a type of math using division and remainders.
Looking back this probably was the easiest thing we learned, but while studying it it felt confusing. Examples helped a lot. Like so:
Let’s look at examples to help understand. Let’s say we want to divide 10/3. That would equal 3 with a remainder of 1. Well in Modular arithmetic this can be written in a simpler form. We can rewrite this as 10= 3 times 3 +1. Which can also be written as 10≡ 1 (mod3)
Primes and Theorems:
For those of you that don’t know, a prime is a number that can only be divided by 1 and itself. A relatively prime pair is 2 numbers that have no common factors other than 1, like 3 and 7. Which helped us understand prime factorization, where integers are factored into a product of powers of primes. To make sense of this, let’s use numbers. Example: 60= 2^2 x 3^1 x 5^1.
Greatest Common Divisor
Additionally, it is important to know the Greatest Common Divisor. This is the greatest common factor of two numbers.
Example: (4,16) – GCD=4
We list out the factors of the numbers 4 and 16. We mark the factors common to both, and we choose the greatest among those. This number is the GCD.
The factors of 4 are, 1,2, and 4 and the factors of 16 are 1, 2, 4, 8, and 16. From that the greatest shared factor is 4. Hence the GCD of 4 and 16 is 4.
Next up, we learned some theorems. There are two that we focused on in order to understand RSA. The first being the Euler-phi theorem which is basically a rule that states if a and n are relatively prime positive numbers, then, a raised to the power phi(n) is congruent to 1 mod n.
And immediately afterwards we were hit with this brick otherwise known as the Chinese remainder theorem. This theorem states that the phi function of a number that is a product of primes is equal to the product of the phi functions of the individual primes.
Finally we were ready to witness the holy grail of our quest: RSA itself.
RSA is essentially sending, receiving, coding and decoding secret messages and numbers. At the end of our work packet, the last problem told us that we would be sending a coded message to the network science table and give them the formula to decode it!
Process and Insight
Looking back, we’ve made progress through struggle and learned that help comes from all sorts of places. We will use the skills we learned from Girls Talk Math for years to come to help us in our education. And maybe we made a couple friends along the way. 🙂