The ciphertext below was encrypted using a substitution cipher. Decrypt the ci-

phertext without knowledge of the key.

 lrvmnir bpr sumvbwvr jx bpr lmiwv yjeryrkbi jx qmbm wi bpr xjvni mkd ymibrut jx irhx wi bpr riirkvr jx ymbinlmtmipw utn qmumbr dj w ipmhh but bj rhnvwdmbr bpr yjeryrkbi jx bpr qmbm mvvjudwko bj yt wkbrusurbmbwjk lmird jk xjubt trmui jx ibndt 

 wb wi kjb mk rmit bmiq bj rashmwk rmvp yjeryrkb mkd wbi iwokwxwvmkvr mkd ijyr ynib urymwk nkrashmwkrd bj ower m vjyshrbr rashmkmbwjk jkr cjnhd pmer bj lr fnmhwxwrd mkd wkiswurd bj invp mk rabrkb bpmb pr vjnhd urmvp bpr ibmbr jx rkhwopbrkrd ywkd vmsmlhr jx urvjokwgwko ijnkdhrii ijnkd mkd ipmsrhrii ipmsr w dj kjb drry ytirhx bpr xwkmh mnbpjuwbt lnb yt rasruwrkvr cwbp qmbm pmi hrxb kj djnlb bpmb bpr xjhhjcwko wi bpr sujsru msshwvmbwjk mkd wkbrusurbmbwjk w jxxru yt bprjuwri wk bpr pjsr bpmb bpr riirkvr jx jqwkmcmk qmumbr cwhh urymwk wkbmvb 

Compute the relative frequency of all letters A...Z in the ciphertext. You may want to use a tool such as the open-source program CrypTool [50] for this task. However, a paper and pencil approach is also still doable.

Decrypt the ciphertext with the help of the relative letter frequency of the English language (see Table 1.1 in Sect. 1.2.2). Note that the text is relatively short and that the letter frequencies in it might not perfectly align with that of general English language from the table.

Who wrote the text?

1.2. We received the following ciphertext which was encoded with a shift cipher:xultpaajcxitltlxaarpjhtiwtgxktghidhipxciwtvgtpilpit

ghlxiwiwtxgqadds.

Perform an attack against the cipher based on a letter frequency count: How many letters do you have to identify through a frequency count to recover the key? What is the cleartext?

Who wrote this message?

1.4. We now consider the relation between passwords and key size. For this purpose we consider a cryptosystem where the user enters a key in the form of a password.

Assume a password consisting of 8 letters, where each letter is encoded by the ASCII scheme (7 bits per character, i.e., 128 possible characters). What is the size of the key space which can be constructed by such passwords?

What is the corresponding key length in bits?

Assume that most users use only the 26 lowercase letters from the alphabet in-

stead of the full 7 bits of the ASCII-encoding. What is the corresponding key

length in bits in this case?

At least how many characters are required for a password in order to generate a

key length of 128 bits in case of letters consisting of

a. 7-bit characters? b. 26 lowercase letters from the alphabet?

1.5. As we learned in this chapter, modular arithmetic is the basis of many cryp- tosystems. As a consequence, we will address this topic with several problems in this and upcoming chapters.

Lets start with an easy one: Compute the result without a calculator.

1529 mod 13

229 mod 13

23 mod 13

?113 mod 13

The results should be given in the range from 0,1,..., modulus-1. Briefly describe the relation between the different parts of the problem.

1.6. Compute without a calculator:

1. 1/5 mod 13 2. 1/5 mod 7 3. 32/5 mod 7

1.7. We consider the ring Z4. Construct a table which describes the addition of all elements in the ring with each other:

26 1 IntroductiontoCryptographyandDataSecurity

+0123 00123 1 1 2 2

3

Construct the multiplication table for Z4.

Construct the addition and multiplication tables for Z5.

Construct the addition and multiplication tables for Z6.

There are elements in Z4 and Z6 without a multiplicative inverse. Which ele-

ments are these? Why does a multiplicative inverse exist for all nonzero elements in Z5?

1.8. What is the multiplicative inverse of 5 in Z11, Z12, and Z13? You can do a trial-and-error search using a calculator or a PC.

With this simple problem we want now to stress the fact that the inverse of an integer in a given ring depends completely on the ring considered. That is, if the modulus changes, the inverse changes. Hence, it doesnt make sense to talk about an inverse of an element unless it is clear what the modulus is. This fact is crucial for the RSA cryptosystem, which is introduced in Chap. 7. The extended Euclidean algorithm, which can be used for computing inverses efficiently, is introduced in Sect. 6.3.

1.9. Compute x as far as possible without a calculator. Where appropriate, make use of a smart decomposition of the exponent as shown in the example in Sect. 1.4.1:

1.x=32 mod13 2.x=72 mod13 3. x=310 mod 13 4. x=7100 mod 13 5. 7x = 11 mod 13

The last problem is called a discrete logarithm and points to a hard problem which we discuss in Chap. 8. The security of many public-key schemes is based on the hardness of solving the discrete logarithm for large numbers, e.g., with more than 1000 bits.

1.10. Find all integers n between 0 ? n < m that are relatively prime to m for m =4,5,9,26. We denote the number of integers n which fulfill the condition by ?(m), e.g. ? (3) = 2. This function is called Eulers phi function. What is ? (m) for m =4,5,9,26?

1.11. This problem deals with the affine cipher with the key parameters a = 7, b =22.

Decrypt the text below:

 falszztysyjzyjkywjrztyjztyynaryjkyswarztyegyyj 

Who wrote the line?

Problems 27

1.12. Now, we want to extend the affine cipher from Sect. 1.4.4 such that we can encrypt and decrypt messages written with the full German alphabet. The German alphabet consists of the English one together with the three umlauts, A? , O? , U? , and the (even stranger) double s character . We use the following mapping from letters to integers:

A?0 B?1 C?2 D?3 G?6 H?7 I?8 J?9 M?12 N?13 O?14 P?15 S ? 18 T?19 U?20 V?21 Y ? 24 Z?25 A??26 O??27

E?4 F?5 K?10 L?11 Q?16 R?17 W?22 X?23 U??28 ?29

What are the encryption and decryption equations for the cipher?

How large is the key space of the affine cipher for this alphabet?

The following ciphertext was encrypted using the key (a = 17,b = 1). What is

the corresponding plaintext?

?a u w

From which village does the plaintext come?