Introduction Solutions

Chapter 1 Introduction – Solutions 1.1 Decrypt the ciphertext provided at the end of the section on mono- alphabetic substitution.

Solution:The ciphertext decrypts to the following plaintext (we have

added punctuation and capitalization):

Cryptographic systems are extremely difficult to build. Never- theless, for some reason many non-experts insist on designing new encryption schemes that seem to them to be more se- cure than any other scheme on earth. The unfortunate truth, however, is that such schemes are usually trivial to break.We would expect students to describe the methodology they used to derive the solution.

1.2 Provide a formal definition of theGen,Enc, andDecalgorithms for the mono-alphabetic substitution cipher.

Solution:For this exercise, we identify numbers and letters in the

natural way. That is,a= 0,b= 1 and so on. We start with the

mono-alphabetic substitution cipher:

•Gen: Choose a random permutationπof{0, . . . ,25}and let the

key be this permutation. (A random permutation on{0, . . . ,25}

can be chosen as follows: fori= 0 to 25, setπ(i) equal to a random

number from{0, . . . ,25}that has not been chosen so far.)

•Enc: Given a plaintextm=m

1, . . . , mℓ(wherem i∈ {0, . . . ,25}) and a keyπ, setc

i:=π(m i) and outputc1, . . . , cn.

•Dec: Given a ciphertextc=c

1, . . . , cnand keyπ, setmi:=π

−1 (ci) whereπ −1 is the inverse ofπand outputm1, . . . , mn.

1.3 Provide a formal definition of theGen,Enc, andDecalgorithms for

the Vigen`ere cipher. (Note: there are several plausible choices forGen;

choose one.)

Solution:As in the previous exercise, we identify numbers and letters

in the natural way. That is,a= 0,b= 1 and so on.•Gen: Choose a random period: this can be chosen uniformly in a fixed set of some size, or it can be chosen according to some valid 3

K16478_SM_Cover.indd 905/04/16 3:43 pm

(Chapman and Hall Introduction to Modern Cryptography, 2e Williams Bldg Katz, Yehuda Lindell) (Solution Manual all Chapters) 1 / 4

4Introduction to Modern Cryptography – 2nd Edition Solutions Manual probability distribution over the integers (e.g., assign the length

• +iwith probability 2

−i

• Denote the chosen period byt. For

i= 0, . . . , t−1 choose uniformk iin{0, . . . ,25}. Output the key k=k 0, . . . , kt−1.

•Enc: Given a plaintextp=p

0, . . . , pnand a keyk=k0, . . . , kt−1, setc

i:= [p i+k

[imodt] mod 26]. Outputc0, . . . , cn.

•Dec: Given a ciphertextc=c

0, . . . , cnand a keyk=k0, . . . , kt−1, setp

i:= [c i−k

[imodt] mod 26]. Outputp0, . . . , pn.

1.4 Implement the attacks described in this chapter for the shift cipher and the Vigen´ere cipher.No solution given.

1.5 Show that the shift, substitution, and Vigen`ere ciphers are all trivial to break using a chosen-plaintext attack. How much known plaintext is needed to completely recover the key for each of the ciphers?Solution:For the shift cipher: ask for the encryption of any plaintext characterpand letcbe the ciphertext character returned; the key is

simplyk:= [c−pmod 26]. The encryption of only a single plaintext

character thus suffices to recover the key. For the substitution cipher, given a plaintext characterp iand corresponding ciphertext characterci, we can conclude thatπ(p

• =c i(whereπis the permutation determining

the key as in the solution of Exercise 1.2). In order to fully determine the key, it therefore suffices to ask for an encryption of a plaintext containing 25 distinct letters of the alphabet. (Sinceπis a permutation, knowing the value ofπon 25 inputs fully determines the value ofπon the last remaining input.) For the Vigen`ere cipher, if the periodtis known then the encryption of a plaintext of lengtht(consecutive) suffices to recover the entire key. If only an upper boundt maxontis known, thentmust be learned as well; this can be done using a single plaintext of lengthO(t).

(Note: it is actually a bit challenging to determine the minimal length

of a plaintext that suffices to determinet. We only expect students to understand that a plaintext of lengthO(t max) suffices.) 1.6 Assume an attacker knows that a user’s password is eitherabcdorbedg.Say the user encrypts his password using the shift cipher, and the at- tacker sees the resulting ciphertext. Show how the attacker can deter- mine the user’s password, or explain why this is not possible.

Solution:In the shift cipher, the relative shift between characters is

preserved. Thus an encryption ofabcdwill always be a ciphertext con- taining 4 consecutive characters (e.g.,lmno), whereasbedgwill not.

1.7 Repeat the previous exercise for the Vigen`ere cipher using period 2, using period 3, and using period 4.

K16478_SM_Cover.indd 1005/04/16 3:43 pm 2 / 4

Introduction5

Solution:For the sake of clarity, we will mostly omit the fact that

operations are modulo 26 in this solution.When the period is 2, it is impossible to determine which password was encrypted. This is due to the fact that the shifts used in the first and third (resp., second and fourth) positions are the same, and the differ- ence between the first and third (resp., second and fourth) characters in the first password is the same as the difference between the first and third (resp., second and fourth) characters in the second password.When the period is 3, it is possible to tell which password was encrypted because the shifts used in the first and fourth positions are the same, but the difference between the first and fourth characters of the first plaintext is not the same as the difference between the first and fourth characters of the second plaintext.When the period is 4, it is impossible to tell which password was en- crypted, because using a 4-character key to encrypt a 4-character plain- text is perfectly secret (by analogy to the one-time pad).

1.8 The shift, substitution, and Vigen`ere 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.

Solution:We describe the solution for the Vigen`ere cipher, which is

the most complex case.(a) Key generation chooses a periodt(say, uniform in{1, . . . , t max}for some specifiedt max) and then, fori= 0, . . . , t−1, chooses uniform k i∈ {1, . . . ,127}. The encryption of a plaintextm=m1, . . . , mℓ isc=c 1, . . . , cℓ, wherec i= [m i+k [imodt] mod 128]. Decryption is done in the natural way.(b) The exact same attacks described in the text work, though one must be careful now to letp ibe the frequency of theith ASCII character (so, e.g., the frequency of ‘A’ is different from the fre- quency of ‘a,’ and frequencies of the space character and punctua- tion is also taken into account).

K16478_SM_Cover.indd 1105/04/16 3:43 pm 3 / 4

Chapter 2 PerfectlySecret Encryption – Solutions 2.1 Prove that, by redefining the key space, we may assume that the key- generation algorithmGenchooses a key uniformly at random from the key space, without changing Pr[C=c|M=m] for anym, c.

Solution:IfGenis a randomized algorithm, we may view it as a deter-

ministic algorithm that takes as input a random tapeωof some length; the distribution on the output ofGenis, by definition, the distribution obtained by choosing uniformωand then runningGen(ω). So, rather than letting the key be the output ofGen, we can simply let the key be ωitself (and redefine the key space accordingly).Formally, given a scheme (Gen,Enc,Dec) in whichGenis randomized, construct a new scheme (Enc ′ ,Dec ′

• where the key is a uniformω. Then

defineEnc ′ ω

(m) to computek:=Gen(ω) followed byEnck(m), and define

decryption analogously.

2.2 Prove that, by redefining the key space, we may assume thatEncis deterministic without changing Pr[C=c|M=m] for anym, c.

Solution:As in the previous exercise, ifEncis a randomized algorithm

then we may view it as being a deterministic algorithm that also takes a random tapeωas additional input. The distribution on the output ofEnc k(m) is then, by definition, the distribution obtained by choosing uniformωand then computingEnc k(m;ω). We then define key genera- tion to includeωas well ask(and redefine the key space accordingly).Formally, given a scheme (Gen,Enc,Dec) in whichEncis randomized, construct a new scheme (Gen ′ ,Enc ′ ,Dec ′ =Dec) as follows.Gen ′ com- putesk←Genand also chooses uniformω; the key is (k, ω ). Then defineEnc ′ (k,ω) (m) to beEnc k(m;ω).

2.3 Prove or refute: An encryption scheme with message spaceMis per-

fectly secret if and only if for every probability distribution overMand everyc 0, c1∈ Cwe have Pr[C=c0] = Pr[C=c1].

Solution:This is not true. Consider modifying the one-time pad so

encryption appends a bit that is 0 with probability 1/4 and 1 with prob- ability 3/4. This scheme will still be perfectly secret, but ciphertexts ending in 1 are more likely than ciphertexts ending in 0.7

K16478_SM_Cover.indd 1305/04/16 3:43 pm

• / 4