n/a
Assignment-4 Due Date: April 7th, upload your typeset solutions to BB 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: (Explain why!) A. Compress then encrypt B. Encrypt then compress C. Either order does not make a difference D. Depends on the Encryption and Compression algorithms used. 2. A bank uses (K,E,D), a one-time pad symmetric encryption scheme with key space K={0,1}ℓ for their cryptographic needs. Observe that the encryption and decryption keys are identical as it is a symmetric OTP crypto system. The bank wishes to split the decryption key k ∈ {0,1}ℓ into two pieces p1 and p2 so that both are needed for decryption. The idea is that piece p1 can be given to one executive and p2 to another so that both must contribute their pieces for decryption to proceed. Following this idea, the bank generates a random k1 ∈ {0,1}ℓ and sets k1′← k ⊕ k1. Note that k1 ⊕ k1′ = k. The bank can give k1 to one executive and k1′ to another executive. Both must be present for decryption to proceed since, by itself, each piece contains no information about the secret key k (note that each piece is a one-time pad encryption of k, interesting!). Now, suppose the bank wants to split k into three pieces p1, p2, and p3 so that any two of the pieces enable decryption using k. This ensures that even if one executive is out sick, decryption can still succeed. To do so the bank generates two random pairs (k1,k1′) and (k2,k2′) as in the previous paragraph so that k1⊕k1′=k2⊕k2′=k. How should the bank assign pieces so that any two pieces enable decryption using k, but no single piece can decrypt? 3. Let M = C = K = {0, 1, 2,…, 255}. Consider the following cipher defined over (K,M,C) as E(k,m) = m + k % 256; D(k,c) = c − k % 256. Here % stands for the modulus operator. Does this cipher have perfect secrecy? 4. 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 hexadecimal). What would be the one time pad encryption of the message "attack at dusk" under the same OTP key? 5. The movie industry wants to protect their digital content distributed on DVDs. If you are interested, read about how Blu-ray disks are protected using a method called AACS. Suppose there are at most a total of n DVD players in the world (for some large n e.g. n=264). We view these n players as the leaves of a binary tree of height log2n (Logarithm of n to the base 2). Each node in this binary tree contains a key ki. 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 ∈ [0, n−1]. Consider the set of nodes Si along the path from the root to leaf number i in the binary tree. The manufacturer of the DVD player embeds in player number i the keys associated with the nodes in the set Si. A DVD movie m is encrypted as E(kroot,k)∥E(k,m) where k is a random key http://en.wikipedia.org/wiki/Advanced_Access_Content_System called the content-key and kroot is the key associated with the root of the tree and ∥ represents concatentation. Since all DVD players have the key kroot all players can decrypt the movie m. We refer to E(kroot,k) as the header and E(k,m) as the body. Notice that the DVD header may contain multiple ciphertexts where each ciphertext is the encryption of the content-key k under some key ki in the binary tree. Suppose the keys embedded in DVD player number r 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 log2n keys) so that all DVD players, except for DVD player number r, can decrypt the movie. In effect, the movie industry disables player number r without affecting other players. As shown below, consider a tree with n=16 leaves. Suppose the leaf node labeled 25 corresponds to an exposed DVD player key. List the set of keys under which to encrypt the content key k so that every player other than player 25 can decrypt the DVD. Obviously, list the least number of keys that are needed. 6. From your readings, you know that a popular cipher in history was the monoalphabetic substitution cipher, where each letter in the alphabet is mapped to a substitution letter. Example: a goes to h, b goes to p, c goes to e and so on, etc. Clearly it is obvious to you by now that the monoalphabetic substitution cipher does not offer perfect secrecy. In this problem, you will prove this fact – You will show that the monoalphabetic substitution cipher is an imperfect cipher (one that does not offer perfect secrecy). Here is a hint: Use the Shannon’s Keyspace theorem that says that for any cipher that offers perfect secrecy, the length of the keys must be at least as long as the length of the message. A different way to state the same theorem is that the number of keys in the key space is at least as large as the number of messages in the message space, i.e., |K| ≥ |M|. Question: Given this premise and the fact the English language has a 26-letter alphabet, what length message is needed to show that the Shannon theorem is violated, i.e. |K| < |m| for a monoalphabetic cipher and why? 7. provide a shorter proof for the above problem that the monoalphabetic substitution cipher is imperfect. your proof will essentially be done through a practical demonstration, a proof by existence – show that there exists a two-letter ciphertext that will not decrypt to the plaintext tx for any key. incidentally, why is this demonstration a proof of the fact that the monoalphabetic substitution cipher is imperfect? 8. another secret sharing question one useful property of xor is that we can use it to share a secret. we saw one such example in the “bank secret sharing problem” in problem-2 above. you can take a secret and divide it among a bunch of people in such a way that no individual learns anything about the secret, but when they get together and combine their shares, they can determine the secret. here is the problem set up: alice has a secret x = x0 x1 x2…xn-1 that she guards with her life. she would like to give this secret to her friends bob and cindy for safe keeping. of course, she does not want them to learn her secret x (because it is after all her secret that she guards with her life!). so, instead of giving them the plaintext x she does the following: 1. first, she picks a random n-bit string, key k = k0k1k2…kn-1 2. then, she performs the following operation: s = k ⊕ x, si = ki ⊕xi , where s is obtained by the bit-wise exclusive-or of k and x for 0 ≤ i ≤ n-1. alice now gives key k to bob and s to cindy with the stern understanding that bob and cindy never collude behind her back to determine x. first, argue that neither bob nor cindy (individually) have any information about x. then, show how bob and cindy can come together and collude behind alice’s back to determine alice’s secret x. naturally, at this point, alice is worried that bob and cindy might collude behind her back. so, she wants to share her secret x among 4 people. how many key bits does she need to share a 100-bit long secret x among 4 people and show me how your scheme works clearly proving the security aspects of your scheme. 9. give me your thoughts on this assignment. |m|="" for="" a="" monoalphabetic="" cipher="" and="" why?="" 7.="" provide="" a="" shorter="" proof="" for="" the="" above="" problem="" that="" the="" monoalphabetic="" substitution="" cipher="" is="" imperfect.="" your="" proof="" will="" essentially="" be="" done="" through="" a="" practical="" demonstration,="" a="" proof="" by="" existence="" –="" show="" that="" there="" exists="" a="" two-letter="" ciphertext="" that="" will="" not="" decrypt="" to="" the="" plaintext="" tx="" for="" any="" key.="" incidentally,="" why="" is="" this="" demonstration="" a="" proof="" of="" the="" fact="" that="" the="" monoalphabetic="" substitution="" cipher="" is="" imperfect?="" 8.="" another="" secret="" sharing="" question="" one="" useful="" property="" of="" xor="" is="" that="" we="" can="" use="" it="" to="" share="" a="" secret.="" we="" saw="" one="" such="" example="" in="" the="" “bank="" secret="" sharing="" problem”="" in="" problem-2="" above.="" you="" can="" take="" a="" secret="" and="" divide="" it="" among="" a="" bunch="" of="" people="" in="" such="" a="" way="" that="" no="" individual="" learns="" anything="" about="" the="" secret,="" but="" when="" they="" get="" together="" and="" combine="" their="" shares,="" they="" can="" determine="" the="" secret.="" here="" is="" the="" problem="" set="" up:="" alice="" has="" a="" secret="" x="x0" x1="" x2…xn-1="" that="" she="" guards="" with="" her="" life.="" she="" would="" like="" to="" give="" this="" secret="" to="" her="" friends="" bob="" and="" cindy="" for="" safe="" keeping.="" of="" course,="" she="" does="" not="" want="" them="" to="" learn="" her="" secret="" x="" (because="" it="" is="" after="" all="" her="" secret="" that="" she="" guards="" with="" her="" life!).="" so,="" instead="" of="" giving="" them="" the="" plaintext="" x="" she="" does="" the="" following:="" 1.="" first,="" she="" picks="" a="" random="" n-bit="" string,="" key="" k="k0k1k2…kn-1" 2.="" then,="" she="" performs="" the="" following="" operation:="" s="k" ⊕="" x,="" si="ki" ⊕xi="" ,="" where="" s="" is="" obtained="" by="" the="" bit-wise="" exclusive-or="" of="" k="" and="" x="" for="" 0="" ≤="" i="" ≤="" n-1.="" alice="" now="" gives="" key="" k="" to="" bob="" and="" s="" to="" cindy="" with="" the="" stern="" understanding="" that="" bob="" and="" cindy="" never="" collude="" behind="" her="" back="" to="" determine="" x.="" first,="" argue="" that="" neither="" bob="" nor="" cindy="" (individually)="" have="" any="" information="" about="" x.="" then,="" show="" how="" bob="" and="" cindy="" can="" come="" together="" and="" collude="" behind="" alice’s="" back="" to="" determine="" alice’s="" secret="" x.="" naturally,="" at="" this="" point,="" alice="" is="" worried="" that="" bob="" and="" cindy="" might="" collude="" behind="" her="" back.="" so,="" she="" wants="" to="" share="" her="" secret="" x="" among="" 4="" people.="" how="" many="" key="" bits="" does="" she="" need="" to="" share="" a="" 100-bit="" long="" secret="" x="" among="" 4="" people="" and="" show="" me="" how="" your="" scheme="" works="" clearly="" proving="" the="" security="" aspects="" of="" your="" scheme.="" 9.="" give="" me="" your="" thoughts="" on="" this="">