What is a homophonic substitution cipher Explain in detail h

What is a homophonic substitution cipher? Explain in detail how an HMM can be used to break a homophonic substitution cipher. Be sure to include an explanation of how the model is initialized and re-estimated, and how the key is determined from a converged model.

Solution

Homophonic substitution cipher:

  Homophonic substitution ciphers are many-to-one, that is, multipleciphertext symbols can map to one plaintext symbol. ... For example, the most common cipher- text symbol corresponds to the most common plaintext symbol, which for English plaintext is most likely the letter E.

An example of a homophonic substitution cipher is given in below , where used some non-alphabetic symbols, since we require more than 26 ciphertext symbols. For the key in Table 2, any of the symbols R, 3, or 9 can be substituted for a plaintext E, and either Y or 6 can be substituted for plaintext L. So, using this key, plaintext HELLO can be encrypted as U96YB. In this case, a cryptanalyst has no indication that ciphertext 6 and Y both represent the same plaintext letter.

Table 2: Homophonic Substitution Key

plaintext A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

ciphertext N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

8 9 1 6 4

3 5

Suppose that a given homophonic substitution cipher has n distinct ciphertext symbols and the plaintext is English. Assuming that each of the 26 plaintext letters maps to at least one ciphertext symbol, the theoretical key space is of size n 26 26! 26n26 < 26n 2 4.7n . Recall that for the simple substitution, the key space is of size 26! 2 88, with an exhaustive search having a work factor of 287, on average. Using the upper bound of 24.7n , and assuming that we can test a million keys per second, an exhaustive search on a homphonic substitution with n = 100 ciphertext symbols will require about 2470/2 20 = 2450 seconds, or 9.2 × 10127 years. For a cipher with 62 symbols—such as the Zodiac 340 cipher—the same assumptions give an exhaustive key search time of “only” 1.59 × 1074 years. As discussed in the previous section, under the same assumptions, an exhaustive search on a simple substitution requires a paltry 4.9 × 1012 years. The point here is that an exhaustive search is out of the question. In Sections 3 and 4 we consider efficient attacks on simple substitutions and homophonic substitutions, respectively. These attacks rely on statistical information that leaks from the plaintext into the ciphertext.