CIS 4363 Spring 2005 Homework Assignment 1

1. Let p(x) = x⁷ + x⁵ + x + 1 and q(x) = x³ + x² + 1 be polynomial over GF(2).  Calculate p(x)*q(x) mod m(x)

 where m(x) = x⁴ + x + 1. Show the steps you perform in doing these calculations.

2. We saw that 3DES (triple DES) was defined as E_k1D_k2K_k3 i.e. encrypt, decrypt and then encrypt instead of 3 encryptions so that 3DES could decrypt ciphertext that was encrypted with single DES. Is it possible to do the same with double DES?

3. Suppose that someone suggests the following way to confirm that you and your partner are both in possession of the same secret key. You create a random bit string the length of the key, XOR it with the key, and send it to your partner. Your partner XORs the incoming block with the key (which should be the same as your key) and sends it back. You check, and if what you receive is your original random string, you have verified that your partner has the same secret key, yet neither of you has ever transmitted the key. Is there a flaw in this scheme?

4. Determine gcd(24140,16762). Show the steps you perform in doing these calculations.

5. Use Fermat's theorem to find 3²⁰⁰⁰⁰¹ mod 11.

6. Suppose Alice and Bob are going to use RSA public key encryption.

a.       Alice chooses primes p = 41 and q = 53

b.       Alice chooses e = 623.

What are Alice's public and private keys? Show in detail all the computations performed by Alice in computing her public and private keys.

Suppose Bob wants to send Alice the message m=37. Show in detail all the computations performed by both Bob and Alice as Bob encrypts and Alice decrypts the message.

Show the steps you perform in doing these calculations, even if you use a calculator.

7. Suppose Alice and Bob are going to use Diffie Hellman key exchange to agree on a secret key.

a. The public prime p = 197

b. The public base g = 31

c. Alice chooses T_A = 101

d. Bob chooses T_B = 85

Show in detail all the computations performed by both Alice and Bob and their results.

What is the secret key that they can both use?

What is Alice's private key?

What is Alice's public key?

Show the steps you perform in doing these calculations, even if you use a calculator.

8. Decrypt the ciphertext <mxrsr bu yxr arrybhj>.

9. Number 5 on page 92 in the text.

This assignment must be turned in on Thursday March 4^th at class time. At that time I will go over the assignment as part of the review for Exam I.