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

 

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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s