Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen

frequencies. Compare your results with Table 2.1. (See Solution 2.16.)

2.10 Solutions

      1 2.1Encode HQFRGHEncode ZIXJYZ

      2 2.2 Since , the number of rows is two. Thus, the message is encoded as follows:ECDECDNOENOE

      3 2.3 We use a brute‐force attack, with results shown in the following table. The value corresponds to a Caesar shift of magnitude .kJRYYQBAR1IQXXPAZQ2HPWWOZYP3GOVVNYXO4FNUUMXWN5EMTTLWVM6DLSSKVUL7CKRRJUTK8BJQQITSJ9AIPPHSRI10ZHOOGRQH11YGNNFQPG12XFMMEPOF13WELLDONE14VDKKCNMD15UCJJBMLC16TBIIALKB17SAHHZKJA18RZGGYJIZ19QYFFXIHY20PXEEWHGX21OWDDVGFW22NVCCUFEV23MUBBTEDU24LTAASDCT25KSZZRCBS26JRYYQBARAfter investigating the entries in the table, the only intelligible message exists for . The plain text message is “well done.”

      4 2.4 No. For example, if a message is enciphered with a key of 4, and the resulting cipher text is enciphered again using a key of 8, the final cipher text will be the same as if the message was enciphered with a key of 12.

      5 2.5 Since the key is 7, we know that we need 7 rows. For the number of columns, count up the total number of characters and check if it is divisible by 7. Since it is not, we must add 4 Zs to the end. Therefore, we have 91 characters, and . Thus, we need 13 columns. Writing the message out in columns, we get the following matrix:TMHNRAFIRAETREUAIOVADHCFOOLSTOWEREEKAWYLEIUHLAAHEMNZMONSOLNFADOOZEFGHTEDTDTUFZOTEERDWESHSTZAfter unwrapping, we obtain the encrypted message:TMHNR AFIRA ETREU AIOVA DHCFO OLSTO WEREE KAWYL EIUHLAAHEM NZMON SOINF ADOOZ EFGHT EDTDT UFZOT EERDW ESHST Z

      6 2.6 Transposition ciphering will produce cipher text with roughly the same frequency distribution as the English language. Substitution ciphering, with a polyalphabetic cipher for example, will yield frequencies that can be much different, since the plain text letters are actually changed instead of reordered. Therefore, if the distribution “flattened,” we can assume a substitution cipher was used. If it does not, we can assume that a transposition cipher was used.

      7 2.7 The computations for the first few letters are shown.Keyword:ODYSSEYODYPlain text:TellmeomusCipher text:HHJDEIMAXQContinuing the process, the corresponding cipher text isHHJDE IMAXQ WQJRV DRAFK CBHMM KLCFR UZGXP OYBDD IBTDPSFHUW GCSXX CFKCZ SHQOF IWVXF SIYEG YQHRU FGJRF RW

      8 2.8 We obtain the plain text by subtracting the cipher text from the keyword:Keyword:CIPHERCIPHCipher text:VPXZGZRTYMPlain text:thiscipherWorking the rest of it out, we obtain the message.“this cipher is easy to break if one knows the keyword”

      9 2.9 The message has perfect security, because the message could be any of the 26 letters of the alphabet. That is, knowledge of the cipher text does not give any information regarding the message. Alternatively, one can think intuitively that “the key is as long as the message.”

      10 2.10 Substitution enciphering, because each letter of the plain text message is obtained by substituting different cipher text characters. Transposition enciphering is the reordering of the same letters, whereas substitution enciphering doesn't necessarily use the same characters.

      11 2.11 Three rotors with 26 possible initial settings each = initial settings = 17 576. Since the three rotors can be interchanged, there are six ways to order them. Therefore, we have a total of different initial settings.

      12 2.12 The corresponding cipher text is JCJDUKJ.The initial settings are the following: = (0 15 6 10 14 8 19 17 22 18 11) (1 2 9 13 21 25) (3 4 23 5 24 7 12 16 20) = (0 7 9 4 6 18 23 25 8) (1 17 19) (2 20 10) (3 12) (5 11 13 21) (14 22 15 16 24) = (0 2 4 7 16 17 19 5) (1 6 3 8 21 24 11 13 9 10 25 12 14 15) (18 23 20 22) = (0 4)(1 7)(2 9)(3 16)(5 20)(6 8)(10 19)(11 17)(12 25)(13 18)(14 24)(15 22)(21 23) = (11 18 22 17 19 8 14 10 6 15 0) (25 21 13 9 2 1) (20 16 12 7 24 5 23 4 3) = (8 25 23 18 6 4 9 7 0) (19 17 1) (10 20 2) (12 3) (21 13 11 5) (24 16 15 22 14) = (5 19 17 16 7 4 2 0) (15 14 12 25 10 9 13 11 24 21 8 3 6 1) (22 20 23 18)Also, the initial settings were defined as follows:, , Using the given information, the cipher text was obtained as follows:1st letter: (m)Reaching the reflector, we get Now following the signal back through the rotors, we obtainTherefore, the first cipher text character is J.Now, we must update the rotor settings: .For the remaining characters, proceed through the same process. Remember, when changes from 25 back to 0, update to 8 (this occurs after the fourth cipher text character is computed).

      13 2.13 After writing the cipher text on two strips of paper, we obtain the following table:Displacement# of coincidences1420334353667184Here we note that the maximum number of coincidences occurs for a displacement of 6. Therefore, the period is either 3 or 6, because the displacement producing the largest number of coincidences is a scalar multiple of the period.

      14 2.14 To complete the problem, we will try a period of 3 first. If it doesn't succeed, we will try the second choice of 6. With our results, we will find the most common letter and assume it deciphers to “e.” If there are ties for the most frequent character, we will investigate each case individually to determine the most probable choice.Starting with the first letter of the keyword, we create a table of cipher text frequencies:The first, fourth, seventh, letters of cipher text areLKXRSXOZBXZDBUYFGROSWDDOOICSDXNSVESKOX.From this, we computeABCDEFGHIJKLM0214111010210NOPQRSTUVWXYZ1500250111502Here we note that the most frequent cipher text letters are O, S, and X. Now, we have to consider each letter to determine which is most likely the key letter. If O deciphers to “e”(yielding a key letter of “K”), then S i, and X n. Looking at Table 2.1, the number of occurrences of “i and “n” in the cipher text are reasonable. Alternatively, if S deciphers to “e” (yielding a key letter of “O”), then O “a” and X “j”. However, 5 occurrences out of 38 letters is far too high for j (the frequency of j is 0.002%). Finally, if X deciphers to “e,” (yielding a key letter of “T”), then O “v” and S “y.” Again, 5 occurrences for each “v” and “y” in 38 letters are far too high to be correct. Therefore, “K” is the most probable key letter.We use the same reasoning for the next two key letters. For the second, fifth, eighth, letters, we compute:ABCDEFGHIJKLM1010323282213NOPQRSTUVWXYZ0100200110410Here we have an overwhelming choice for “e,” namely “I.” Thus, if I deciphers to “e,” we have a key letter of “E.”Similarly, for the third, sixth, nineth, letters, we computeABCDEFGHIJKLM3150024012022NOPQRSTUVWXYZ0051421000011This gives us two likely choices for “e,” although two others are very close. If “C' deciphers to “e,” we have a key letter of “Y.” If this is the case, them G “I,” R “t,” and P “r,” all of which have a reasonable number of occurrences. If, on the other hand, P deciphers to “e,” then the key letter is “L.” This would mean that C “r,” G “v,” and R “g.” However, the number of occurrences of both “v” and “g” are too high to be realistic. Therefore, we arrive at a key letter of “Y,” producing a keyword of “key.”To make sure that 3 is the period, one can use the newly acquired keyword to decipher the message. For long messages, it is nearly impossible that two separate messages would appear out of the same piece of cipher text. Thus, if the first key works, we are done. If not, then the period is likely 6 instead. This problem illustrates the ambiguities one can run into when attempting to break the Vigenère cipher, and serves as a reminder to use the methods outlined here with diligence and care.

      15 2.15 Repeat the exact same process as in Problem 2.14, inputting the letters YDDMYU with the same initial settings as before. The resulting output is the message “attack.”

      16 2.16 If the book contained typical English text, then the frequencies should be very similar to the table.

Chapter 3 RSA, Key Searches, TLS, and Encrypting Email

      Goals, Discussion This chapter is important and does not require too much mathematical background. We avoid making essential use of number theory in the text, although it can be used to shorten the calculations. We discuss one of the main public key algorithms, namely RSA, as well as some of its applications to e‐Commerce with Transport Layer Security (TLS) and to the encryption of email.

Public key and symmetric cryptography