CSC 485/685 – Fall 2023 – Practice Problems

Note that practice problems are required – they are not optional problems!

For each week’s topic(s), students should work the practice problems below during the week that the topic is discussed as part of their normal reading and studying. On Tuesday of the next week, these will be worked in class with students being called on to provide solutions – so be prepared! These will not be graded unless it becomes clear that students are not doing the practice problems. As additional incentive, the practice problems will be very similar to the problems you will see on exams.

For Week 1 (Aug 14 – Aug 18)

Complete before Tuesday, Aug 22

Textbook, Exercises 0.1, 0.7, 0.8 (a-c), 0.9

For Week 2 (Aug 21 – Aug 25)

Complete before Tuesday, Aug 29

Textbook, Exercises 1.4, 1.8, 2.1, and 2.2 (a and d)

Challenge (optional): Exercise 2.5 – this involves more abstract thinking, but is a very useful mental exercise if you can work through it. We’ll talk about this briefly in class, but only if time allows.

For Week 3 (Aug 28 – Sept 1)

Complete before Tuesday, Sept 5

Textbook, Exercise 2.6

In the set-up for Exercise 2.12, the problem requires that \(\Sigma.{\mathcal C}\subseteq \Sigma.{\mathcal M}\). Think through what this means: Argue/prove that for any scheme that is correct, \(|\Sigma.{\mathcal C}|\geq|\Sigma.{\mathcal M}|\). What does the \(\Sigma.{\mathcal C}\subseteq \Sigma.{\mathcal M}\) imply about the relation between the sizes of \(\Sigma.{\mathcal C}\) and \(\Sigma.{\mathcal M}\)? What can you conclude from these facts about the relationship between the sets \(\Sigma.{\mathcal C}\) and \(\Sigma.{\mathcal M}\)?

Working over \(\mathbb{Z}_{11}\), what is the unique degree 1 polynomial through the points \((1,4)\) and \((2,9)\)? What is the \(y\) value of this polynomial when \(x=3\)? If you want a slightly harder problem, pick three points and find the degree 2 polynomial through those points.

Textbook Exercise 3.7: There is a very simple solution to this problem that, once discovered is obviously correct and requires no math at all to justify – just working with the definition of \(t\) of \(n\) secret sharing. You may use a standard secret sharing scheme in solving this problem.

For Week 4 (Sept 4 – Sept 8)

Practice with the Share() function by creating shares for a 3-out-of-5 using Shamir’s scheme with modulus 11 and secret 3. Note that the algorithm is randomized, so there isn’t a single correct answer to this question!

Textbook, Exercise 4.2

Textbook, Exercise 4.3c

Textbook, Exercise 4.12a-b

For Week 6 (Sept 18 – Sept 22)

Textbook, Exercise 4.9

Using Lemma 4.10, what is the lemma-provided upper bound of the “birthday probability” if the number of queries is less than the cube-root of the number of values \(N\) (in other words, \(q\leq N^{1/3}\)).

In the previous question, if \(N=2^{\lambda}\), is the probability negligible?

Textbook, Exercise 5.8c (the answer is “no”, this is not a secure RNG, and the point of this exercise is to work with the definition of a secure RNG and write a simple distinguisher)

For Week 7 (Sept 25 – 29)

Textbook, Exercise 6.5

Textbook, Exercise 6.7

Textbook, Exercise 6.11

A little more challenging: Try 6.8d

For Week 8 (Oct 2 – Oct 5)

Textbook, Exercise 7.7 (a) [this is not CPA secure, so give a distinguisher]

Textbook, Exercise 8.2

Consider a bad implementation of CBC mode, where a programmer took the process ID of the running program, which is a 16-bit number, ran it through a secure PRG to stretch that out to \(blen\) bits, and used that as block \(c_0\) in CBC mode. This is not CPA secure. Give a distinguisher for the cpa-L vs cpa-R libraries.

For Week 9 (Oct 9 – Oct 12)

(Note: Short week – Fall Break)

Textbook, Exercise 8.9

Explain how to modify the padding attack in the book so that it works with PKCS#7 padding (instead of X.923 padding).

Give a distinguisher that shows that CTR mode is not CCA secure.

For Week 11 (Oct 23 – Oct 27)

Consider a four-character message encyrpted using AES in CTR mode, which you know contains your grade of “FAIL”. You intercept the ciphertext and can temper with it. Explain how you would change the ciphertext so that the receiver, when decrypting it, reads “PASS”.

Textbook Exercise 10.3. “Prove X is secure” normally uses a long hybrid proof. However, in this case, that is not necessary. Think about the logical construction (“If A is secure then B is secure”) and prove this through the logical contrapositive (“If B is not secure then A is not secure.”) It’s a trivial proof once you flip it around like this.

For Week 12 (Oct 30 – Nov 3)

Textbook, Exercise 11.3 (and 11.4)

Textbook, Exercise 11.13

For Week 13 (Nov 6 – Nov 10)

Consider RSA with the following prime values: \(p=19\), \(q=31\).

Textbook, Exercise 13.8

Textbook, Exercise 13.11