Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

EECS 376: Foundations of Computer Science

Fall 2022

Homework 11

We will grade a subset of the assigned questions, to be determined after the deadline, so that we can provide better feedback on the graded questions.

Unless otherwise stated, each question requires sufficient justification to convince the reader of the correctness of your answer.

For bonus questions, we will not provide any insight during office hours or Piazza, and we do not guarantee anything about the difficulty of these questions.

We strongly encourage you to typeset your solutions in LATEX.

If you collaborated with someone, you must state their name(s). You must write your own solution for all problems and may not look at any other student’s write-up.

0. If applicable, state the name(s) and uniqname(s) of your collaborator(s).

1. Captcha test technology is often used to distinguish between human and robotic traffic to various web services. These tests can err and declare that a human user is actually a robot, and this can frustrate users of the web service.  We will attempt to estimate the true error rate p of captcha tests in this problem.

(a) Let c be a constant and Z a random variable. Show that Var(cZ) = c2 Var(Z).

(b) Let X be the number of times that a captcha test errs in a sample of N captcha tests. Then we can model X  = Xi  where each Xi  is an independent and identically distributed indicator variable taking value 1 with probability p and value 0 otherwise. Furthermore, we can write = to be the estimated error rate1. Compute Var().

(c) Bound the probability that | p| > 0.05 using Chebyshev’s inequality.

(d) Show that x(1 − x) ≤ 1/4 for all x ∈ R.

(e) Determine the number of samples N required to be 95% confident that | p| ≤ 0.05

according to Chebyshev’s inequality.

2. What day of the week will it be 376280376  days after this homework is due?  Show all your work, and do not use a calculator.   Hint : Use Fermat’s Little Theorem.

3. Sam and Peter want to collaboratively write the solutions for the written part of the 376 final, while keeping them secret from the students.  As a first step, they decide to use the Diffie-Hellman protocol with a large prime p and generator g to establish a shared key that is known only to them.  Peter chooses random a ← {1, . . . ,p − 1} and sends A = ga mod p to Sam; similarly, Sam chooses random b ← {1, . . . ,p − 1} and sends B = gb mod p to Peter. Then, they each compute k = gab mod p as the shared key.

However, unknown to them, a mischievous student, Malcolm, is able to eavesdrop on and also modify  all their communications, including the values A,B they send to each other. (This is called a man-in-the-middle” attack.)  Specifically, Malcolm chooses an exponent c ∈ {1, . . . ,p − 1}, and replaces both A and B with C = gc mod p.

(a) After Malcolm performs the above substitutions, what is the key computed by Peter?

What is the key computed by Sam? Show how Malcolm can compute both of these keys.

(b) To privately collaborate, Peter and Sam plan to encrypt and send their work in progress to each other, using their shared key in an encryption scheme.2 Such a scheme involves an encryption algorithm Enc and a decryption algorithm Dec. The encryption algorithm takes a key and message, and outputs a ciphertext.  The decryption algorithm takes a key and a ciphertext, outputs a message, and satisfies the following property:  for all keys k and messages m,

Dec(k,Enc(k,m)) = m.

Describe how Malcolm can read Peter and Sam’s work on the solutions,  without  be- ing  detected.  That is, Peter and Sam should be under the impression that they are communicating privately with each other, with nothing appearing out of the ordinary.

(c) The week before the exam, Peter and Sam wake up at 7 a.m. to double check the exam solutions they have written. It just so happens that Malcolm is a night owl and is asleep. As a result, he is not present to intercept and modify Peter and Sam’s messages.  Is it guaranteed that Peter and Sam will be able to communicate? And why?

4. Here we will run through an example of the RSA cryptosystem.  Let n = 91 be our large semi-prime (the RSA modulus) and e = 23 be our RSA public key. Do not use a calculator, but use the efficient algorithms that a calculator would use and show all of your work.

(a) Compute d, the private key by using the extended Euclidean algorithm.

Input: integers x > y 0

Output: a triple (g,a,b) of integers where g = gcd(x,y) and ax + by = g

1: function ExtendedEuclid(x,y)

2: if y = 0 then

3: return (x,1, 0) // Base case: 1x + 0y = gcd(x,y) = x

4: else

5: Write x = qy + r for an integer q, where 0 ≤ r < y

6: (g,a\ ,b\ ) ← ExtendedEuclid(y,r)

7: a b\

8: b a\ b\ q

9: return (g,a,b)

(b) Next, sign the message m = 3.

(c) Finally, verify that the signature s you found in (b) is correct.

5. You have decided to take a well deserved winter vacation after the semester. Unfortunately, the cruise you were on encountered a hurricane in the Bermuda triangle and you fell overboard and are sucked into a whirlpool! Fortunately, you are fished out by some friendly pirates who are willing to take you back to the ship. However, being pirates, such generosity comes at a price: in particular, you must decode a secret message that reveals the location of invaluable treasure.  The pirates tell you that the treasure map is from Roman times and the location was encoded using a Caesar cipher. Further, the pirates tell you that

the sum modulo 376 of the digits of the plaintext is equal to 124.

For this problem you may use a computer, but please include an explanation of what you did and why your answer is correct.

(a) First, decode the following ciphertext:

514936095159363250525936094050093352594036350933

364536325149092927132724272945092328132216211654

(b) To decipher the decoded text, the pirates tell you that the Romans split the text into

pairs of digits which can then be interpreted as the values of ASCII characters in order to further obscure the location of the treasure.  Truly ahead of their time!  Use this information to interpret the recovered ciphertext.