Reading and Homework Assignments




Notes:
  1. Before solving the homework problems, you are expected to do the reading assignment and understand the related material. An asterisk (*) indicates supplementary reading material.
  2. Homework assignments must be typed, saved as PDF, and electronically submitted on the Blackboard.
  3. 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.doc (or in pdf) which can be used as a template for your homework.
  4. Assignments deadlines are announced on the Blackboard.
  5. Late submission is subjected to a 50% penalty if it is submitted by the cut-off time (usually 48 hours after the announced deadline).
  6. You may find your Class-SN here on the Blackboard/Grades.

Reading Assignment [Weeks 1-2]: Introduction to Cryptography, Modular Arithmetic, Prime Numbers.
Stallings: Chapter 1.
Stallings: Sections 2.1-2.4

Homework Assignment HW1:
Stallings: Chapter 1. Exer: 1, 5.
Stallings: Chapter 2. Exer: 2, 3(b,c), 5, 7 (only for k=6,7,8 positive divisors), 10, 11.
Additional Problems: (Required, Not optional)
EP#1. Use modular arithmetic as explained in the class to compute the following (Show work for credit).
(a) 2640 * 3928 (mod 13)
(b) 3456789 * 34567 (mod 9)
(c) 23456789 * 654321 (mod 11)
EP#2. Use the extended Euclidean algprithms as explained in the class to find the mubliplication inveres of 13 mod 61. Show the steps in equations (not tables)
Total: 10 exercises.

Reading Assignment [Weeks 3-4]: Symmetric Cipher, Cryptanalysis, Block Ciphers, DES, Number Theory.
Stallings: Chapter 3
Stallings: Sections 4.1-4.2
Stalling: Sections 2.4-2.7
Forouzan: Chapters 3*, 5*, 6*

Homework Assignment HW2:
Stallings: Chapter 2. Exer: 20, 22.
Stallings: Chapter 3. Exer: 1, 2.
Stallings: Chapter 4. Exer: 1, 2.
Additional Problems:
EP#1. In Hill cipher, the ciphertext is computed by: C = PK (mod 26), where P is the plaintext matrix and K is the key. All computations are done in (mod 26) for English alphabet.
(a) Explain how Eve can break the system if enough plaintext-ciphertext pairs are provided.
(b) What is the type of this attack?
EP#2. Consider a 24-bit ideal block cipher.
(a) What is the key size in this cipher?
(b) What is the size of the key-space? (How many keys are there?)
EP#3. Using Fermat't Little Theorem for primality test. Answer the following. Show work for credit.
(a) Test whether each of the following numbers is a prime: 101, 341, and 1105. Try at least two bases if needed, and state if the number is pseudoprime to any base you try. You may use a claculator to compute large powers.
(b) Find a composit number that is pseudoprime to base 3 and 7 but not pseudoprime to base 2.
EP#4. Apply the Chinese remainder theorem to solve the followiwng system of congruences:
x = 3 (mod 4)
x = 1 (mod 5)
x = 5 (mod 7)
Show work for credit.
Total: 10 exercises.

Programming Assignment PA1: See the PA1.pdf document.

Reading Assignment [Weeks 5-6]: Group Theory, Subgroups, Cyclic Groups, Primitive Roots, Group Isomorphism
LNGT: Sections 1 and 2

Homework Assignment HW3:
LNGT: Section 1. Exer: 3, 4, 5, 6(c,d), 7(b,c).
LNGT: Section 2. Exer: 3(a,b,c,f,g), 6(a,b), 7(a,b,c), 8(a,b), 9.
Total: 10 exercises.

Reading Assignment [Week 7]: Review, Midterm exam preparation

Reading Assignment [Weeks 8-9]: Permutation Groups, Finite Fields, 3DES, AES
LNGT: Section 3.
Stallings: Chapter 5, Chapter 6, Section 7.1*
Online materials on AES: Lecture 07-AES.ppt, AES_Demo.swf*.

Homework Assignment HW4:
LNGT: Section 3. Exer: 3(a,b,c), 4(a,b,c), 5, 6(c,e), 7, 8.
Additional Problems:
EP#1. Apply the Shift-Xor algorithm to multiply P1=(00001101) by P2=(11001101) in GF(256) using the irreducible polynomial x^8 + x^4 + x^3 + x + 1 as a modulus. Show all the steps in a table as explained in the class.
EP#2. Consider the generator for GF(2^3) in Table 5.5. This table is used to efficiently perform operations in this field.
(a) Reconstruct Table 5.5 for GF(2^3) using the modulus x^3+x^2+1 (No need for the Hex column).
(b) Use your table to compute: (g^2 + g)(g^2 + 1) and (g^2)/(g^2 + g)
EP#3. Answer the following questions about AES:
(a) What are the main advantages and disadvantages 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. Organize your answer in a 6x5 table (including the headers)
Total: 10 exercises.

Programming Assignment PA2: See the PA2.pdf document.

Reading Assignment [Weeks 10-12]: Public-Key Cryptography: Diffie Hellman, Elgamal, Digital Signature, Secure Hashing, Blockchian
Stallings: Sections 9.1, 10.1, 10.2.
Stallings: Chapter 11*, Sections 13.1*, 13.2.
Bashir: Chapter 1 (Blockchain 101*)
Narayanan: Chapter 1.
Online materials: PPT Slides Lectures 08, 09 and 10.

Homework Assignment HW5:
Stallings: Chapter 10. Exer: 2, 3, 5.
Stallings: Chapter 11. Exer: 3(a,b), 4, 6.
Narayanan: Chapter 1. Exer: 4.
Additional 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. Show that that if Eve can break Diffie-Hellman key exchange scheme, then she can also break ElGamal cryptosystem.
EP#3. 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.
Total: 10 exercises.

Reading Assignment [Weeks 13-14]: RSA, DSS, Bitcoin, Zero-Knowledge Proofs
Stallings: Sections 9.2.
Forouzan: Section 10.2*.
Stallings: Section 13.4.
Schneier: Secions 5.1, 5.2.
Satoshi Nakamoto: Bitcoin white paper.
Online materials: PPT Slides Lectures 11, 12, and 13.

Homework Assignment HW6:
Stallings: Chapter 9. Exer: 2(b), 7(and explain), 8, 18.
Stallings: Chapter 13. Exer: 2, 3, 5.
Additional Problems:
EP#1. Prove or disprove that computing the totient of n is equivalent to factorizing n in RSA.
EP#2. Answer the following about Bitcoin:
(a) if the block reward is 6.25 BTC now, what is the expected block reward in year 2050?
(b) Explain how to increase the difficulty level of block mining using the proof-of-work.
(c) If Eve has 40% of the total network computation power, what is the probability she can successfully attack the system if each transaction has to wait for the 6 block confirmation?
(d) Eve suggests that the proof-of-work should be easy so that we don't consume lots of electricity. Explain the potential risk if the proof of work takes one second instead of 10 minutes on average.
EP#3. Answer the following about Zero-knowledge proofs.
(a) What is the main reason behind the high cost associated with ZKPs in general?
(b) Consider the zero-knowledge proof of graph-isomorphism. If each graph has 128 nodes, compute the optimal number of rounds.
(c) Explain why ZKPs are needed in the setup of an RSA cryptosystem.
(d) Besides RSA, name three other applications that use ZKPs and explain why ZKP is needed in each case.
(e) What are the main requirements of a zero-knowledge proof?
(e) Which of the following functions are negligible? Justify your answer in each case.
1. f(n) = 1/log(n)
2. f(n) = 1/(2n)
3. f(n) = 1/(n^2)
4. f(n) = n/(n!)
Total: 10 exercises.

Reading Assignment [Week 15]: Cryptocurrency, Smart Contracts, POW Alternatives, Mining, Traceablity.
Bashir: Chapters 8-11*.
Narayanan: Chapters 5-6*.
Online materials: PPT Slides Lecture 14.

Homework Assignment HW7:
EP#1. In a 2x8 table, compare Bitcoin and Ethereum in terms of the following:
(a) Year of release
(b) Average block time
(c) Current block reward*
(d) Maximum supply
(e) POW hash function
(f) Current block height (latest block number)*
(g) Current network difficulty*
(h) Current hashrate*
(* Can be found in the blockchain explorer. Write the date/time in which you access the page)
EP#2. Answer the following questions about Ethereum:
(a) What programming languages are used to implement EVM?
(b) What programming languages are used to write Ethereum smart contracts?
(c) What is the advantage of using Ethash in Ethereum proof of work?
(d) What alternative of proof of work is proposed for Ethereum 2.0?
EP#3. Unlike Bitcoin, Ethereum has no maximum supply by design.
(a) Explain the reason behind having no fixed maximum supply in Ethereum? How this will affect the inflation rate?
(b) Suppose that 0.1% of all Ether is lost every year within the global Ethereum community. If the current supply is 113805000 ETH, block reward is 2 ETH per block, and the average block time is 13 seconds (fixed), estimate the expected maximum supply deduced by the equilibrium point per the design. When is this equilibrium expected to happen (in which year)?
EP#4. Answer the following questions about Proof of work alternatives.
(a) What are the advantages and disadvantages of POW?
(b) Name two cryptocurrency using POW, and two using POS.
(c) Consider the Pay and Play mechanism. What is the pay in POW, in POS, and in proof of capacity?
(d) Explain how the proof of elapsed time works, and why it is not suitable for cryptocurrency.
EP#5. Suppose that Coin XYZ has an average block time of 5 minutes, and it is adjusted every 1000 blocks. Assume the current network difficulty is 16 GH, and more miners join the network.
(a) Approximately how many leading zero bits does the target hashcode in the POW of XYZ have?
(b) Compute the next difficulty if the total time to mine the last 1000 blocks was 66 hours.
EP#6. Answer the following questions about Cryptomining:
(a) Explain the mining process.
(b) What is a hashrate? What is it used for?
(c) A target hashcode of some cryptocurrency starts in 16 zero hex digits followed by 7A. Compute the network difficulty.
(d) What is a mining pool? Why miners join mining pools? Give two examples of mining pools for Bitcoin and two for Ethereum.
EP#7. Search the Internet and find the top 5 Bitcoin mining pools as of today. For each mining pool, write its name, year founded, country/location, and mining hashrate (for Bitcoin). Rank these pools based on performance and organize your answer in a table. Provide a Pie chart similar to the one given in the slides of Lecture 14.
Total: 7 exercises.