By: Shai Caspin, Natalie Bowers, Bryana Dorsey, Nia Pierce, and Cana Perry

Cryptography is the act of encrypting and decrypting codes. It’s used to pass secret messages and keep outsiders from accessing information. Math is used to help encrypt codes using different methods. One common methods is to use RSA encryptions, which uses prime numbers and mod functions to make deciphering impossible. RSA encryptions are so successful since factoring large numbers into their prime factors is incredibly difficult, and there is yet a way to do so quickly and efficiently. 

We were all very interested in learning more about cryptography since it incorporates everyday math with real-world problems and situations.

Our process

We were given many problems covering a wide array of topics. The three major topics covered were logic problems, prime number manipulation, and RSA encryption. Each topic played a huge role in our understanding of encryption and generally math. For example, the logic problems we were presented with made us think about our process for solving such problems, forcing us to focus on building algorithms to solve problems. Using prime number manipulation we learned how to identify large prime numbers, find Euler’s phi function for all numbers, and determine relative primeness. We also learned how to use RSA encryption and why it is so important in our modern society.

Our process was very random. We just used knowledge we previously had or asked for help if we couldn’t figure a problem out. When we were presented with a problem, the first thing we did was ask ourselves “what do we know that can help us solve this?” and usually we used Euler’s phi function for all the problems we faced. We had to solve proofs that show why phi functions of numbers are used in the RSA encryption algorithm.

 

Challenges 

Some challenges that we faced were when some of us knew that we had to do for certain problems and other people didn’t. Sometimes we disagreed on how to solve a problem but we all eventually agreed. The logic problems particularly were  little more difficult to do since we had to figure out the way to solve each problem using what we knew. Whenever we couldn’t figure out a problem, we just asked some of the supervisors or other students doing the same problems.

Real World Applications of Cryptography

Cryptography, as mentioned before, is the art of writing and solving codes. In the real world cryptology is used in a variety of things from computers to credit cards, we also have used them during times of war. During the war allied countries needed a way to communicate without the opposing countries being able to decipher what exactly they were communicating. How the communication worked is that the allies started out by establishing a cipher that both parties would use, and from there one ally would use the numbers correlating to a certain number to create a message. Once the message was received from the other ally that group would use the cipher established to decode the message. In credit cards cryptography is used on the strip used when swiping one’s card. When credit cards are created each card is given a specific set of numbers that are transferred to the EDC machine to charge the card with purchase as well as to check for authenticity. Who knew that this math concept is a part of so many aspects of our lives?

One large concern that faces the field is the potential ability to factor large numbers into their prime factors easily. Usually 20+ digit numbers are used for encryptions, which makes finding their prime factors by hand and by computer very difficult, but if a way was discovered to factor these numbers quickly, private information will no longer be secure. Nowadays, it takes a computer a couple of years to factor such a large number, but if the time was to be shortened by a lot, that would be a cause for concern.

What we learned

We had a number of worksheets to help us understand cryptography and how to encrypt and decrypt RSA encryptions. In the first worksheet we learned about a(mod N) and how to find it.  How you find it is:

1. Divide a by N
2. Find the remainder

Ex) 22 (mod 12)

1. 22/12
2. Remainder of 10
3. 22 (mod 12) is equal to 10

Next we learned about prime factorization.  Almost all numbers are either prime or made up of primes. Primes are organized from least to greatest.

Ex) 210= 2*3*5*7

Something else we learned was what makes numbers relatively prime.  Relatively prime numbers do not share any of the same primes.

After this, we learned about the Euler Phi function.  The Euler Phi function is the number of numbers relatively prime that are less than the number.  This sounds confusing, but it is really fairly easy!  An example for clarification is below.

1	2	3	4	5	6	7	8
1	2	3	2*2	5	2*3	7	2*2*2*2
0	1	2	2	4	2	6	4

The top row is the number, the middle row is the factorization, and the bottom row is the Euler Phi function.

For an example, we will used the number 8.

1. See that the prime factorization of 8 is 2*2*2*2.  So the only prime is 2. Now we have to look for all the numbers that do NOT have a two.
2. The numbers that don’t have a two are: 1, 3, 5, and 7.
3. There are 4 numbers that do not have a two, therefore the Euler Phi function of 8 is 4.

Lastly, we learned about RSA encryption.  RSA encryption is a way to keep messages secret, and it it is secure and difficult to crack because it is extremely difficult to factor large numbers into primes.  Also, with an RSA encryption, only one side or person has the “key” to finding out the answer.  This is how it works:

Rose and Mary are sending secret messages.

1. Rose picks two primes to multiply together, lets say 11 and 7.
2. She multiplies them to get the number.  This number will be considered N.  So N= 77.
3. Then she finds the Euler Phi function of N.  This is 60.
4. Now she needs to find two numbers (s and t) so that s*t = 1 (mod 60).
5. She finds that 13*23 work for s and t.  This is because 13*23/60 has a remainder of 1.
6. N= 77, s= 13, t=23.  Rose gives the information (s= 13, N= 77) to Mary.
7. When Mary wants to send a letter to Rose, lets say B.  B corresponds to 2 on the cipher that Mary and Rose share.  To encrypt 2, Rose needs to input the numbers she knows into the equation x^s (mod N).  So 2^13 (mod 77).
8. 2^13 (mod 77) is equal to 30.  Mary sends the number 30 to Rose.
9. Rose raises 30 to t, and takes mod 77 of it to decrypt it.
10. Rose gets the answer 2, and 2 corresponds to the letter b on the cipher.

And that is how RSA encryption works!

We had a great time learning about cryptography and expanding our knowledge of different mathematical principles, and hope you enjoyed our insights as well!

Thanks,

Shai, Natalie, Bryana, Nia, and Cana

 

Check out our podcast about Agnes Meyer Driscoll at https://soundcloud.com/girls_talk_math/agnes-meyer-driscoll!