You are allowed to work individually or with a partner on this project. If you work with a partner, you will turn in one project with both names on it.

plaintext | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |

ciphertext | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D |

If we wanted to send the plaintext

ONE IF BY LAND AND TWO IF BY SEAwe would send the ciphertext

SRI MJ FC PERH ERH XAS MJ FC WIE.

- Using 0 for A, 1 for B, and so on, let the numbers 0 to 25 stand for the letters of the alphabet. What is the numerical representation of the word SEA? Write your answer down.
- What does the numerical representation of this word become if we shift every letter two places to the right? What does it become if we shift every letter 13 places to the right?
- A Caesar cipher is a shift of the letters. This can be
expressed mathematically by using the modulo function. If the shift
of letters is 2, then each number
*n*in our message is replaced with*(n + 2) mod 26*. Using a Caesar cipher with a shift of*s*, each number*n*gets replaced with*(n+s) mod 26*. Using a Caesar cipher corresponding to a shift with size equal to the number of letters in your first name, encrypt your first name. Write down your encrypted name and show the work you did. For example, my name is Pam, so I will use a shift of 3. The name PAM will get encrypted as follows:P --> 15 --> 15+3 = 18 (mod 26) --> S

If you are working with a partner, you need to encrypt both names for this exercise.

A --> 0 --> 0+3 = 3 (mod 26) --> D

M --> 12 --> 12+3 = 15 (mod 26) --> P

- To decrypt text that was encrypted by a Caesar cipher, each
letter must be shifted to the left by the shift amount.
Since
ciphertext = (plaintext + shift) (mod 26),

we subtract the shift from both sides of the congruence, to getciphertext - shift = plaintext (mod 26).

Decrypt the text UZHMPQMFRUHQ that was encrypted with a shift of 12. Write down the plaintext.Do

**ONE**of the next two exercises. - Write a program to encrypt and decrypt a text using a
Caesar cipher. The user should enter the text, specify
whether they would like to encrypt or decrypt, and what
their secret key (
*i.e.*, the shift) is. You may use Java, Python, or JavaScript to write your program. If you have extensive programming experience, you are free to make the program as sophisticated as you would like. One idea is to explore converting characters to ASCII code instead of using A = 0, B = 1, etc. Using ASCII characters gives you freedom to encrypt a larger character set. Think about how your modulus would need to change. Another idea might be to group letters in groups of 2 or 3 and then encrypt, which would make frequency analysis a little more difficult. If you are relatively new to programming, keep it simple! Ask for some guidance if you'd like some ideas. - Suppose you are an adversary and you obtained the
ciphertext (see below) that you understood to be encrypted by a
Caesar cipher. Look up some information on the relative
frequency of letters in the English language. Using this
information, decrypt this ciphertext. Create a frequency
table showing how many times each letter in the text
appears. Write down what you suspect the shift is and then
using that shift, write down your
plaintext.
TE TD L APCTZO ZQ NTGTW HLC. CPMPW DALNPDSTAD, DECTVTYR QCZX L STOOPY MLDP, SLGP HZY ESPTC QTCDE GTNEZCJ LRLTYDE ESP PGTW RLWLNETN PXATCP. OFCTYR ESP MLEEWP, CPMPW DATPD XLYLRPO EZ DEPLW DPNCPE AWLYD EZ ESP PXATCP'D FWETXLEP HPLAZY, ESP OPLES DELC, LYO DALNP DELETZY HTES PYZFRS AZHPC EZ OPDECZJ LY PYETCP AWLYPE. AFCDFPO MJ ESP PXATCP'D DTYTDEPC LRPYED, ACTYNPDD WPTL CLNPD SZXP LMZLCO SPC DELCDSTA, NFDEZOTLY ZQ ESP DEZWPY AWLYD ESLE NLY DLGP SPC APZAWP LYO CPDEZCP QCPPOZX EZ ESP RLWLIJ

- Bob obtains Alice's public key
*p*. - Bob applies Alice's public key to message
*M*to create ciphertext*C = p(M)*.

Then the message encrypting/decrypting works as follows:Alice does the following to create a public and a private key:

- Choose 2 large primes, p and q.
- Compute n = p * q.
- Choose e so that gcd(e, (p-1)(q-1)) = 1.
- Choose d = e
^{-1}mod (p-1)(q-1).- Publish e and n as the public key.
- Keep d as the secret key.

Bob does the following:

- Read the public directory for Alice's public key.
- Compute c = m
^{e}(mod n).- Send c to Alice.

Alice then does the following:- Receive c from Bob.
- Compute m = c
^{d}(mod n), using secret key d.- Read m.
## Exercises

You should do one of the following sets of exercises (programming or proof).

- Verify that gcd(13, 42*58) = 1. Show your work.
- Find an integer d so that 13*d = 1 (mod 42*58). Show your work or cite the online source you used to find d.
- Encipher the message ATTACK using the RSA cipher with public key n = 43*59 and e = 13. Show your work.
- Decipher the message 2116 140 0 581 140 that was encrypted using this cipher. Show your work.

## In this option, you will write a program to encrypt and decrypt using the RSA algorithm.

Programming Option- Set up: Follow the steps for creating a public key (n, e) and a private key d. You may decide if you want to program this or compute the key by hand and just store the key values as variables.
- Encryption should do the following:

- Convert the message into numbers (A = 1, B = 2, etc). To keep it simple, stick to using only capital letters.
- Obtain the public key for whom the message is to be sent.
- Encipher each letter by computing c = m
^{e}(mod n).- Print out the ciphertext.
- Decryption should do the following:
You may keep your program simple, or if you have more programming experience, you may add more to it.

- When you receive a string of numbers such as 1743 452 625, use your private key d to compute 1743
^{d}(mod n), 452^{d}(mod n), etc. This n is from your public key.- Take the results and translate back into letters.

## With this option, you will become more familiar with the mathematics behind the algorithm, and will research some applications where and how RSA is currently being used.

Proof Option- Each person who participates in an RSA system chooses large primes
pandq, then computesn = p * qandφ = (p -1)(q-1). They then choose an integere, with1 < e < φandgcd(e, φ) = 1. They next computed,1 < d < φsuch thated = 1 (mod φ). Research the Extended Euclidean Algorithm to find out how to findd. Explain how the algorithm works, and then demonstrate it by choosingp, q,andeas in RSA and computingd.You must cite any references you use!- Prove the following theorem (Theorem 1): Suppose
ris a set of_{1}, r_{2}, ..., r_{φ}φintegers such that gcd(r) = 1 for each i,_{i}, n1 ≤ i ≤ φandrfor_{i}≠ r_{j}(mod n)i ≠ j. Ifais a positive integer with gcd(a, n) = 1, thenaris also a set of_{1}, ar_{2}, ..., ar_{φ}φintegers such that gcd(ar) = 1 for each_{i}, ni,1 ≤ i ≤ φ, andarfor_{i}≠ ar_{j}(mod n)i ≠ j.You must cite any reference you use.- Prove the following Theorem (Euler's Theorem): If
n = p*qis a positive integer andais an integer with gcd(a, n) = 1, thena, wheere^{φ}= 1 (mod n)φ = (p-1)(q-1).You must cite any reference you use.- One of the beauties of RSA is that once you have chosen
e, the encryption key, and and determined the dercyption key,d, we havem. Show how Euler's Theorem can be used to get this result in RSA.^{ed}= m (mod n)You must cite any references used.- Do some research on how and where RSA cryptography is being used today. Write a page or two discussing an application and how RSA is being in it. Also discuss the required size of numbers needed to keep RSA secure today.
You must cite any sources you use.## Submit

Submit your solutions to the exercises along with your well-documented code or you well-written proofs on Kit.