Week 1 – Problem Set >> Cryptography I
Week 1 – Problem Set LATEST SUBMISSION GRADE 80% 1. Question 1 Data compression is often used in data storage and transmission. Suppose you want to use data compression in conjunction with encryption. Does it make more sense to: 0 / 1 point The order does not matter — either one is fine. Encrypt then compress. The order does not matter — neither one will compress the data. Compress then encrypt. Incorrect Ciphertexts tend to look like random strings and therefore compressing after encryption will not compress the data. 2. Question 2 Let G:\{0,1\}^s \to \{0,1\}^nG:{0,1} s →{0,1} n be a secure PRG. Which of the following is a secure PRG (there is more than one correct answer): 1 / 1 point G'(k) = G(k) \bigoplus 1^nG ′ (k)=G(k)⨁1 n Correct a distinguisher for G’G ′ gives a distinguisher for GG. G'(k) = G(k \oplus 1^s)G ′ (k)=G(k⊕1 s ) Correct a distinguisher for G’G ′ gives a distinguisher for GG. G'(k) = G(k)[0,\ldots,n-2]G ′ (k)=G(k)[0,…,n−2] (i.e., G'(k)G ′ (k) drops the last bit of G(k)G(k)) Correct a distinguisher for G’G ′ gives a distinguisher for GG. G'(k) = G(k) \;\big\|\; 0G ′ (k)=G(k) ∥ ∥ ∥ 0 (here \big\| ∥ ∥ ∥ denotes concatenation) G'(k) = G(0)G ′ (k)=G(0) G'(k) = G(k) \;\big\|\; G(k)G ′ (k)=G(k) ∥ ∥ ∥ G(k) (here \big\| ∥ ∥ ∥ denotes concatenation) 3. Question 3 Let G:K \to \{0,1\}^nG:K→{0,1} n be a secure PRG. Define G'(k_1,k_2) = G(k_1) \;\bigwedge\; G(k_2)G ′ (k 1 ,k 2 )=G(k 1 )⋀G(k 2 ) where \bigwedge⋀ is the bit-wise AND function. Consider the following statistical test AA on \{0,1\}^n{0,1} n : A(x)A(x) outputs \text{LSB}(x)LSB(x), the least significant bit of xx. What is Adv_{\text{PRG}}[A,G’]Adv PRG [A,G ′ ] ? You may assume that \text{LSB}(G(k))LSB(G(k)) is 0 for exactly half the seeds kk in KK. Note: Please enter the advantage as a decimal between 0 and 1 with a leading 0. If the advantage is 3/4, you should enter it as 0.75 1 / 1 point 0.25 Correct for a random string x we have Pr[A(x)=1]=1/2Pr[A(x)=1]=1/2 but for a pseudorandom string G'(k_1,k_2)G ′ (k 1 ,k 2 ) we have Pr_{k_1,k_2}[A(G'(k_1,k_2))=1]=1/4Pr k 1 ,k 2 [A(G ′ (k 1 ,k 2 ))=1]=1/4. 4. Question 4 Let (E,D)(E,D) be a (one-time) semantically secure cipher with key space K = \{0,1\}^\ellK={0,1} ℓ . A bank wishes to split a decryption key k \in \{0,1\}^\ellk∈{0,1} ℓ into two pieces p_1p 1 and p_2p 2 so that both are needed for decryption. The piece p_1p 1 can be given to one executive and p_2p 2 to another so that both must contribute their pieces for decryption to proceed. The bank generates random k_1k 1 in \{0,1\}^\ell{0,1} ℓ and sets k_1′ \gets k \oplus k_1k 1 ′ ←k⊕k 1 . Note that k_1 \oplus k_1′ = kk 1 ⊕k 1 ′ =k. The bank can give k_1k 1 to one executive and k_1’k 1 ′ to another. Both must be present for decryption to proceed since, by itself, each piece contains no information about the secret key kk (note that each piece is a one-time pad encryption of kk). Now, suppose the bank wants to split kk into three pieces p_1,p_2,p_3p 1 ,p 2 ,p 3 so that any two of the pieces enable decryption using kk. This ensures that even if one executive is out sick, decryption can still succeed. To do so the bank generates two random pairs (k_1,k_1′)(k 1 ,k 1 ′ ) and (k_2,k_2′)(k 2 ,k 2 ′ ) as in the previous paragraph so that k_1 \oplus k_1′ = k_2 \oplus k_2′ = kk 1 ⊕k 1 ′ =k 2 ⊕k 2 ′ =k. How should the bank assign pieces so that any two pieces enable decryption using kk, but no single piece can decrypt? 1 / 1 point p_1 = (k_1,k_2),\quad p_2 = (k_1′,k_2), \quad p_3 = (k_2′)p 1 =(k 1 ,k 2 ),p 2 =(k 1 ′ ,k 2 ),p 3 =(k 2 ′ ) p_1 = (k_1,k_2),\quad p_2 = (k_1′,k_2′), \quad p_3 = (k_2′)p 1 =(k 1 ,k 2 ),p 2 =(k 1 ′ ,k 2 ′ ),p 3 =(k 2 ′ ) p_1 = (k_1,k_2),\quad p_2 = (k_1′), \quad p_3 = (k_2′)p 1 =(k 1 ,k 2 ),p 2 =(k 1 ′ ),p 3 =(k 2 ′ ) p_1 = (k_1,k_2),\quad p_2 = (k_1,k_2), \quad p_3 = (k_2′)p 1 =(k 1 ,k 2 ),p 2 =(k 1 ,k 2 ),p 3 =(k 2 ′ ) p_1 = (k_1,k_2),\quad p_2 = (k_2,k_2′), \quad p_3 = (k_2′)p 1 =(k 1 ,k 2 ),p 2 =(k 2 ,k 2 ′ ),p 3 =(k 2 ′ ) Correct executives 1 and 2 can decrypt using k_1,k_1’k 1 ,k 1 ′ , executives 1 and 3 can decrypt using k_2,k_2’k 2 ,k 2 ′ , and executives 2 and 3 can decrypt using k_2,k_2’k 2 ,k 2 ′ . Moreover, a single executive has no information about $k$. 5. Question 5 Let M=C=K=\{0,1,2,\ldots,255\}M=C=K={0,1,2,…,255} and consider the following cipher defined over (K,M,C)(K,M,C): E(k,m) = m+k \pmod{256} \qquad;\qquad D(k,c) = c-k \pmod{256} \ .E(k,m)=m+k(mod256);D(k,c)=c−k(mod256) . Does this cipher have perfect secrecy? 1 / 1 point Yes. No, only the One Time Pad has perfect secrecy. No, there is a simple attack on this cipher. Correct as with the one-time pad, there is exactly one key mapping a given message m to a given ciphertext c. 6. Question 6 Let (E,D)(E,D) be a (one-time) semantically secure cipher where the message and ciphertext space is \{0,1\}^n{0,1} n . Which of the following encryption schemes are (one-time) semantically secure? 1 / 1 point E'(\ (k,k’),\ m) = E(k,m) \;\big\|\; E(k’,m) E ′ ( (k,k ′ ), m)=E(k,m) ∥ ∥ ∥ E(k ′ ,m) Correct an attack on E’E ′ gives an attack on EE. E'(k,m) = \text{reverse}(E(k,m))E ′ (k,m)=reverse(E(k,m)) Correct an attack on E’E ′ gives an attack on EE. E'(k,m) = E(k,m) \;\big\|\; k E ′ (k,m)=E(k,m) ∥ ∥ ∥ k E'(k,m) = E(k,m) \;\big\|\; \text{LSB}(m) E ′ (k,m)=E(k,m) ∥ ∥ ∥ LSB(m) E'(k,m) = 0 \;\big\|\; E(k,m)E ′ (k,m)=0 ∥ ∥ ∥ E(k,m) (i.e. prepend 0 to the ciphertext) Correct an attack on E’E ′ gives an attack on EE. E'(k,m) = E(0^n,m) E ′ (k,m)=E(0 n ,m) 7. Question 7 Suppose you are told that the one time pad encryption of the message “attack at dawn” is 6c73d5240a948c86981bc294814d (the plaintext letters are encoded as 8-bit ASCII and the given ciphertext is written in hex). What would be the one time pad encryption of the message “attack at dusk” under the same OTP key? 1 / 1 point 6c73d5240a948c86981bc2808548 Correct 8. Question 8 The movie industry wants to protect digital content distributed on DVD’s. We develop a variant of a method used to protect Blu-ray disks called AACS. Suppose there are at most a total of nn DVD players in the world (e.g. n = 2^{32}n=2 32 ). We view these nn players as the leaves of a binary tree of height \log_2{n}log 2 n. Each node in this binary tree contains an AES key k_ik i . These keys are kept secret from consumers and are fixed for all time. At manufacturing time each DVD player is assigned a serial number i \in [0, n − 1]i∈[0,n−1]. Consider the set of nodes S_iS i along the path from the root to leaf number ii in the binary tree. The manufacturer of the DVD player embeds in player number ii the keys associated with the nodes in the set S_iS i . A DVD movie mm is encrypted as E(k_{\text{root}},k) \big\| E(k,m)E(k root ,k) ∥ ∥ ∥ E(k,m) where kk is a random AES key called a content-key and k_{\text{root}}k root is the key associated with the root of the tree. Since all DVD players have the key k_{\text{root}}k root all players can decrypt the movie mm. We refer to E(k_{\text{root}},k)E(k root ,k) as the header and E(k,m)E(k,m) as the body. In what follows the DVD header may contain multiple ciphertexts where each ciphertext is the encryption of the content-key kk under some key k_ik i in the binary tree. Suppose the keys embedded in DVD player number rr are exposed by hackers and published on the Internet. In this problem we show that when the movie industry distributes a new DVD movie, they can encrypt the contents of the DVD using a slightly larger header (containing about \log_2 nlog 2 n keys) so that all DVD players, except for player number rr, can decrypt the movie. In effect, the movie industry disables player number rr without affecting other players. As shown below, consider a tree with n=16n=16 leaves. Suppose the leaf node labeled 25 corresponds to an exposed DVD player key. Check the set of keys below under which to encrypt the key kk so that every player other than player 25 can decrypt the DVD. Only four keys are needed. 1 / 1 point 11 Correct You cannot encrypt kk under key 5, but 11’s children must be able to decrypt kk. 29 1 Correct You cannot encrypt kk under the root, but 1’s children must be able to decrypt kk. 5 7 6 Correct You cannot encrypt kk under 2, but 6’s children must be able to decrypt kk. 26 Correct You cannot encrypt kk under any key on the path from the root to node 25. Therefore 26 can only decrypt if you encrypt kk under key k_{26}k 26 . 10 9. Question 9 Continuing with the previous question, if there are nn DVD players, what is the number of keys under which the content key kk must be encrypted if exactly one DVD player’s key needs to be revoked? 1 / 1 point \log_2{n}log 2 n n-1n−1 22 n/2n/2 \sqrt{n} n Correct That’s right. The key will need to be encrypted under one key for each node on the path from the root to the revoked leaf. There are \log_2{n}log 2 n nodes on the path. 10. Question 10 Continuing with question 8, suppose the leaf nodes labeled 16, 18, and 25 correspond to exposed DVD player keys. Check the smallest set of keys under which to encrypt the key k so that every player other than players 16,18,25 can decrypt the DVD. Only six keys are needed. 0 / 1 point 4 Correct Yes, this will let players 19-22 decrypt. 6 11 Correct Yes, this will let players 23,24 decrypt. 15 Correct Yes, this will let players 15 decrypt. 17 Correct Yes, this will let players 17 decrypt. 26 Correct Yes, this will let players 26 decrypt. 8 13 14 20 You didn’t select all the correct answers
*Please Wait 15 Seconds To Get The Pdf Loaded
