CS 3333 Introduction to Cryptography

Assignment 1

Q1 [5] Consider the shift cipher, where we have the following distribution over the message space M:

Pr[M = a] = 0.7 and Pr[M = z] = 0:3: Here M is the random variable denoting the plaintext. What

is the probability that the ciphertext is c? What is the probability that message z was encrypted,

given that we observe the ciphertext c ?

Q2 [6+6] For each of the following encryption schemes, state whether the scheme is perfectly secret.

Justify your answer in each case.

(a) The message space is M = {0, . . . , 4}. Algorithm Gen chooses a uniform key from the key

space {0, . . . , 5}. Enck (m) returns [k + m mod 5], and Deck(c) returns [c – k mod 5].

(b) The message space is M = {m ∈ {0, 1}` : the last bit of m is 0}. Gen chooses a uniform key

from {0, 1}`−1 . Enck (m) returns ciphertext m ⊕ (kk0), and Deck (c) returns c ⊕ (kk0). Note: k

means concatenation.

Q3 [5+5+5 points]The shift, substitution, and Vigenère ciphers can also be defined over the

128-character ASCII alphabet (rather than the 26-character English alphabet).

(a) Provide a formal definition of each of these schemes in this case.

(b) Discuss how the attacks we have shown in this chapter can be modified to break each of these

modified schemes.

Q4 [8 points] Let |G(s)| = `(|s|) for some `. Consider the following experiment:

The PRG indistinguishability experiment PRGA,G(n):

(a) A uniform bit b ∈ {0, 1} is chosen. If b = 0 then choose a uniform r ∈ {0, 1}`(n) ; if b = 1 then

choose a uniform s ∈ {0, 1}n and set r := G(s).

(b) The adversary A is given r, and outputs a bit b’.

(c) The output of the experiment is defined to be 1 if b’ = b, and 0 otherwise.

Provide a definition of a pseudorandom generator based on this experiment, and prove that your

definition is equivalent to the definition discussed in class (See slide titled Pseudo Random Number

Generator: Definition ) (That is, show that G satisfies your definition if and only if it satisfies the

definition discussed in the class.)

1

Purchase answer to see full

attachment

Assignment 1

Q1 [5] Consider the shift cipher, where we have the following distribution over the message space M:

Pr[M = a] = 0.7 and Pr[M = z] = 0:3: Here M is the random variable denoting the plaintext. What

is the probability that the ciphertext is c? What is the probability that message z was encrypted,

given that we observe the ciphertext c ?

Q2 [6+6] For each of the following encryption schemes, state whether the scheme is perfectly secret.

Justify your answer in each case.

(a) The message space is M = {0, . . . , 4}. Algorithm Gen chooses a uniform key from the key

space {0, . . . , 5}. Enck (m) returns [k + m mod 5], and Deck(c) returns [c – k mod 5].

(b) The message space is M = {m ∈ {0, 1}` : the last bit of m is 0}. Gen chooses a uniform key

from {0, 1}`−1 . Enck (m) returns ciphertext m ⊕ (kk0), and Deck (c) returns c ⊕ (kk0). Note: k

means concatenation.

Q3 [5+5+5 points]The shift, substitution, and Vigenère ciphers can also be defined over the

128-character ASCII alphabet (rather than the 26-character English alphabet).

(a) Provide a formal definition of each of these schemes in this case.

(b) Discuss how the attacks we have shown in this chapter can be modified to break each of these

modified schemes.

Q4 [8 points] Let |G(s)| = `(|s|) for some `. Consider the following experiment:

The PRG indistinguishability experiment PRGA,G(n):

(a) A uniform bit b ∈ {0, 1} is chosen. If b = 0 then choose a uniform r ∈ {0, 1}`(n) ; if b = 1 then

choose a uniform s ∈ {0, 1}n and set r := G(s).

(b) The adversary A is given r, and outputs a bit b’.

(c) The output of the experiment is defined to be 1 if b’ = b, and 0 otherwise.

Provide a definition of a pseudorandom generator based on this experiment, and prove that your

definition is equivalent to the definition discussed in class (See slide titled Pseudo Random Number

Generator: Definition ) (That is, show that G satisfies your definition if and only if it satisfies the

definition discussed in the class.)

1

Purchase answer to see full

attachment

## Leave a comment