Cipher Project

Introduction

For thousands of years, people have searched for ways to send secret messages. Cryptography is the study of methods for sending and receiving secret messages. In general, there is a sender who is trying to send a message to a receiver. There is also an adversary who wants to steal the message. The method is considered to be successful if the sender is able to communicate a message to the receiver without the adversary learning what the message was.

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.

Part 1: Private Key Cryptography

Traditional cryptography is known as private-key cryptography. The sender and receiver agree in advance on a secret code and then send messages using that code. A Caesar cipher is one of the oldest private-key ciphers. In this code, the letters of the alphabet are shifted by some fixed amount. The original message is referred to as the plaintext and the encoded text is referred to as the ciphertext. For example, the following code is a Caesar cipher:
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 SEA
we would send the ciphertext
SRI MJ FC PERH ERH XAS MJ FC WIE.

Exercises

In these exercises you will be writing answers to some questions and may be writing code for others. You will be expected to submit any files you create for these exercises on Kit.
  1. 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.
  2. 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?
  3. 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
    A --> 0 --> 0+3 = 3 (mod 26) --> D
    M --> 12 --> 12+3 = 15 (mod 26) --> P
    If you are working with a partner, you need to encrypt both names for this exercise.
  4. 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 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.

  5. 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.
  6. 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

Part 2: Public Key Cryptography

In a public-key cryptosystem, the sender and the receiver do not need to agree in advance on a secret key. In fact, they each publish part of their key in a public directory. Yet, anyone with access to the encoded message and the public directory still cannot decode the message. Each person in a public-key system has two parts to their key - a public part used by others to encrypt messages to be sent to them, and a private part, used for decrypting messages that they receive. If Bob wants to send a secret message to Alice, he takes the following steps:
  1. Bob obtains Alice's public key p.
  2. Bob applies Alice's public key to message M to create ciphertext C = p(M).
Bob then sends C to Alice. She decodes the message by applying her secret key s to get the plaintext M = s(C). In order for this to work, p and s must be inverses such that it is difficult to compute s just by knowing p.

RSA Cryptosystem

Thd RSA Cryptosystem (named after its creators, Ron Rivest, Adi Shamir, and Leonard Adleman) is a public-key cryptosystem uses modular arithmetic and is based on the premise that it is difficult to factor a large random integer. The algorithm would work in the following way for Bob to send a message to Alice:
    Alice does the following to create a public and a private key:
  1. Choose 2 large primes, p and q.
  2. Compute n = p * q.
  3. Choose e so that gcd(e, (p-1)(q-1)) = 1.
  4. Choose d = e-1 mod (p-1)(q-1).
  5. Publish e and n as the public key.
  6. Keep d as the secret key.
Then the message encrypting/decrypting works as follows:
    Bob does the following:
  1. Read the public directory for Alice's public key.
  2. Compute c = me (mod n).
  3. Send c to Alice.

    Alice then does the following:
  4. Receive c from Bob.
  5. Compute m = cd (mod n), using secret key d.
  6. Read m.

Exercises

  1. Verify that gcd(13, 42*58) = 1. Show your work.
  2. 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.
  3. Encipher the message ATTACK using the RSA cipher with public key n = 43*59 and e = 13. Show your work.
  4. Decipher the message 2116 140 0 581 140 that was encrypted using this cipher. Show your work.
You should do one of the following sets of exercises (programming or proof).

    Programming Option

    In this option, you will write a program to encrypt and decrypt using the RSA algorithm.
  1. 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.
  2. 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.
  3. Decryption should do the following:
    • 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.
    You may keep your program simple, or if you have more programming experience, you may add more to it.

    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.
  4. 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!
  5. 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.
  6. 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.
  7. 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.
  8. 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.