Cryptography Week 2 Quiz Answer
By University Of Maryland
Cryptography Quiz 2
Computational Secrecy and Principles of Modern Cryptography
Q2) Two ASCII messages containing English letters and spaces only are encrypted using the one-time pad and the same key. The 10th byte of the first ciphertext is observed to be 0xB7 and the 10th byte of the second ciphertext is observed to be 0xE7. Let m1 (resp., m2) denote the 10th ASCII character in the first (resp., second) message. What is the most you can conclude about m1 and m2?
- m1 is the space character and m2 is the character 'p'.
- m1 is the character 'p' and m2 is the space character.
- m1 is the character 'B' and m2 is the character 'E'.
- One of m1 or m2 is the space character, and the other is the character 'p'.
- Nothing can be determined about m1 or m2 since the one-time pad is perfectly secret.
Q2) Three ASCII messages containing English letters and spaces only are encrypted using the one-time pad and the same key. The 10th byte of the first ciphertext is observed to be 0x66, the 10th byte of the second ciphertext is observed to be 0x32, and the 10th byte of the third ciphertext is observed to be 0x23. Let m1 (resp., m2, m3) denote the 10th ASCII character in the first (resp., second, third) message. What is the most you can conclude about m1, m2, and m3?
- m1 is the character 't', m2 is the space character, and m3 is the character 's'.
- m1 is the space character, m2 is the character 't', and m3 is the character 'e'.
- Exactly one of m1, m2, or m3 is the space character, but nothing else can be determined.
- Nothing can be determined about m1, m2, or m3 since the one-time pad is perfectly secret.
Q3) Which of the following is true about computational secrecy? (Select all that apply.)
- Computational secrecy currently relies on unproven assumptions.
- Computational secrecy means that it is trivial for an attacker to always learn the entire message.
- Computational secrecy only ensures secrecy against attackers running in some bounded amount of time.
- Computational secrecy allows an attacker to learn information about the message with small probability.
Q4) Let G be a function mapping n-bit inputs to 2n-bit outputs. Which of the following is true of the pseudo one-time pad encryption scheme based on G? (Check all that apply.)
- The scheme is perfectly secret.
- The scheme is computationally secret if G is a pseudorandom generator.
- The key space of the scheme is at least as large as the message space. The scheme can be used securely to encrypt multiple messages using the same key.
Q5) Which of the following attackers can be used to demonstrate that the shift cipher for 3-character messages does not satisfy perfect indistinguishability?
- Output m0 = 'aaa' and m1 = 'abc'. Given challenge ciphertext C, output 0 if the first character of C is 'a'.
- Output m0 = 'aaa' and m1 = 'bbb'. Given challenge ciphertext C, output 0 if the first character of C is 'a'.
- Output m0 = 'aaa' and m1 = 'abc'. Given challenge ciphertext C, output 1 if the three characters of C are all different.
- Output m0 = 'abc' and m1 = 'bcd'. Given challenge ciphertext C, output 1 if the three characters of C are all different.
Q6) Which of the following is a negligible function? (Check all that apply.)
- f(n) = 1/n.
- f(n) = 1/2^n
- f(n) = 1/2
- f(n) = n/2^n
Q7) Define the following function G taking n-bit inputs and producing (n+1)-bit outputs: G(x)=x∥0, where ∥ denotes concatenation. Which of the following attackers shows that this G is not a pseudorandom function?
- On input an (n+1)-bit string y, output 0 if the last bit of y is 0.
- On input an (n+1)-bit string y, output 1 if the first bit of y is 0.
- On input an (n+1)-bit string y, output 0 if the first bit of y is 0.
- On input an (n+1)-bit string y, output 0 if the first bit of y is equal to the last bit of y.
Q8) Say G is a pseudorandom generator taking n-bit inputs and producing 2n-bit outputs. Which of the following are necessarily true? (Check all that apply. The symbol '|' is used here for string concatenation.)
- G(r) | G(r+1) is computationally indistinguishable from a uniform, 4n-bit string if r is a uniform n-bit string.
- G(r) is computationally indistinguishable from a uniform, 2n-bit string if r is a uniform n-bit string.
- r | G(r) is computationally indistinguishable from a uniform, 3n-bit string if r is a uniform n-bit string.
- G(0 | r) is computationally indistinguishable from a uniform, 2n-bit string if r is a uniform (n-1)-bit string.
Q9) Which of the following is a setting in which a pseudorandom generator could be applied?
- You have a 1 MB file that you would like to compress.
- You have a 1 MB file and you would like to make sure that it has not been tampered with.
- You have a way to generate random bits at the rate of 100 bits/second, but you need 1,000,000 random bits to run a statistical simulation.
Q10) Consider a pseudo one-time pad encryption scheme Π constructed using some function G. Which of the following did our proof of security for the pseudo one-time pad show?
- Π is always perfectly secret, for any G.
- Π is always computationally secret, for any G.
- If G is a pseudorandom generator, then Π is perfectly secret.
- If G is a pseudorandom generator, then Π is computationally secret.
--------------------------------------------------------------------------------------------------------------------------------------------------------------
Cryptography
-----------------------------------------------------------------------------------------------------------------------------------------------------------
0 Comments