 # The Art of Cryptography

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) st=Nx+1,where x,s, and t can be any positive integer. 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