Cryptography lab

Don't sit too near your partner during this lab. If possible, sit on opposite sides of the room. Communicate with your partner only via e-mail. Each person will need a computer with Web access. You can use your own computer or one of the lab machines.

• Homework exercise 8.0: Who is your lab partner?

In this lab, you will be using cryptography to send your phone number to your lab partner via e-mail. (To protect your privacy, you can of course use a fake phone number). You will use encryption, so that even someone who has access to all of your e-mail (and all of your partner's e-mail) cannot determine your phone number. In addition, you will only communicate with your partner via e-mail! In other words, even someone who has access to all of the communication between you and your partner cannot determine your phone number.

In fact, you're going to send your phone number twice. In Part 1 of the lab, you will use Diffie-Hellman key exchange to establish a shared secret key, and then use that key to encrypt the phone number. In Part 2 of the lab, you will encrypt and send your phone number using RSA public-key cryptography.

For all numerical calculations in this lab, it is recommended that you use Wolfram Alpha (http://wolframalpha.com). This site is capable of computing a vast range of mathematical expressions. In particular, we can use it for doing exponentiation and clock arithmetic with very large numbers. As an initial example, compute 3453342^2134462 (mod 37865763), by entering "3453342^2134462 mod 37865763" at Wolfram Alpha. You should obtain the answer 28627686. Note that you can copy and paste the answer by hovering over the results, and then hovering over "A" symbol below the result. Make sure to practice this so that you don't have to type out long numbers manually.

• Homework exercise 8.1: Let b=54376845678265437, e=3473443267, and m=25367532678235867. What is b^e (mod m)?
• Homework exercise 8.2: What is the 10-digit phone number you plan to use for this lab? (This can be a fake phone number, or your real phone number.)

Part 1: Diffie-Hellman key exchange and symmetric key cryptography

1. Choose a private number. This should be random, 8-digit number. You can just make one up, or you can enter RandomInteger(10^8) into Wolfram Alpha.
   • Homework exercise 8.3: What is your private number?
2. If your partner hasn't already done it for you, create the public numbers for this exchange and send them to your partner. Specifically, choose a random base (5 digits) and a random modulus (15 digits) and e-mail them to your partner. You can use Wolfram Alpha for the random numbers, or just make them up yourself. (By the way, this lab deliberately simplifies the process of selecting a modulus---in fact, using a random modulus doesn't guarantee that the key exchange will be secure. See below for an optional extension exercise that tells you how to make the exchange secure.)
   • Homework exercise 8.4: What is your public base?
   • Homework exercise 8.5: What is your public modulus?
3. Compute your public-private mixture, and e-mail it to your partner.
   • Homework exercise 8.6: What is your public-private mixture?
   • Homework exercise 8.7: What is your partner's public-private mixture?
4. Compute the shared secret key.
   • Homework exercise 8.8: What is the shared secret key?
5. We will be using the secret key as a one-time pad. In class, we used a one-time pad with the XOR operation, but in this lab we will make things even easier by using ordinary addition. So, to encrypt your phone number, just add your 10-digit phone number to the secret key (use Wolfram Alpha), and send the result to your partner by e-mail.
   • Homework exercise 8.9: What is your ciphertext (i.e. the encrypted version of your phone number)?
6. Wait until your partner sends you their encrypted phone number. Decrypt it. (Ask for help if you can't see how to do this.)
   • Homework exercise 8.10: What is your partner's plaintext (i.e. the decrypted version of your partner's phone number)?

Part 2: Public key cryptography using RSA

1. Generate your RSA public and private keys.
   We will do this using the site Mobilefish RSA key generation service. Recall that you need three numbers for RSA: (i) a private exponent; (ii) a public exponent; and (iii) a public modulus. The method for generating these depends on some mathematical details that we did not cover in class. The following instructions walk you through the process. You are not required to understand how or why it works.
   • (a) On the Mobilefish page linked above, scroll down to "Step 1: Enter or generate prime numbers." Leave the key size as 1024 bits. Update, 10:05am, 2/14: use 128 bits instead. Click on the button labeled "Auto generate prime number p and q."
   • (b) Scroll down to "Step 2: Enter public exponent." In the drop-down box next to "Public exponent (e) is a," select "decimal." You should now see the default value "65537" entered in the box next to "Public exponent (e)." Delete the default value, and enter your own random 10-digit public exponent.
   • (c) Scroll down to "Step 3: Generate public / private keys based on prime numbers and exponent." In the drop-down box next to "Convert generated keys to," select "decimal." Now click the button labeled "Generates keys." At this point, you may see an error message, stating "Exponent e and phi are no comprimes, select another e." If you get this error message, return to step (b) and select a different random public exponent. Repeat steps (b) and (c) as necessary until the key generation succeeds. Hint: don't use an even number for your public exponent, since even numbers will always produce the error message.
   • (d) Record all your keys (the format should be set to "decimal" for each one):
     • Homework exercise 8.11: What is your modulus? (This is shown under "Step 3" next to the box that says "Enter modulus (n).")
     • Homework exercise 8.12: What is your public exponent? (This is shown under "Step 3" next to the box that says "Public exponent (e).")
     • Homework exercise 8.13: What is your private exponent? (This is shown under "Step 3" next to the box that says "Enter private exponent (d)." The web page refers to your private key as "Private key A." You can ignore the entries under "Private key B.")
   Once you've recorded your public and private keys, close the Mobilefish RSA page. There are encryption and decryption facilities further down the page, but we won't use them in this lab. We will be encrypting and decrypting using Wolfram Alpha. Note that because of the way the Mobilefish site translates messages into binary numbers before encrypting them, it produces different answers than Wolfram Alpha, so don't use Mobilefish to check your answers either.
2. E-mail your modulus and public exponent to your partner. Keep your private exponent secret, of course.
3. Once your partner has sent you their modulus and public exponent, use this information to encrypt your 10-digit phone number. Send the resulting ciphertext to your partner. Update, 10:05am, 2/14: All remaining questions are optional.
   • Homework exercise 8.14: What is your ciphertext (i.e. the encrypted version of your phone number)?
4. Once your partner has sent you their encrypted phone number, decrypt it.
   • Homework exercise 8.15: What is the ciphertext you received from your partner (i.e. the encrypted version of your partner's phone number)?
   • Homework exercise 8.16: What is the plaintext you received from your partner (i.e. the decrypted version of your partner's phone number)?
   • Homework exercise 8.17: Is the received plaintext the same as you computed in Part 1 of this lab? Why or why not? (Give a one-sentence answer.)

Part 3: Optional extensions

1. As mentioned above, choosing a random modulus for Diffie-Hellman doesn't guarantee the usual level of security for the key exchange. To achieve that level of security, the modulus must be a prime number. That is, the modulus must be a number that has no factors, other than 1 and itself. Wolfram Alpha does have a function called isprime (e.g. try isprime(17), and isprime(26)). But it could take you a long time to guess a 15-digit prime number (only about 3% of 15-digit numbers are prime). Instead, think of a way of generating a random 15-digit prime number that employs the Wolfram Alpha function NextPrime.
2. Use your new, secure modulus to generate a new secret key via Diffie-Hellman. If your partner isn't ready, do both ends of the key exchange yourself.
3. Above, we used the shared secret key as a one-time pad by adding the key to the plaintext. In class, however, we learned that a more usual application of one-time pads is to XOR the key and the plaintext. Wolfram Alpha can do this XOR for you (for example, try 234 xor 543). Use this XOR functionality to encrypt your phone number. How would you decrypt the resulting ciphertext? If your partner is working on this part of the lab, send each other your XOR-encrypted phone numbers and verify that you can decrypt them correctly.
4. Our method of generating an RSA modulus omitted some of the important details. The correct way to generate an RSA modulus is to select two large random primes p and q, then use the modulus n=pq. Using this fact, generate a new RSA modulus, roughly 30 digits in length. Generate the public and private exponents via Mobilefish. Verify that you can encrypt and decrypt your phone number using these new keys.
5. How do we know that about 3% of 15-digit numbers are prime? (Hint: look up the Prime Number Theorem on Wikipedia.)