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.
P --> 15 --> 15+3 = 18 (mod 26) --> SIf 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
ciphertext = (plaintext + shift) (mod 26),we subtract the shift from both sides of the congruence, to get
ciphertext - 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.
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
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 = me (mod n).
- Send c to Alice.
Alice then does the following:- Receive c from Bob.
- Compute m = cd (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.
Programming Option
In this option, you will write a program to encrypt and decrypt using the RSA algorithm.- 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 = me (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 1743d (mod n), 452d(mod n), etc. This n is from your public key.
- Take the results and translate back into letters.
Proof Option
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.- Each person who participates in an RSA system chooses large primes p and q, then computes n = p * q and φ = (p -1)(q-1). They then choose an integer e, with 1 < e < φ and gcd(e, φ) = 1. They next compute d, 1 < d < φ such that ed = 1 (mod φ). Research the Extended Euclidean Algorithm to find out how to find d. Explain how the algorithm works, and then demonstrate it by choosing p, q, and e as in RSA and computing d. You must cite any references you use!
- Prove the following theorem (Theorem 1): Suppose r1, r2, ..., rφ is a set of φ integers such that gcd(ri, n) = 1 for each i, 1 ≤ i ≤ φ and ri ≠ rj (mod n) for i ≠ j. If a is a positive integer with gcd(a, n) = 1, then ar1, ar2, ..., arφ is also a set of φ integers such that gcd(ari, n) = 1 for each i, 1 ≤ i ≤ φ, and ari ≠ arj (mod n) for i ≠ j.
You must cite any reference you use.- Prove the following Theorem (Euler's Theorem): If n = p*q is a positive integer and a is an integer with gcd(a, n) = 1, then aφ = 1 (mod n), wheere φ = (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 have med = m (mod n). Show how Euler's Theorem can be used to get this result in RSA.
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.