Cryptography

Cryptography text

Question 1. (15 points) The problem with the substitution cipher that it encrypts the same pla-

intext character to the same ciphertext character every time, so someone come up with a modi�cation.

De�ne the encryption scheme Π as follows (we identify the letters of the alphabet and the numbers in the common way, that is a = 0, b = 1,...,z = 25.

• Key generation: Choose a random permutation of {0, 1, ..., 25}, that is π, and a k ∈{0, 1, ..., 25}.

• Encryption: Given m = (m1, ...,mn), compute ci = π(mi) +i·k mod 26. Output c = (c1, ...,cn) Show how to decrypt! Show that any plaintext character is encrypted into multiple ciphertext cha-

racters. Show that the encryption scheme is still easily breakable if English text is used as a message.

What is the largest message space you can �nd for which the encryption Π provides perfect secrecy?

Question 2. (8 points)

1. Present an example of a negligible function f such that 2nf(n) is (i) negligible; (ii) non-negligible!

2. Prove that if f and g are both negligible functions then fg is also negligible.

Question 3. (10 points) The best algorithm known today for �nding the prime factors of an n-bit

number runs in the time 2c·n 1/3(log n)2/3. Assuming 8Ghz computers and c = 1 (and that the units of

the given expression are clock cycles), estimate the size of numbers that cannot be factored for the

next 100 years.

Question 4. (10 points) Say we require only that an encryption scheme (Gen,Enc,Dec) over a message space M satisfy the following: for all m ∈ M, the probability that Deck(Enck(m)) = m is at least 2−t. (This probability is take over choice of k as well as any randomness that may be used during encryption or decryption.) Show that perfect secrecy can be achieved with |K| < |M|.

Question 5. (10 points)

1. Let G be a pseudorandom generator with expansion factor G(s) = ` > |s| + 1. Let G′ be the same as G, but delete the last bit. Decide if G′ is a PRG. Prove your answer!

2. Let G and G′ be two di�erent pseudorandom generators (there output is di�erent for at least one input). De�ne the function G∗(s) = G(s)‖G′(s). Is G∗ always a pseudorandom generator (for any choice of G and G′)?

Question 6. (10 points) Let Π1 = (Gen 1,Enc1,Dec1) and Π2 = (Gen

2,Enc2,Dec2) be two encryption scheme for which it is known that at least one is CPA-secure. The problem is that you don't

know which one is CPA-secure and which one may not be. Decide which of the following encryption

scheme is guaranteed to be secure against CPA adversary. Prove your answer!

Encryption algorithm 1

1. Gen(1n) computes k1 ← Gen1(1n) and k2 ← Gen2(1n) and outputs (k1,k2).

2. Upon input k = (k1,k2) and m, algorithm Enc chooses a random r ← {0, 1}|m| and outputs c =

⟨ Enc1k1 (m⊕r),Enc

2 k2

(r) ⟩

Encryption algorithm 2

1. Gen(1n) computes k1 ← Gen1(1n) and k2 ← Gen2(1n) and outputs (k1,k2).

2. Upon input k = (k1,k2) and m, algorithm Enc divide m into m1,, and m2 such that m = m1||m2 (‖ is the concatenation), then outputs c =

⟨ Enc1k1 (m1),Enc

2 k2

(m2) ⟩

Question 7. (7 points) Cipher Feedback (CFB) mode is another way to encrypt arbitrary long

messages using a block cipher. Let F be a pseudorandom-permutation, with key k. Given a message m = m1, ...,ml, where each mi is a block of length n, choose IV ∈ {0, 1}n with uniform distribution, and compute ci = Fk(ci−1) ⊕mi for i = 1, ..., l (de�ne c0 = IV ). Output (IV,c = c1, ...,cl).

Show how to decrypt! Decide if the encryption, or the decryption are parallelizable. Show that

CFB is not safe against CCA attack.