Reading and Homework Assignments




Notes:
  1. Before solving the homework problems, you are expected to do the reading assignment and understand the related material.
  2. Homework assignments must be typed, saved as PDF, and electronically submitted on the Blackboard.
  3. It is highly recommeneded to do the homeowk in Latex. Please register with ShareLatex for an online account. Collaboration is only allowed in ShareLatex (must be shared with instructor before start).
  4. The homework PDF file must have a header on the first page, and a header for each question. See HW-format. You should follow this format when you submit your homework in order to be graded. See also a HW_Sample which can be used as a template for your homework.
  5. Assignments deadlines are announced on the Blackboard.
  6. Late submission is subjected to a 50% penalty if it is submitted by the cut-off time (usually 48 hours after the announced deadline).
  7. You may find your Class-SN here.

Reading Assignment [Weeks 1-2]: Introduction to Cryptography, Modular Arithmetic
Forouzan: Chapters 1 and 2 (all)
Rosen: Sections 4.1 - 4.3

Homework Assignment HW1:
Forouzan: Chapter 1. Exer: 1, 2, 7, 8(a).
Forouzan: Chapter 2. Exer: 12(a,b), 16(b), 18(b,c), 25, 26, 32(a, b), 36(c), 40(b).
Total: 12 exercises.

Reading Assignment [Weeks 3-4]: Traditional symmetric-key ciphers, Group Theory
Rosen: Section 4.4
Forouzan: Chapter 3
LNGT: Section 1

Homework Assignment HW2:
Forouzan: Chapter 3. Exer: 11, 12, 13, 14, 16, 18, 22(for P="the house"), 36.
LNGT: Section 1. Exer: 1, 3, 4, 5, 6, 7, 8.
Total: 15 exercises.

Reading Assignment [Weeks 5-7]: Cyclic Groups, Group Isomorphism, Rings, Fields, Finite Fields
LNGT: Section 2
Forouzan: Chapter 4

Homework Assignment HW3:
LNGT. Sec 2. Exer: 1(a), 3, 4, 6, 7(a, b), 8(a, c), 10.
Forouzan: Chapter 4. Exer: 14, 17, 18(c), 19(c), 24, 35, 36, 37.
Total: 15 exercises.

Reading Assignment [Weeks 8-9]: Modern Asymmetric-key Ciphers, Blockcipher, DES, AES, Encipherment.
Forouzan: Chapters 5, 6, 7 and 8.
Additional ppt slides on: Blockcipher, DES, and AES.

Homework Assignment HW4:
Forouzan: Chapter 5. Exer: 8, 14, 24, 29.
Forouzan: Chapter 6. Exer: 10.
Forouzan: Chapter 7. Exer: 6, 12.
Forouzan: Chapter 8. Exer: 8, 11, 18.
Extra Problems:
EP#1. Compute the key size of a 24-bit ideal block cipher.
EP#2. Explain how meet-in-the-middle attack reduces the key search from 2^112 to 2^57 in double DES. How much extra storage is needed?
EP#3. Answer the following questions about AES:
(a) What are the main advantages and disadvantage of 3DES? How does AES keep the advantages and eliminate the disadvantages?
(b) What are the main requirements of AES stated by NIST?
(c) Briefly describe the 4 stages in the AES round?
(d) The 4 stages in the AES round together provide high security. Explain the weakness of each stage alone.
(e) What are the main strength points of the design of the S-box in AES?
EP#4. Compare DES, 3DES and the three AES versions in terms of: block size, number of rounds, the main key length, and the round-key length. (Use a 5x4 table)
Total: 14 exercises.

Reading Assignment [Weeks 10-11]: Math for Cryptography, Asymmetric-key Ciphers, RSA, and Diffie-Hellaman Scheme.
Forouzan: Sections: 9.1-9.4 and 9.6 (skip Pollard Methods in 9.3).
Forouzan: Sections 10.1, 10.2 and 15.3.

Homework Assignment HW5:
Forouzan: Chapter 9. Exer: 31(a), 35(a), 36(a,d).
Forouzan: Chapter 10. Exer: 12(c), 14, 17, 19, 20.
Extra Problems:
EP#1. Explain the timing attack on RSA.
EP#2. Suppose Alice, Bob, and Eve use RSA with the same modulus n, and each user has a different pair of public/private keys assigned by a trusted party. What are the possible risks?
EP#3. Alice and Bob exchange keys in Diffie-Hellman scheme, with p = 19, g = 2. If Alice chooses a random value x = 16, and recieves 13 from Bob.
(a) What value Alice should send to Bob?
(b) Compute the exchanged key.
EP#4. Explain the man-in-the-middle attack on Diffie-Hellman key exchange scheme.
Total: 12 exercises.

Reading Assignment [Weeks 12-13]: Quadratic Residues, Rabin Cryptosystem, ElGamal Cryptosystem, Digital Signature.
Forouzan: Sections 9.5, 10.3, 10.4.
Forouzan: Section 13.5.

Homework Assignment HW6:
Forouzan: Chapter 9. Exer: 33 (b, c), 34(c).
Forouzan: Chapter 10. Exer: 22, 24, 25.
Forouzan: Chapter 13. Exer: 5, 11, 16, 27.
Extra Problems:
EP#1. Consider ElGamal cryptosystem with the following parameters: prime p = 19, generator g = 2, your private key is x = 6.
(a) Compute your public key.
(b) If you receive the ciphertext C = (14, 13), what is the plaintext?
(c) Encrypt the message M = 5 to Alice, with public-key = (23, 3, 4).
EP#2. Find all square roots of 92 modulo n where (a) n = 103, (b) n = 133, (c) n = 127.
EP#3. The modular sequare function, y = x*x (mod n = pq), is a trapdoor one-way function, with (p,q) as a secret. It is easy to compute y from x, but it is hard to compute x from y unless you know the secret. Besides this funtion, think of another example of a trapdoor one-way function. Explain the function and the secret parameter in your example.
Total: 12 exercises.

Reading Assignment [Weeks 14-15]: Secure Hashing, DSS, Integrity, Authentication, Key Management.
Forouzan: Sections 11.1-11.3. 15.1-15.3
Slides on Integrity & Authentication and Secure Hashing and DSS.

Homework Assignment HW7:
Forouzan: Chapter 11. Exer: 1, 11, 13, 15, 16, 24.
Forouzan: Chapter 15. Exer: 18, 20.
Extra Problems:
EP#1. Consider ElGamal digital signature scheme with the following parameters: prime p = 19, generator g = 2, your private key is x = 6, and Alice's public key is (p = 19, g = 2, y = 9).
(a) Sign the message digest M = 3 using your private key and random parameter k = 5
(b) If Eve gives you a signed document [M = 9, a = 2, b = 9] and she said that this document is signed by Alice. Is Eve telling the truth? How do you know?
(c) If Alice used the same random parameter (k) to sign two documents, can Eve break the system? Give an example of two signatures to justify your claim.
EP#2. Answer the following questions about Secure hashing and DSS:
(a) What is a secure hash function?
(b) What are the criteria of cryptograpic hash function?
(c) Given a secure has function, h, and a hash value y = h(x) of 144 bits, how many attempts (on average) are needed to find x?
(d) How many attempts (on average) are needed to find two different input: x and y, such that h(x) = h(y) using the secure hash function in Part (c)?
(e) What are the main required features of DSA by NIST?
EP#3. Show that breaking Rabin cryptosystem is equivalent to factorizing n.
Total: 11 exercises.