Alphabetic Substitution with Symbols

Question

I was reading on a site about the Zodiac Killer and how he used a basic substitution cipher, but instead of substituting english letters and characters he substituted symbols.

I was wondering, if you had a large enough subset of symbols to use for commonly repeating letters like E,T,S ... then by what means could someone decipher the cipher. This is also referring to the fact that no one has yet to decipher his last message. Obviously this type of system of cryptography would not withstand in modern computing.

I am more interested in other techniques that could be used, I also found this site '340 Cipher', which includes frequency counts.

Answer 1

If I understand your cipher idea right, you would have a larger ciphertext alphabet than the plaintext alphabet, where each plaintext symbol maps to multiple ciphertext symbols (and the number is dependent on the frequency of the plaintext symbol), one of which is used randomly.

This is known as a Homophonic substitution, and with it the single-symbol frequency analysis usable for simple substitution ciphers is thwarted, since all symbols now have similar frequencies.

But as soon as we start to look at frequencies of letter-pairs (and triplets), we will observe enough structures to break this, too. For example, q is almost always followed by u, and thus the ciphertexts of q will almost always be followed by one of the ciphertexts of u. (I don't know enough about the statistic properties of the English language to give more examples, but you can be sure that an attacker would know.)

Some examples from German:

• As in English, q is almost always followed by u.
• A c is almost always followed by either k or h.
• ei has about same frequency as ie (and i is the only letter who has this property related to e).

Some more details are given in David's answer.

Of course, if the ciphertext is so short (or the translation table so large) that each symbol is only used once or twice (or not at all), cryptanalysis is more difficult (or even impossible).

Answer 2

As Paŭlo Ebermann says, this is (apparently) a homophonic cipher.

Ciphers that obscure single-letter frequencies, such as homophonic ciphers, the Alberti cipher, Vigenère cipher, the Playfair cipher, etc. are impossible to crack using single-letter frequency analysis, which is the only cryptanalysis technique published before 1863.

However, other cryptanalysis techniques that have been developed since then. Given enough ciphertext, you can discover other patterns and decrypt the message. Several of these techniques are mentioned in Stahl's proposal for a homophonic cipher that attempts to resist those techniques:

F. A. Stahl. "A homophonic cipher for computational cryptography" 1973

Ciphertext-only cryptanalysis techniques that can be applied to homophonic ciphers include:

• Some words (and word fragments) are very common. If we find a near-repeat -- "aBcde" in one place, and "aXcde" in another -- we begin to suspect that B and X both refer to the same plaintext letter.
• When encrypting a plaintext letter that could be represented by several ciphertext symbols, one way to guarantee that all those ciphertext symbols have exactly the same frequency is for the writer to cycle through them -- when encrypting the first plaintext "h", the writer writes "M", the next plaintext "h" becomes ")", the next "M", then ")", etc. Later when the cryptanalyst sees that 2 symbols that always occur in the order (neglecting all other symbols) "M)M)M)M)" in the ciphertext, or 3 symbols that always occur in order "tr\tr\tr\tr\", we begin to suspect that M and ) both refer to one plaintext letter, and that t, r, and \ all refer to one other plaintext letter.
• many bigram frequencies in English are significantly different than what we might predict from the underlying single-letter frequencies alone. Some enciphered letters might have a next-cipher-letter frequency that is relatively flat (all other ciphertext letters follow it), so perhaps it is a vowel, while other enciphered letters have a very spiked next-letter frequency (the next letter is nearly always one of a small set of ciphertext letters), so perhaps it is a consonant -- if extremely spiked, perhaps it is the 'q'.
• And other cryptanalysis techniques.

This type of cryptographic system would not withstand modern computer-based cryptanalysis.

However, certain ciphertexts from such a system have withstood modern attempts at decoding because:

With a homophonic cipher message where every symbol is unique (and we have no other messages that use the same ciphertext-to-plaintext mapping) -- imagine if we only had the first 2 rows of the 340 Cipher -- every possible message is a plausible message, much like every possible message is a plausible message with a one-time pad, and such a "entirely unique" message is impossible to decrypt.

With messages that contain some repeats, we can rule out some possible messages, but if the message is short enough, there may be a huge number of plausible deciphered plaintexts (using different homophonic encryption alphabets), much like the one-time pad gives a huge number of plausible deciphered plaintexts (using different keypads). One of them is the original message, but even an infinite amount of computer power won't help you figure out which one it is.

Answer 3

What you're describing sounds very similar to the Caesar Cipher which can be cracked by counting the frequency of commonly repeating letters.

As for other techniques, it depends what you mean by 'other'. I presume that you mean other techniques that use a one-to-one mapping (or a variant thereof). If so, have a look at the one-time-pad which, if used correctly is (almost) impossible to crack.

Essentially, each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key (or pad) of the same length as the plaintext, resulting in a ciphertext. If the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key.