Information Security. Mark Stamp

is the key?If the plaintext is “tiller,″ what is the key?

      19 Suppose that the following is an excerpt from the decryption codebook for a classic codebook cipher:123once199or202maybe221twice233time332upon451aDecrypt the ciphertextassuming that the following additive sequencewas used to encrypt the message.

      20 An affine cipher is a type of substitution where each letter is encrypted according to the rule (see the Appendix for a discussion of the operation). Here, , , , and are each numbers in the range 0 to 25, where represents the plaintext letter, the ciphertext letter, and and are constants. For the plaintext and ciphertext, the number 0 corresponds to “ a ,″ 1 corresponds to “ b ,″ and so on. Consider the ciphertext QJKES REOGH GXXRE OXEO , which was generated using an affine cipher. Determine the constants and and decipher the message. Hint: Plaintext “ t″ encrypts to ciphertext “ H ″ and plaintext “ o ″ encrypts to ciphertext “ E .″

      21 A Vigenre cipher uses a sequence of shift‐by‐ simple substitutions, where the shifts are indexed using a keyword, with “A″ representing a shift‐by‐0, “B″ representing a shift‐by‐1, etc. For example, if the keyword is “DOG,″ then the first letter is encrypted using a simple substitution with a shift‐by‐3, the second letter is encrypted using a shift‐by‐14, the third letter is encrypted using a shift‐by‐6, and the pattern is repeated—the fourth letter is encrypted using a shift‐by‐3, the fifth letter is encrypted using a shift‐by‐14, and so on. Cryptanalyze the following ciphertext, i.e., determine the plaintext and the key:This particular message was encrypted using a Vigenre cipher with a 3‐letter English keyword:

      22 Suppose that on the planet Binary, the written language uses an alphabet that contains only two letters X and Y. Also, suppose that in the Binarian language, the letter X occurs 75% of the time, while Y occurs 25% of the time. Assume that you have two messages in the Binary language, and the messages are of equal length.If you compare the corresponding letters of the two messages, what fraction of the time will the letters match?Suppose that one of the two messages is encrypted with a simple substitution, where X is encrypted as Y and Y is encrypted as X. If you now compare the corresponding letters of the two messages—one encrypted and one not—what fraction of the time will the letters match?Suppose that both of the messages are encrypted with a simple substitution, where X is encrypted as Y and Y is encrypted as X. If you now compare the corresponding letters of the two messages—both of which are encrypted with the same key—what fraction of the time will the letters match?Suppose instead that you are given two randomly generated sequences consisting of the two letters X and Y. If you compare the corresponding letters of the two messages, what fraction of the time will the letters match?Briefly describe the index of coincidence (IC), as described, for example, in [42].How can the index of coincidence be used to determine the length of the keyword in a Vigenre cipher (see Problem 21 for the definition of a Vigenre cipher)?

      23 In this chapter, we discussed a forward search attack on a public key cryptosystem.Explain how to conduct a forward search attack.How can you prevent a forward search attack against a public key cryptosystem?Why can't a forward search attack be used to break a symmetric cipher?

      24 Consider a “one‐way″ function , that is, a function where given the value , it is computationally infeasible to find directly from .Suppose that Alice computes , where is Aliceś salary, in dollars. If Trudy obtains , how can she determine Aliceś salary ? Hint: Adapt the forward search attack to this problem.Why does your attack in part a) not violate the one‐way property of ?How could Alice prevent this attack? We assume that Trudy has access to the output of the function , Trudy knows that the input includes Aliceś salary, and Trudy knows the format of the input. Also, no keys are available, so Alice cannot encrypt the output value.

      25 Suppose that a particular cipher uses a 40‐bit key, and the cipher is secure, i.e., there is no known shortcut attack.How much work, on average, is an exhaustive search attack?Outline an attack, assuming that known plaintext is available.How would you attack this cipher in the ciphertext‐only case?

Notes

      1 1 This is the only black box you'll find in this book!

      2 2 Public key crypto is also known as asymmetric crypto, in reference to the fact that the encryption and decryption keys are different—in contrast to symmetric key crypto.

      3 3 Historians generally agree that the Caesar's cipher was named after the Roman dictator, not the salad.

      4 4 In 1998 the Electronic Frontier Foundation (EFF) built a special‐purpose key cracking machine for attacking the Data Encryption Standard (DES). This machine, which cost $220,000, used about processors, each of which ran at 40 MHz and, overall, it was capable of testing about 2.5 million keys per second. Extrapolating this to a PC with a single 4 GHz processor, Trudy could test fewer than keys per second on one such machine. If Trudy had access to 1000 such machines, she could test about keys per second.

      5 5 On rare occasion, an Electoral College delegate is a “faithless elector,″ meaning that the delegate votes for a different candidate than the one the elector is pledged to support.

      6 6 Foreshadowing the U.S. presidential election of the year 2000, one of these four disputed states was, believe it or not, Florida.

      7 7 Apparently, this message had not initially attracted attention because it was not encrypted. The lesson here is that, ironically, encryption with a weak cipher may be worse than no encryption at all. We have more to say about this issue in Chapter 7.

      8 8 David Greenglass served ten years of a fifteen year sentence for his part in the crime. He later claimed that he lied in crucial testimony about his sister Ethyl Rosenberg's level of involvement—testimony that may have been decisive in her being sentenced to death.

      9 9 Remarkably, the Polish cryptanalysts were not allowed to continue their work on the Enigma in Britain.

      10 10 NBS has since been rechristened as the National Institute of Standards and Technology, or NIST, perhaps in an effort to recycle three‐letter acronyms and thereby delay their eventual exhaustion by government agencies.

      11 11 Cryptographic hash functions are not to be confused with the hash functions that you may have seen in other computing contexts. As compared to non‐cryptographic hash functions, weĺl have very stringent requirements for our cryptographic hash functions, as you will see in Chapter 5.