By: Nia Beverly, Makayla McDaniel, Yuanyuan Matherly, and Tyler Deegan
Introduction
Cryptography is defined as the art of writing and solving codes. Upon first thought, many people picture codes as an antiquated war time communication technique. However, the field of cryptography is alive and well, and it has become pervasive in our everyday lives. The world is becoming more and more connected through technology, and with this, there is a greater need to protect information. Encryption is probably the most widely used application of cryptography, and it is used to protect information by making it so only one person with a key can understand what is transmitted. In the following paragraphs we will walk through the steps to mathematically understanding one widely used type of encryption.
Prime Numbers
Prime numbers are numbers whose only factors are one and itself. For example, if a number is greater than two and is evenly divisible by two, then the number cannot be a prime number. The number 52 is greater than two but it can be divided evenly by two and, therefore, 52 is not a prime number. Also, mathematicians do not consider zero or one to be prime numbers. This is a chart of all of the prime numbers up to 1,000:
| 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
23 |
|
|
29 |
31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 |
|
71 |
73 | 79 | 83 | 89 | 97 | 101 | 103 | 107 |
109 |
| 113 | 127 | 131 | 137 | 139 | 149 | 151 | 157 | 163 |
167 |
|
173 |
179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 |
|
229 |
233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 |
|
281 |
283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 |
347 |
|
349 |
353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 |
401 |
| 409 | 419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 |
461 |
|
463 |
467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 |
| 541 | 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 |
599 |
|
601 |
607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 |
653 |
|
659 |
661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 |
|
733 |
739 | 743 |
751 |
757 | 761 | 769 | 773 | 787 |
797 |
|
809 |
811 | 821 | 823 | 827 | 829 | 839 | 853 | 857 | 859 |
|
863 |
877 | 881 | 883 | 887 | 907 | 911 | 919 | 929 |
937 |
| 941 | 947 | 953 | 967 | 971 | 977 | 983 | 991 |
997 |
Continuing, the term prime factorization is the act of breaking down a number into its prime factors. For example, the number 42 has the factors 21 and 2. We do not need to break down 2 any further because it is already prime number. The number 21 on the other hand can be broken down further. The factors of 21 are 7 and 3. Again, because 7 and 3 are both prime numbers they cannot be broken down any further. So, the prime factorization of 42 is 2*3*7. In addition to prime factorization we have the term relatively prime. Two numbers are relatively prime if they do not have any of the same prime factors. This means that if you break the two numbers down using prime factorization, neither of the two numbers should share a similar prime factors. For example, we are trying to figure out if the numbers 10 and 21 are relatively prime. The first step is to break both of the numbers down into their prime factorizations. The number 10 breaks down into 5*2 and the number 21 breaks down into 7*3. Because these two prime factorizations share none of the same prime factors, the two numbers 10 and 21 are relatively prime.
Modular Arithmetic
a=b mod (n)
Divide the given number “a” by the natural number “n” and then “b” should be the resulting remainder, or number leftover after the division. The possible answers would be from 0, where the mod (n) divides evenly into the number, and up to one less than the mod (n), since once at “n” again it can divide evenly and start the pattern over.
Example:
20(mod 6) 63=18
20-18=2
20(mod 6)=2
|
a |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |
| a (mod 6) | 0 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 3 | 4 | 5 | 0 |
1 |
|
According to this chart certain values have the same mod (6) for example 13=1(mod 6) because they both have remainder 1. Attached is a video that further explains modular arithmetic.
What is Modular Arithmetic – Introduction to Modular Arithmetic – Cryptography
Euler Phi Function
The Euler Phi Function describes that for any natural number n, (n) counts the number of numbers less than n that are relatively prime to n. This may sound confusing, but we are going to break it down with some examples.
Examples:
1) (9)
Prime factorization of 9: 3*3
- 8: 2*2*2
- 7: 7*1
- 6: 2*3
- 5: 5*1
- 4: 2*2
- 3: 3*1
- 2: 2*1
- 1: 1*1
In this example, for a number to be relatively prime to 9, it must not have 3 as a prime factor. The numbers 8,7,5,4,2 and 1 do not have 3 as a prime factor, therefore they are relatively prime to 9. So (9) is 6 because there are six numbers less than 9 that are relatively prime.
2) (12)
Prime Factorization of 12: 2*2*3
- 11: 11*1
- 10: 5*2
- 9: 3*3
- 8: 2*2*2
- 7: 7*1
- 6: 2*3
- 5: 5*1
- 4: 2*2
- 3: 3*1
- 2: 2*1
- 1: 1*1
In this example, for a number to be relatively prime to 12, it must not have 2 or 3 as a prime factor. The numbers 11,7,5 and 1 do not have 2 or 3 as a prime factor, therefore they are relatively prime to 12. So (12) is 4 because there are four numbers less than 12 that are relatively prime.
3) (7)
Prime factorization of 7: 7*1
- 6: 2*3
- 5: 5*1
- 4: 2*2
- 3: 3*1
- 2: 2*1
- 1: 1*1
Notice that, unlike the two previous examples, 7 is a prime number. In order for a number to be relatively prime to 7, it cannot have 7 as a factor. None of the numbers less than 7 have 7 as a prime factor. Therefore (7) is 7. This demonstrates a rule, if n is prime, then (n)=n.
RSA Algorithm
The RSA algorithm is a tool which allows two parties to encode and decode messages that they wish to send to one another without the interference of a third party. The algorithm includes a public key, which is used by one of the parties to encode the message, and a private key, which is used by the second party to decode the message. For example, the party that wishes to receive the message must start the process by creating both the public key and the private key. Then that party sends the public key to the other party so that they are able to encode the message that they wish to send. The public key can be seen by anyone because only the party with the private key will be able to decode the message that is sent. Once the second party has encoded the message, that party will send it back to the first party and with the private key the first party will decrypt the message. Below is an example of this process:
Note: Public key: S & N Private Key:T
| Steps | Example |
| Where Y and H are prime
yh=N |
y=3 h=5 N=15
(3)(5)=15 |
| (N)=(y-1)(h-1) | (15)= (3-1)(5-1)
(15)= 8 |
st1mod (N)
|
s=3 t=11
st=1mod (8) 1mod(8)=33 311=33 |
| A is the message you want to send
asmod(N)=b |
Wants to tell person 12 Sends person 3
123mod(15)=3 |
| B is the message received
btmod(N)=a |
Receives 3 Understands 12
311mod(15)=12 |
About Us
Written by Nia Beverly, Makayla McDaniel, Yuanyuan Matherly, and Tyler Degan. This blog was created during camp at UNC Chapel Hill called Girls Talk Math where high school girls learn about famous female mathematicians and are empowered to pursue educations and careers in math. This blog was created as part of a three part project that culminates the camp experience.
Check out our podcast about Wang Xiaoyun at https://soundcloud.com/girls_talk_math/wang-xiaoyun!
girlstalkmath.com 