The

Mathematics

of Cryptography By Ciara timban What is

cryptography? the enciphering and deciphering of messages in secret code or cipher so that they cannot be read by persons other than the intended recipient Key terms Plaintext the original, readable, comprehensible text ciphertext coded, unintelligible text encipher/encrypt decipher/decrypt Encryption key decryption key to translate the plaintext into ciphertext to translate the ciphertext into plaintext the algorithm that turns the plaintext into ciphertext the algorithm that turns the ciphertext into plaintext background/history cryptography has been around for over 1000 years it comes from the greek words kryptos, which means hidden, and graphein, which means writing there has been the need to conceal and send secret messages ever since the beginning of human

civilizations People turned to cryptography in order to change their messages into gibberish so that they could not be read by persons other than the intended recipient cryptography has seen the end of empires, determined wars, and now rules over cyberspace throughout history, many forms and

methods of cryptography have been

developed and used, like the Caesar

cipher and rsa public key encryption almost all methods and forms of cryptography

rely heavily on mathematics and depend on the

many important properties and functions of math,

like number theory, modular arithmetic, prime

factorization, the phi function, and others. the Caesar cipher The Caesar cipher, or the Caesar shift, was

named for Julius Caesar, who used this type

of cryptography to communicate with his generals the Caesar cipher is One of the most simplest

and widely-used methods of encryption it is a monoalphabetic substitution cipher where the plaintext is translated into the ciphertext through the means of a shift in the alphabet used Let's say two people, Alice and Bob want to send each other a secret message using the Caesar cipher first, they would have to decide on an encryption

and decryption key that only the two of them knew. the key would be the shift in the alphabet used. the two decide to use a right shift of three using a right shift of 3, A would become D, B would become E, C would become F, and so on. When you reach x, y, and z, you rotate back to the beginning so that they become a, b, and c respectively. to encrypt her message "pre-calculus is fun", Alice would have to apply the shift of three to each letter. Her encrypted message would be

“SUH-FDOFXOXV LV IXQ”. to decrypt the message, bob would subtract three from each letter to get Alice's original message. the encryption process can be done more efficiently if you assign each letter a number so that a is 1, b is 2, y is 25, z is 26, and so on. to encrypt the letter a, you would take its assigned number, 1, and add 3 (the shift) to get 4, which is the letter d. The CAesar cipher can also be modeled used Modular arithmetic modular arithmetic Modular arithmetic, also known as clock arithmetic, deals with whole numbers in a way that the numbers are replaced by their remainders after they are divided by a modulus, or a fixed number defined by the equation where n does not equal 0 and a is congruent to the remainder of b divided by n. The two integers a and b are congruent modulo n if b-a is divisible by the modulus Another way to think of it is as numbers wrapping around back to the start after reaching a certain number (the modulus), like a clock, where the modulus would be 12 since the numbers restart after 12 Using a 24-hour clock, 13 o’clock would be the same as 1, 14 would be the same as 2, 15 would be the same as 3, and so on Say you have a clock in military time. You can use modular

arithmetic to figure out the time past 12 noon. if it's 15 o'clock, what time would it be in standard time? This can be modeled as a = 15 mod 12 a is derived by dividing 15 by 12 and taking the remainder, which is 3 so 3 = 15 mod 12

3 is congruent to 15 modulo 12 since

15 - 3 = 12, which is divisible by 12 Modular arithmetic can be applied to the

Caesar cipher since the numbers wrap

around back to a after z Encryption:

Decryption: x: the number of the letter

n: the number of the shift En(x)= (x+n)mod26 Dn(x)= (x-n)mod26 26 is the modulus since there are 26 different letters in the alphabet and the letters repeat after the 26th letter, z In the cases of x, y, and z, or the letters 24, 25, and 26 respectively,

when you add the shift of 3, you get the numbers 27, 28, and 29, which

do not have assigned letters. for example, Take y, or letter 25; the encryption of y using modular arithmetic would be En(25)=(25+3) mod 26. The answer is the letter 2, or b, since the remainder of 28 divided by 26 is 2 However.....

the Caesar cipher, along with the large majority of monoalphabetic substitution ciphers, can be easily broken and deciphered.

One could crack the code simply by attempting to guess the shift with the help of frequency analysis (the study of the frequency of letters in a ciphertext) or just plain brute force. Ever since Arab mathematician Al-Kindi broke

the Caesar cipher, newer, stronger, and more complex forms of cryptography have emerged public-key cryptography Public-key cryptography solved the dilemma

involving Secure key distribution (making sure that

the key is securely relayed between both parties

without being intercepted by a third outside party) the enciphering and deciphering of a message using two separate keys, the public and private keys.

the public key encrypts the message and the private key decrypts it it's also classified as a one-way or trapdoor function, which is something that is easy to do in one direction but difficult or impossible to do in the reverse direction A one-way function is like mixing two colors. it's

easy to mix them but impossible to separate them

back into the original two colors rsa encryption developed by ron rivest, adi shamir, and leonard adleman in 1978 type of public-key cryptography that utilizes

and depends on the properties of prime

factorization and the phi function to derive the

algorithms for the public and private keys The algorithm depends on prime factorization

as the one-way function "The RSA cryptosystem is based on the difficulty of factoring large numbers which are the product of two prime numbers."

- Adi Shamir, co-inventor of RSa

it's quite easy to generate large, 100-200

digit-long prime numbers and then multiply

them but relatively harder to factor them the rsa algorithm also depends on and includes

the phi function RSA encryption is the most commonly used and popular form of encryption and authentication algorithm. It is used to keep personal information secure on the internet via methods like..... integrity checking sender/receiver authentication and digital signatures The RSA algorithm is also included as part of the web browsers for Microsoft and Netscape Cryptography will continue to evolve and improve with the help of mathematics the phi function, also know as euler's

totient function, is defined as the number

of positive integers less than or equal

to n that do not share a common factor

other than 1 with n. The Phi function is also

multiplicative, so that phi of (a*b) = phi(a)*phi(b) For example, the phi(8) = 4, since there are four numbers (1,3,5,& 7) 8that do not share a common factor with 8. the larger the numbers get, the harder it is to find the phi function however, the phi of any prime number p

is easy to find since prime numbers don't

share common factors with any other

number except for 1. therefore, the phi of

p = p-1 the end! To generate the public and private keys for RSA encryption... 1. come up with two primes, p and q, and multiply them to get n 2. then form phi of (n), or phi of (p*q). Since phi of (p*q) is equal to phi of (p)* phi of (q),

and the phi of any prime number x is equal to x-1,

then phi of (n)= (p-1)(q-1) 3. Then find a number e that is relatively prime to phi of (n), and a number d, such that e*d = 1 mod (phi of(n)) public key becomes the numbers n and e

private key becomes the numbers n and d encryption algorithm decryption algorithm Where m is the plaintext message and

c is the ciphertext "it is perfectly sound and usable into

the future."

- Ron Rivest, co-inventor of RSA,

speaking about the RSA cryptosystem

### Present Remotely

Send the link below via email or IM

CopyPresent to your audience

Start remote presentation- Invited audience members
**will follow you**as you navigate and present - People invited to a presentation
**do not need a Prezi account** - This link expires
**10 minutes**after you close the presentation - A maximum of
**30 users**can follow your presentation - Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

### Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.

You can change this under Settings & Account at any time.

# The Mathematics of Cryptography

Exploring cryptography and the math that is involved.

by

Tweet