If one strips down the English alphabet to only lower case letters, (eliminate c

Question

If one strips down the English alphabet to only lower case letters, (eliminate capitalization, white space, and punctuation), there are 26 letters. We know from combinatorics that there are 26 factorial possible distinct permutations of these 26 symbols, which, is approximately 3x10 25 , which is about 50 moles, which is approximately the number of water molecules in a glass of water. In other words, there are as many substitution ciphers that operate on written English as there are molecules in a glass of water. This HUGE key space would lead a naive person, e.g., Mary the Queen of the Scotts, to believe they are secure.

Try to explain why substitution ciphers are not secure, by using your knowledge of frequency

analysis and your understanding of the concepts of two cryptography concepts named: confusion and diffusion.

Explanation / Answer

Substitution cipher is perhaps the oldest technique used for cryptography. Even though it seems secure, it isnt. We do a frequency analysis to explain why it is not secure.

We assume a few things: we have no prior knowledge of the (unencrypted) message sent. We know that the message sent was written in English. We also know that it was encrypted using a simple substitution cipher. Is it then possible to decrypt this message? The answer is : probably yes, using frequency analysis.

Frequency analysis is the analysis of the frequency of each letter appearing in a piece of text. If a simple substitution cipher defines a one-to-one correspondence between the pre-encrypted letters and post-encrypted letters, then the frequency of the post-encrypted letters in the cipher text and pre-encrypted letters in the plain text must be equal.

First, we need to recognize that we're making some assumptions about the plaintext:

As long as we know that there is a 1-to-1, unique, mapping from plaintext to ciphertext (and therefore also from ciphertext to plaintext), we can employ our knowledge of those letter frequencies to help us crack a substitution cipher. Note that we need a large enough piece of text to give us some expectation that we have a large enough statistical sample. The longer the message, the better statistical sample we are likely to have.

Confusion and Diffusion

In cryptography, confusion and diffusion are two properties of the operation of a secure cipher.

Encryption is based on two principles: confusion and diffusion. Confusion means that the process drastically changes data from the input to the output. For example, by translating the data through a non-linear table created from the key. We have lots of ways to reverse linear calculations (starting with high school algebra), so the more non-linear it is, the more analysis tools it breaks.

Diffusion means that changing a single character of the input will change many characters of the output. Done well, every part of the input affects every part of the output, making analysis much harder. No confusion process is perfect: it always lets through some patterns. Good diffusion scatters those patterns widely through the output, and if there are several patterns making it through they scramble each other. This makes patterns vastly harder to spot, and vastly increases the amount of data to analyze to break the cipher.

One aim of confusion is to make it very hard to find the key even if one has a large number of plaintext-ciphertext pairs produced with the same key. Therefore, each bit of the ciphertext should depend on the entire key, and in different ways on different bits of the key. In particular, changing one bit of the key should change the ciphertext completely.

The simplest way to achieve both diffusion and confusion is a substitution-permutation network. In these systems, the plaintext and the key often have a very similar role in producing the output, hence it is the same mechanism that ensures both diffusion and confusion.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.