CS 257 - Problem Set 3

Assigned:Wednesday September 23
Deadline:Thursday October 8, 11:59pm

Reading

Mark Stamp, “Information Security: Principles and Practice”, Chapter 4.

Available at Yale as a licensed online book.

Deliverable

Create a pdf file yournetid.cs257hw3.pdf with your answers to the following questions. DO NOT include your name or netid in the file. You should use gradescope to submit your assigments.

Problem 1: (10 points) [Chapter 4, problem 2, page 115]

Suppose that Bob receives Alice's digital certificate from someone claiming to be Alice.
  1. Before Bob verifies the signature on the certificate, what does he know about the identity of the sender of the certificate?
  2. How does Bob verify the signature on the certificate and what useful information does Bob gain by verifying the signature?
  3. After Bob verifies the signature on the certificate, what does he know about the identity of the sender of the certificate?

Problem 2: (10 points) [Chapter 4, problem 6, page 116]

Suppose that Alice's RSA public key is (N, e) = (33,3) and her private key is d = 7.
  1. If Bob encrypts the message M = 19 using Alice's public key, what is the ciphertext C? Show that Alice can decrypt C to obtain M.
  2. Let S be the result when Alice digitally signs the message M = 25. What is S? If Bob receives M and S, explain the process Bob will use to verify the signature and show that in this particular case, the signature verification succeeds.

Problem 3: (15 points) [Chapter 4, problem 10, page 116]

Consider the RSA public key cryptosystem. The best generally known attack is to factor the modulus, and the best known factoring algorithm (for a sufficiently large modulus) is the number field sieve. In terms of bits, the work factor for the number field sieve is

f(n) = 1.9223n1/3(log2n)2/3,

where n is the number of bits in the number being factored. For example, since f(390) ≈ 60, the work required to factor a 390-bit RSA modulus is roughly equivalent to the work needed for an exhaustive search to recover a 61-bit symmetric key.

  1. Graph the function f(n) for 1 < n < 10,000.
  2. A 1024-bit RSA modulus N provides roughly the same security as a symmetric key of what length?
  3. A 2048-bit RSA modulus N provides roughly the same security as a symmetric key of what length?
  4. What size of modulus N is required to have security roughly comparable to a 256-bit symmetric key?

Problem 4: (10 points) [Chapter 4, problem 14, page 117]

Suppose that Alice and Bob share a 4-digit PIN number, X. To establish a shared symmetric key, Bob proposes the following protocol: Bob will generate a random key K that he will encrypt using the PIN number X, that is, E(K, X). Bob will send E(K, X) to Alice, who will decrypt it using the shared PIN number X to obtain K. Alice and Bob will then use the symmetric key K to protect their subsequent conversation. However, Trudy can easily determine K by a brute force attack on the PIN number X, so this protocol is insecure. Modify the protocol to make it more secure. Note that Alice and Bob only share the 4-digit PIN number X and they do not have access to any other symmetric key or public keys. Hint: Use Diffie-Hellman.

Problem 5: (10 points) [Chapter 4, problem 20, page 118]

Suppose that Bob's knapsack private key consists of (3,5,10, 23) along with the multiplier m-1 = 6 and modulus n = 47.
  1. Find the plaintext given the ciphertext C = 20. Give your answer in binary.
  2. Find the plaintext given the ciphertext C = 29. Give your answer in binary.
  3. Find m and the public key.

Problem 6: (15 points) [Chapter 4, problem 29, page 120]

In the RSA cryptosystem, it is possible that M = C, that is, the plaintext and the ciphertext may be identical.

  1. Is this a security concern in practice?
  2. For modulus N = 3127 and encryption exponent e = 17, find at least one message M that encrypts to itself.

(Do not include trivial solutions, e.g., 0 and 1)

Problem 7: (10 points) [Chapter 4, problem 35, page 122]

This problem deals with digital signatures.

  1. How and why does a digital signature provide integrity?
  2. How and why does a digital signature provide non-repudiation?

Problem 8: (10 points) [Chapter 4, problem 37, page 122]

A digital signature or a MAC can be used to provide a cryptographic integrity check.

  1. Suppose that Alice and Bob want to use a cryptographic integrity check. Which would you recommend that they use, a MAC or a digital signature? Why?
  2. Suppose that Alice and Bob require a cryptographic integrity check and they also require non-repudiation. Which would you recommend that Alice and Bob use, a MAC or a digital signature? Why?

Problem 9: (10 points) openssl code signing and verification

Read the tutorial: code signing and verification with OpenSSL. The directory /c/cs257/hws/hw3 contains the following files: 
-rw-rw-r-- 1 sbs5 cs257ta  644 Sep 24 13:28 file2.txt
-rw-rw-r-- 1 sbs5 cs257ta  761 Sep 24 13:29 file3.txt
-rw-rw-r-- 1 sbs5 cs257ta  851 Sep 24 13:29 file4.txt
-rw-rw-r-- 1 sbs5 cs257ta 1249 Sep 24 13:29 file5.txt
-rw-rw-r-- 1 sbs5 cs257ta  518 Sep 24 13:38 file6.txt
-rw-rw-r-- 1 sbs5 cs257ta 1715 Sep 24 13:39 file7.txt
-rw-rw-r-- 1 sbs5 cs257ta  451 Sep 24 13:09 public.pem
-rw-rw-r-- 1 sbs5 cs257ta  256 Sep 24 13:24 sign.txt.sha256
-rw-rw-r-- 1 sbs5 cs257ta  350 Sep 24 13:25 sign.txt.sha256.base64
One of the text files (file[2-7].txt) has been signed with a private key corresponding to the public key public.pem. Verify the signature and identify which file was signed. Note: you can use the openssl UNIX command. You do not need to write code. (I didn't.)

Extra credit point: who is the author of the text?